lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp

   1 //===-- DependenceAnalyzer.cpp - DependenceAnalyzer  ------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //
  11 //
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #define DEBUG_TYPE "ModuloSched"
  15
  16 #include "DependenceAnalyzer.h"
  17 #include "llvm/Type.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Constants.h"
  21
  22 using namespace llvm;
  23
  24 namespace llvm {
  25
  26   /// Create ModuloSchedulingPass
  27   FunctionPass *createDependenceAnalyzer() {
  28     return new DependenceAnalyzer();
  29   }
  30 }
  31
  32 Statistic<> NoDeps("depanalyzer-nodeps", "Number of dependences eliminated");
  33 Statistic<> NumDeps("depanalyzer-deps",
  34                     "Number of dependences could not eliminate");
  35 Statistic<> AdvDeps("depanalyzer-advdeps",
  36                     "Number of dependences using advanced techniques");
  37
  38 bool DependenceAnalyzer::runOnFunction(Function &F) {
  39   AA = &getAnalysis<AliasAnalysis>();
  40   TD = &getAnalysis<TargetData>();
  41   SE = &getAnalysis<ScalarEvolution>();
  42
  43   return  false;
  44 }
  45
  46 static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer",
  47                                              "Dependence Analyzer");
  48
  49 //  - Get inter and intra dependences between loads and stores
  50 //
  51 // Overview of Method:
  52 // Step 1: Use alias analysis to determine dependencies if values are loop
  53 //       invariant
  54 // Step 2: If pointers are not GEP, then there is a dependence.
  55 // Step 3: Compare GEP base pointers with AA. If no alias, no dependence.
  56 //         If may alias, then add a dependence. If must alias, then analyze
  57 //         further (Step 4)
  58 // Step 4: do advanced analysis
  59 void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad,
  60                                      bool val2Load,
  61                                      std::vector<Dependence> &deps,
  62                                      BasicBlock *BB,
  63                                      bool srcBeforeDest) {
  64
  65   bool loopInvariant = true;
  66
  67   //Check if both are instructions and prove not loop invariant if possible
  68   if(Instruction *valInst = dyn_cast<Instruction>(val))
  69     if(valInst->getParent() == BB)
  70       loopInvariant = false;
  71   if(Instruction *val2Inst = dyn_cast<Instruction>(val2))
  72     if(val2Inst->getParent() == BB)
  73       loopInvariant = false;
  74
  75
  76   //If Loop invariant, let AA decide
  77   if(loopInvariant) {
  78     if(AA->alias(val, (unsigned)TD->getTypeSize(val->getType()),
  79                  val2,(unsigned)TD->getTypeSize(val2->getType()))
  80        != AliasAnalysis::NoAlias) {
  81       createDep(deps, valLoad, val2Load, srcBeforeDest);
  82     }
  83     else
  84       ++NoDeps;
  85     return;
  86   }
  87
  88   //Otherwise, continue with step 2
  89
  90   GetElementPtrInst *GP = dyn_cast<GetElementPtrInst>(val);
  91   GetElementPtrInst *GP2 = dyn_cast<GetElementPtrInst>(val2);
  92
  93   //If both are not GP instructions, we can not do further analysis
  94   if(!GP || !GP2) {
  95     createDep(deps, valLoad, val2Load, srcBeforeDest);
  96     return;
  97   }
  98
  99
 100   //Otherwise, compare GEP bases (op #0) with Alias Analysis
 101
 102   Value *GPop = GP->getOperand(0);
 103   Value *GP2op = GP2->getOperand(0);
 104   int alias = AA->alias(GPop, (unsigned)TD->getTypeSize(GPop->getType()),
 105                         GP2op,(unsigned)TD->getTypeSize(GP2op->getType()));
 106
 107
 108   if(alias == AliasAnalysis::MustAlias) {
 109     //Further dep analysis to do
 110     advancedDepAnalysis(GP, GP2, valLoad, val2Load, deps, srcBeforeDest);
 111     ++AdvDeps;
 112   }
 113   else if(alias == AliasAnalysis::MayAlias) {
 114     createDep(deps, valLoad, val2Load, srcBeforeDest);
 115   }
 116   //Otherwise no dependence since there is no alias
 117   else
 118     ++NoDeps;
 119 }
 120
 121
 122 // advancedDepAnalysis - Do advanced data dependence tests
 123 void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1,
 124                                              GetElementPtrInst *gp2,
 125                                              bool valLoad,
 126                                              bool val2Load,
 127                                              std::vector<Dependence> &deps,
 128                                              bool srcBeforeDest) {
 129
 130   //Check if both GEPs are in a simple form: 3 ops, constant 0 as second arg
 131   if(gp1->getNumOperands() != 3 || gp2->getNumOperands() != 3) {
 132     createDep(deps, valLoad, val2Load, srcBeforeDest);
 133     return;
 134   }
 135
 136   //Check second arg is constant 0
 137   bool GPok = false;
 138   if(Constant *c1 = dyn_cast<Constant>(gp1->getOperand(1)))
 139     if(Constant *c2 = dyn_cast<Constant>(gp2->getOperand(1)))
 140       if(c1->isNullValue() && c2->isNullValue())
 141         GPok = true;
 142
 143   if(!GPok) {
 144     createDep(deps, valLoad, val2Load, srcBeforeDest);
 145     return;
 146
 147   }
 148
 149   Value *Gep1Idx = gp1->getOperand(2);
 150   Value *Gep2Idx = gp2->getOperand(2);
 151
 152   if(CastInst *c1 = dyn_cast<CastInst>(Gep1Idx))
 153     Gep1Idx = c1->getOperand(0);
 154   if(CastInst *c2 = dyn_cast<CastInst>(Gep2Idx))
 155     Gep2Idx = c2->getOperand(0);
 156
 157   //Get SCEV for each index into the area
 158   SCEVHandle SV1 = SE->getSCEV(Gep1Idx);
 159   SCEVHandle SV2 = SE->getSCEV(Gep2Idx);
 160
 161   //Now handle special cases of dependence analysis
 162   //SV1->print(std::cerr);
 163   //std::cerr << "\n";
 164   //SV2->print(std::cerr);
 165   //std::cerr << "\n";
 166
 167   //Check if we have an SCEVAddExpr, cause we can only handle those
 168   SCEVAddRecExpr *SVAdd1 = dyn_cast<SCEVAddRecExpr>(SV1);
 169   SCEVAddRecExpr *SVAdd2 = dyn_cast<SCEVAddRecExpr>(SV2);
 170
 171   //Default to having a dependence since we can't analyze further
 172   if(!SVAdd1 || !SVAdd2) {
 173     createDep(deps, valLoad, val2Load, srcBeforeDest);
 174     return;
 175   }
 176
 177   //Check if not Affine, we can't handle those
 178   if(!SVAdd1->isAffine( ) || !SVAdd2->isAffine()) {
 179     createDep(deps, valLoad, val2Load, srcBeforeDest);
 180     return;
 181   }
 182
 183   //We know the SCEV is in the form A + B*x, check that B is the same for both
 184   SCEVConstant *B1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(1));
 185   SCEVConstant *B2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(1));
 186
 187   if(B1->getValue() != B2->getValue()) {
 188     createDep(deps, valLoad, val2Load, srcBeforeDest);
 189     return;
 190   }
 191
 192   if(B1->getValue()->getRawValue() != 1 || B2->getValue()->getRawValue() != 1) {
 193     createDep(deps, valLoad, val2Load, srcBeforeDest);
 194     return;
 195   }
 196
 197
 198   SCEVConstant *A1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(0));
 199   SCEVConstant *A2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(0));
 200
 201   //Come back and deal with nested SCEV!
 202   if(!A1 || !A2) {
 203     createDep(deps, valLoad, val2Load, srcBeforeDest);
 204     return;
 205   }
 206
 207   //If equal, create dep as normal
 208   if(A1->getValue() == A2->getValue()) {
 209     createDep(deps, valLoad, val2Load, srcBeforeDest);
 210     return;
 211   }
 212   //Eliminate a dep if this is a intra dep
 213   else if(srcBeforeDest) {
 214     ++NoDeps;
 215     return;
 216   }
 217
 218   //Find constant index difference
 219   int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue();
 220   //std::cerr << diff << "\n";
 221   if(diff > 5)
 222     diff = 2;
 223
 224   if(diff > 0)
 225     createDep(deps, valLoad, val2Load, srcBeforeDest, diff);
 226
 227   //assert(diff > 0 && "Expected diff to be greater then 0");
 228 }
 229
 230 // Create dependences once its determined these two instructions
 231 // references the same memory
 232 void DependenceAnalyzer::createDep(std::vector<Dependence> &deps,
 233                                    bool valLoad, bool val2Load,
 234                                    bool srcBeforeDest, int diff) {
 235
 236   //If the source instruction occurs after the destination instruction
 237   //(execution order), then this dependence is across iterations
 238   if(!srcBeforeDest && (diff==0))
 239     diff = 1;
 240
 241   //If load/store pair
 242   if(valLoad && !val2Load) {
 243     if(srcBeforeDest)
 244       //Anti Dep
 245       deps.push_back(Dependence(diff, Dependence::AntiDep));
 246     else
 247       deps.push_back(Dependence(diff, Dependence::TrueDep));
 248
 249     ++NumDeps;
 250   }
 251   //If store/load pair
 252   else if(!valLoad && val2Load) {
 253     if(srcBeforeDest)
 254       //True Dep
 255       deps.push_back(Dependence(diff, Dependence::TrueDep));
 256     else
 257       deps.push_back(Dependence(diff, Dependence::AntiDep));
 258     ++NumDeps;
 259   }
 260   //If store/store pair
 261   else if(!valLoad && !val2Load) {
 262     //True Dep
 263     deps.push_back(Dependence(diff, Dependence::OutputDep));
 264     ++NumDeps;
 265   }
 266 }
 267
 268
 269
 270 //Get Dependence Info for a pair of Instructions
 271 DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1,
 272                                                        Instruction *inst2,
 273                                                        bool srcBeforeDest) {
 274   std::vector<Dependence> deps;
 275
 276   DEBUG(std::cerr << "Inst1: " << *inst1 << "\n");
 277   DEBUG(std::cerr << "Inst2: " << *inst2 << "\n");
 278
 279   //No self deps
 280   if(inst1 == inst2)
 281     return DependenceResult(deps);
 282
 283   if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) {
 284
 285     if(StoreInst *stInst = dyn_cast<StoreInst>(inst2))
 286       AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1),
 287                   true, false, deps, ldInst->getParent(), srcBeforeDest);
 288   }
 289   else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) {
 290
 291     if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2))
 292       AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true,
 293                   deps, ldInst->getParent(), srcBeforeDest);
 294
 295     else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2))
 296       AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false,
 297                   deps, stInst->getParent(), srcBeforeDest);
 298   }
 299   else
 300     assert(0 && "Expected a load or a store\n");
 301
 302   DependenceResult dr = DependenceResult(deps);
 303   return dr;
 304 }
 305