BlockGenerator: Do not redundantly reload from PHI-allocas in non-affine stmts

[grosser]

Summary

Before this change we created an additional reload in the copy of the incoming
block of a PHI node to reload the incoming value, even though the necessary
value has already been made available by the normally generated scalar loads.
In this change, we drop the code that generates this redundant reload and
instead just reuse the scalar value already available.

Besides making the generated code slightly cleaner, this change also makes sure
that scalar loads go through the normal logic, which means they can be remapped
(e.g. to array slots) and corresponding code is generated to load from the
remapped location. Without this change, the original scalar load at the
beginning of the non-affine region would have been remapped, but the redundant
scalar load would continue to load from the old PHI slot location.

We also document the current behavior a little bit better.

[Meinersbur]

Did you forget to prefix the title with "[Polly]"?

include/polly/CodeGen/BlockGenerators.h

837–906 ↗

(On Diff #84946)

Good description

lib/CodeGen/BlockGenerators.cpp

1444 ↗

(On Diff #84946)

Any reason to not use getNewValue?

Could you consider adding an assertion verifying that BBCopy/PHI already exist in the maps?

With those two changes both cases of StmtR->contains(IncomingBB) would share some code that could be put before the condition, maybe the condition can be entirely removed.

Instead of the const-cast, we could remove the const-qualifier which doesn't serve any purpose anyway.

[grosser]

Hi Michael,

thanks for the very useful review comments. I integrated most of them, but could not pull out the getNewValue easily. I still need to understand if/when I can pull out the insertionpoint update logic. I committed this for now, as this already seems to be a strict improvement. Will look into the insertion point logic at again.

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

private:
 
   /// Repair the dominance tree after we created a copy block for @p BB.
   ///
   /// @returns The immediate dominator in the DT for @p BBCopy if in the region.
   BasicBlock *repairDominance(BasicBlock *BB, BasicBlock *BBCopy);
 
   /// Add the new operand from the copy of @p IncomingBB to @p PHICopy.
   ///
+  /// PHI nodes, which may have (multiple) edges that enter from outside the
+  /// non-affine subregion and even from outside the scop, are code generated as
+  /// follows:
+  ///
+  /// # Original
+  ///
+  ///   Region: %A-> %exit
+  ///   NonAffine Stmt: %nonaffB -> %D (includes %nonaffB, %nonaffC)
+  ///
+  ///     pre:
+  ///       %val = add i64 1, 1
+  ///
+  ///     A:
+  ///      br label %nonaff
+  ///
+  ///     nonaffB:
+  ///       %phi = phi i64 [%val, %A], [%valC, %nonAffC], [%valD, %D]
+  ///       %cmp = <nonaff>
+  ///       br i1 %cmp, label %C, label %nonaffC
+  ///
+  ///     nonaffC:
+  ///       %valC = add i64 1, 1
+  ///       br i1 undef, label %D, label %nonaffB
+  ///
+  ///     D:
+  ///       %valD = ...
+  ///       %exit_cond = <loopexit>
+  ///       br i1 %exit_cond, label %nonaffB, label %exit
+  ///
+  ///     exit:
+  ///       ...
+  ///
+  ///  - %start and %C enter from outside the non-affine region.
+  ///  - %nonaffC enters from within the non-affine region.
+  ///
+  ///  # New
+  ///
+  ///    polly.A:
+  ///       store i64 %val, i64* %phi.phiops
+  ///       br label %polly.nonaffA.entry
+  ///
+  ///    polly.nonaffB.entry:
+  ///       %phi.phiops.reload = load i64, i64* %phi.phiops
+  ///       br label %nonaffB
+  ///
+  ///    polly.nonaffB:
+  ///       %polly.phi = [%phi.phiops.reload, %nonaffB.entry],
+  ///                    [%p.valC, %polly.nonaffC]
+  ///
+  ///    polly.nonaffC:
+  ///       %p.valC = add i64 1, 1
+  ///       br i1 undef, label %polly.D, label %polly.nonaffB
+  ///
+  ///    polly.D:
+  ///        %p.valD = ...
+  ///        store i64 %p.valD, i64* %phi.phiops
+  ///        %p.exit_cond = <loopexit>
+  ///        br i1 %p.exit_cond, label %polly.nonaffB, label %exit
+  ///
+  /// Values that enter the PHI from outside the non-affine region are stored
+  /// into the stack slot %phi.phiops by statements %polly.A and %polly.D and
+  /// reloaded in %polly.nonaffB.entry, a basic block generated before the
+  /// actual non-affine region.
+  ///
+  /// When generating the PHI node of the non-affine region in %polly.nonaffB,
+  /// incoming edges from outside the region are combined into a single branch
+  /// from %polly.nonaffB.entry which has as incoming value the value reloaded
+  /// from the %phi.phiops stack slot. Incoming edges from within the region
+  /// refer to the copied instructions (%p.valC) and basic blocks
+  /// (%polly.nonaffC) of the non-affine region.
+  ///
   /// @param Stmt       The statement to code generate.
   /// @param PHI        The original PHI we copy.
   /// @param PHICopy    The copy of @p PHI.
   /// @param IncomingBB An incoming block of @p PHI.
   /// @param LTS        A map from old loops to new induction variables as
   /// SCEVs.
   void addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, PHINode *PHICopy,
                        BasicBlock *IncomingBB, LoopToScevMapT &LTS);

polly/trunk/lib/CodeGen/BlockGenerators.cpp

void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
   BasicBlock *BBCopy = BlockMap[IncomingBB];
   if (!BBCopy) {
     assert(StmtR->contains(IncomingBB) &&
            "Bad incoming block for PHI in non-affine region");
     IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
     return;
   }
 
-  Value *OpCopy = nullptr;
-  if (StmtR->contains(IncomingBB)) {
-    assert(RegionMaps.count(BBCopy) &&
-           "Incoming PHI block did not have a BBMap");
-    ValueMapT &BBCopyMap = RegionMaps[BBCopy];
+  assert(RegionMaps.count(BBCopy) && "Incoming PHI block did not have a BBMap");
 
+  Value *OpCopy = nullptr;
+
+  if (StmtR->contains(IncomingBB)) {
     Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
 
     // If the current insert block is different from the PHIs incoming block
     // change it, otherwise do not.
     auto IP = Builder.GetInsertPoint();
     if (IP->getParent() != BBCopy)
       Builder.SetInsertPoint(BBCopy->getTerminator());
     OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
     if (IP->getParent() != BBCopy)
       Builder.SetInsertPoint(&*IP);
   } else {
-
+    // All edges from outside the non-affine region become a single edge
+    // in the new copy of the non-affine region. Make sure to only add the
+    // corresponding edge the first time we encounter a basic block from
+    // outside the non-affine region.
     if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
       return;
 
-    Value *PHIOpAddr = getOrCreatePHIAlloca(PHI);
-    OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",
-                          BlockMap[IncomingBB]->getTerminator());
+    // Get the reloaded value.
+    OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt));
   }
 
   assert(OpCopy && "Incoming PHI value was not copied properly");
   assert(BBCopy && "Incoming PHI block was not copied properly");
   PHICopy->addIncoming(OpCopy, BBCopy);
 }
 
 void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,

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

 ; RUN: opt %loadPolly -S -polly-codegen < %s | FileCheck %s
 ;
 ; Verify we do not crash for this test case and additionally check the code
 ; that we generate for the %tmp PHI node in the non-affine region. This code
 ; is difficult to generate as some incoming edges are from basic blocks
 ; from within the region and others from basic blocks from outside of the
 ; non-affine region. As visible in the CHECK lines, the code we generate
 ; currently loads from the PHI twice in %polly.stmt.bb2.entry, which is
 ; something we should avoid.
 ;
 ; CHECK: polly.start
 
 ; CHECK: polly.stmt.bb2.entry:                             ; preds = %polly.start
 ; CHECK-NEXT:   %tmp.phiops.reload = load i32, i32* %tmp.phiops
