BlockGenerators: Replace getNewScalarValue with getNewValue

[grosser]

Summary

Both functions implement the same functionality, with the difference that
getNewScalarValue assumes that globals and out-of-scop scalars can be directly
reused without loading them from their corresponding stack slot. This is correct
for sequential code generation, but causes issues with outlining code e.g. for
OpenMP code generation. getNewValue handles such cases correctly.

Hence, we can replace getNewScalarValue with getNewValue. This is not only more
future proof, but also eliminates a bunch of code.

The only functionality that was available in getNewScalarValue that is lost
is the on-demand creation of scalar values. However, this is not necessary any
more as scalars are always loaded at the beginning of each basic block and will
consequently always be available when scalar stores are generated. As this was
not the case in older versions of Polly, it seems the on-demand loading is just
some older code that has not yet been removed.

Finally, generateScalarLoads also generated loads for values that are loop
invariant, available in GlobalMap and which are preferred over the ones loaded
in generateScalarLoads. Hence, we can just skip the code generation of such
scalar values, avoiding the generation of dead code.

[Meinersbur]

Bu coincidence, I was working on the very same patch. Since rebasing D15687, a new bug appear for which to solve this is needed. I was still in the process of testing whether there are no other problems. My version of this patch is here

lib/CodeGen/BlockGenerators.cpp

412 ↗

