Updated dependence analyzer. Fixed numerous bugs. Same stage scheduling, etc.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21444 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 259 insertions, 72 deletions

diff --git a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
index b99ecdfe49..0fd7c604ed 100644
--- a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
+++ b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
@@ -1,4 +1,4 @@
-//===-- DependenceAnalyzer.cpp - DependenceAnalyzer  ----------------*- C++ -*-===//
+//===-- DependenceAnalyzer.cpp - DependenceAnalyzer  ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -16,94 +16,281 @@
 #include "DependenceAnalyzer.h"
 #include "llvm/Type.h"
 #include "llvm/Support/Debug.h"
-using namespace llvm;
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Constants.h"
 
+using namespace llvm;
 
-/// Create ModuloSchedulingPass
-///
 namespace llvm {
-FunctionPass *createDependenceAnalyzer() {
-  return new DependenceAnalyzer();
+
+  /// Create ModuloSchedulingPass
+  FunctionPass *createDependenceAnalyzer() {
+    return new DependenceAnalyzer(); 
+  }
 }
+
+Statistic<> NoDeps("depanalyzer-nodeps", "Number of dependences eliminated");
+Statistic<> NumDeps("depanalyzer-deps", 
+		    "Number of dependences could not eliminate");
+Statistic<> AdvDeps("depanalyzer-advdeps", 
+		    "Number of dependences using advanced techniques");
+
+bool DependenceAnalyzer::runOnFunction(Function &F) {
+  AA = &getAnalysis<AliasAnalysis>();
+  TD = &getAnalysis<TargetData>();
+  SE = &getAnalysis<ScalarEvolution>();
+
+  return  false;
 }
 
-  bool DependenceAnalyzer::runOnFunction(Function &F) {
-    AA = &getAnalysis<AliasAnalysis>();
-    TD = &getAnalysis<TargetData>();
+static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer", 
+					     "Dependence Analyzer");
+ 
+//  - Get inter and intra dependences between loads and stores
+//
+// Overview of Method: 
+// Step 1: Use alias analysis to determine dependencies if values are loop 
+//       invariant 
+// Step 2: If pointers are not GEP, then there is a dependence.  
+// Step 3: Compare GEP base pointers with AA. If no alias, no dependence. 
+//         If may alias, then add a dependence. If must alias, then analyze 
+//         further (Step 4) 
+// Step 4: do advanced analysis
+void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, 
+				     bool val2Load, 
+				     std::vector<Dependence> &deps, 
+				     BasicBlock *BB, 
+				     bool srcBeforeDest) {
+    
+  bool loopInvariant = true;
 
-    return  false;
+  //Check if both are instructions and prove not loop invariant if possible
+  if(Instruction *valInst = dyn_cast<Instruction>(val))
+    if(valInst->getParent() == BB)
+      loopInvariant = false;
+  if(Instruction *val2Inst = dyn_cast<Instruction>(val2))
+    if(val2Inst->getParent() == BB)
+      loopInvariant = false;
+   
+    
+  //If Loop invariant, let AA decide
+  if(loopInvariant) {
+    if(AA->alias(val, (unsigned)TD->getTypeSize(val->getType()),
+		 val2,(unsigned)TD->getTypeSize(val2->getType()))
+       != AliasAnalysis::NoAlias) {
+      createDep(deps, valLoad, val2Load, srcBeforeDest);
+    }
+    else
+      ++NoDeps;
+    return;
   }
+    
+  //Otherwise, continue with step 2
 
-  static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer", "Dependence Analyzer");
+  GetElementPtrInst *GP = dyn_cast<GetElementPtrInst>(val);
+  GetElementPtrInst *GP2 = dyn_cast<GetElementPtrInst>(val2);
 
-  DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, Instruction *inst2) {
-    std::vector<Dependence> deps;
+  //If both are not GP instructions, we can not do further analysis
+  if(!GP || !GP2) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
 
-    DEBUG(std::cerr << "Inst1: " << *inst1 << "\n");
-    DEBUG(std::cerr << "Inst2: " << *inst2 << "\n");
 
+  //Otherwise, compare GEP bases (op #0) with Alias Analysis
 
-    if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) {
+  Value *GPop = GP->getOperand(0);
+  Value *GP2op = GP2->getOperand(0);
+  int alias = AA->alias(GPop, (unsigned)TD->getTypeSize(GPop->getType()),
+			GP2op,(unsigned)TD->getTypeSize(GP2op->getType()));
 
-      if(StoreInst *stInst = dyn_cast<StoreInst>(inst2)) {
-	//Get load mem ref
-	Value *ldOp = ldInst->getOperand(0);
-	
-	//Get store mem ref
-	Value *stOp = stInst->getOperand(1);
-	
-	if(AA->alias(ldOp, (unsigned)TD->getTypeSize(ldOp->getType()),
-		     stOp,(unsigned)TD->getTypeSize(stOp->getType()))
-	   != AliasAnalysis::NoAlias) {
-	
-	  //Anti Dep
-	  deps.push_back(Dependence(0, Dependence::AntiDep));
-	}
-      }
-    }
 
