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;
}