LLVM API Documentation

DependenceAnalyzer.cpp

Go to the documentation of this file.
00001 //===-- DependenceAnalyzer.cpp - DependenceAnalyzer  ------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //
00011 //
00012 //
00013 //===----------------------------------------------------------------------===//
00014 #define DEBUG_TYPE "ModuloSched"
00015 
00016 #include "DependenceAnalyzer.h"
00017 #include "llvm/Type.h"
00018 #include "llvm/Support/Debug.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Constants.h"
00021 #include <iostream>
00022 using namespace llvm;
00023 
00024 namespace llvm {
00025 
00026   /// Create ModuloSchedulingPass
00027   FunctionPass *createDependenceAnalyzer() {
00028     return new DependenceAnalyzer();
00029   }
00030 }
00031 
00032 Statistic<> NoDeps("depanalyzer-nodeps", "Number of dependences eliminated");
00033 Statistic<> NumDeps("depanalyzer-deps",
00034                     "Number of dependences could not eliminate");
00035 Statistic<> AdvDeps("depanalyzer-advdeps",
00036                     "Number of dependences using advanced techniques");
00037 
00038 bool DependenceAnalyzer::runOnFunction(Function &F) {
00039   AA = &getAnalysis<AliasAnalysis>();
00040   TD = &getAnalysis<TargetData>();
00041   SE = &getAnalysis<ScalarEvolution>();
00042 
00043   return  false;
00044 }
00045 
00046 static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer",
00047                                              "Dependence Analyzer");
00048 
00049 //  - Get inter and intra dependences between loads and stores
00050 //
00051 // Overview of Method:
00052 // Step 1: Use alias analysis to determine dependencies if values are loop
00053 //       invariant
00054 // Step 2: If pointers are not GEP, then there is a dependence.
00055 // Step 3: Compare GEP base pointers with AA. If no alias, no dependence.
00056 //         If may alias, then add a dependence. If must alias, then analyze
00057 //         further (Step 4)
00058 // Step 4: do advanced analysis
00059 void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad,
00060                                      bool val2Load,
00061                                      std::vector<Dependence> &deps,
00062                                      BasicBlock *BB,
00063                                      bool srcBeforeDest) {
00064 
00065   bool loopInvariant = true;
00066 
00067   //Check if both are instructions and prove not loop invariant if possible
00068   if(Instruction *valInst = dyn_cast<Instruction>(val))
00069     if(valInst->getParent() == BB)
00070       loopInvariant = false;
00071   if(Instruction *val2Inst = dyn_cast<Instruction>(val2))
00072     if(val2Inst->getParent() == BB)
00073       loopInvariant = false;
00074 
00075 
00076   //If Loop invariant, let AA decide
00077   if(loopInvariant) {
00078     if(AA->alias(val, (unsigned)TD->getTypeSize(val->getType()),
00079                  val2,(unsigned)TD->getTypeSize(val2->getType()))
00080        != AliasAnalysis::NoAlias) {
00081       createDep(deps, valLoad, val2Load, srcBeforeDest);
00082     }
00083     else
00084       ++NoDeps;
00085     return;
00086   }
00087 
00088   //Otherwise, continue with step 2
00089 
00090   GetElementPtrInst *GP = dyn_cast<GetElementPtrInst>(val);
00091   GetElementPtrInst *GP2 = dyn_cast<GetElementPtrInst>(val2);
00092 
00093   //If both are not GP instructions, we can not do further analysis
00094   if(!GP || !GP2) {
00095     createDep(deps, valLoad, val2Load, srcBeforeDest);
00096     return;
00097   }
00098 
00099 
00100   //Otherwise, compare GEP bases (op #0) with Alias Analysis
00101 
00102   Value *GPop = GP->getOperand(0);
00103   Value *GP2op = GP2->getOperand(0);
00104   int alias = AA->alias(GPop, (unsigned)TD->getTypeSize(GPop->getType()),
00105                         GP2op,(unsigned)TD->getTypeSize(GP2op->getType()));
00106 
00107 
00108   if(alias == AliasAnalysis::MustAlias) {
00109     //Further dep analysis to do
00110     advancedDepAnalysis(GP, GP2, valLoad, val2Load, deps, srcBeforeDest);
00111     ++AdvDeps;
00112   }
00113   else if(alias == AliasAnalysis::MayAlias) {
00114     createDep(deps, valLoad, val2Load, srcBeforeDest);
00115   }
00116   //Otherwise no dependence since there is no alias
00117   else
00118     ++NoDeps;
00119 }
00120 
00121 
00122 // advancedDepAnalysis - Do advanced data dependence tests
00123 void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1,
00124                                              GetElementPtrInst *gp2,
00125                                              bool valLoad,
00126                                              bool val2Load,
00127                                              std::vector<Dependence> &deps,
00128                                              bool srcBeforeDest) {
00129 
00130   //Check if both GEPs are in a simple form: 3 ops, constant 0 as second arg
00131   if(gp1->getNumOperands() != 3 || gp2->getNumOperands() != 3) {
00132     createDep(deps, valLoad, val2Load, srcBeforeDest);
00133     return;
00134   }
00135 
00136   //Check second arg is constant 0
00137   bool GPok = false;
00138   if(Constant *c1 = dyn_cast<Constant>(gp1->getOperand(1)))
00139     if(Constant *c2 = dyn_cast<Constant>(gp2->getOperand(1)))
00140       if(c1->isNullValue() && c2->isNullValue())
00141         GPok = true;
00142 
00143   if(!GPok) {
00144     createDep(deps, valLoad, val2Load, srcBeforeDest);
00145     return;
00146 
00147   }
00148 
00149   Value *Gep1Idx = gp1->getOperand(2);
00150   Value *Gep2Idx = gp2->getOperand(2);
00151 
00152   if(CastInst *c1 = dyn_cast<CastInst>(Gep1Idx))
00153     Gep1Idx = c1->getOperand(0);
00154   if(CastInst *c2 = dyn_cast<CastInst>(Gep2Idx))
00155     Gep2Idx = c2->getOperand(0);
00156 
00157   //Get SCEV for each index into the area
00158   SCEVHandle SV1 = SE->getSCEV(Gep1Idx);
00159   SCEVHandle SV2 = SE->getSCEV(Gep2Idx);
00160 
00161   //Now handle special cases of dependence analysis
00162   //SV1->print(std::cerr);
00163   //std::cerr << "\n";
00164   //SV2->print(std::cerr);
00165   //std::cerr << "\n";
00166 
00167   //Check if we have an SCEVAddExpr, cause we can only handle those
00168   SCEVAddRecExpr *SVAdd1 = dyn_cast<SCEVAddRecExpr>(SV1);
00169   SCEVAddRecExpr *SVAdd2 = dyn_cast<SCEVAddRecExpr>(SV2);
00170 
00171   //Default to having a dependence since we can't analyze further
00172   if(!SVAdd1 || !SVAdd2) {
00173     createDep(deps, valLoad, val2Load, srcBeforeDest);
00174     return;
00175   }
00176 
00177   //Check if not Affine, we can't handle those
00178   if(!SVAdd1->isAffine( ) || !SVAdd2->isAffine()) {
00179     createDep(deps, valLoad, val2Load, srcBeforeDest);
00180     return;
00181   }
00182 
00183   //We know the SCEV is in the form A + B*x, check that B is the same for both
00184   SCEVConstant *B1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(1));
00185   SCEVConstant *B2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(1));
00186 
00187   if(B1->getValue() != B2->getValue()) {
00188     createDep(deps, valLoad, val2Load, srcBeforeDest);
00189     return;
00190   }
00191 
00192   if(B1->getValue()->getRawValue() != 1 || B2->getValue()->getRawValue() != 1) {
00193     createDep(deps, valLoad, val2Load, srcBeforeDest);
00194     return;
00195   }
00196 
00197 
00198   SCEVConstant *A1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(0));
00199   SCEVConstant *A2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(0));
00200 
00201   //Come back and deal with nested SCEV!
00202   if(!A1 || !A2) {
00203     createDep(deps, valLoad, val2Load, srcBeforeDest);
00204     return;
00205   }
00206 
00207   //If equal, create dep as normal
00208   if(A1->getValue() == A2->getValue()) {
00209     createDep(deps, valLoad, val2Load, srcBeforeDest);
00210     return;
00211   }
00212   //Eliminate a dep if this is a intra dep
00213   else if(srcBeforeDest) {
00214     ++NoDeps;
00215     return;
00216   }
00217 
00218   //Find constant index difference
00219   int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue();
00220   //std::cerr << diff << "\n";
00221   if(diff > 5)
00222     diff = 2;
00223 
00224   if(diff > 0)
00225     createDep(deps, valLoad, val2Load, srcBeforeDest, diff);
00226 
00227   //assert(diff > 0 && "Expected diff to be greater then 0");
00228 }
00229 
00230 // Create dependences once its determined these two instructions
00231 // references the same memory
00232 void DependenceAnalyzer::createDep(std::vector<Dependence> &deps,
00233                                    bool valLoad, bool val2Load,
00234                                    bool srcBeforeDest, int diff) {
00235 
00236   //If the source instruction occurs after the destination instruction
00237   //(execution order), then this dependence is across iterations
00238   if(!srcBeforeDest && (diff==0))
00239     diff = 1;
00240 
00241   //If load/store pair
00242   if(valLoad && !val2Load) {
00243     if(srcBeforeDest)
00244       //Anti Dep
00245       deps.push_back(Dependence(diff, Dependence::AntiDep));
00246     else
00247       deps.push_back(Dependence(diff, Dependence::TrueDep));
00248 
00249     ++NumDeps;
00250   }
00251   //If store/load pair
00252   else if(!valLoad && val2Load) {
00253     if(srcBeforeDest)
00254       //True Dep
00255       deps.push_back(Dependence(diff, Dependence::TrueDep));
00256     else
00257       deps.push_back(Dependence(diff, Dependence::AntiDep));
00258     ++NumDeps;
00259   }
00260   //If store/store pair
00261   else if(!valLoad && !val2Load) {
00262     //True Dep
00263     deps.push_back(Dependence(diff, Dependence::OutputDep));
00264     ++NumDeps;
00265   }
00266 }
00267 
00268 
00269 
00270 //Get Dependence Info for a pair of Instructions
00271 DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1,
00272                                                        Instruction *inst2,
00273                                                        bool srcBeforeDest) {
00274   std::vector<Dependence> deps;
00275 
00276   DEBUG(std::cerr << "Inst1: " << *inst1 << "\n");
00277   DEBUG(std::cerr << "Inst2: " << *inst2 << "\n");
00278 
00279   //No self deps
00280   if(inst1 == inst2)
00281     return DependenceResult(deps);
00282 
00283   if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) {
00284 
00285     if(StoreInst *stInst = dyn_cast<StoreInst>(inst2))
00286       AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1),
00287                   true, false, deps, ldInst->getParent(), srcBeforeDest);
00288   }
00289   else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) {
00290 
00291     if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2))
00292       AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true,
00293                   deps, ldInst->getParent(), srcBeforeDest);
00294 
00295     else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2))
00296       AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false,
00297                   deps, stInst->getParent(), srcBeforeDest);
00298   }
00299   else
00300     assert(0 && "Expected a load or a store\n");
00301 
00302   DependenceResult dr = DependenceResult(deps);
00303   return dr;
00304 }
00305