[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?

247

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 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;
+
+  // PHI nodes are modeled as if they had been demoted prior to the SCoP
+  // detection. Hence, the PHI is a load of a new memory location in which the
+  // incoming value was written at the end of the incoming basic block.
+  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) {
+      BasicBlock *OpIBB = OpI->getParent();
+      // As we pretend there is a use (or more precise a write) of OpI in OpBB
+      // we have to insert a scalar dependence from the definition of OpI to
+      // OpBB if the definition is not in OpBB.
+      if (OpIBB != OpBB) {
+        IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true);
+        AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
+        IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true);
+        AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
+      }
+    }
+
+    // If the operand is a constant, global or argument we need an access
+    // instruction and just choose the PHI.
+    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));
     }
   }
 
   if (Functions.empty())

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_1.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
+}

test/ScopInfo/phi_loop_carried_float.ll

+; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+;
+;    float f(float *A, int N) {
+;      float tmp = 0;
+;      for (int i = 0; i < N; i++)
+;        tmp += A[i];
+;    }
+;
+; CHECK:      Statements {
+; CHECK:        Stmt_bb1
+; CHECK:              ReadAccess := [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] };
+; CHECK:              MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] };
+; CHECK:        Stmt_bb4
+; CHECK:              MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
+; CHECK:              ReadAccess := [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
+; CHECK:              ReadAccess := [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] };
+; CHECK:              MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp7[] };
+; CHECK:      }
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ]
+  %tmp.0 = phi float [ 0.000000e+00, %bb ], [ %tmp7, %bb4 ]
+  %tmp2 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp2, label %bb3, label %bb8
+
+bb3:                                              ; preds = %bb1
+  br label %bb4
+
+bb4:                                              ; preds = %bb3
+  %tmp5 = getelementptr inbounds float* %A, i64 %indvars.iv
+  %tmp6 = load float* %tmp5, align 4
+  %tmp7 = fadd float %tmp.0, %tmp6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb8:                                              ; preds = %bb1
+  br label %exit
+
+exit:
+  ret void
+}

test/ScopInfo/phi_scalar_simple_1.ll

+; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+;
+;    int jd(int *restrict A, int x, int N) {
+;      for (int i = 1; i < N; i++)
+;        for (int j = 3; j < N; j++)
+;          x += A[i];
+;      return x;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @jd(i32* noalias %A, i32 %x, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc4, %entry
+; CHECK: Stmt_for_cond
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc4 ], [ 1, %entry ]
+  %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1.lcssa, %for.inc4 ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+; CHECK: Stmt_for_body
+; CHECK:       ReadAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_body[i0] -> MemRef_x_addr_1[] };
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+; CHECK: Stmt_for_cond1
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1_lcssa[] };
+  %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %add, %for.inc ]
+  %j.0 = phi i32 [ 3, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, %N
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+; CHECK: Stmt_for_inc
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_A[1 + i0] };
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp1 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %x.addr.1, %tmp1
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+; CHECK: Stmt_for_end
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_end[i0] -> MemRef_x_addr_1_lcssa[] };
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_end[i0] -> MemRef_x_addr_1_lcssa[] };
+  %x.addr.1.lcssa = phi i32 [ %x.addr.1, %for.cond1 ]
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+; CHECK: Stmt_for_inc4
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc4[i0] -> MemRef_x_addr_1_lcssa[] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc4[i0] -> MemRef_x_addr_0[] };
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret i32 %x.addr.0
+}

test/ScopInfo/phi_scalar_simple_2.ll

+; RUN: opt %loadPolly -polly-scops -polly-model-phi-nodes -disable-polly-intra-scop-scalar-to-array -analyze < %s | FileCheck %s
+;
+;    int jd(int *restrict A, int x, int N, int c) {
+;      for (int i = 0; i < N; i++)
+;        for (int j = 0; j < N; j++)
+;          if (i < c)
+;            x += A[i];
+;      return x;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @jd(i32* noalias %A, i32 %x, i32 %N, i32 %c) {
+entry:
+  %tmp = sext i32 %N to i64
+  %tmp1 = sext i32 %c to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc5, %entry
+; CHECK: Stmt_for_cond
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0_s2a[0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc5 ], [ 0, %entry ]
+  %x.addr.0 = phi i32 [ %x, %entry ], [ %x.addr.1, %for.inc5 ]
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %x.addr.0, i32* %arrayidx2
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end7
+
+for.body:                                         ; preds = %for.cond
+; CHECK: Stmt_for_body
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_1[] };
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+; CHECK: Stmt_for_cond1
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
+  %x.addr.1 = phi i32 [ %x.addr.0, %for.body ], [ %x.addr.2, %for.inc ]
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, %N
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+; CHECK: Stmt_for_body3
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_2[] };
+  %cmp4 = icmp slt i64 %indvars.iv, %tmp1
+  br i1 %cmp4, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body3
+; CHECK: Stmt_if_then
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_A[i0] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_2[] };
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp2 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %x.addr.1, %tmp2
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body3
+; CHECK: Stmt_if_end
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_end[i0, i1] -> MemRef_x_addr_2[] };
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_end[i0, i1] -> MemRef_x_addr_2[] };
+  %x.addr.2 = phi i32 [ %add, %if.then ], [ %x.addr.1, %for.body3 ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+; CHECK: Stmt_for_inc
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_2[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc5
+
+for.inc5:                                         ; preds = %for.end
+; CHECK: Stmt_for_inc5
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_inc5[i0] -> MemRef_x_addr_1[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_for_inc5[i0] -> MemRef_x_addr_0[] };
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end7:                                         ; preds = %for.cond
+  ret i32 %x.addr.0
+}
+