[Polly] Model PHI nodes without demoting them

[jdoerfert]

Summary

This allows us to model PHI nodes in the polyhedral description
without demoting them. The modeling however will result in the
same accesses as the demotion would have introduced.

[grosser]

Hi Johannes,

the patch looks good in general. As you mentioned earlier, the test coverage is still a little low. I would be interested in a loop with a non-IV PHI node, as well as two tests where the values in the PHis are instructions, once executed in the incoming basic blocks and once in a block that is post-dominated by the relevant incoming block. What do you think?

Cheers,
Tobias

lib/Analysis/ScopDetection.cpp

155

without

lib/Analysis/TempScopInfo.cpp

102

Maybe a comment on how we handle PHI accesses, where loads/stores are created.

111

Can this ever happen? If it can, maybe this is worth a test case, otherwise maybe make this an assert?

229

No need for braces?

[jdoerfert]

I don't know what test you exactly want. I added some and also fixed an
inconsistency I encountered along the way. If you want a specific test please
give me some C snippet or a at least a more precise description.

include/polly/ScopDetection.h

 };
 
 typedef std::map<const Instruction *, MemAcc *> MapInsnToMemAcc;
 typedef std::pair<const Instruction *, const SCEV *> PairInstSCEV;
 typedef std::vector<PairInstSCEV> AFs;
 typedef std::map<const SCEVUnknown *, AFs> BaseToAFs;
 typedef std::map<const SCEVUnknown *, const SCEV *> BaseToElSize;
 
+extern bool PollyModelPHINodes;
 extern bool PollyTrackFailures;
 extern bool PollyDelinearize;
 extern bool PollyUseRuntimeAliasChecks;
 
 /// @brief A function attribute which will cause Polly to skip the function
 extern llvm::StringRef PollySkipFnAttr;
 
 //===----------------------------------------------------------------------===//

include/polly/TempScopInfo.h

class TempScopInfo : public FunctionPass {
   ///
   /// @param Inst The instruction to be analyzed
   /// @param R    The SCoP region
   ///
   /// @return     True if the Instruction is used in other BB and a scalar write
   ///             Access is required.
   bool buildScalarDependences(Instruction *Inst, Region *R);
 
+  /// @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);
+
   void buildAccessFunctions(Region &RefRegion, BasicBlock &BB);
 
 public:
   static char ID;
   explicit TempScopInfo() : FunctionPass(ID) {}
   ~TempScopInfo();
 
   /// @brief Get the temporay Scop information in LLVM IR represent

lib/Analysis/ScopDetection.cpp

PollyDelinearizeX("polly-delinearize",
                       cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     VerifyScops("polly-detect-verify",
                 cl::desc("Verify the detected SCoPs after each transformation"),
                 cl::Hidden, cl::init(false), cl::ZeroOrMore,
                 cl::cat(PollyCategory));
 
+static cl::opt<bool, true> XPollyModelPHINodes(
+    "polly-model-phi-nodes",
+    cl::desc(
+        "Allow PHI nodes in the input [Unsafe with any code-generation!]."),
+    cl::location(PollyModelPHINodes), cl::Hidden, cl::ZeroOrMore,
+    cl::init(false), cl::cat(PollyCategory));
+
+bool polly::PollyModelPHINodes = false;
 bool polly::PollyTrackFailures = false;
 bool polly::PollyDelinearize = false;
 StringRef polly::PollySkipFnAttr = "polly.skip.fn";
 
 //===----------------------------------------------------------------------===//
 // Statistics.
 
 STATISTIC(ValidRegion, "Number of regions that a valid part of Scop");
bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   }
 
