[Polly] Follow uses to create value MemoryAccesses

[Meinersbur]

Summary

The previously implemented approach is to follow value definitions and create write accesses ("push defs") while searching for uses. This requires the same relatively validity- and requirement conditions to be replicated at multiple locations (PHI instructions, other instructions, uses by PHIs).

We replace this by iterating over the uses in a SCoP ("pull in requirements"), and add writes only when at least one read has been added. It turns out to be simpler code because each use is only iterated over once and writes are added for the first access that reads it. We need another iteration to identify escaping values (uses not in the SCoP), which also makes the difference between such accesses more obvious.

[llvm-commits]

+; TODO: Because of the phi with 3 incoming blocks, the loop for => outofscop is
+; not recognized as a loop, but as a non-affine subregion.

My guess would be this is because ScalarEvolution cannot create an
AddRec for %j. PHIs with multiple incoming blocks are generally not a
problem.

+
+define void @func(i32 %n, double* nonnull noalias %A) {
+entry:
+ br label %for
+
+for:
+ %phi = phi double [0.0, %entry], [0.0, %inc], [%phi, %outofscop]
+ %j = phi i32 [0, %entry], [%j.inc, %inc], [0, %outofscop]
+ %j.cmp = icmp slt i32 %j, %n
+ br i1 %j.cmp, label %body, label %outofscop
+
+body:
+ store double 4.2, double* %A
+ br label %inc
+
+inc:
+ %j.inc = add nuw nsw i32 %j, 1
+ br label %for
+
+outofscop:
+ fence seq_cst
+ br i1 true, label %return, label %for
+
+return:
+ ret void
+}

• signature.asc219 BDownload
• msg-2084-335.txt162 BDownload

[Meinersbur]

In D15706#315267, @llvm-commits wrote:

+; TODO: Because of the phi with 3 incoming blocks, the loop for => outofscop is
+; not recognized as a loop, but as a non-affine subregion.

My guess would be this is because ScalarEvolution cannot create an
AddRec for %j. PHIs with multiple incoming blocks are generally not a
problem.

The loop is correctly identified without the %outofscop block. From the region's standpoint, is also entering the region with the same incoming value. %outofscop adds another surrounding loop.

I think I will look at it again and commit this test case separately as it is not specific to this patch; It was helpful for finding a bug, though;

[Meinersbur]

Rebase

[Meinersbur]

Rebase to r258998

[grosser]

This rebase seems broken. It contains three patches of which two are already committed.

[Meinersbur]

Somehow r258947 got mixed-in in the previous diff; rebase to r259041

[grosser]

Hi Michael,

this patch looks like a nice improvement. Also, I like that the patch is very targeted only changing the order a couple of memory writes. I only have some minor questions:

From the commit message:

Because it does not catch all uses (e.g. those by PHIs), some code adds more scalar reads write on the fly, with relatively conditions and possible creation of MemoryAccesses that are not required.

Is this still correct? As far as I see, this patch does not reduce the number of memory accesses modeled. Maybe this functionality was already committed with the previous patch?

Also, I do not yet fully understand why we add new accesses in "test/ScopInfo/invariant-loads-leave-read-only-statements.ll". Was this what the sentence above was about? Could you maybe point out again the reason why we need to add more load accesses.
My feeling was that this is an [NFC] patch when ignoring the order of the generated memory accesses.

lib/Analysis/ScopInfo.cpp

3886

What about GlobalVariable constants. I assume we want to keep accesses to them, no?

[Meinersbur]

Filter ScopRIL for definitions, not uses

[Meinersbur]

In D15706#340524, @grosser wrote:

From the commit message:

Because it does not catch all uses (e.g. those by PHIs), some code adds more scalar reads write on the fly, with relatively conditions and possible creation of MemoryAccesses that are not required.

s/relatively conditions/relatively complicated conditions

Is this still correct? As far as I see, this patch does not reduce the number of memory accesses modeled. Maybe this functionality was already committed with the previous patch?

This describes the situation in current trunk.

Also, I do not yet fully understand why we add new accesses in "test/ScopInfo/invariant-loads-leave-read-only-statements.ll". Could you maybe point out again the reason why we need to add more load accesses.

