-bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier & DF) {
- // Calculate the set of safe allocas
- findSafeAllocas(F);
-
- // 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.
- for (unsigned i = 0; i<Allocas.size(); ++i)
- {
- AllocaInst * AI = Allocas[i];
- WriteSets.push_back(std::vector<BasicBlock *>()); //add a new set
- for (Value::use_iterator U = AI->use_begin();U!=AI->use_end();++U)
- {
- if (MemAccessInst *MAI = dyn_cast<StoreInst>(*U)) {
- WriteSets[i].push_back(MAI->getParent()); // jot down the basic-block it came from
- }
- }
- }
-
- // 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();p!=s.end(); ++p)
- {
- if (queuePhiNode(*p, i))
- PhiNodes[i].push_back(*p);
- }
- }
- // 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(); p!=s.end(); ++p)
- {
- if (queuePhiNode(*p,i))
- PhiNodes[i].push_back(*p);
- }
- }
- }
-
- // Walks all basic blocks in the function
- // performing the SSA rename algorithm
- // and inserting the phi nodes we marked as necessary
- BasicBlock * f = F->front(); //get root basic-block
-
- CurrentValue.push_back(vector<Value *>(Allocas.size()));
-
- traverse(f, NULL); // there is no predecessor of the root node
-
-
- // ** REMOVE EVERYTHING IN THE KILL-LIST **
- // we need to kill 'uses' before root values
- // so we should probably run through in reverse
- for (vector<Instruction *>::reverse_iterator i = killlist.rbegin(); i!=killlist.rend(); ++i)
- {
- Instruction * r = *i;
- BasicBlock * o = r->getParent();
- //now go find..
-
- BasicBlock::InstListType & l = o->getInstList();
- o->getInstList().remove(r);
- delete r;
- }
-
- return !Allocas.empty();
+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]->getType()->getElementType());
+
+ // 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->front(), 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().remove(I);
+ delete I;
+ }
+
+ // Purge data structurse so they are available the next iteration...
+ Allocas.clear();
+ AllocaLookup.clear();
+ PhiNodes.clear();
+ NewPhiNodes.clear();
+ return true;