+// MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not
+// "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF
+// as usual (inserting the PHI nodes in the DeadPHINodes set), then processes
+// each read of the variable. For each block that reads the variable, this
+// function is called, which removes used PHI nodes from the DeadPHINodes set.
+// After all of the reads have been processed, any PHI nodes left in the
+// DeadPHINodes set are removed.
+//
+void PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
+ std::set<PHINode*> &DeadPHINodes) {
+ // Scan the immediate dominators of this block looking for a block which has a
+ // PHI node for Alloca num. If we find it, mark the PHI node as being alive!
+ for (DominatorTree::Node *N = DT[BB]; N; N = N->getIDom()) {
+ BasicBlock *DomBB = N->getBlock();
+ std::map<BasicBlock*, std::vector<PHINode*> >::iterator
+ I = NewPhiNodes.find(DomBB);
+ if (I != NewPhiNodes.end() && I->second[AllocaNum]) {
+ // Ok, we found an inserted PHI node which dominates this value.
+ PHINode *DominatingPHI = I->second[AllocaNum];
+
+ // Find out if we previously thought it was dead.
+ std::set<PHINode*>::iterator DPNI = DeadPHINodes.find(DominatingPHI);
+ if (DPNI != DeadPHINodes.end()) {
+ // Ok, until now, we thought this PHI node was dead. Mark it as being
+ // alive/needed.
+ DeadPHINodes.erase(DPNI);
+
+ // Now that we have marked the PHI node alive, also mark any PHI nodes
+ // which it might use as being alive as well.
+ for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB);
+ PI != PE; ++PI)
+ MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes);
+ }
+ }
+ }
+}
+
+/// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic
+/// block. If this is the case, avoid traversing the CFG and inserting a lot of
+/// potentially useless PHI nodes by just performing a single linear pass over
+/// the basic block using the Alloca.
+///
+/// If we cannot promote this alloca (because it is read before it is written),
+/// return true. This is necessary in cases where, due to control flow, the
+/// alloca is potentially undefined on some control flow paths. e.g. code like
+/// this is potentially correct:
+///
+/// for (...) { if (c) { A = undef; undef = B; } }
+///
+/// ... so long as A is not used before undef is set.
+///
+bool PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) {
+ assert(!AI->use_empty() && "There are no uses of the alloca!");
+
+ // Handle degenerate cases quickly.
+ if (AI->hasOneUse()) {
+ Instruction *U = cast<Instruction>(AI->use_back());
+ if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
+ // Must be a load of uninitialized value.
+ LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType()));
+ if (AST && isa<PointerType>(LI->getType()))
+ AST->deleteValue(LI);
+ } else {
+ // Otherwise it must be a store which is never read.
+ assert(isa<StoreInst>(U));
+ }
+ BB->getInstList().erase(U);
+ } else {
+ // Uses of the uninitialized memory location shall get undef.
+ Value *CurVal = 0;
+
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
+ Instruction *Inst = I++;
+ if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+ if (LI->getOperand(0) == AI) {
+ if (!CurVal) return true; // Could not locally promote!
+
+ // Loads just returns the "current value"...
+ LI->replaceAllUsesWith(CurVal);
+ if (AST && isa<PointerType>(LI->getType()))
+ AST->deleteValue(LI);
+ BB->getInstList().erase(LI);
+ }
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+ if (SI->getOperand(1) == AI) {
+ // Store updates the "current value"...
+ CurVal = SI->getOperand(0);
+ BB->getInstList().erase(SI);
+ }
+ }
+ }
+ }
+
+ // After traversing the basic block, there should be no more uses of the
+ // alloca, remove it now.
+ assert(AI->use_empty() && "Uses of alloca from more than one BB??");
+ if (AST) AST->deleteValue(AI);
+ AI->getParent()->getInstList().erase(AI);
+ return false;
+}
+
+/// PromoteLocallyUsedAllocas - This method is just like
+/// PromoteLocallyUsedAlloca, except that it processes multiple alloca
+/// instructions in parallel. This is important in cases where we have large
+/// basic blocks, as we don't want to rescan the entire basic block for each
+/// alloca which is locally used in it (which might be a lot).
+void PromoteMem2Reg::
+PromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) {
+ std::map<AllocaInst*, Value*> CurValues;
+ for (unsigned i = 0, e = AIs.size(); i != e; ++i)
+ CurValues[AIs[i]] = 0; // Insert with null value
+
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
+ Instruction *Inst = I++;
+ if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+ // Is this a load of an alloca we are tracking?
+ if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) {
+ std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI);
+ if (AIt != CurValues.end()) {
+ // If loading an uninitialized value, allow the inter-block case to
+ // handle it. Due to control flow, this might actually be ok.
+ if (AIt->second == 0) { // Use of locally uninitialized value??
+ RetryList.push_back(AI); // Retry elsewhere.
+ CurValues.erase(AIt); // Stop tracking this here.
+ if (CurValues.empty()) return;
+ } else {
+ // Loads just returns the "current value"...
+ LI->replaceAllUsesWith(AIt->second);
+ if (AST && isa<PointerType>(LI->getType()))
+ AST->deleteValue(LI);
+ BB->getInstList().erase(LI);
+ }
+ }
+ }
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+ if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) {
+ std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI);
+ if (AIt != CurValues.end()) {
+ // Store updates the "current value"...
+ AIt->second = SI->getOperand(0);
+ BB->getInstList().erase(SI);
+ }
+ }
+ }
+ }