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 PHI nodes, terminators,
+ /// BasicBlock can only be used by Users (specifically terminators
/// and BlockAddress's).
User *use_back() { return cast<User>(*use_begin());}
const User *use_back() const { return cast<User>(*use_begin());}
/// 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
explicit PHINode(const Type *Ty, unsigned NumReservedValues,
const Twine &NameStr = "", Instruction *InsertBefore = 0)
: Instruction(Ty, Instruction::PHI, 0, 0, InsertBefore),
- ReservedSpace(NumReservedValues * 2) {
+ ReservedSpace(NumReservedValues) {
setName(NameStr);
OperandList = allocHungoffUses(ReservedSpace);
}
PHINode(const Type *Ty, unsigned NumReservedValues, const Twine &NameStr,
BasicBlock *InsertAtEnd)
: Instruction(Ty, Instruction::PHI, 0, 0, InsertAtEnd),
- ReservedSpace(NumReservedValues * 2) {
+ ReservedSpace(NumReservedValues) {
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
/// 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<Use::UserRef*>(op_begin() + ReservedSpace);
+ return reinterpret_cast<block_iterator>(ref + 1);
+ }
+
+ const_block_iterator block_begin() const {
+ const Use::UserRef *ref =
+ reinterpret_cast<const Use::UserRef*>(op_begin() + ReservedSpace);
+ return reinterpret_cast<const_block_iterator>(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()/2; }
+ unsigned getNumIncomingValues() const { return getNumOperands(); }
/// getIncomingValue - Return incoming value number x
///
Value *getIncomingValue(unsigned i) const {
- assert(i*2 < getNumOperands() && "Invalid value number!");
- return getOperand(i*2);
+ return getOperand(i);
}
void setIncomingValue(unsigned i, Value *V) {
- assert(i*2 < getNumOperands() && "Invalid value number!");
- setOperand(i*2, V);
+ setOperand(i, V);
}
static unsigned getOperandNumForIncomingValue(unsigned i) {
- return i*2;
+ return i;
}
static unsigned getIncomingValueNumForOperand(unsigned i) {
- assert(i % 2 == 0 && "Invalid incoming-value operand index!");
- return i/2;
+ return i;
}
/// getIncomingBlock - Return incoming basic block number @p i.
///
BasicBlock *getIncomingBlock(unsigned i) const {
- return cast<BasicBlock>(getOperand(i*2+1));
+ return block_begin()[i];
}
/// getIncomingBlock - Return incoming basic block corresponding
///
BasicBlock *getIncomingBlock(const Use &U) const {
assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
- return cast<BasicBlock>((&U + 1)->get());
+ return getIncomingBlock(unsigned(&U - op_begin()));
}
/// getIncomingBlock - Return incoming basic block corresponding
return getIncomingBlock(I.getUse());
}
-
void setIncomingBlock(unsigned i, BasicBlock *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;
+ block_begin()[i] = BB;
}
/// addIncoming - Add an incoming value to the end of the PHI list
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!");
- unsigned OpNo = NumOperands;
- if (OpNo+2 > ReservedSpace)
+ if (NumOperands == ReservedSpace)
growOperands(); // Get more space!
// Initialize some new operands.
- NumOperands = OpNo+2;
- OperandList[OpNo] = V;
- OperandList[OpNo+1] = (Value*)BB;
+ ++NumOperands;
+ setIncomingValue(NumOperands - 1, V);
+ setIncomingBlock(NumOperands - 1, BB);
}
/// removeIncomingValue - Remove an incoming value. This is useful if a
/// block in the value list for this PHI. Returns -1 if no instance.
///
int getBasicBlockIndex(const BasicBlock *BB) const {
- Use *OL = OperandList;
- for (unsigned i = 0, e = getNumOperands(); i != e; i += 2)
- if (OL[i+1].get() == (const Value*)BB) return i/2;
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+ if (block_begin()[i] == BB)
+ return i;
return -1;
}
Value *getIncomingValueForBlock(const BasicBlock *BB) const {
- return getIncomingValue(getBasicBlockIndex(BB));
+ int Idx = getBasicBlockIndex(BB);
+ assert(Idx >= 0 && "Invalid basic block argument!");
+ return getIncomingValue(Idx);
}
/// hasConstantValue - If the specified PHI node always merges together the
USE_iterator It;
inline void advancePastNonTerminators() {
- // Loop to ignore non terminator uses (for example PHI nodes).
+ // Loop to ignore non terminator uses (for example BlockAddresses).
while (!It.atEnd() && !isa<TerminatorInst>(*It))
++It;
}
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;
}
friend class Value;
- friend class User;
};
// simplify_type - Allow clients to treat uses just like values when using
} else {
// Otherwise, write out in binary.
OS << "0b";
- for (int j = 7; j >= 0; j--) {
+ for (unsigned j = 8; j--;) {
unsigned Bit = (Code[i] >> j) & 1;
unsigned FixupBit;
else
FixupBit = i * 8 + (7-j);
- if (uint8_t FixupMapEntry = FixupMap[FixupBit]) {
- //assert(Bit == 0 && "Encoder wrote into fixed up bit!");
- OS << char('A' + FixupMapEntry - 1);
+ if (uint8_t MapEntry = FixupMap[FixupBit]) {
+ assert(Bit == 0 && "Encoder wrote into fixed up bit!");
+ OS << char('A' + MapEntry - 1);
} else
OS << Bit;
}
for (unsigned i = 0; i < phi->getNumIncomingValues(); ++i) {
Out << iName << "->addIncoming("
<< opNames[PHINode::getOperandNumForIncomingValue(i)] << ", "
- << opNames[PHINode::getOperandNumForIncomingBlock(i)] << ");";
+ << getOpName(phi->getIncomingBlock(i)) << ");";
nl(Out);
}
break;
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());
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);
// 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);
// 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);
}
}
// 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();
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();
// 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);
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()) {
// 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) {
// 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.
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
// 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...
BasicBlock *Header = L->getHeader();
BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
-
+
if (!BI || BI->isUnconditional()) {
// The loop-rotate pass can be helpful to avoid this in many cases.
DEBUG(dbgs() <<
" Can't unroll; loop not terminated by a conditional branch.\n");
return false;
}
-
+
if (Header->hasAddressTaken()) {
// The loop-rotate pass can be helpful to avoid this in many cases.
DEBUG(dbgs() <<
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
OrigPHINode.push_back(PN);
- if (Instruction *I =
+ if (Instruction *I =
dyn_cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)))
if (L->contains(I))
LastValueMap[I] = I;
for (unsigned It = 1; It != Count; ++It) {
std::vector<BasicBlock*> NewBlocks;
-
+
for (std::vector<BasicBlock*>::iterator BB = LoopBlocks.begin(),
E = LoopBlocks.end(); BB != E; ++BB) {
ValueToValueMapTy VMap;
// 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();
+ 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.
NewBlocks.push_back(New);
}
-
+
// Remap all instructions in the most recent iteration
for (unsigned i = 0; i < NewBlocks.size(); ++i)
for (BasicBlock::iterator I = NewBlocks[i]->begin(),
E = NewBlocks[i]->end(); I != E; ++I)
::RemapInstruction(I, LastValueMap);
}
-
+
// The latch block exits the loop. If there are any PHI nodes in the
// 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();
+ 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);
}
}
// 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)) {
- std::replace(Latches.begin(), Latches.end(), Dest, Fold);
- std::replace(Headers.begin(), Headers.end(), Dest, Fold);
- }
}
}
+ // 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);
+ }
+ }
+
// At this point, the code is well formed. We now do a quick sweep over the
// inserted code, doing constant propagation and dead code elimination as we
// go.
#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;
"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);
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<PHINode>(II);
+ ++II) {
+ int i;
+ while ((i = PN->getBasicBlockIndex(this)) >= 0)
+ PN->setIncomingBlock(i, New);
+ }
+ }
+}
: Instruction(PN.getType(), Instruction::PHI,
allocHungoffUses(PN.getNumOperands()), PN.getNumOperands()),
ReservedSpace(PN.getNumOperands()) {
- 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);
- }
+ std::copy(PN.op_begin(), PN.op_end(), op_begin());
+ std::copy(PN.block_begin(), PN.block_end(), block_begin());
SubclassOptionalData = PN.SubclassOptionalData;
}
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<Use*>(::operator new(size));
+ Use *End = Begin + N;
+ (void) new(End) Use::UserRef(const_cast<PHINode*>(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) {
- unsigned NumOps = getNumOperands();
- Use *OL = OperandList;
- assert(Idx*2 < NumOps && "BB not in PHI node!");
- Value *Removed = OL[Idx*2];
+ Value *Removed = getIncomingValue(Idx);
// Move everything after this operand down.
//
// FIXME: we could just swap with the end of the list, then erase. However,
- // client might not expect this to happen. The code as it is thrashes the
+ // clients might not expect this to happen. The code as it is thrashes the
// use/def lists, which is kinda lame.
- for (unsigned i = (Idx+1)*2; i != NumOps; i += 2) {
- OL[i-2] = OL[i];
- OL[i-2+1] = OL[i+1];
- }
+ std::copy(op_begin() + Idx + 1, op_end(), op_begin() + Idx);
+ std::copy(block_begin() + Idx + 1, block_end(), block_begin() + Idx);
// Nuke the last value.
- OL[NumOps-2].set(0);
- OL[NumOps-2+1].set(0);
- NumOperands = NumOps-2;
+ Op<-1>().set(0);
+ --NumOperands;
// If the PHI node is dead, because it has zero entries, nuke it now.
- if (NumOps == 2 && DeletePHIIfEmpty) {
+ if (getNumOperands() == 0 && DeletePHIIfEmpty) {
// If anyone is using this PHI, make them use a dummy value instead...
replaceAllUsesWith(UndefValue::get(getType()));
eraseFromParent();
///
void PHINode::growOperands() {
unsigned e = getNumOperands();
- // 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.
+ 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();
ReservedSpace = NumOps;
- Use *OldOps = OperandList;
- Use *NewOps = allocHungoffUses(NumOps);
- std::copy(OldOps, OldOps + e, NewOps);
- OperandList = NewOps;
+ OperandList = allocHungoffUses(ReservedSpace);
+
+ std::copy(OldOps, OldOps + e, op_begin());
+ std::copy(OldBlocks, OldBlocks + e, block_begin());
+
Use::zap(OldOps, OldOps + e, true);
}
//===----------------------------------------------------------------------===//
Use *User::allocHungoffUses(unsigned N) const {
- Use *Begin = static_cast<Use*>(::operator new(sizeof(Use) * N
- + sizeof(Use::UserRef)));
+ // 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<Use*>(::operator new(size));
Use *End = Begin + N;
(void) new(End) Use::UserRef(const_cast<User*>(this), 1);
return Use::initTags(Begin, End);
U.set(New);
}
+
+ if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
+ BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
}
void Value::replaceAllUsesWith(Value *New) {
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<BasicBlock>(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.