-    else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) {
-
-      if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2)) {
-	//Get load mem ref
-	Value *ldOp = ldInst->getOperand(0);
-	
-	//Get store mem ref
-	Value *stOp = stInst->getOperand(1);
-	
-	
-	if(AA->alias(ldOp, (unsigned)TD->getTypeSize(ldOp->getType()),
-		     stOp,(unsigned)TD->getTypeSize(stOp->getType()))
-	   != AliasAnalysis::NoAlias) {
-	
-	  //Anti Dep
-	  deps.push_back(Dependence(0, Dependence::TrueDep));
-	}
-      }
-      else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2)) {
-
-	//Get load mem ref
-	Value *stOp1 = stInst->getOperand(1);
-	
-	//Get store mem ref
-	Value *stOp2 = stInst2->getOperand(1);
-
-
-	if(AA->alias(stOp1, (unsigned)TD->getTypeSize(stOp1->getType()),
-		     stOp2,(unsigned)TD->getTypeSize(stOp2->getType()))
-	   != AliasAnalysis::NoAlias) {
-	
-	  //Anti Dep
-	  deps.push_back(Dependence(0, Dependence::OutputDep));
-	}
-      }
+  if(alias == AliasAnalysis::MustAlias) {
+    //Further dep analysis to do
+    advancedDepAnalysis(GP, GP2, valLoad, val2Load, deps, srcBeforeDest);
+    ++AdvDeps;
+  }
+  else if(alias == AliasAnalysis::MayAlias) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+  }
+  //Otherwise no dependence since there is no alias
+  else
+    ++NoDeps;
+}
+
 
+// advancedDepAnalysis - Do advanced data dependence tests
+void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, 
+					     GetElementPtrInst *gp2,
+					     bool valLoad,
+					     bool val2Load,
+					     std::vector<Dependence> &deps,
+					     bool srcBeforeDest) {
 
-    }
-    else
-      assert("Expected a load or a store\n");
+  //Check if both GEPs are in a simple form: 3 ops, constant 0 as second arg
+  if(gp1->getNumOperands() != 3 || gp2->getNumOperands() != 3) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
+
+  //Check second arg is constant 0
+  bool GPok = false;
+  if(Constant *c1 = dyn_cast<Constant>(gp1->getOperand(1)))
+    if(Constant *c2 = dyn_cast<Constant>(gp2->getOperand(1)))
+      if(c1->isNullValue() && c2->isNullValue())
+	GPok = true;
+  
+  if(!GPok) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+
+  }
+
+  Value *Gep1Idx = gp1->getOperand(2);
+  Value *Gep2Idx = gp2->getOperand(2);
+
+  if(CastInst *c1 = dyn_cast<CastInst>(Gep1Idx))
+    Gep1Idx = c1->getOperand(0);
+  if(CastInst *c2 = dyn_cast<CastInst>(Gep2Idx))
+    Gep2Idx = c2->getOperand(0);
+  
+  //Get SCEV for each index into the area
+  SCEVHandle SV1 = SE->getSCEV(Gep1Idx);
+  SCEVHandle SV2 = SE->getSCEV(Gep2Idx);
+
+  //Now handle special cases of dependence analysis
+  SV1->print(std::cerr);
+  std::cerr << "\n";
+  SV2->print(std::cerr);
+  std::cerr << "\n";
+
+  //Check if we have an SCEVAddExpr, cause we can only handle those
+  SCEVAddRecExpr *SVAdd1 = dyn_cast<SCEVAddRecExpr>(SV1);
+  SCEVAddRecExpr *SVAdd2 = dyn_cast<SCEVAddRecExpr>(SV2);
+
+  //Default to having a dependence since we can't analyze further
+  if(!SVAdd1 || !SVAdd2) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
 
