From a88a0ca8082006b37d14d8aee4a644b20bae8bc9 Mon Sep 17 00:00:00 2001 From: Chad Rosier Date: Tue, 21 Jun 2011 02:09:03 +0000 Subject: [PATCH] Revert r133435 and r133449 to appease buildbots. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133499 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/BasicBlock.h | 6 +- include/llvm/Instructions.h | 81 ++++++++------------- include/llvm/Support/CFG.h | 2 +- include/llvm/Use.h | 6 +- lib/Target/CppBackend/CPPBackend.cpp | 2 +- lib/Transforms/Scalar/LoopUnswitch.cpp | 8 +- lib/Transforms/Utils/BasicBlockUtils.cpp | 6 +- lib/Transforms/Utils/BreakCriticalEdges.cpp | 54 ++++++++++---- lib/Transforms/Utils/CloneFunction.cpp | 6 +- lib/Transforms/Utils/InlineFunction.cpp | 10 +-- lib/Transforms/Utils/Local.cpp | 17 ++--- lib/Transforms/Utils/LoopUnroll.cpp | 71 ++++++++---------- lib/Transforms/Utils/ValueMapper.cpp | 14 ---- lib/VMCore/BasicBlock.cpp | 16 ---- lib/VMCore/Instructions.cpp | 56 +++++++------- lib/VMCore/User.cpp | 6 +- lib/VMCore/Value.cpp | 3 - lib/VMCore/Verifier.cpp | 3 + 18 files changed, 156 insertions(+), 211 deletions(-) diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h index b02c249c7ee..7e7c9e76943 100644 --- a/include/llvm/BasicBlock.h +++ b/include/llvm/BasicBlock.h @@ -110,7 +110,7 @@ public: Function *getParent() { return Parent; } /// use_back - Specialize the methods defined in Value, as we know that an - /// BasicBlock can only be used by Users (specifically terminators + /// BasicBlock can only be used by Users (specifically PHI nodes, terminators, /// and BlockAddress's). User *use_back() { return cast(*use_begin());} const User *use_back() const { return cast(*use_begin());} @@ -248,10 +248,6 @@ public: /// other than direct branches, switches, etc. to it. bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; } - /// replaceSuccessorsPhiUsesWith - Update all phi nodes in all our successors - /// to refer to basic block New instead of to us. - void replaceSuccessorsPhiUsesWith(BasicBlock *New); - private: /// AdjustBlockAddressRefCount - BasicBlock stores the number of BlockAddress /// objects using it. This is almost always 0, sometimes one, possibly but diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h index cc3801043e4..54dfe3957ff 100644 --- a/include/llvm/Instructions.h +++ b/include/llvm/Instructions.h @@ -1814,7 +1814,7 @@ class PHINode : public Instruction { explicit PHINode(const Type *Ty, unsigned NumReservedValues, const Twine &NameStr = "", Instruction *InsertBefore = 0) : Instruction(Ty, Instruction::PHI, 0, 0, InsertBefore), - ReservedSpace(NumReservedValues) { + ReservedSpace(NumReservedValues * 2) { setName(NameStr); OperandList = allocHungoffUses(ReservedSpace); } @@ -1822,16 +1822,11 @@ class PHINode : public Instruction { PHINode(const Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock *InsertAtEnd) : Instruction(Ty, Instruction::PHI, 0, 0, InsertAtEnd), - ReservedSpace(NumReservedValues) { + ReservedSpace(NumReservedValues * 2) { setName(NameStr); OperandList = allocHungoffUses(ReservedSpace); } protected: - // allocHungoffUses - this is more complicated than the generic - // User::allocHungoffUses, because we have to allocate Uses for the incoming - // values and pointers to the incoming blocks, all in one allocation. - Use *allocHungoffUses(unsigned) const; - virtual PHINode *clone_impl() const; public: /// Constructors - NumReservedValues is a hint for the number of incoming @@ -1850,55 +1845,32 @@ public: /// Provide fast operand accessors DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); - // Block iterator interface. This provides access to the list of incoming - // basic blocks, which parallels the list of incoming values. - - typedef BasicBlock **block_iterator; - typedef BasicBlock * const *const_block_iterator; - - block_iterator block_begin() { - Use::UserRef *ref = - reinterpret_cast(op_begin() + ReservedSpace); - return reinterpret_cast(ref + 1); - } - - const_block_iterator block_begin() const { - const Use::UserRef *ref = - reinterpret_cast(op_begin() + ReservedSpace); - return reinterpret_cast(ref + 1); - } - - block_iterator block_end() { - return block_begin() + getNumOperands(); - } - - const_block_iterator block_end() const { - return block_begin() + getNumOperands(); - } - /// getNumIncomingValues - Return the number of incoming edges /// - unsigned getNumIncomingValues() const { return getNumOperands(); } + unsigned getNumIncomingValues() const { return getNumOperands()/2; } /// getIncomingValue - Return incoming value number x /// Value *getIncomingValue(unsigned i) const { - return getOperand(i); + assert(i*2 < getNumOperands() && "Invalid value number!"); + return getOperand(i*2); } void setIncomingValue(unsigned i, Value *V) { - setOperand(i, V); + assert(i*2 < getNumOperands() && "Invalid value number!"); + setOperand(i*2, V); } static unsigned getOperandNumForIncomingValue(unsigned i) { - return i; + return i*2; } static unsigned getIncomingValueNumForOperand(unsigned i) { - return i; + assert(i % 2 == 0 && "Invalid incoming-value operand index!"); + return i/2; } /// getIncomingBlock - Return incoming basic block number @p i. /// BasicBlock *getIncomingBlock(unsigned i) const { - return block_begin()[i]; + return cast(getOperand(i*2+1)); } /// getIncomingBlock - Return incoming basic block corresponding @@ -1906,7 +1878,7 @@ public: /// BasicBlock *getIncomingBlock(const Use &U) const { assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?"); - return getIncomingBlock(&U - op_begin()); + return cast((&U + 1)->get()); } /// getIncomingBlock - Return incoming basic block corresponding @@ -1917,8 +1889,16 @@ public: return getIncomingBlock(I.getUse()); } + void setIncomingBlock(unsigned i, BasicBlock *BB) { - block_begin()[i] = BB; + setOperand(i*2+1, (Value*)BB); + } + static unsigned getOperandNumForIncomingBlock(unsigned i) { + return i*2+1; + } + static unsigned getIncomingBlockNumForOperand(unsigned i) { + assert(i % 2 == 1 && "Invalid incoming-block operand index!"); + return i/2; } /// addIncoming - Add an incoming value to the end of the PHI list @@ -1928,12 +1908,13 @@ public: assert(BB && "PHI node got a null basic block!"); assert(getType() == V->getType() && "All operands to PHI node must be the same type as the PHI node!"); - if (NumOperands == ReservedSpace) + unsigned OpNo = NumOperands; + if (OpNo+2 > ReservedSpace) growOperands(); // Get more space! // Initialize some new operands. - ++NumOperands; - setIncomingValue(NumOperands - 1, V); - setIncomingBlock(NumOperands - 1, BB); + NumOperands = OpNo+2; + OperandList[OpNo] = V; + OperandList[OpNo+1] = (Value*)BB; } /// removeIncomingValue - Remove an incoming value. This is useful if a @@ -1956,16 +1937,14 @@ public: /// block in the value list for this PHI. Returns -1 if no instance. /// int getBasicBlockIndex(const BasicBlock *BB) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (block_begin()[i] == BB) - return i; + Use *OL = OperandList; + for (unsigned i = 0, e = getNumOperands(); i != e; i += 2) + if (OL[i+1].get() == (const Value*)BB) return i/2; return -1; } Value *getIncomingValueForBlock(const BasicBlock *BB) const { - int Idx = getBasicBlockIndex(BB); - assert(Idx >= 0 && "Invalid basic block argument!"); - return getIncomingValue(Idx); + return getIncomingValue(getBasicBlockIndex(BB)); } /// hasConstantValue - If the specified PHI node always merges together the diff --git a/include/llvm/Support/CFG.h b/include/llvm/Support/CFG.h index 7e193ff15e6..d2ea12364e9 100644 --- a/include/llvm/Support/CFG.h +++ b/include/llvm/Support/CFG.h @@ -33,7 +33,7 @@ class PredIterator : public std::iterator(*It)) ++It; } diff --git a/include/llvm/Use.h b/include/llvm/Use.h index a496325c1fc..1bdacb48f4d 100644 --- a/include/llvm/Use.h +++ b/include/llvm/Use.h @@ -112,16 +112,13 @@ public: Use *getNext() const { return Next; } - /// initTags - initialize the waymarking tags on an array of Uses, so that - /// getUser() can find the User from any of those Uses. - static Use *initTags(Use *Start, Use *Stop); - /// zap - This is used to destroy Use operands when the number of operands of /// a User changes. static void zap(Use *Start, const Use *Stop, bool del = false); private: const Use* getImpliedUser() const; + static Use *initTags(Use *Start, Use *Stop); Value *Val; Use *Next; @@ -143,6 +140,7 @@ private: } friend class Value; + friend class User; }; // simplify_type - Allow clients to treat uses just like values when using diff --git a/lib/Target/CppBackend/CPPBackend.cpp b/lib/Target/CppBackend/CPPBackend.cpp index 0d15514d8cf..2ba773bd5e5 100644 --- a/lib/Target/CppBackend/CPPBackend.cpp +++ b/lib/Target/CppBackend/CPPBackend.cpp @@ -1356,7 +1356,7 @@ void CppWriter::printInstruction(const Instruction *I, for (unsigned i = 0; i < phi->getNumIncomingValues(); ++i) { Out << iName << "->addIncoming(" << opNames[PHINode::getOperandNumForIncomingValue(i)] << ", " - << getOpName(phi->getIncomingBlock(i)) << ");"; + << opNames[PHINode::getOperandNumForIncomingBlock(i)] << ");"; nl(Out); } break; diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 840c4b69cf0..e05f29c3e13 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -1021,10 +1021,6 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { while (PHINode *PN = dyn_cast(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()); @@ -1032,6 +1028,10 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { 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 b4f74f97e97..92464e8cf13 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -153,13 +153,13 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) { // 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 92ce50030a5..d6206a3f332 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -193,22 +193,44 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // 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. - { - unsigned BBIdx = 0; - for (BasicBlock::iterator I = DestBB->begin(); isa(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(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); + if (PHINode *APHI = dyn_cast(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(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(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 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(*Use)) { + // Remove one entry from each PHI. + if (PN->getParent() == DestBB && UpdatedPHIs.insert(PN)) + PN->setOperand(Use.getOperandNo(), NewBB); + } + } } } diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp index 561b69dd1ee..d967ceb9685 100644 --- a/lib/Transforms/Utils/CloneFunction.cpp +++ b/lib/Transforms/Utils/CloneFunction.cpp @@ -572,12 +572,12 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, // removed, so we just need to splice the blocks. BI->eraseFromParent(); - // 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()); + // Make all PHI nodes that referred to Dest now refer to I as their source. + Dest->replaceAllUsesWith(I); + // Remove the dest block. Dest->eraseFromParent(); diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp index 18ecd615ae8..946e62f4345 100644 --- a/lib/Transforms/Utils/InlineFunction.cpp +++ b/lib/Transforms/Utils/InlineFunction.cpp @@ -1097,15 +1097,15 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { 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 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { // Splice the code entry block into calling block, right before the // unconditional branch. - CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); + CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes // Remove the unconditional branch. OrigBB->getInstList().erase(Br); diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 506e5e8424f..19c3c72a218 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -427,6 +427,10 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 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()) { @@ -441,10 +445,6 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { // 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(); if (DT) { @@ -660,17 +660,12 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { // 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(static_cast(*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(static_cast(*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 c91bf82f11a..7da7271e642 100644 --- a/lib/Transforms/Utils/LoopUnroll.cpp +++ b/lib/Transforms/Utils/LoopUnroll.cpp @@ -47,14 +47,6 @@ static inline void RemapInstruction(Instruction *I, if (It != VMap.end()) I->setOperand(op, It->second); } - - if (PHINode *PN = dyn_cast(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(It->second)); - } - } } /// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it @@ -83,13 +75,13 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { // 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... @@ -255,14 +247,16 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // 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 (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(BBI); ++BBI) { - Value *Incoming = phi->getIncomingValueForBlock(*BB); - phi->addIncoming(Incoming, New); - } + for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end(); + UI != UE;) { + Instruction *UseInst = cast(*UI); + ++UI; + if (isa(UseInst) && !L->contains(UseInst)) { + PHINode *phi = cast(UseInst); + 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. @@ -294,20 +288,24 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // successor blocks, update them to use the appropriate values computed as the // last iteration of the loop. if (Count != 1) { + SmallPtrSet Users; + for (Value::use_iterator UI = LatchBlock->use_begin(), + UE = LatchBlock->use_end(); UI != UE; ++UI) + if (PHINode *phi = dyn_cast(*UI)) + Users.insert(phi); + BasicBlock *LastIterationBB = cast(LastValueMap[LatchBlock]); - for (succ_iterator SI = succ_begin(LatchBlock), SE = succ_end(LatchBlock); + for (SmallPtrSet::iterator SI = Users.begin(), SE = Users.end(); SI != SE; ++SI) { - for (BasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end(); - PHINode *PN = dyn_cast(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(InVal)) { - if (L->contains(InValI)) - InVal = LastValueMap[InVal]; - } - PN->addIncoming(InVal, LastIterationBB); + 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(InVal)) { + if (L->contains(InValI)) + InVal = LastValueMap[InVal]; } + PN->addIncoming(InVal, LastIterationBB); } } @@ -354,16 +352,11 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // Replace the conditional branch with an unconditional one. BranchInst::Create(Dest, Term); Term->eraseFromParent(); - } - } - - // Merge adjacent basic blocks, if possible. - for (unsigned i = 0, e = Latches.size(); i != e; ++i) { - BranchInst *Term = cast(Latches[i]->getTerminator()); - if (Term->isUnconditional()) { - BasicBlock *Dest = Term->getSuccessor(0); - if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) + // Merge adjacent basic blocks, if possible. + 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 de6cbdc92d5..a73bf044981 100644 --- a/lib/Transforms/Utils/ValueMapper.cpp +++ b/lib/Transforms/Utils/ValueMapper.cpp @@ -16,7 +16,6 @@ #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; @@ -129,19 +128,6 @@ void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, "Referenced value not in value map!"); } - // Remap phi nodes' incoming blocks. - if (PHINode *PN = dyn_cast(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(V)); - else - assert((Flags & RF_IgnoreMissingEntries) && - "Referenced block not in value map!"); - } - } - // Remap attached metadata. SmallVector, 4> MDs; I->getAllMetadata(MDs); diff --git a/lib/VMCore/BasicBlock.cpp b/lib/VMCore/BasicBlock.cpp index 7d470440aff..3f1a6a99b64 100644 --- a/lib/VMCore/BasicBlock.cpp +++ b/lib/VMCore/BasicBlock.cpp @@ -308,19 +308,3 @@ BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { return New; } -void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { - TerminatorInst *TI = getTerminator(); - if (!TI) - // Cope with being called on a BasicBlock that doesn't have a terminator - // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. - return; - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { - BasicBlock *Succ = TI->getSuccessor(i); - for (iterator II = Succ->begin(); PHINode *PN = dyn_cast(II); - ++II) { - int i; - while ((i = PN->getBasicBlockIndex(this)) >= 0) - PN->setIncomingBlock(i, New); - } - } -} diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp index 0eddd5ada7a..8f4eabeb8ae 100644 --- a/lib/VMCore/Instructions.cpp +++ b/lib/VMCore/Instructions.cpp @@ -87,8 +87,11 @@ PHINode::PHINode(const PHINode &PN) : Instruction(PN.getType(), Instruction::PHI, allocHungoffUses(PN.getNumOperands()), PN.getNumOperands()), ReservedSpace(PN.getNumOperands()) { - std::copy(PN.op_begin(), PN.op_end(), op_begin()); - std::copy(PN.block_begin(), PN.block_end(), block_begin()); + Use *OL = OperandList; + for (unsigned i = 0, e = PN.getNumOperands(); i != e; i+=2) { + OL[i] = PN.getOperand(i); + OL[i+1] = PN.getOperand(i+1); + } SubclassOptionalData = PN.SubclassOptionalData; } @@ -96,37 +99,31 @@ PHINode::~PHINode() { dropHungoffUses(); } -Use *PHINode::allocHungoffUses(unsigned N) const { - // Allocate the array of Uses of the incoming values, followed by a pointer - // (with bottom bit set) to the User, followed by the array of pointers to - // the incoming basic blocks. - size_t size = N * sizeof(Use) + sizeof(Use::UserRef) - + N * sizeof(BasicBlock*); - Use *Begin = static_cast(::operator new(size)); - Use *End = Begin + N; - (void) new(End) Use::UserRef(const_cast(this), 1); - return Use::initTags(Begin, End); -} - // removeIncomingValue - Remove an incoming value. This is useful if a // predecessor basic block is deleted. Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) { - Value *Removed = getIncomingValue(Idx); + unsigned NumOps = getNumOperands(); + Use *OL = OperandList; + assert(Idx*2 < NumOps && "BB not in PHI node!"); + Value *Removed = OL[Idx*2]; // Move everything after this operand down. // // FIXME: we could just swap with the end of the list, then erase. However, - // clients might not expect this to happen. The code as it is thrashes the + // client might not expect this to happen. The code as it is thrashes the // use/def lists, which is kinda lame. - std::copy(op_begin() + Idx + 1, op_end(), op_begin() + Idx); - std::copy(block_begin() + Idx + 1, block_end(), block_begin() + Idx); + for (unsigned i = (Idx+1)*2; i != NumOps; i += 2) { + OL[i-2] = OL[i]; + OL[i-2+1] = OL[i+1]; + } // Nuke the last value. - Op<-1>().set(0); - --NumOperands; + OL[NumOps-2].set(0); + OL[NumOps-2+1].set(0); + NumOperands = NumOps-2; // If the PHI node is dead, because it has zero entries, nuke it now. - if (getNumOperands() == 0 && DeletePHIIfEmpty) { + if (NumOps == 2 && DeletePHIIfEmpty) { // If anyone is using this PHI, make them use a dummy value instead... replaceAllUsesWith(UndefValue::get(getType())); eraseFromParent(); @@ -140,18 +137,15 @@ Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) { /// void PHINode::growOperands() { unsigned e = getNumOperands(); - unsigned NumOps = e + e / 2; - if (NumOps < 2) NumOps = 2; // 2 op PHI nodes are VERY common. - - Use *OldOps = op_begin(); - BasicBlock **OldBlocks = block_begin(); + // Multiply by 1.5 and round down so the result is still even. + unsigned NumOps = e + e / 4 * 2; + if (NumOps < 4) NumOps = 4; // 4 op PHI nodes are VERY common. ReservedSpace = NumOps; - OperandList = allocHungoffUses(ReservedSpace); - - std::copy(OldOps, OldOps + e, op_begin()); - std::copy(OldBlocks, OldBlocks + e, block_begin()); - + Use *OldOps = OperandList; + Use *NewOps = allocHungoffUses(NumOps); + std::copy(OldOps, OldOps + e, NewOps); + OperandList = NewOps; Use::zap(OldOps, OldOps + e, true); } diff --git a/lib/VMCore/User.cpp b/lib/VMCore/User.cpp index f01fa349adf..9601da7011e 100644 --- a/lib/VMCore/User.cpp +++ b/lib/VMCore/User.cpp @@ -40,10 +40,8 @@ void User::replaceUsesOfWith(Value *From, Value *To) { //===----------------------------------------------------------------------===// Use *User::allocHungoffUses(unsigned N) const { - // Allocate the array of Uses, followed by a pointer (with bottom bit set) to - // the User. - size_t size = N * sizeof(Use) + sizeof(Use::UserRef); - Use *Begin = static_cast(::operator new(size)); + Use *Begin = static_cast(::operator new(sizeof(Use) * N + + sizeof(Use::UserRef))); Use *End = Begin + N; (void) new(End) Use::UserRef(const_cast(this), 1); return Use::initTags(Begin, End); diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index a03cddc9d5e..29f6a8094f0 100644 --- a/lib/VMCore/Value.cpp +++ b/lib/VMCore/Value.cpp @@ -305,9 +305,6 @@ void Value::uncheckedReplaceAllUsesWith(Value *New) { U.set(New); } - - if (BasicBlock *BB = dyn_cast(this)) - BB->replaceSuccessorsPhiUsesWith(cast(New)); } void Value::replaceAllUsesWith(Value *New) { diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp index 18de67155ff..e504016169c 100644 --- a/lib/VMCore/Verifier.cpp +++ b/lib/VMCore/Verifier.cpp @@ -1139,6 +1139,9 @@ void Verifier::visitPHINode(PHINode &PN) { for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { Assert1(PN.getType() == PN.getIncomingValue(i)->getType(), "PHI node operands are not the same type as the result!", &PN); + Assert1(isa(PN.getOperand( + PHINode::getOperandNumForIncomingBlock(i))), + "PHI node incoming block is not a BasicBlock!", &PN); } // All other PHI node constraints are checked in the visitBasicBlock method. -- 2.34.1