+bool PromotePass::runOnFunction(Function &F) {
+ // Calculate the set of safe allocas
+ FindSafeAllocas(F);
+
+ // If there is nothing to do, bail out...
+ if (Allocas.empty()) return false;
+
+ // Add each alloca to the KillList. Note: KillList is destroyed MOST recently
+ // added to least recently.
+ KillList.assign(Allocas.begin(), Allocas.end());
+
+ // Calculate the set of write-locations for each alloca. This is analogous to
+ // counting the number of 'redefinitions' of each variable.
+ vector<vector<BasicBlock*> > WriteSets; // index corresponds to Allocas
+ WriteSets.resize(Allocas.size());
+ for (unsigned i = 0; i != Allocas.size(); ++i) {
+ AllocaInst *AI = Allocas[i];
+ for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E; ++U)
+ if (StoreInst *SI = dyn_cast<StoreInst>(*U))
+ // jot down the basic-block it came from
+ WriteSets[i].push_back(SI->getParent());
+ }
+
+ // Get dominance frontier information...
+ DominanceFrontier &DF = getAnalysis<DominanceFrontier>();
+
+ // Compute the locations where PhiNodes need to be inserted. Look at the
+ // dominance frontier of EACH basic-block we have a write in
+ //
+ PhiNodes.resize(Allocas.size());
+ for (unsigned i = 0; i != Allocas.size(); ++i) {
+ for (unsigned j = 0; j != WriteSets[i].size(); j++) {
+ // Look up the DF for this write, add it to PhiNodes
+ DominanceFrontier::const_iterator it = DF.find(WriteSets[i][j]);
+ DominanceFrontier::DomSetType S = it->second;
+ for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end();
+ P != PE; ++P)
+ QueuePhiNode(*P, i);
+ }
+
+ // Perform iterative step
+ for (unsigned k = 0; k != PhiNodes[i].size(); k++) {
+ DominanceFrontier::const_iterator it = DF.find(PhiNodes[i][k]);
+ DominanceFrontier::DomSetType S = it->second;
+ for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end();
+ P != PE; ++P)
+ QueuePhiNode(*P, i);
+ }
+ }
+
+ // Set the incoming values for the basic block to be null values for all of
+ // the alloca's. We do this in case there is a load of a value that has not
+ // been stored yet. In this case, it will get this null value.
+ //
+ vector<Value *> Values(Allocas.size());
+ for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
+ Values[i] = Constant::getNullValue(Allocas[i]->getAllocatedType());
+
+ // Walks all basic blocks in the function performing the SSA rename algorithm
+ // and inserting the phi nodes we marked as necessary
+ //
+ set<BasicBlock*> Visited; // The basic blocks we've already visited
+ Traverse(F.begin(), 0, Values, Visited);
+
+ // Remove all instructions marked by being placed in the KillList...
+ //
+ while (!KillList.empty()) {
+ Instruction *I = KillList.back();
+ KillList.pop_back();
+
+ I->getParent()->getInstList().erase(I);
+ }
+
+ NumPromoted += Allocas.size();
+
+ // Purge data structurse so they are available the next iteration...
+ Allocas.clear();
+ AllocaLookup.clear();
+ PhiNodes.clear();
+ NewPhiNodes.clear();
+ return true;