(On Diff #45828)

This is fixing a symptom only. The MemoryAccess shouldn't exist in the first place if we are going to ignore it.

In fact, invariant loads do not need any MemoryAccesses inserted at all. One can just use the loaded llvm::Value as it is inserted before the generated code. In case the load is conditional, inserting a phi with an undef on one side is simple.

1222 ↗

(On Diff #45828)

This is wrong; we don't need the loop where the value is defined but where it is used. The difference comes in to play when the value is defined in the loop, but we write its scalar value after the loop, thus use the value after the last loop iteration.

test/Isl/CodeGen/invariant_load_scalar_escape_alloca_sharing.ll

14 ↗

(On Diff #45828)

This store became useless as well, didn't it?

[grosser]

Hi Michael,

thank you for this fast review.

lib/CodeGen/BlockGenerators.cpp

412 ↗

(On Diff #45828)

Right.

However, I am not sure that dropping the memory access is the solution we want, as this would mean we do not represent this read-access in our polyhedral access functions (http://llvm.org/PR25107). This causes trouble in case we want to know the precise set of data-locations read e.g. for kernel outlining or other things (even though it currently works with our OpenMP code generation). I think the right solution is to not add the InvariantLoads to GlobalMap, but to instead model them as normal read/write memory accesses (which are code-generated accordingly).

As this is a little bit more involved and probably also requires some discussion, I would prefer to discuss and address this issue independently. Regarding this patch, I could just leave out the change above and add a FIXME saying that we currently generate redundant memory accesses as we
directly read data from the invariant-load-motioned register.

1222 ↗

(On Diff #45828)

Is this not what is happening? ScalarInst comes from getAccessInstruction(), which is defined to return:

/// For memory accesses of kind MK_Value the access instruction of a load      
/// access is the instruction that uses the load. The access instruction of    
/// a write access is the instruction that defines the llvm::Value.

Now, the original code was slightly different. It was using: getLoopForInst(ScalarValueInst) where ScalarValueInst was the definition of the ScalarValueInst.

So it seems the behavior was changed (maybe needs a test case?), but the result should be more correct? In case I got it wrong, could you suggest what value to use otherwise.

(In case we drop the MA->getAccessInstruction() mapping for scalar values, we can probably just use the loop around the entry block.)

test/Isl/CodeGen/invariant_load_scalar_escape_alloca_sharing.ll

14 ↗

(On Diff #45828)

Right. It is also redundant.

[Meinersbur]

lib/CodeGen/BlockGenerators.cpp

412 ↗

(On Diff #45828)

OK

1222 ↗

(On Diff #45828)

This is true for accesses of type MK_Value (where the definition must necessarily be in the same Stmt), but not for MK_PHI or MK_ExitPHI. Here, getAccessInstruction() returns the incoming value (at least before D15681) which might be defined anywhere before. Eg.

loop:
  %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
  %i.inc = add nsw i32 %i, 1
  %cmp5 = icmp slt i32 %i.inc, 2
  br i1 %cmp5, label %exit, label %loop

exit:
  br label %join

join:
  %phi = phi i32 [i.inc, %join]

There'd be a PHI write in Stmt_exit, writing the value of %i.inc. Hence, the AccessInstruction of that would be %i.inc. Synthesizing it within loop (getLoopForInt(%i.inc)) will expand to something dependent on %i, whereas at %exit the correct value is 2.

You might look into my version of the patch for how I solved the issue.

[Meinersbur]

Test case.

This might currently not exploitable because getNewScalarValue
prioritizes values from BBMap over synthesizable ones. D15706 should
remove such memory accesses for synthesizable values.

Michael

• synthesizable_phi_write_after_loop.ll1 KBDownload

[grosser]

Address Michael's review comments

[grosser]

Hi Michael,

thanks for the comments. I added your test case and addressed the PHI/EXITING_PHI issue. Could you confirm I did not miss anything and this is now ready to go?

Best,
Tobias

lib/CodeGen/BlockGenerators.cpp

1222 ↗

(On Diff #45828)

I looked at your code and now derive the loop from getRegion->getEntry().

You derive it from getExit(). This might be incorrect if the region is on a backedge and the exit is the header of a loop that dominates the original region. This is highly unlikely, though. getEntry() on the other hand seems to be save in general as it is itself within the scop region.

[Meinersbur]

lib/CodeGen/BlockGenerators.cpp

1216 ↗

(On Diff #45860)

I see the problem with getExit(), but I am not yet convinced it is wrong. If it's the backedge that means that we did not leave that loop, i.e. passing that loop to the SCEV expander is correct.

On the other side, getEntry() might be wrong as well. With -polly-allow-nonaffine-loops, there might be a loop in the non-affine subregion as well and the SCEV depend on that. If the entry is part of the loop, SCEV expander will generate an expression depending on its induction variable, but the point of evaluation is the edge to the exit block, which is not part of the contained loop.

ASCII-Art:

 _____
/      Entry
\      /       
 - loop       
      |               
 loop.after  
       |  \
       |   side
       |   /
       Exit

Let's say the loop Entry=>loop has a non-affine exit condition (such as "i*i <n" which AFAIK is supported by SCEV). With -polly-allow-nonaffine-loops, the non-affine subregion should be Entry=>Exit. Exit has a phi:

Exit:

%phi = phi i32 [%i.inc, %loop.after], [0, %side]

%i.inc needs to be evaluated in %loop.after for the MK_PHI MemoryAccess, but if passing the Loop Entry=>loop to it, we expand to an expression that depends on the loop's iv.

[grosser]

lib/CodeGen/BlockGenerators.cpp

1216 ↗

(On Diff #45860)

Hi Michael,

for now I took your getExit() and committed the patch. I am not 100% certain this is the right choice, but have currently difficulties to write working test cases as the non-affine loop domain generation is broken (http://llvm.org/PR26309, http://llvm.org/PR26310). As this code does not yet seem to be tested, is not enabled by default and seems to have been broken (for this corner case) before, I don't think this should block this patch. Hence, I pushed this out in https://llvm.org/svn/llvm-project/polly/trunk@258799

I also opened a bug report to track this issue until the domain generation is fixed: http://PR26311

[Meinersbur]

Thanks for committing. I will go an and commit my patches on top of it.

lib/CodeGen/BlockGenerators.cpp

1216 ↗

(On Diff #45860)

Hi Tobias,

given that loops within non-affine subregions are currently unsupported, I think it might have been safer to go with the getEntry() version because then we can assume there is no additional loop that the entry block is part of, but not all of the region.

Rethinking my argument, it is probably wrong too: we could enter a new loop (header) that is not part of the non-affine subregion.

What we are really looking for is the loop of the subregion's exiting edges. We could get it e.g.:

• Take the top entry of ScopStmt's NestLoops (if not empty)
• Get the innermost loop that contains both, the subregion exiting and exit node.

polly/trunk/include/polly/CodeGen/BlockGenerators.h

protected:
   ///                    (for values recalculated in the new ScoP, but not
   ///                     within this basic block).
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
                        LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses);
 
-  /// @brief Helper to get the newest version of @p ScalarValue.
-  ///
-  /// @param ScalarValue The original value needed.
-  /// @param R           The current SCoP region.
-  /// @param Stmt        The ScopStmt in which we look up this value.
-  /// @param LTS         A mapping from loops virtual canonical induction
-  ///                    variable to their new values
-  ///                    (for values recalculated in the new ScoP, but not
-  ///                     within this basic block)
-  /// @param BBMap       A mapping from old values to their new values
-  ///                    (for values recalculated within this basic block).
-  ///
-  /// @returns The newest version (e.g., reloaded) of the scalar value.
-  Value *getNewScalarValue(Value *ScalarValue, const Region &R, ScopStmt &,
-                           LoopToScevMapT &LTS, ValueMapT &BBMap);
-
   /// @brief Helper to determine if @p Inst can be synthezised in @p Stmt.
   ///
   /// @returns false, iff @p Inst can be synthesized in @p Stmt.
   bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst);
 };
 
 /// @brief Generate a new vector basic block for a polyhedral statement.
 ///

polly/trunk/lib/CodeGen/BlockGenerators.cpp

if (MA->isArrayKind() || MA->isWrite())
       continue;
 
     auto *Address = getOrCreateAlloca(*MA);
     BBMap[MA->getBaseAddr()] =
         Builder.CreateLoad(Address, Address->getName() + ".reload");
   }
 }
 
-Value *BlockGenerator::getNewScalarValue(Value *ScalarValue, const Region &R,
-                                         ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                         ValueMapT &BBMap) {
-  // If the value we want to store is an instruction we might have demoted it
-  // in order to make it accessible here. In such a case a reload is
-  // necessary. If it is no instruction it will always be a value that
-  // dominates the current point and we can just use it. In total there are 4
-  // options:
-  //  (1) The value is no instruction ==> use the value.
-  //  (2) The value is an instruction that was split out of the region prior to
-  //      code generation  ==> use the instruction as it dominates the region.
-  //  (3) The value is an instruction:
-  //      (a) The value was defined in the current block, thus a copy is in
-  //          the BBMap ==> use the mapped value.
-  //      (b) The value was defined in a previous block, thus we demoted it
-  //          earlier ==> use the reloaded value.
-  Instruction *ScalarValueInst = dyn_cast<Instruction>(ScalarValue);
-  if (!ScalarValueInst)
-    return ScalarValue;
-
-  if (!R.contains(ScalarValueInst)) {
-    if (Value *ScalarValueCopy = GlobalMap.lookup(ScalarValueInst))
-      return /* Case (3a) */ ScalarValueCopy;
-    else
-      return /* Case 2 */ ScalarValue;
-  }
-
-  if (Value *ScalarValueCopy = BBMap.lookup(ScalarValueInst))
-    return /* Case (3a) */ ScalarValueCopy;
-
-  if ((Stmt.isBlockStmt() &&
-       Stmt.getBasicBlock() == ScalarValueInst->getParent()) ||
-      (Stmt.isRegionStmt() && Stmt.getRegion()->contains(ScalarValueInst))) {
-    auto SynthesizedValue = trySynthesizeNewValue(
-        Stmt, ScalarValueInst, BBMap, LTS, getLoopForInst(ScalarValueInst));
-
-    if (SynthesizedValue)
-      return SynthesizedValue;
-  }
-
-  // Case (3b)
-  Value *Address = getOrCreateScalarAlloca(ScalarValueInst);
-  ScalarValue = Builder.CreateLoad(Address, Address->getName() + ".reload");
-
-  return ScalarValue;
-}
-
 void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                           ValueMapT &BBMap) {
-  const Region &R = Stmt.getParent()->getRegion();
+  Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 
   assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
     if (MA->isArrayKind() || MA->isRead())
       continue;
 
     Value *Val = MA->getAccessValue();
     auto *Address = getOrCreateAlloca(*MA);
 
-    Val = getNewScalarValue(Val, R, Stmt, LTS, BBMap);
+    Val = getNewValue(Stmt, Val, BBMap, LTS, L);
     Builder.CreateStore(Val, Address);
   }
 }
 
 void BlockGenerator::createScalarInitialization(Scop &S) {
   Region &R = S.getRegion();
   BasicBlock *ExitBB = R.getExit();
 
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   generateScalarStores(Stmt, LTS, ValueMap);
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 }
 
 void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                            ValueMapT &BBMap) {
-  const Region &R = Stmt.getParent()->getRegion();
-
   assert(Stmt.getRegion() &&
          "Block statements need to use the generateScalarStores() "
          "function in the BlockGenerator");
 
+  // TODO: Add some test cases that ensure this is really the right choice.
+  Loop *L = LI.getLoopFor(Stmt.getRegion()->getExit());
+
   for (MemoryAccess *MA : Stmt) {
     if (MA->isArrayKind() || MA->isRead())
       continue;
 
     Instruction *ScalarInst = MA->getAccessInstruction();
     Value *Val = MA->getAccessValue();
 
     // In case we add the store into an exiting block, we need to restore the
if (MA->isPHIKind() || MA->isExitPHIKind()) {
 
       // For the incoming blocks, use the block's BBMap instead of the one for
       // the entire region.
       LocalBBMap = &RegionMaps[ExitingBBCopy];
     }
 
     auto Address = getOrCreateAlloca(*MA);
 
-    Val = getNewScalarValue(Val, R, Stmt, LTS, *LocalBBMap);
+    Val = getNewValue(Stmt, Val, *LocalBBMap, LTS, L);
     Builder.CreateStore(Val, Address);
 
     // Restore the insertion point if necessary.
     if (MA->isPHIKind() || MA->isExitPHIKind())
       Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint);
   }
 }
 

polly/trunk/test/Isl/CodeGen/invariant_load_scalar_escape_alloca_sharing.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 ;
-; Verify the preloaded %0 is stored and communicated in the same alloca.
+; Verify the preloaded %tmp0 is stored and communicated in the same alloca.
+; In this case, we do not reload %ncol.load from the scalar stack slot, but
+; instead use directly the preloaded value stored in GlobalMap.
+;
+; TODO: We may want to not add preloaded values to GlobalMap, but instead model
+;       them as normal read/write memory accesses. This will allow us to
+;       easily reason about the use of preloaded data in scop statements.
+;       At the moment, we would need to scan the IR to understand if a stmt
+;       uses any preloaded values.
 ;
 ; CHECK-NOT: alloca
 ; CHECK:     %dec3.s2a = alloca i32
 ; CHECK-NOT: alloca
 ; CHECK:     %dec3.in.phiops = alloca i32
 ; CHECK-NOT: alloca
 ; CHECK:     %tmp0.preload.s2a = alloca i32
 ; CHECK-NOT: alloca
 ;
 ; CHECK:       %ncol.load = load i32, i32* @ncol
 ; CHECK-NEXT:  store i32 %ncol.load, i32* %tmp0.preload.s2a
 ;
 ; CHECK:      polly.stmt.while.body.lr.ph:
 ; CHECK-NEXT:   %tmp0.preload.s2a.reload = load i32, i32* %tmp0.preload.s2a
-; CHECK-NEXT:   store i32 %tmp0.preload.s2a.reload, i32* %dec3.in.phiops
+; CHECK-NEXT:   store i32 %ncol.load, i32* %dec3.in.phiops
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @ncol = external global i32, align 4
 
 define void @melt_data(i32* %data1, i32* %data2) {
 entry:
   br label %entry.split

polly/trunk/test/Isl/CodeGen/phi-defined-before-scop.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 
 ; CHECK-LABEL: polly.merge_new_and_old:
 ; CHECK-NEXT: %tmp7.ph.merge = phi %struct.wibble* [ %tmp7.ph.final_reload, %polly.exiting ], [ %tmp7.ph, %bb6.region_exiting ]
 
 ; CHECK-LABEL: polly.stmt.bb3:
 ; CHECK-NEXT: %tmp2.s2a.reload = load %struct.wibble*, %struct.wibble** %tmp2.s2a
-; CHECK-NEXT: store %struct.wibble* %tmp2, %struct.wibble** %tmp7.s2a
+; CHECK-NEXT: store %struct.wibble* %tmp2.s2a.reload, %struct.wibble** %tmp7.s2a
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %struct.blam = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
 %struct.wibble = type { i32, %struct.wibble*, %struct.wibble* }
 
 @global = external global %struct.blam*, align 8
 

polly/trunk/test/Isl/CodeGen/synthesizable_phi_write_after_loop.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; Check for the correct written value of a scalar phi write whose value is
+; defined within the loop, but its effective value is its last definition when
+; leaving the loop (in this test it is the value 2 for %i.inc). This can be
+; either computed:
+; - Using SCEVExpander:
+;         In this case the Loop passed to the expander must NOT be the loop
+; - Overwriting the same alloca in each iteration s.t. the last value will
+;         retain in %i.inc.s2a
+; The latter is currently generated by Polly and tested here.
+
+; CHECK:      polly.stmt.next:
+; CHECK-NEXT:   %i.inc.s2a.reload = load i32, i32* %i.inc.s2a
+; CHECK-NEXT:   store i32 %i.inc.s2a.reload, i32* %phi.phiops
+; CHECK-NEXT:   br label %polly.stmt.join
+;
+; CHECK:      polly.stmt.loop:
+; CHECK:        %0 = trunc i64 %polly.indvar to i32
+; CHECK:        %1 = add i32 %0, 1
+; CHECK:        store i32 %1, i32* %i.inc.s2a
+
+define i32 @func() {
+entry:
+  br label %start
+
+start:
+  br i1 true, label %loop, label %join
+
+loop:
+  %i = phi i32 [ 0, %start ], [ %i.inc, %loop ]
+  %i.inc = add nsw i32 %i, 1
+  %cond = icmp slt i32 %i.inc, 2
+  br i1 %cond, label %loop, label %next
+
+next:
+  br label %join
+
+join:
+  %phi = phi i32 [%i.inc, %next], [0, %start]
+  br label %return
+
+return:
+  ret i32 %phi
+}