[Polly] Model scalar dependences to avoid trivial statements

[jdoerfert]

Summary

In case a statement might be trivial but contains a scalar dependence
to an instruction outside the SCoP we need to model this scalar
dependence even though the instruction or the user can be synthesized.

Added testcase modeled after ClamAV/clamscan.

[grosser]

Hi Johannes,

the patch looks good in general. Some minor comments.

Tobias

lib/Analysis/TempScopInfo.cpp

150

I don't really understand why scalar dependences to uses outside of the scop region only need to be modelled for otherwise trivial basic blocks. Should we not model them in general?

172

Would it make sense to make this an early return?

if (!R->contains(UseParent)) {
  AnyCrossStmtUse = true;
  continue;
}

177

Is this condition not implied by the condition below?

[jdoerfert]

lib/Analysis/TempScopInfo.cpp

150

Maybe,... I'll think about it.

[Later I wanted to model the write only for the last iteration of the domain if there is no other scalar dependence for that instruction]

172

Sure.

177

canSynthesizeInst is not equal to canSynthesize(UI,...), at least I don't have a good reason why it should be.

[grosser]

lib/Analysis/TempScopInfo.cpp

150

OK, I would be interested in the outcome of your thoughts. ;-)

[Why would you want to only model the last write? What would be the benefit?]

177

Right. That's fine than.

[jdoerfert]

I addressed your comments and commited it with a extended test case in r228847.

lib/Analysis/TempScopInfo.cpp

150

Your right, we need to model all accesses as we would allow reordering otherwise.

include/polly/TempScopInfo.h

class TempScopInfo : public FunctionPass {
   ///
   /// @return     The IRAccess to describe the access function of the
   ///             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
+  /// @param Inst      The instruction to be analyzed
+  /// @param R         The SCoP region
+  /// @param Functions The access functions of the current BB
   ///
   /// @return     True if the Instruction is used in other BB and a scalar write
   ///             Access is required.
-  bool buildScalarDependences(Instruction *Inst, Region *R);
+  bool buildScalarDependences(Instruction *Inst, Region *R,
+                              AccFuncSetType &Functions);
 
   /// @brief Create IRAccesses for the given PHI node in the given region.
   ///
   /// @param PHI       The PHI node to be handled
   /// @param R         The SCoP region
   /// @param Functions The access functions of the current BB
   void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions);
 

lib/Analysis/TempScopInfo.cpp

for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true);
     AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
   }
 
   IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true);
   Functions.push_back(std::make_pair(ScalarAccess, PHI));
 }
 
-bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R) {
+bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
+                                          AccFuncSetType &Functions) {
   // 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))
+  // synthesizable scalars can be generated by the code generator. However, only
+  // if the statement is non-trivial, hence there is at least one access in the
+  // statement.
+  bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
+  if (canSynthesizeInst && !Functions.empty())
     return false;
   if (isIgnoredIntrinsic(Inst))
     return false;
 
   bool AnyCrossStmtUse = false;
   BasicBlock *ParentBB = Inst->getParent();
 
   for (User *U : Inst->users()) {
     Instruction *UI = dyn_cast<Instruction>(U);
 
     // Ignore the strange user
     if (UI == 0)
       continue;
 
     BasicBlock *UseParent = UI->getParent();
 
     // Ignore the users in the same BB (statement)
     if (UseParent == ParentBB)
       continue;
 
+    // Check whether or not the use is in the SCoP.
+    bool inRegion = R->contains(UseParent);
+
+    // If the instruction can be synthesized and the user is in the region
+    // we do not need to add scalar dependences.
+    if (inRegion && canSynthesizeInst)
+      continue;
+
     // No need to translate these scalar dependences into polyhedral form,
     // because synthesizable scalars can be generated by the code generator.
-    if (canSynthesize(UI, LI, SE, R))
+    if (inRegion && canSynthesize(UI, LI, SE, R))
       continue;
 
-    // Skip PHI nodes as they handle their operands on their own.
-    if (isa<PHINode>(UI))
+    // Skip PHI nodes in the region as they handle their operands on their own.
+    if (inRegion && isa<PHINode>(UI))
       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))
+    if (!inRegion)
       continue;
 
     // Use the def instruction as base address of the IRAccess, so that it will
     // become the name of the scalar access in the polyhedral form.
     IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true);
     AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));
   }
 
void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) {
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst));
 
     if (PHINode *PHI = dyn_cast<PHINode>(Inst))
       buildPHIAccesses(PHI, R, Functions);
 
-    if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R)) {
+    if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R, Functions)) {
       // If the Instruction is used outside the statement, we need to build the
       // write access.
       IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true);
       Functions.push_back(std::make_pair(ScalarAccess, Inst));
     }
   }
 
   if (Functions.empty())

test/ScopInfo/escaping_empty_scop.ll

+; RUN: opt %loadPolly -polly-scops -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes -analyze < %s | FileCheck %s
+;
+;    void g();
+;    int f(int *A) {
+;      int a = 0;
+;      for (int i = 0; i < 1000; i++)
+;        a = 2 * i;
+;      g();
+;      return a;
+;    }
+;
+; CHECK:      Stmt_bb1
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb1[i0] -> MemRef_a_0[] };
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @f(i32* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb3, %bb
+  %i.0 = phi i32 [ 0, %bb ], [ %tmp4, %bb3 ]
+  %a.0 = mul i32 %i.0, 2
+  %exitcond = icmp ne i32 %i.0, 1000
+  br i1 %exitcond, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb2
+  %tmp = shl nsw i32 %i.0, 1
+  %tmp4 = add nuw nsw i32 %i.0, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  call void (...)* @g() #2
+  ret i32 %a.0
+}
+
+declare void @g(...) #1