Untitled
unknown
plain_text
a year ago
6.4 kB
4
Indexable
/** * USCC Compiler * Jianping Zeng (zeng207@purdue.edu) * An iterative backward liveness analysis. * This pass intends to compute a set of live-out/in variables for each LLVM basic block * and maintain a set of LLVM instructions that are dead---not used by any following others. */ #include "Liveness.h" #include <iostream> using namespace std; using namespace llvm; bool enableLiveness; char Liveness::ID = 0; INITIALIZE_PASS(Liveness, "liveness", "Liveness Analysis", true, true) FunctionPass *llvm::createLivenessPass() { return new Liveness(); } bool Liveness::runOnFunction(Function &F) { if (F.empty()) return false; BasicBlock &frontBB = F.front(); BasicBlock &endBB = F.back(); assert(!frontBB.empty() && !endBB.empty() && "the front/end basic block must not be empty!"); // The OUT set of the last block is empty. bb2Out[&endBB] = std::set<StringRef>(); // PA3 // Step #1: identify program variables. for(auto &BB:F) { for(auto &inst:BB) { if(inst.getOpcode() == llvm::Instruction::Alloca && inst.hasName()) { namedVars.insert(inst.getName()); } } } // Step #2: calculate DEF/USE set for each basic block std::map<BasicBlock*, std::set<StringRef>> use, def; for(auto &BB:F) { for(auto itr=BB.rbegin(); itr!=BB.rend();itr++) { std::set<StringRef> null_set; use[&BB] = null_set; def[&BB] = null_set; /*if instruction is load instruction*/ if(auto *loadInst = dyn_cast_or_null<LoadInst>(&*itr)) { StringRef ldVar = loadInst->getPointerOperand()->getName(); outs()<<"LOAD---->: "<<ldVar<<"\n"; if(namedVars.find(ldVar)!=namedVars.end()) { use[&BB].erase(ldVar); def[&BB].insert(ldVar); } } /*if instruction is store instruction*/ else if(auto *storeInst = dyn_cast_or_null<StoreInst>(&*itr)) { StringRef stVar = storeInst->getPointerOperand()->getName(); outs()<<"STORE---->: "<<stVar<<"\n"; if(namedVars.find(stVar)!=namedVars.end()) { use[&BB].insert(stVar); def[&BB].erase(stVar); } } } } // Step #3: compute post order traversal. std::set<BasicBlock*> visited; std::vector<BasicBlock*> bb_list; //vector to store post-order traversal std::stack<BasicBlock*> bb_stack; visited.insert(&frontBB); bb_stack.push(&frontBB); while(!bb_stack.empty()) { BasicBlock* bb = bb_stack.top(); bool inserted=false; for(auto succ_itr=succ_begin(bb);succ_itr!=succ_end(bb);succ_itr++) { BasicBlock* sbb= *succ_itr; if(visited.find(sbb)==visited.end()) { bb_stack.push(sbb); visited.insert(sbb); inserted=true; } } if(!inserted) { bb_stack.pop(); bb_list.push_back(bb); } } // Step #4: iterate over control flow graph of the input function until the fixed point. unsigned cnt = 0; bool change=true; while(change) { change=false; for(auto *bb:bb_list) { if(bb2In.find(bb)==bb2In.end()) { set<StringRef> nullset; bb2In[bb]=nullset; } set<StringRef> in=use[bb],out; if(bb!=&endBB) { for(auto succ_itr=succ_begin(bb);succ_itr!=succ_end(bb);succ_itr++) { BasicBlock* sbb= *succ_itr; if(bb2In.find(sbb)!=bb2In.end()) { out.insert(bb2In[sbb].begin(),bb2In[sbb].end()); } } bb2Out[bb]=out; } else { out=bb2Out[bb]; } for(auto str: def[bb]) { out.erase(str); } in.insert(out.begin(),out.end()); if(bb2In[bb]!=in) { bb2In[bb]=in; change=true; } llvm::outs() << " USE:"; for (auto &var : use[bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; llvm::outs() << " DEF:"; for (auto &var : def[bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; llvm::outs() << " IN:"; for (auto &var : bb2In[bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; llvm::outs() << " OUT:"; for (auto &var : bb2Out[bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; } cnt++; } // Step #5: output IN/OUT set for each basic block. if (enableLiveness) { llvm::outs() << "********** Live-in/Live-out information **********\n"; llvm::outs() << "********** Function: " << F.getName().str() << ", analysis iterates " << cnt << " times\n"; for (auto &bb : F) { llvm::outs() << bb.getName() << ":\n"; llvm::outs() << " IN:"; for (auto &var : bb2In[&bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; llvm::outs() << " OUT:"; for (auto &var : bb2Out[&bb]) llvm::outs() << " " << var.substr(0, var.size() - 5); llvm::outs() << "\n"; } } // Liveness does not change the input function at all. return false; } bool Liveness::isDead(llvm::Instruction &inst) { BasicBlock *bb = inst.getParent(); if (!bb) return true; if (!bb2Out.count(bb)) return true; // PA3 return false; }
Editor is loading...
Leave a Comment