-; CHECK-NEXT:   %tmp.phiops.reload2 = load i32, i32* %tmp.phiops
 ; CHECK-NEXT:   br label %polly.stmt.bb2
 
 ; CHECK: polly.stmt.bb2:                                   ; preds = %polly.stmt.bb2, %polly.stmt.bb2.entry
-; CHECK-NEXT:   %polly.tmp = phi i32 [ %tmp.phiops.reload2, %polly.stmt.bb2.entry ], [ %p_tmp4, %polly.stmt.bb2 ]
+; CHECK-NEXT:   %polly.tmp = phi i32 [ %tmp.phiops.reload, %polly.stmt.bb2.entry ], [ %p_tmp4, %polly.stmt.bb2 ]
 ; CHECK-NEXT:   %p_tmp3 = or i32 undef, undef
 ; CHECK-NEXT:   %p_tmp4 = udiv i32 %p_tmp3, 10
 ; CHECK-NEXT:   %p_tmp6 = icmp eq i8 undef, 0
 ; CHECK-NEXT:   br i1 %p_tmp6, label %polly.stmt.polly.merge_new_and_old.exit, label %polly.stmt.bb2
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @baz(i32 %before) {

polly/trunk/test/ScopInfo/out-of-scop-use-in-region-entry-phi-node-nonaffine-subregion.ll

 ;
 ; CHECK-LABEL: polly.start:
 ; CHECK:         store float %loop_carried.ph, float* %loop_carried.phiops
 ;
 ; CHECK-LABEL: polly.stmt.subregion_entry.entry:
 ; CHECK:         %loop_carried.phiops.reload = load float, float* %loop_carried.phiops
 ;
 ; CHECK-LABEL: polly.stmt.subregion_entry:
-; CHECK:         %polly.loop_carried = phi float [ %loop_carried.phiops.reload2, %polly.stmt.subregion_entry.entry ]
+; CHECK:         %polly.loop_carried = phi float [ %loop_carried.phiops.reload, %polly.stmt.subregion_entry.entry ]
 ; CHECK:         %p_newval = fadd float %polly.loop_carried, 1.000000e+00
 ;
 ; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
 ; CHECK:         %newval.final_reload = load float, float* %newval.s2a
 
 define void @func() {
 entry:
   br label %subregion_entry