Reinstate r133435 and r133449 (reverted in r133499) now that the clang
self-hosted build failure has been fixed (r133512).
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133513 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index e05f29c..840c4b6 100644
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -1021,6 +1021,10 @@
while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
+ // If Succ has any successors with PHI nodes, update them to have
+ // entries coming from Pred instead of Succ.
+ Succ->replaceAllUsesWith(Pred);
+
// Move all of the successor contents from Succ to Pred.
Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),
Succ->end());
@@ -1028,10 +1032,6 @@
BI->eraseFromParent();
RemoveFromWorklist(BI, Worklist);
- // If Succ has any successors with PHI nodes, update them to have
- // entries coming from Pred instead of Succ.
- Succ->replaceAllUsesWith(Pred);
-
// Remove Succ from the loop tree.
LI->removeBlock(Succ);
LPM->deleteSimpleAnalysisValue(Succ, L);
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 92464e8..b4f74f9 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -153,13 +153,13 @@
// Delete the unconditional branch from the predecessor...
PredBB->getInstList().pop_back();
- // Move all definitions in the successor to the predecessor...
- PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
-
// Make all PHI nodes that referred to BB now refer to Pred as their
// source...
BB->replaceAllUsesWith(PredBB);
+ // Move all definitions in the successor to the predecessor...
+ PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
+
// Inherit predecessors name if it exists.
if (!PredBB->hasName())
PredBB->takeName(BB);
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index d6206a3..92ce500 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -193,44 +193,22 @@
// If there are any PHI nodes in DestBB, we need to update them so that they
// merge incoming values from NewBB instead of from TIBB.
- if (PHINode *APHI = dyn_cast<PHINode>(DestBB->begin())) {
- // This conceptually does:
- // foreach (PHINode *PN in DestBB)
- // PN->setIncomingBlock(PN->getIncomingBlock(TIBB), NewBB);
- // but is optimized for two cases.
-
- if (APHI->getNumIncomingValues() <= 8) { // Small # preds case.
- unsigned BBIdx = 0;
- for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
- // We no longer enter through TIBB, now we come in through NewBB.
- // Revector exactly one entry in the PHI node that used to come from
- // TIBB to come from NewBB.
- PHINode *PN = cast<PHINode>(I);
-
- // Reuse the previous value of BBIdx if it lines up. In cases where we
- // have multiple phi nodes with *lots* of predecessors, this is a speed
- // win because we don't have to scan the PHI looking for TIBB. This
- // happens because the BB list of PHI nodes are usually in the same
- // order.
- if (PN->getIncomingBlock(BBIdx) != TIBB)
- BBIdx = PN->getBasicBlockIndex(TIBB);
- PN->setIncomingBlock(BBIdx, NewBB);
- }
- } else {
- // However, the foreach loop is slow for blocks with lots of predecessors
- // because PHINode::getIncomingBlock is O(n) in # preds. Instead, walk
- // the user list of TIBB to find the PHI nodes.
- SmallPtrSet<PHINode*, 16> UpdatedPHIs;
-
- for (Value::use_iterator UI = TIBB->use_begin(), E = TIBB->use_end();
- UI != E; ) {
- Value::use_iterator Use = UI++;
- if (PHINode *PN = dyn_cast<PHINode>(*Use)) {
- // Remove one entry from each PHI.
- if (PN->getParent() == DestBB && UpdatedPHIs.insert(PN))
- PN->setOperand(Use.getOperandNo(), NewBB);
- }
- }
+ {
+ unsigned BBIdx = 0;
+ for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
+ // We no longer enter through TIBB, now we come in through NewBB.
+ // Revector exactly one entry in the PHI node that used to come from
+ // TIBB to come from NewBB.
+ PHINode *PN = cast<PHINode>(I);
+
+ // Reuse the previous value of BBIdx if it lines up. In cases where we
+ // have multiple phi nodes with *lots* of predecessors, this is a speed
+ // win because we don't have to scan the PHI looking for TIBB. This
+ // happens because the BB list of PHI nodes are usually in the same
+ // order.
+ if (PN->getIncomingBlock(BBIdx) != TIBB)
+ BBIdx = PN->getBasicBlockIndex(TIBB);
+ PN->setIncomingBlock(BBIdx, NewBB);
}
}
diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp
index d967ceb..561b69d 100644
--- a/lib/Transforms/Utils/CloneFunction.cpp
+++ b/lib/Transforms/Utils/CloneFunction.cpp
@@ -572,12 +572,12 @@
// removed, so we just need to splice the blocks.
BI->eraseFromParent();
- // Move all the instructions in the succ to the pred.
- I->getInstList().splice(I->end(), Dest->getInstList());
-
// Make all PHI nodes that referred to Dest now refer to I as their source.
Dest->replaceAllUsesWith(I);
+ // Move all the instructions in the succ to the pred.
+ I->getInstList().splice(I->end(), Dest->getInstList());
+
// Remove the dest block.
Dest->eraseFromParent();
diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp
index 946e62f..18ecd61 100644
--- a/lib/Transforms/Utils/InlineFunction.cpp
+++ b/lib/Transforms/Utils/InlineFunction.cpp
@@ -1097,15 +1097,15 @@
TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
}
+ // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
+ BasicBlock *ReturnBB = Returns[0]->getParent();
+ ReturnBB->replaceAllUsesWith(AfterCallBB);
+
// Splice the code from the return block into the block that it will return
// to, which contains the code that was after the call.
- BasicBlock *ReturnBB = Returns[0]->getParent();
AfterCallBB->getInstList().splice(AfterCallBB->begin(),
ReturnBB->getInstList());
- // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
- ReturnBB->replaceAllUsesWith(AfterCallBB);
-
// Delete the return instruction now and empty ReturnBB now.
Returns[0]->eraseFromParent();
ReturnBB->eraseFromParent();
@@ -1125,8 +1125,8 @@
// Splice the code entry block into calling block, right before the
// unconditional branch.
- OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes
+ OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
// Remove the unconditional branch.
OrigBB->getInstList().erase(Br);
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 19c3c72..506e5e8 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -427,10 +427,6 @@
BasicBlock *PredBB = DestBB->getSinglePredecessor();
assert(PredBB && "Block doesn't have a single predecessor!");
- // Splice all the instructions from PredBB to DestBB.
- PredBB->getTerminator()->eraseFromParent();
- DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
-
// Zap anything that took the address of DestBB. Not doing this will give the
// address an invalid value.
if (DestBB->hasAddressTaken()) {
@@ -445,6 +441,10 @@
// Anything that branched to PredBB now branches to DestBB.
PredBB->replaceAllUsesWith(DestBB);
+ // Splice all the instructions from PredBB to DestBB.
+ PredBB->getTerminator()->eraseFromParent();
+ DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
+
if (P) {
DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>();
if (DT) {
@@ -660,12 +660,17 @@
// them, which helps expose duplicates, but we have to check all the
// operands to be safe in case instcombine hasn't run.
uintptr_t Hash = 0;
+ // This hash algorithm is quite weak as hash functions go, but it seems
+ // to do a good enough job for this particular purpose, and is very quick.
for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
- // This hash algorithm is quite weak as hash functions go, but it seems
- // to do a good enough job for this particular purpose, and is very quick.
Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
}
+ for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end();
+ I != E; ++I) {
+ Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I));
+ Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
+ }
// Avoid colliding with the DenseMap sentinels ~0 and ~0-1.
Hash >>= 1;
// If we've never seen this hash value before, it's a unique PHI.
diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp
index 7da7271..c91bf82 100644
--- a/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/lib/Transforms/Utils/LoopUnroll.cpp
@@ -47,6 +47,14 @@
if (It != VMap.end())
I->setOperand(op, It->second);
}
+
+ if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+ ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(i));
+ if (It != VMap.end())
+ PN->setIncomingBlock(i, cast<BasicBlock>(It->second));
+ }
+ }
}
/// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
@@ -75,13 +83,13 @@
// Delete the unconditional branch from the predecessor...
OnlyPred->getInstList().pop_back();
- // Move all definitions in the successor to the predecessor...
- OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
-
// Make all PHI nodes that referred to BB now refer to Pred as their
// source...
BB->replaceAllUsesWith(OnlyPred);
+ // Move all definitions in the successor to the predecessor...
+ OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
+
std::string OldName = BB->getName();
// Erase basic block from the function...
@@ -247,16 +255,14 @@
// the successor of the latch block. The successor of the exit block will
// be updated specially after unrolling all the way.
if (*BB != LatchBlock)
- for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end();
- UI != UE;) {
- Instruction *UseInst = cast<Instruction>(*UI);
- ++UI;
- if (isa<PHINode>(UseInst) && !L->contains(UseInst)) {
- PHINode *phi = cast<PHINode>(UseInst);
- Value *Incoming = phi->getIncomingValueForBlock(*BB);
- phi->addIncoming(Incoming, New);
- }
- }
+ for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB); SI != SE;
+ ++SI)
+ if (!L->contains(*SI))
+ for (BasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
+ PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) {
+ Value *Incoming = phi->getIncomingValueForBlock(*BB);
+ phi->addIncoming(Incoming, New);
+ }
// Keep track of new headers and latches as we create them, so that
// we can insert the proper branches later.
@@ -288,24 +294,20 @@
// successor blocks, update them to use the appropriate values computed as the
// last iteration of the loop.
if (Count != 1) {
- SmallPtrSet<PHINode*, 8> Users;
- for (Value::use_iterator UI = LatchBlock->use_begin(),
- UE = LatchBlock->use_end(); UI != UE; ++UI)
- if (PHINode *phi = dyn_cast<PHINode>(*UI))
- Users.insert(phi);
-
BasicBlock *LastIterationBB = cast<BasicBlock>(LastValueMap[LatchBlock]);
- for (SmallPtrSet<PHINode*,8>::iterator SI = Users.begin(), SE = Users.end();
+ for (succ_iterator SI = succ_begin(LatchBlock), SE = succ_end(LatchBlock);
SI != SE; ++SI) {
- PHINode *PN = *SI;
- Value *InVal = PN->removeIncomingValue(LatchBlock, false);
- // If this value was defined in the loop, take the value defined by the
- // last iteration of the loop.
- if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
- if (L->contains(InValI))
- InVal = LastValueMap[InVal];
+ for (BasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
+ PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) {
+ Value *InVal = PN->removeIncomingValue(LatchBlock, false);
+ // If this value was defined in the loop, take the value defined by the
+ // last iteration of the loop.
+ if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
+ if (L->contains(InValI))
+ InVal = LastValueMap[InVal];
+ }
+ PN->addIncoming(InVal, LastIterationBB);
}
- PN->addIncoming(InVal, LastIterationBB);
}
}
@@ -352,11 +354,16 @@
// Replace the conditional branch with an unconditional one.
BranchInst::Create(Dest, Term);
Term->eraseFromParent();
- // Merge adjacent basic blocks, if possible.
- if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) {
+ }
+ }
+
+ // Merge adjacent basic blocks, if possible.
+ for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
+ BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
+ if (Term->isUnconditional()) {
+ BasicBlock *Dest = Term->getSuccessor(0);
+ if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI))
std::replace(Latches.begin(), Latches.end(), Dest, Fold);
- std::replace(Headers.begin(), Headers.end(), Dest, Fold);
- }
}
}
diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp
index a73bf04..de6cbdc 100644
--- a/lib/Transforms/Utils/ValueMapper.cpp
+++ b/lib/Transforms/Utils/ValueMapper.cpp
@@ -16,6 +16,7 @@
#include "llvm/Type.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
+#include "llvm/Instructions.h"
#include "llvm/Metadata.h"
#include "llvm/ADT/SmallVector.h"
using namespace llvm;
@@ -128,6 +129,19 @@
"Referenced value not in value map!");
}
+ // Remap phi nodes' incoming blocks.
+ if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+ Value *V = MapValue(PN->getIncomingBlock(i), VMap, Flags);
+ // If we aren't ignoring missing entries, assert that something happened.
+ if (V != 0)
+ PN->setIncomingBlock(i, cast<BasicBlock>(V));
+ else
+ assert((Flags & RF_IgnoreMissingEntries) &&
+ "Referenced block not in value map!");
+ }
+ }
+
// Remap attached metadata.
SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
I->getAllMetadata(MDs);