   return true;
 }
 
 bool ScopDetection::isValidInstruction(Instruction &Inst,
                                        DetectionContext &Context) const {
   if (PHINode *PN = dyn_cast<PHINode>(&Inst))
-    if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) {
+    if (!PollyModelPHINodes && !canSynthesize(PN, LI, SE, &Context.CurRegion)) {
       return invalid<ReportPhiNodeRefInRegion>(Context, /*Assert=*/true, &Inst);
     }
 
   // We only check the call instruction but not invoke instruction.
   if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
     if (isValidCallInst(*CI))
       return true;
 

lib/Analysis/ScopInfo.cpp

case READ:
     break;
   case MUST_WRITE:
     OS.indent(12) << "MustWriteAccess :=\t";
     break;
   case MAY_WRITE:
     OS.indent(12) << "MayWriteAccess :=\t";
     break;
   }
-  OS << "[Reduction Type: " << getReductionType() << "]\n";
+  OS << "[Reduction Type: " << getReductionType() << "] ";
+  OS << "[Scalar: " << isScalar() << "]\n";
   OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
 }
 
 void MemoryAccess::dump() const { print(errs()); }
 
 // Create a map in the size of the provided set domain, that maps from the
 // one element of the provided set domain to another element of the provided
 // set domain.

lib/Analysis/TempScopInfo.cpp

for (const auto &CurBlock : CurR->blocks()) {
     const AccFuncSetType &AccFuncs = AccSetIt->second;
 
     for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
          ++AI)
       AI->first.print(OS.indent(ind + 2));
   }
 }
 
+void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
+                                    AccFuncSetType &Functions) {
+  if (canSynthesize(PHI, LI, SE, &R))
+    return;
+
+  for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
+    Value *Op = PHI->getIncomingValue(u);
+    BasicBlock *OpBB = PHI->getIncomingBlock(u);
+
+    if (!R.contains(OpBB))
+      continue;
+
+    Instruction *OpI = dyn_cast<Instruction>(Op);
+    if (!OpI)
+      OpI = PHI;
+
+    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) {
   // 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 false;
   if (isIgnoredIntrinsic(Inst))
     return false;
 
for (User *U : Inst->users()) {
     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(UI, LI, SE, R))
       continue;
 
+    // Skip PHI nodes as they handle their operands on their own.
+    if (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))
       continue;
 
-    assert(!isa<PHINode>(UI) && "Non synthesizable PHINode found in a SCoP!");
-
     // 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));
   }
 
   return AnyCrossStmtUse;
 }
void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) {
   AccFuncSetType Functions;
   Loop *L = LI->getLoopFor(&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 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));
     }
   }
 

lib/Transform/CodePreparation.cpp

 // referencing loop counters.
 //
 // XXX: In the future, we should remove the need for this pass entirely and
 // instead add support for scalar dependences to ScopInfo and code generation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/LinkAllPasses.h"
+#include "polly/ScopDetection.h"
 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Transforms/Utils/Local.h"
 
