LLVM API Documentation
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