Untitled
/** * 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" 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) { std::set<StringRef> null_set; use[&BB] = null_set; def[&BB] = null_set; for(auto itr=BB.rbegin(); itr!=BB.rend();itr++) { /*if instruction is store instruction*/ if(auto *storeInst = dyn_cast_or_null<StoreInst>(&*itr)) { StringRef stVar = storeInst->getPointerOperand()->getName(); if(namedVars.find(stVar)!=namedVars.end()) { use[&BB].erase(stVar); def[&BB].insert(stVar); } } /*if instruction is load instruction*/ else if(auto *loadInst = dyn_cast_or_null<LoadInst>(&*itr)) { StringRef ldVar = loadInst->getPointerOperand()->getName(); if(namedVars.find(ldVar)!=namedVars.end()) { use[&BB].insert(ldVar); def[&BB].erase(ldVar); } } } } // 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; bb_stack.push(&frontBB); while(!bb_stack.empty()) { BasicBlock* bb = bb_stack.top(); //once block and its descendants discovered pop and put into the vector if(visited.find(bb)!=visited.end()) { bb_stack.pop(); bb_list.push_back(bb); } else { visited.insert(bb); //put all successors on stack 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); } } } } // 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; 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; //eval out[bb]-def[bb] for(auto str: def[bb]) { out.erase(str); } in.insert(out.begin(),out.end()); //check for change if(bb2In[bb]!=in) { bb2In[bb]=in; change=true; } } 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; }
Leave a Comment