-    DependenceResult dr = DependenceResult(deps);
-    return dr;
+  //Check if not Affine, we can't handle those
+  if(!SVAdd1->isAffine( ) || !SVAdd2->isAffine()) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
   }
 
+  //We know the SCEV is in the form A + B*x, check that B is the same for both
+  SCEVConstant *B1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(1));
+  SCEVConstant *B2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(1));
+
+  if(B1->getValue() != B2->getValue()) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
+  
+  if(B1->getValue()->getRawValue() != 1 || B2->getValue()->getRawValue() != 1) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
+
+
+  SCEVConstant *A1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(0));
+  SCEVConstant *A2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(0));
+
+  //Come back and deal with nested SCEV!
+  if(!A1 || !A2) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
+
+  //If equal, create dep as normal
+  if(A1->getValue() == A2->getValue()) {
+    createDep(deps, valLoad, val2Load, srcBeforeDest);
+    return;
+  }
+  //Eliminate a dep if this is a intra dep
+  else if(srcBeforeDest) {
+    ++NoDeps;
+    return;
+  }
+  
+  //Find constant index difference
+  int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue();
+  std::cerr << diff << "\n";
+  
+  if(diff > 0)
+    createDep(deps, valLoad, val2Load, srcBeforeDest, diff);
+  
+  //assert(diff > 0 && "Expected diff to be greater then 0");
+}
+
+// Create dependences once its determined these two instructions
+// references the same memory
+void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, 
+				   bool valLoad, bool val2Load, 
+				   bool srcBeforeDest, int diff) {
+
+  //If the source instruction occurs after the destination instruction
+  //(execution order), then this dependence is across iterations
+  if(!srcBeforeDest && (diff==0))
+    diff = 1;
+
+  //If load/store pair
+  if(valLoad && !val2Load) {
+    //Anti Dep
+    deps.push_back(Dependence(diff, Dependence::AntiDep));
+    ++NumDeps;
+  }
+  //If store/load pair
+  else if(!valLoad && val2Load) {
+    //True Dep
+    deps.push_back(Dependence(diff, Dependence::TrueDep));
+    ++NumDeps;
+  }
+  //If store/store pair
+  else if(!valLoad && !val2Load) {
+    //True Dep
+    deps.push_back(Dependence(diff, Dependence::OutputDep));
+    ++NumDeps;
+  }
+}
+
+
+  
+//Get Dependence Info for a pair of Instructions
+DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, 
+						       Instruction *inst2, 
+						       bool srcBeforeDest) {
+  std::vector<Dependence> deps;
+
+  DEBUG(std::cerr << "Inst1: " << *inst1 << "\n");
+  DEBUG(std::cerr << "Inst2: " << *inst2 << "\n");
+
+  //No self deps
+  if(inst1 == inst2)
+    return DependenceResult(deps);
+
+  if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) {
+      
+    if(StoreInst *stInst = dyn_cast<StoreInst>(inst2))
+      AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1), 
+		  true, false, deps, ldInst->getParent(), srcBeforeDest);
+  }
+  else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) {
+      
+    if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2))
+      AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true, 
+		  deps, ldInst->getParent(), srcBeforeDest);
+      
+    else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2))
+      AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false, 
+		  deps, stInst->getParent(), srcBeforeDest);
+  }
+  else
+    assert(0 && "Expected a load or a store\n");
+    
+  DependenceResult dr = DependenceResult(deps);
+  return dr;
+}
+