This is something I forgot. Before the ScopRIL.count was tested on definitions (always LoadInsts), after with this it actually iterates over uses. I moved the ScopRIL.count to ensureValueLoad so it also tests whether an access is not required because is it will be hoisted.

This was also the reason behing the TODO in invariant_load_scalar_escape_alloca_sharing.ll, because the ScopRIL.count was checked only after buildPHIAccesses.

My feeling was that this is an [NFC] patch when ignoring the order of the generated memory accesses.

[grosser]

Hi,

thanks for the fast turnaround.

I understood pretty much what you mean, but am still not 100% about this sentence:

possible creation of MemoryAccesses that are not required

Are you saying we could possibly create unnecessary memory accesses in trunk. This commit message makes the impression we now do not generate such redundant accesses, but looking at the test cases the number of accesses does not change. Now, I wonder: does this commit potentially change the number of memory accesses generated? In case it does, do we lack test coverage to see this?

Otherwise, there is just one typo that you introduced with the last update.

lib/Analysis/ScopInfo.cpp

3887

ConstantFP twice?

[Meinersbur]

Refined constant filter condition (Filter out UndefValue, but also all kinds of structured literal constants). GlobalVariable seems to be the only 'changeable' constant. Not sure about GlobalAlias.

[grosser]

LGTM

include/polly/ScopInfo.h

class ScopInfo : public RegionPass {
   void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
                          const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
                          const InvariantLoadsSetTy &ScopRIL);
 
   /// @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 NonAffineSubRegion The non affine sub-region @p Inst is in.
-  ///
-  /// @return     True if the Instruction is used in other BB and a scalar write
-  ///             Access is required.
-  bool buildScalarDependences(Instruction *Inst, Region *R,
-                              Region *NonAffineSubRegio);
+  void buildScalarDependences(Instruction *Inst);
+
+  /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
+  /// within the SCoP. If there is such use, add a SCALAR WRITE such that it is
+  /// available after the SCoP as escaping value.
+  void buildEscapingDependences(Instruction *Inst);
 
   /// @brief Create MemoryAccesses for the given PHI node in the given region.
   ///
   /// @param PHI                The PHI node to be handled
   /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
   void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion,

lib/Analysis/ScopInfo.cpp

for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
     BasicBlock *OpBB = PHI->getIncomingBlock(u);
 
     // Do not build scalar dependences inside a non-affine subregion.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
       continue;
 
     OnlyNonAffineSubRegionOperands = false;
-
-    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 (scop->getStmtForBasicBlock(OpIBB) !=
-          scop->getStmtForBasicBlock(OpBB)) {
-        ensureValueRead(OpI, OpBB);
-        ensureValueWrite(OpI);
-      }
-    } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
-      ensureValueRead(Op, OpBB);
-    }
-
     ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
     addPHIReadAccess(PHI);
   }
 }
 
-bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
-                                      Region *NonAffineSubRegion) {
-  bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
-  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;
+void ScopInfo::buildScalarDependences(Instruction *Inst) {
+  assert(!isa<PHINode>(Inst));
 
-    BasicBlock *UseParent = UI->getParent();
-
-    // Ignore basic block local uses. A value that is defined in a scop, but
-    // used in a PHI node in the same basic block does not count as basic block
-    // local, as for such cases a control flow edge is passed between definition
-    // and use.
-    if (UseParent == ParentBB && !isa<PHINode>(UI))
-      continue;
-
-    // Uses by PHI nodes in the entry node count as external uses in case the
-    // use is through an incoming block that is itself not contained in the
-    // region.
-    if (R->getEntry() == UseParent) {
-      if (auto *PHI = dyn_cast<PHINode>(UI)) {
-        bool ExternalUse = false;
-        for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
-          if (PHI->getIncomingValue(i) == Inst &&
-              !R->contains(PHI->getIncomingBlock(i))) {
-            ExternalUse = true;
-            break;
-          }
-        }
-
-        if (ExternalUse) {
-          AnyCrossStmtUse = true;
-          continue;
-        }
-      }
-    }
-
-    // Do not build scalar dependences inside a non-affine subregion.
-    if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
-      continue;
-
-    // Check for PHI nodes in the region exit and skip them, if they will be
-    // modeled as PHI nodes.
-    //
-    // PHI nodes in the region exit that have more than two incoming edges need
-    // to be modeled as PHI-Nodes to correctly model the fact that depending on
-    // the control flow a different value will be assigned to the PHI node. In
-    // case this is the case, there is no need to create an additional normal
-    // scalar dependence. Hence, bail out before we register an "out-of-region"
-    // use for this definition.
-    if (isa<PHINode>(UI) && UI->getParent() == R->getExit() &&
-        !R->getExitingBlock())
-      continue;
-
-    // Check whether or not the use is in the SCoP.
-    if (!R->contains(UseParent)) {
-      AnyCrossStmtUse = true;
-      continue;
-    }
-
-    // If the instruction can be synthesized and the user is in the region
-    // we do not need to add scalar dependences.
-    if (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))
-      continue;
-
-    // Skip PHI nodes in the region 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
-    // Use the def instruction as base address of the MemoryAccess, so that it
-    // will become the name of the scalar access in the polyhedral form.
-    ensureValueRead(Inst, UI->getParent());
-  }
-
-  if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
-    for (Value *Op : Inst->operands()) {
-      if (canSynthesize(Op, LI, SE, R))
-        continue;
-
-      if (Instruction *OpInst = dyn_cast<Instruction>(Op))
-        if (R->contains(OpInst))
-          continue;
-
-      if (isa<Constant>(Op))
-        continue;
-
-      ensureValueRead(Op, Inst->getParent());
-    }
-  }
-
-  return AnyCrossStmtUse;
+  // Pull-in required operands.
+  for (auto &Op : Inst->operands())
+    ensureValueRead(Op.get(), Inst->getParent());
+}
+
+void ScopInfo::buildEscapingDependences(Instruction *Inst) {
+  Region *R = &scop->getRegion();
+
+  // Check for uses of this instruction outside the scop. Because we do not
+  // iterate over such instructions and therefore did not "ensure" the existence
+  // of a write, we must determine such use here.
+  for (Use &U : Inst->uses()) {
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
+    if (!UI)
+      continue;
+
+    BasicBlock *UseParent = getUseBlock(U);
+    BasicBlock *UserParent = UI->getParent();
+
+    // An escaping value is either used by an instruction not within the scop,
+    // or (when the scop region's exit needs to be simplified) by a PHI in the
+    // scop's exit block. This is because region simplification before code
+    // generation inserts new basic blocks before the PHI such that its incoming
+    // blocks are not in the scop anymore.
+    if (!R->contains(UseParent) ||
+        (isa<PHINode>(UI) && UserParent == R->getExit() &&
+         R->getExitingBlock())) {
+      // At least one escaping use found.
+      ensureValueWrite(Inst);
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
 void ScopInfo::buildMemoryAccess(
     Instruction *Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 
   // The set of loads that are required to be invariant.
   auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
 
-  for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
-    Instruction *Inst = &*I;
+  for (Instruction &Inst : BB) {
 
-    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
       buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
     // TODO: At this point we only know that elements of ScopRIL have to be
     //       invariant and will be hoisted for the SCoP to be processed. Though,
     //       there might be other invariant accesses that will be hoisted and
     //       that would allow to make a non-affine access affine.
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
-      buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
+      buildMemoryAccess(&Inst, L, &R, BoxedLoops, ScopRIL);
 
-    if (isIgnoredIntrinsic(Inst))
+    if (isIgnoredIntrinsic(&Inst))
       continue;
 
     // Do not build scalar dependences for required invariant loads as we will
     // hoist them later on anyway or drop the SCoP if we cannot.
-    if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
+    if (ScopRIL.count(dyn_cast<LoadInst>(&Inst)))
       continue;
 
-    if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
-      if (!isa<StoreInst>(Inst))
-        ensureValueWrite(Inst);
-    }
+    if (!PHI)
+      buildScalarDependences(&Inst);
+    if (!IsExitBlock)
+      buildEscapingDependences(&Inst);
   }
 }
 
 MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                         MemoryAccess::AccessType Type,
                                         Value *BaseAddress, unsigned ElemBytes,
                                         bool Affine, Value *AccessValue,
                                         ArrayRef<const SCEV *> Subscripts,
void ScopInfo::ensureValueWrite(Instruction *Value) {
 
   addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
                   true, Value, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
 }
 void ScopInfo::ensureValueRead(Value *Value, BasicBlock *UserBB) {
 
   // There cannot be an "access" for constants.
   if (isa<Constant>(Value) || isa<BasicBlock>(Value))
     return;
 
   // If the instruction can be synthesized and the user is in the region we do
   // not need to add a value dependences.
   Region &ScopRegion = scop->getRegion();
   if (canSynthesize(Value, LI, SE, &ScopRegion))
     return;
 
   // Determine the ScopStmt containing the value's definition and use. There is
void ScopInfo::ensureValueRead(Value *Value, BasicBlock *UserBB) {
   if (ValueStmt == UserStmt)
     return;
 
   // Do not create another MemoryAccess for reloading the value if one already
   // exists.
   if (UserStmt->lookupValueReadOf(Value))
     return;
 
-  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, Value, 1, true, Value,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  ScopArrayInfo::MK_Value);
+  auto Acc = addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, Value, 1,
+                             true, Value, ArrayRef<const SCEV *>(),
+                             ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
+  assert(Acc);
+  if (ValueInst)
+    ensureValueWrite(ValueInst);
 }
 void ScopInfo::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
                               Value *IncomingValue, bool IsExitBlock) {
   ScopStmt *IncomingStmt = scop->getStmtForBasicBlock(IncomingBlock);
+  if (!IncomingStmt)
+    return;
+
+  // Take care for the incoming value being available in the incoming block.
+  // This must be done before the check for multiple PHI writes because multiple
+  // exiting edges from subregion each can be the effective written value of the
+  // subregion. As such, all of them must be made available in the subregion
+  // statement.
+  ensureValueRead(IncomingValue, IncomingBlock);
 
   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
     assert(Acc->getAccessInstruction() == PHI);
     Acc->addIncoming(IncomingBlock, IncomingValue);
     return;
   }
 

test/Isl/CodeGen/MemAccess/update_access_functions.ll

 ; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \
 ; RUN:                -polly-import-jscop-postfix=transformed -polly-codegen \
 ; RUN:                 < %s -S | FileCheck %s
 
 ; CHECK: polly.stmt.loop2:
 ; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i64 42
 ; CHECK-NEXT:   %val_p_scalar_ = load double, double* %polly.access.A
 
 ; CHECK: polly.stmt.loop3:
 ; CHECK-NEXT:   %val.s2a.reload = load double, double* %val.s2a
-; CHECK-NEXT:   %polly.access.A20 = getelementptr double, double* %A, i64 42
-; CHECK-NEXT:   store double %val.s2a.reload, double* %polly.access.A20
+; CHECK-NEXT:   %scevgep[[R21:[0-9]*]] = getelementptr double, double* %scevgep{{[0-9]*}}, i64 %polly.indvar16
+; CHECK-NEXT:   store double %val.s2a.reload, double* %scevgep[[R21]]
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @update_access_functions(i64 %arg, double* %A) {
 bb3:
   br label %loop1
 
 loop1:

test/Isl/CodeGen/phi_escaping_phi_incoming_user_1.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+
+; The scop's entry has a PHI with incoming block from inside and outside the
+; scop, where %phi is defined within the scop, but also escaping it because the
+; incoming block for the incoming value is not in the SCoP.
+
+; TODO: Because of the phi with 3 incoming blocks, the loop for => outofscop is 
+; not recognized as a loop, but as a non-affine subregion.
+
+define void @func(i32 %n, double* nonnull noalias %A) {
+entry:
+  br label %for
+
+for:
+  %phi = phi double [0.0, %entry], [0.0, %inc], [%phi, %outofscop]
+  %j = phi i32 [0, %entry], [%j.inc, %inc], [0, %outofscop]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %outofscop
+
+body:
+  store double 4.2, double* %A
+  br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+outofscop:
+  fence seq_cst
+  br i1 true, label %return, label %for
+
+return:
+  ret void
+}
+
+; CHECK-LABEL: for.region_entering:
+; CHECK:         %phi.ph = phi double [ %phi.merge, %outofscop ], [ 0.000000e+00, %entry ]
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK:         %phi.merge = phi double [ %phi.final_reload, %polly.exiting ], [ %phi, %for ]
+; CHECK:         br label
+;
+; CHECK-LABEL: polly.start:
+; CHECK:         store double %phi.ph, double* %phi.phiops
+;
+; CHECK-LABEL: polly.stmt.for.entry:
+; CHECK:         %phi.phiops.reload[[R1:[0-9]+]] = load double, double* %phi.phiops
+;
+; CHECK-LABEL: polly.stmt.for:
+; CHECK:         %polly.phi = phi double [ %phi.phiops.reload[[R1]], %polly.stmt.for.entry ], [ 0.000000e+00, %polly.stmt.inc ]
+;
+; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
+; CHECK:         %phi.s2a.reload = load double, double* %phi.s2a
+; CHECK:         store double %phi.s2a.reload, double* %phi.s2a
+;
+; CHECK-LABEL: polly.exiting:
+; CHECK:         %phi.final_reload = load double, double* %phi.s2a

test/ScopInfo/invariant-loads-leave-read-only-statements.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -analyze < %s
 ;
 ;
 ; CHECK:         Statements {
 ; CHECK-NEXT:      Stmt_top_split
 ; CHECK-NEXT:            Domain :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] };
 ; CHECK-NEXT:            Schedule :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> [0, 0, 0, 0] };
 ; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
-; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_26[] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
 ; CHECK-NEXT:      Stmt_L_4
 ; CHECK-NEXT:            Domain :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] : i0 >= 0 and i0 <= -1 + p_0 and i1 >= 0 and i1 <= -1 + p_0 and i2 >= 0 and i2 <= -1 + p_0 };
 ; CHECK-NEXT:            Schedule :=
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> [1, i0, i1, i2] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_25[] };
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_22[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_8[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_5[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_5[i2, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_15[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_12[] };
 ; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_12[i2, i1] };
 ; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_25[] };
 ; CHECK-NEXT:    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %jl_value_t = type { %jl_value_t* }
 
 define %jl_value_t* @julia_gemm_22583(%jl_value_t*, %jl_value_t**, i32) {
 top:

test/ScopInfo/many-scalar-dependences.ll

 ; CHECK:           { Stmt_bb11[i0, i1, i2] -> MemRef_x_3__phi[] };
 ; CHECK: Stmt_bb12
 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb12[i0, i1, i2] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 and i2 <= 99 and i2 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> [i0, 2, i1, 2, i2, 3] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3__phi[] };
-; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           { Stmt_bb12[i0, i1, i2] -> MemRef_x_3[] };
 ; CHECK: Stmt_bb16
 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb16[i0, i1, i2] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 and i2 <= 99 and i2 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb16[i0, i1, i2] -> [i0, 2, i1, 2, i2, 4] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb16[i0, i1, i2] -> MemRef_x_2__phi[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]

test/ScopInfo/non_affine_region_4.ll

 ;        A[i] = x + y;
 ;      }
 ;    }
 ;
 ; CHECK:    Region: %bb1---%bb11
 ;
 ; CHECK: Arrays {
 ; CHECK:   i32 MemRef_A[*];
-; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi;
+; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
 ; CHECK:   i32 MemRef_A[*];
-; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi;
+; CHECK:   i32 MemRef_x; [BasePtrOrigin: MemRef_A]
 ; CHECK: }
 ;
 ; CHECK:      Stmt_bb2__TO__bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> [i0, 0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_A[i0] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
-; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
 ; CHECK:      Stmt_bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb7[i0] :
 ; CHECK-DAG:               i0 >= 0
 ; CHECK-DAG:             and
 ; CHECK-DAG:               i0 <= 1023
 ; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb7[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                { Stmt_bb7[i0] -> MemRef_x[] };
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                { Stmt_bb7[i0] -> MemRef_y__phi[] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_bb7[i0] -> MemRef_x[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                { Stmt_bb7[i0] -> MemRef_A[i0] };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i32 %b) {
 bb:
   br label %bb1

test/ScopInfo/phi_condition_modeling_2.ll

 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8b
 ; CHECK-NOT: Access
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] };
-; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                [N, c] -> { Stmt_bb8b[i0] -> MemRef_tmp_0[] };
+; CHECK-NOT: Access
 ; 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

test/ScopInfo/phi_loop_carried_float.ll

 ; CHECK:                  [N] -> { Stmt_bb1[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:   Stmt_bb4
 ; CHECK-NOT: Access
 ; CHECK:              MustWriteAccess :=  [Reduction Type: NONE]
 ; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:              ReadAccess := [Reduction Type: NONE]
-; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
 ; CHECK:              ReadAccess := [Reduction Type: NONE]
-; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_A[i0] };
+; CHECK:                  [N] -> { Stmt_bb4[i0] -> MemRef_tmp_0[] };
 ; CHECK-NOT: Access
 ; 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

test/ScopInfo/phi_scalar_simple_1.ll

 for.body3:                                        ; preds = %for.cond1
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body3
 ; CHECK-LABEL: Stmt_for_inc
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1__phi[] };
 ; CHECK-NOT: Access
-; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
 ; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_A[1 + i0] };
 ; CHECK-NOT: Access
+; CHECK:       ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:           [N] -> { Stmt_for_inc[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK-NOT: Access
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %tmp1 = load i32, 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-LABEL: Stmt_for_end

test/ScopInfo/phi_scalar_simple_2.ll

 ; CHECK:         [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_2__phi[] };
 ; CHECK-NOT: Access
   %cmp4 = icmp slt i64 %indvars.iv, %tmp1
   br i1 %cmp4, label %if.then, label %if.end
 
 if.then:                                          ; preds = %for.body3
 ; CHECK-LABEL: Stmt_if_then
 ; CHECK-NOT: Access
-; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NOT: Access
 ; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_A[i0] };
 ; CHECK-NOT: Access
+; CHECK:     ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_1[] };
+; CHECK-NOT: Access
 ; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:         [N, c] -> { Stmt_if_then[i0, i1] -> MemRef_x_addr_2__phi[] };
 ; CHECK-NOT: Access
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
   %tmp2 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %x.addr.1, %tmp2
   br label %if.end
 

test/ScopInfo/scalar.ll

 ; CHECK:           [N] -> { Stmt_S1[i0] -> MemRef_a[i0] };
 ; CHECK:       MustWriteAccess :=
 ; CHECK:           [N] -> { Stmt_S1[i0] -> MemRef_val[] };
 ; CHECK: Stmt_S2
 ; CHECK:       Domain :=
 ; CHECK:           [N] -> { Stmt_S2[i0] : i0 >= 0 and i0 <= -1 + N };
 ; CHECK:       Schedule :=
 ; CHECK:           [N] -> { Stmt_S2[i0] -> [i0, 1] };
-; CHECK:       ReadAccess :=
-; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_val[] };
 ; CHECK:       MustWriteAccess :=
 ; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_a[i0] };
+; CHECK:       ReadAccess :=
+; CHECK:           [N] -> { Stmt_S2[i0] -> MemRef_val[] };

test/ScopInfo/tempscop-printing.ll

; CHECK-NOT:      Stmt_entry_next
   %init = load i64, i64* %init_ptr
   br label %for.j
 
 for.j:
 ; CHECK:      Stmt_for_j
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
   %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
   store i64 %init, i64* %scevgep
-; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
   %indvar.j.next = add nsw i64 %indvar.j, 1
   %exitcond.j = icmp eq i64 %indvar.j.next, %N
   br i1 %exitcond.j, label %for.i.end, label %for.j
 
 for.i.end:
   %exitcond.i = icmp eq i64 %indvar.i.next, %N
   br i1 %exitcond.i, label %return, label %for.i
 
 return:
   ret void
 }