void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
 
   AU.addPreserved<LoopInfoWrapperPass>();
   AU.addPreserved<RegionInfoPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<DominanceFrontier>();
 }
 
 bool CodePreparation::runOnFunction(Function &F) {
+  if (PollyModelPHINodes)
+    return false;
+
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   SE = &getAnalysis<ScalarEvolution>();
 
   splitEntryBlockForAlloca(&F.getEntryBlock(), this);
 
   eliminatePHINodes(F);
 
   return false;

lib/Transform/IndependentBlocks.cpp

bool IndependentBlocks::createIndependentBlocks(BasicBlock *BB,
   for (Instruction &Inst : *BB)
     if (!isSafeToMove(&Inst) && !canSynthesize(&Inst, LI, SE, R))
       WorkList.push_back(&Inst);
 
   ReplacedMapType ReplacedMap;
   Instruction *InsertPos = BB->getFirstNonPHIOrDbg();
 
   for (Instruction *Inst : WorkList)
+    if (!isa<PHINode>(Inst))
       moveOperandTree(Inst, R, ReplacedMap, InsertPos);
 
   // The BB was changed if we replaced any operand.
   return !ReplacedMap.empty();
 }
 
 bool IndependentBlocks::createIndependentBlocks(const Region *R) {
   bool Changed = false;
 

test/ScopInfo/phi_condition_modeling.ll

+; RUN: opt %loadPolly -analyze -polly-scops -polly-model-phi-nodes < %s | FileCheck %s
+;
+;    void f(int *A, int c, int N) {
+;      int tmp;
+;      for (int i = 0; i < N; i++) {
+;        if (i > c)
+;          tmp = 3;
+;        else
+;          tmp = 5;
+;        A[i] = tmp;
+;      }
+;    }
+;
+; CHECK:    Statements {
+; CHECK:      Stmt_bb6
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0[] };
+; CHECK:      Stmt_bb7
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0[] };
+; CHECK:      Stmt_bb8
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_A[i0] };
+; CHECK:    }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %c, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  %tmp1 = sext i32 %c to i64
+  br label %bb2
+
+bb2:                                              ; preds = %bb10, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp3, label %bb4, label %bb11
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = icmp sgt i64 %indvars.iv, %tmp1
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:                                              ; preds = %bb4
+  br label %bb8
+
+bb7:                                              ; preds = %bb4
+  br label %bb8
+
+bb8:                                              ; preds = %bb7, %bb6
+  %tmp.0 = phi i32 [ 3, %bb6 ], [ 5, %bb7 ]
+  %tmp9 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp.0, i32* %tmp9, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb2
+
+bb11:                                             ; preds = %bb2
+  ret void
+}

test/ScopInfo/phi_condition_modeling_2.ll

+; RUN: opt %loadPolly -analyze -polly-scops -disable-polly-intra-scop-scalar-to-array -polly-model-phi-nodes < %s | FileCheck %s
+;
+;    void f(int *A, int c, int N) {
+;      int tmp;
+;      for (int i = 0; i < N; i++) {
+;        if (i > c)
+;          tmp = 3;
+;        else
+;          tmp = 5;
+;        A[i] = tmp;
+;      }
+;    }
+;
+; CHECK:    Statements {
+; CHECK:      Stmt_bb6
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0[] };
+; CHECK:      Stmt_bb7
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0[] };
+; CHECK:      Stmt_bb8
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };
+; CHECK:      Stmt_bb8b
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_A[i0] };
+; CHECK:    }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %c, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  %tmp1 = sext i32 %c to i64
+  br label %bb2
+
+bb2:                                              ; preds = %bb10, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb10 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp3, label %bb4, label %bb11
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = icmp sgt i64 %indvars.iv, %tmp1
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:                                              ; preds = %bb4
+  br label %bb8
+
+bb7:                                              ; preds = %bb4
+  br label %bb8
+
+bb8:                                              ; preds = %bb7, %bb6
+  %tmp.0 = phi i32 [ 3, %bb6 ], [ 5, %bb7 ]
+  br label %bb8b
+
+bb8b:
+  %tmp9 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp.0, i32* %tmp9, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb2
+
+bb11:                                             ; preds = %bb2
+  ret void
+}

test/ScopInfo/phi_conditional_simple_1.ll

+; RUN: opt %loadPolly -analyze -polly-scops -polly-model-phi-nodes < %s | FileCheck %s
+;
+;    void jd(int *A, int c) {
+;      for (int i = 0; i < 1024; i++) {
+;        if (c)
+;          A[i] = 1;
+;        else
+;          A[i] = 2;
+;      }
+;    }
+;
+; CHECK:    Statements {
+; CHECK:      Stmt_if_else
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [c] -> { Stmt_if_else[i0] -> MemRef_phi[] };
+; CHECK:      Stmt_if_then
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [c] -> { Stmt_if_then[i0] -> MemRef_phi[] };
+; CHECK:      Stmt_if_end
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [c] -> { Stmt_if_end[i0] -> MemRef_phi[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [c] -> { Stmt_if_end[i0] -> MemRef_A[i0] };
+; CHECK:    }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tobool = icmp eq i32 %c, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %for.body
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %phi = phi i32 [ 1, %if.then], [ 2, %if.else ]
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %phi, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}