[LLVMdev] Finding all values derived from a function argument

[Stephan Reiter]

Hello!

I am trying to retrieve all instructions from a function's body that
are dependent on a specific argument. The strategy I am currently
using for that is to follow all uses of the argument and record them.
Also, whenever I encounter a store of a dependent value, I try to find
loads in the function that are dependent on that store and resume
use-tracking from there. For this purpose I am using the
MemoryDependenceAnalysis pass, but to be honest, I think I am not
using it correctly or not in the most efficient way.

Is such functionality - finding dependent instructions - present in
LLVM? If not, is there a more efficient way to determine dependent
instructions than like in the code below? In particular, I'm wondering
if it is possible to find all loads that depend on a particular store
more efficiently?

Thank you,
Stephan

    llvm::DenseSet<llvm::Instruction *> findDependents(llvm::Argument
*arg, llvm::Function *func)
    {
      std::vector<llvm::Instruction *> workList;
      for(llvm::Argument::use_iterator I = arg->use_begin(), E =
arg->use_end(); I != E; ++I)
      {
        if(llvm::Instruction *user = llvm::dyn_cast<llvm::Instruction>(*I))
          workList.push_back(user);
      }

      llvm::FunctionPassManager fpm(func->getParent());
      llvm::MemoryDependenceAnalysis *mda = new
llvm::MemoryDependenceAnalysis();
      fpm.add(mda);
      fpm.run(*func);

      // find all loads in the current function
      std::list<llvm::LoadInst *> loads;
      for(llvm::Function::iterator I = func->begin(), E = func->end();
I != E; ++I)
      {
        for(llvm::BasicBlock::iterator II = I->begin(), EE = I->end();
II != EE; ++II)
        {
          if(llvm::LoadInst *load = llvm::dyn_cast<llvm::LoadInst>(II))
            loads.push_back(load);
        }
      }

      llvm::DenseSet<llvm::Instruction *> deps;
      for(;;)
      {
        llvm::DenseSet<llvm::Instruction *> stores;
        while(!workList.empty())
        {
          llvm::Instruction *I = workList.back();
          workList.pop_back();

          if(deps.count(I) != 0)
            continue;

          deps.insert(I);

          if(llvm::StoreInst *store = llvm::dyn_cast<llvm::StoreInst>(I))
            stores.insert(I);

          for(llvm::Value::use_iterator II = I->use_begin(), EE =
I->use_end(); II != EE; ++II)
          {
            if(llvm::Instruction *user = llvm::dyn_cast<llvm::Instruction>(*II))
              workList.push_back(user);
          }
        }

        if(stores.size() > 0)
        {
          // find loads that depend on our stores, TODO: this seems fishy!
          for(std::list<llvm::LoadInst *>::iterator I = loads.begin(),
E = loads.end(); I != E; )
          {
            bool pick = false;
#if 1
            llvm::SmallVector<llvm::NonLocalDepResult, 16> results;
            mda->getNonLocalPointerDependency((*I)->getPointerOperand(),
true, (*I)->getParent(), results);
            for(llvm::SmallVector<llvm::NonLocalDepResult,
16>::iterator II = results.begin(), EE = results.end(); !pick && II !=
EE; ++II)
            {
              const llvm::MemDepResult &result = II->getResult();
              if(llvm::Instruction *dep = result.getInst())
              {
                if(llvm::StoreInst *store =
llvm::dyn_cast<llvm::StoreInst>(dep))
                  pick |= (stores.count(store) != 0);
              }
            }
#else
            llvm::MemDepResult result = mda->getDependency(*I);
            if(llvm::Instruction *dep = result.getInst())
            {
              if(llvm::StoreInst *store = llvm::dyn_cast<llvm::StoreInst>(dep))
                pick = (stores.count(store) != 0);
            }
#endif
            if(pick)
            {
              workList.push_back(*I);
              I = loads.erase(I);
            }
            else
              ++I;
          }

          stores.clear();
        }
        else
          break;
      }
      return deps;
    }