TempScopInfo: Add code to build the scalar dependences.

llvm-svn: 183653

2 files changed, 76 insertions, 5 deletions

diff --git a/polly/include/polly/TempScopInfo.h b/polly/include/polly/TempScopInfo.h
index 1e9ce4773ce..51c543c8096 100755
--- a/polly/include/polly/TempScopInfo.h
+++ b/polly/include/polly/TempScopInfo.h
@@ -39,8 +39,11 @@ public:
 
   // The type of the scev affine function
   enum TypeKind {
-    READ,
-    WRITE
+    READ = 0x1,
+    WRITE = 0x2,
+    SCALAR = 0x4,
+    SCALARREAD = SCALAR | READ,
+    SCALARWRITE = SCALAR | WRITE
   };
 
 private:
@@ -64,9 +67,11 @@ public:
 
   bool isAffine() const { return IsAffine; }
 
-  bool isRead() const { return Type == READ; }
+  bool isRead() const { return Type & READ; }
 
-  bool isWrite() const { return Type == WRITE; }
+  bool isWrite() const { return Type & WRITE; }
+
+  bool isScalar() const { return Type & SCALAR; }
 };
 
 class Comparison {
@@ -237,9 +242,13 @@ class TempScopInfo : public FunctionPass {
   // And also Remember the constrains for BBs
   BBCondMapType BBConds;
 
-  // Access function of bbs.
+  // Access function of statements (currently BasicBlocks) .
   AccFuncMapType AccFuncMap;
 
+  // Pre-created zero for the scalar accesses, with it we do not need create a
+  // zero scev every time when we need it.
+  const SCEV *ZeroOffset;
+
   // Mapping regions to the corresponding Scop in current function.
   TempScopMapType TempScops;
 
@@ -274,6 +283,13 @@ class TempScopInfo : public FunctionPass {
   ///             instruction.
   IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R);
 
+  /// @brief Analyze and extract the cross-BB scalar dependences (or,
+  ///        dataflow dependencies) of an instruction.
+  ///
+  /// @param Inst The instruction to be analyzed
+  /// @param R    The SCoP region
+  void buildScalarDependences(Instruction *Inst, Region *R);
+
   void buildAccessFunctions(Region &RefRegion, BasicBlock &BB);
 
   void buildLoopBounds(TempScop &Scop);
diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp
index 78210a532f6..b475ab4555d 100644
--- a/polly/lib/Analysis/TempScopInfo.cpp
+++ b/polly/lib/Analysis/TempScopInfo.cpp
@@ -15,6 +15,7 @@
 
 #include "polly/TempScopInfo.h"
 #include "polly/LinkAllPasses.h"
+#include "polly/CodeGen/BlockGenerators.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
@@ -73,6 +74,57 @@ void TempScop::printDetail(llvm::raw_ostream &OS, ScalarEvolution *SE,
                            LoopInfo *LI, const Region *CurR,
                            unsigned ind) const {}
 
+void TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) {
+  // No need to translate these scalar dependences into polyhedral form, because
+  // synthesizable scalars can be generated by the code generator.
+  if (canSynthesize(Inst, LI, SE, R))
+    return;
+
+  bool AnyCrossStmtUse = false;
+  BasicBlock *ParentBB = Inst->getParent();
+
+  for (Instruction::use_iterator UI = Inst->use_begin(), UE = Inst->use_end();
+       UI != UE; ++UI) {
+    Instruction *U = dyn_cast<Instruction>(*UI);
+
+    // Ignore the strange user
+    if (U == 0)
+      continue;
+
+    BasicBlock *UseParent = U->getParent();
+
+    // Ignore the users in the same BB (statement)
+    if (UseParent == ParentBB)
+      continue;
+
+    // No need to translate these scalar dependences into polyhedral form,
+    // because synthesizable scalars can be generated by the code generator.
+    if (canSynthesize(U, LI, SE, R))
+      continue;
+
+    // Now U is used in another statement.
+    AnyCrossStmtUse = true;
+
+    // Do not build a read access that is not in the current SCoP
+    if (!R->contains(UseParent))
+      continue;
+
+    assert(!isa<PHINode>(U) && "Non synthesizable PHINode found in a SCoP!");
+
+    // Use the def instruction as base address of the IRAccess, so that it will
+    // become the the name of the scalar access in the polyhedral form.
+    IRAccess ScalarAccess(IRAccess::SCALARREAD, Inst, ZeroOffset, 1, true);
+    AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, U));
+  }
+
+  // If the Instruction is used outside the statement, we need to build the
+  // write access.
+  if (AnyCrossStmtUse) {
+    IRAccess ScalarAccess(IRAccess::SCALARWRITE, Inst, ZeroOffset, 1, true);
+    AccFuncMap[ParentBB].push_back(std::make_pair(ScalarAccess, Inst));
+  }
+}
+
 IRAccess TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R) {
   unsigned Size;
   enum IRAccess::TypeKind Type;
@@ -107,6 +159,8 @@ void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) {
     Instruction *Inst = I;
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst));
+
+    if (!isa<StoreInst>(Inst))  buildScalarDependences(Inst, &R);
   }
 
   if (Functions.empty())
@@ -260,6 +314,7 @@ bool TempScopInfo::runOnFunction(Function &F) {
   SD = &getAnalysis<ScopDetection>();
   AA = &getAnalysis<AliasAnalysis>();
   TD = &getAnalysis<DataLayout>();
+  ZeroOffset = SE->getConstant(TD->getIntPtrType(F.getContext()), 0);
 
   for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I) {
     Region *R = const_cast<Region *>(*I);