[OPENMP] llvm.loop.vectorize.enable metadata are lost after critical edge splitting

[zinovy.nis]

Summary

Critical edge splitting called by GVN and Loop Rotation leads to losing of llvm.loop.vectorize.enable metadata for loops as critical edge splitting replaces a branch, corresponding to the loop latch, with a new one.

My patch clones loop latch metadata to a new latch branch thus fixing the issue.

I also had to add LoopInfo analysis for GVN, as it's needed for latch metadata cloning.

[jdoerfert]

I'm not completely sure but this sounds similar to what I did a couple
of weeks ago (http://reviews.llvm.org/D5344) however I didn't force
LoopInfo to be present but rather handled the case it isn't. For the
record, I don't know the benefits/drawbacks for either.

If we use your patch we could possibly add my test cases.

• msg-15942-344.dat219 BDownload

[zinovy.nis]

@jdoerfert, looks you are right, our patches are similar. But seems that your patch will not work when edge splitting is called from GVN, as currently LoopInfo analysis for GVN is not turned on. Is it so?

[jdoerfert]

Correct, GVN is not a "definitive" user of LoopInfo, thus running GVN and critical edge splitting will remove the loop annotations, however that behaviour is at least well defined. In contrast calling BreakCriticalEdges from another "non LoopInfo user pass" might result in invalid loop annotations in your patch.

If we never want to remove metadata information we shouldn't add LoopInfo to the passes GVN needs, but to the passes BreakCriticalEdges needs. That way we can always rely on LoopInfo to "do the right thing" in BreakCriticalEdges without the need to remove annotations for the lack of information.

[zinovy.nis]

OK, if we agree to add AU.addRequired<LoopInfo>(); for BreakCriticalEdges while removing it from GVN I'd be satisfied.

UPD. Sorry, it will not help as GVN doesn't call BreakCriticalEdges pass directly, but just calls a method from BreakCriticalEdges.cpp

[jdoerfert]

In D5539#10, @zinovy.nis wrote:

OK, if we agree to add AU.addRequired<LoopInfo>(); for BreakCriticalEdges while removing it from GVN I'd be satisfied.

UPD. Sorry, it will not help as GVN doesn't call BreakCriticalEdges pass directly, but just calls a method from BreakCriticalEdges.cpp

Yeah, I just saw that too. So you need to add LoopInfo to the passes GVN needs as long as it calls the SplitCriticalEdge directly.

[zinovy.nis]

Yes, I had to do that.

[atrick]

If the problem here is that GVN is dropping the loop.vectortize metadata, adding LoopInfo as a required pass seems fundamentally wrong. Critical edge splitting is supposed to be something any pass can do on-the-fly without extra analysis. Of course, the whole problem would have been simpler if we just required annotated loops to have split edges to begin with, but that issue is out-of-scope for this bug.

I have some basic questions:

• I haven't been paying close attention to the loop.vectorize metadata design. Why does it need to be on the loop backedge branch? It doesn't seem hard to discover the metadata on the last conditional branch leading to the backedge.

• Even if you do need to move the metadata to a different branch, why is LoopInfo required? Is it because we can't tell if we're splitting the backedge or the loop exit? DomTree would often be sufficient to tell them apart.

[jdoerfert]

In D5539#13, @atrick wrote:

If the problem here is that GVN is dropping the loop.vectortize metadata, adding LoopInfo as a required pass seems fundamentally wrong. Critical edge splitting is supposed to be something any pass can do on-the-fly without extra analysis. Of course, the whole problem would have been simpler if we just required annotated loops to have split edges to begin with, but that issue is out-of-scope for this bug.

GVN (and other transformations) use the static SplitCiticalEdge function instead of the BreakCriticalEdges pass. This function does rely on the Pass * argument to get LoopInfo and the DomTreeWrapperPass to update information. However, loop metadata isn't considered so far. Both patches try to fix that issue.

I have some basic questions:

• I haven't been paying close attention to the loop.vectorize metadata design. Why does it need to be on the loop backedge branch? It doesn't seem hard to discover the metadata on the last conditional branch leading to the backedge.

I cannot help you here, I don't know why it is designed like this.

• Even if you do need to move the metadata to a different branch, why is LoopInfo required? Is it because we can't tell if we're splitting the backedge or the loop exit? DomTree would often be sufficient to tell them apart.

Even if we would rely on the DomTree instead of the LoopInfo we have the same problems.

1. Either musst be available over the Pass * argument of SplitCriticalEdges
2. The SplitCriticlEdges need to be patched to use the available pass in order to preserve the loop metadata.
3. We need to invalidate the metadata instead of making it invalid.

[atrick]

Is it incorrect to leave the loop metadata on the original branch when splitting the edge?

GVN already requires DomTree, so no change to the pipeline is needed if you use it.

In splitCriticalEdges, if LoopInfo is available you can use it. Otherwise you can use the DomTree. If the DomTree check fails (ie. both targets dominate the latch) then just invalidate the metadata.

I think there is a fundamental problem with the metadata design--it's ridiculous to assume that any pass that splits critical edges has LoopInfo--but that should at least workaround your problem.

[hfinkel]

• Original Message -----

From: "Andrew Trick" <[e-mail]>
To: "zinovy nis" <[e-mail]>, [e-mail], [e-mail]
Cc: [e-mail]
Sent: Tuesday, September 30, 2014 4:29:08 PM
Subject: Re: [PATCH] [OPENMP] llvm.loop.vectorize.enable metadata are lost after critical edge splitting

Is it incorrect to leave the loop metadata on the original branch
when splitting the edge?

GVN already requires DomTree, so no change to the pipeline is needed
if you use it.

In splitCriticalEdges, if LoopInfo is available you can use it.
Otherwise you can use the DomTree. If the DomTree check fails (ie.
both targets dominate the latch) then just invalidate the metadata.

I think there is a fundamental problem with the metadata design--it's
ridiculous to assume that any pass that splits critical edges has
LoopInfo--but that should at least workaround your problem.

Is that a flaw in the design of the metadata, or just in the fact that the utility functions used to manipulate the metadata are part of LoopInfo?

-Hal

http://reviews.llvm.org/D5539

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[jdoerfert]

In D5539#16, @hfinkel wrote:

• Original Message -----

From: "Andrew Trick" <[e-mail]>
To: "zinovy nis" <[e-mail]>, [e-mail], [e-mail]
Cc: [e-mail]
Sent: Tuesday, September 30, 2014 4:29:08 PM
Subject: Re: [PATCH] [OPENMP] llvm.loop.vectorize.enable metadata are lost after critical edge splitting

Is it incorrect to leave the loop metadata on the original branch
when splitting the edge?

GVN already requires DomTree, so no change to the pipeline is needed
if you use it.

In splitCriticalEdges, if LoopInfo is available you can use it.
Otherwise you can use the DomTree. If the DomTree check fails (ie.
both targets dominate the latch) then just invalidate the metadata.

I think there is a fundamental problem with the metadata design--it's
ridiculous to assume that any pass that splits critical edges has
LoopInfo--but that should at least workaround your problem.

Is that a flaw in the design of the metadata, or just in the fact that the utility functions used to manipulate the metadata are part of LoopInfo?

-Hal

In my opininion the real probelem is the static SplitCriticalEdge function which is called with a black box Pass * instead of the two analysis passes it could actually use to update information.
It is intransparent to the user what passes should be provided to ensure the best result.

The "utility functions to manipulate the metadata" are actually only available in this and the other pending patch http://reviews.llvm.org/D5344 and both currently use LoopInfo. However, we could update them to handle metadata also with the DomTree. In any case the other patch already invalidates metadata if no analysis is present.

[jdoerfert]

In D5539#15, @atrick wrote:

Is it incorrect to leave the loop metadata on the original branch when splitting the edge?

Yes, sometimes. At least if you considere llvm.loop metadata on non loop backedges to be invalid.

GVN already requires DomTree, so no change to the pipeline is needed if you use it.

We could implement the handling of metadata for both cases, if DomTree or LoopInfo are accessable via the Pass * given, then we do not need to change GVN.

In splitCriticalEdges, if LoopInfo is available you can use it. Otherwise you can use the DomTree. If the DomTree check fails (ie. both targets dominate the latch) then just invalidate the metadata.

I could update my patch if we decide to go this way. It would probably require the least change outside the actual SplitCriticalEdge function.

I think there is a fundamental problem with the metadata design--it's ridiculous to assume that any pass that splits critical edges has LoopInfo--but that should at least workaround your problem.

True, but some analysis is needed in order to preserve the metadata in a meaningful way and we always can invalide it as a fallback.

[chandlerc]

Leaving this review to Andy and Hal as they have abetter understanding of the issues around the loop metadata.

One thing I'll note -- it really does seem bad to require LoopInfo here....

[• dberlin]

Err, shouldn't loopinfo just be preserved here rather than required, like BreakCriticalEdges does?
If llvm.loop.vectorize.enable is considered part of the loopinfo pass, adding it as preserved and updating it if available, should have zero cost, unlike making it required.

SplitCriticalEdge already can take LoopInfo as an option nowadays, (see Options.LI), so you don't need to add it again. SplitCriticalEdge is already using it to maintain loopsimplify form. You should just update it if it's around

lib/Transforms/Scalar/GVN.cpp

 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetLibraryInfo.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Analysis/LoopPass.h"
 #include <vector>
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "gvn"
 
 STATISTIC(NumGVNInstr,  "Number of instructions deleted");
 STATISTIC(NumGVNLoad,   "Number of loads deleted");
void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<TargetLibraryInfo>();
       if (!NoLoads)
         AU.addRequired<MemoryDependenceAnalysis>();
       AU.addRequired<AliasAnalysis>();
 
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addPreserved<AliasAnalysis>();
+      AU.addRequired<LoopInfo>();
     }
 
 
     // Helper fuctions of redundant load elimination 
     bool processLoad(LoadInst *L);
     bool processNonLocalLoad(LoadInst *L);
     void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, 
                                  AvailValInBlkVect &ValuesPerBlock,

 }
 
 INITIALIZE_PASS_BEGIN(GVN, "gvn", "Global Value Numbering", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 INITIALIZE_PASS_END(GVN, "gvn", "Global Value Numbering", false, false)
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void GVN::dump(DenseMap<uint32_t, Value*>& d) {
   errs() << "{\n";
   for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
        E = d.end(); I != E; ++I) {
       errs() << I->first << "\n";

lib/Transforms/Utils/BreakCriticalEdges.cpp

BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
   if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return nullptr;
 
   assert(!isa<IndirectBrInst>(TI) &&
          "Cannot split critical edge from IndirectBrInst");
 
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
 
+  LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : nullptr;
+
+  Loop *TIBBLoop = LI ? LI->getLoopFor(TIBB) : nullptr;
+  Loop *DestBBLoop = LI ? LI->getLoopFor(DestBB) : nullptr;
+
+  MDNode *TILoopMD = TIBBLoop ? TIBBLoop->getLoopID() : nullptr;
+  MDNode *DestLoopMD = DestBBLoop ? DestBBLoop->getLoopID() : nullptr;
+
   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
   // it in this generic function.
   if (DestBB->isLandingPad()) return nullptr;
 
   // Create a new basic block, linking it into the CFG.
   BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
                       TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
   // Create our unconditional branch.
for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
       // Remove an entry for TIBB from DestBB phi nodes.
       DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
 
       // We found another edge to DestBB, go to NewBB instead.
       TI->setSuccessor(i, NewBB);
     }
   }
 
-
-
   // If we don't have a pass object, we can't update anything...
   if (!P) return NewBB;
 
   DominatorTreeWrapperPass *DTWP =
       P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>();
 
   // If we have nothing to update, just return.
   if (!DT && !LI)
     return NewBB;
 
   // Now update analysis information.  Since the only predecessor of NewBB is
   // the TIBB, TIBB clearly dominates NewBB.  TIBB usually doesn't dominate
   // anything, as there are other successors of DestBB.  However, if all other
if (Loop *TIL = LI->getLoopFor(TIBB)) {
       // available, which means that all predecessors of loop exit blocks
       // are within the loop. Without LoopSimplify form, it would be
       // necessary to insert a new phi.
       assert((!P->mustPreserveAnalysisID(LCSSAID) ||
               P->mustPreserveAnalysisID(LoopSimplifyID)) &&
              "SplitCriticalEdge doesn't know how to update LCCSA form "
              "without LoopSimplify!");
     }
+    // Loop metadata are stored in the loop latch branch.
+    // If loops latches were changed let's update new latches metadata.
+    if (TILoopMD)
+      TIBBLoop->setLoopID(TILoopMD);
+    if (DestLoopMD && DestBBLoop != TIBBLoop)
+      DestBBLoop->setLoopID(DestLoopMD);
   }
 
   return NewBB;
 }

test/Transforms/LoopVectorize/vect.omp.persistence.gvn.ll

+; RUN: opt < %s -basicaa -gvn -S 2>&1 | FileCheck %s
+
+; CHECK-LABEL: @test_gvn
+; CHECK-LABEL: for.body:
+; Find a branch to critical edge
+; CHECK: br {{.*}} %[[CE:[^_ ]+]]_crit_edge
+; BB where critical edge was found
+; CHECK: [[CE]]_crit_edge:
+; Check that OMP SIMD branch metadata survived after critical edge splitting
+; CHECK: br label %for.body, !llvm.loop !0
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;
+; Ensure that "llvm.loop.vectorize.enable" metadata were not lost after GVN splitted critical edges.
+; In past splitting critical edges was leading to clearing that metadata.
+;
+
+define i64 @test_gvn(i64* nocapture readonly %a, i64* nocapture readonly %b) {
+entry:
+    %0 = load i64* %b, align 4, !llvm.mem.parallel_loop_access !0
+    br label %for.body
+for.body:
+    %i.0 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+    %arrayidx = getelementptr inbounds i64* %a, i64 %i.0
+    %1 = load i64* %arrayidx, align 4, !llvm.mem.parallel_loop_access !1
+    %arrayidx2 = getelementptr inbounds i64* %b, i64 %i.0
+    %2 = load i64* %arrayidx2, align 4, !llvm.mem.parallel_loop_access !1
+    %cmp3 = icmp sgt i64 %1, %2
+    %add16 = select i1 %cmp3, i64 0, i64 %2
+    %inc = add nsw i64 %i.0, 1
+    %add = add nsw i64 %0, %inc
+    %cmp = icmp slt i64 %i.0, %add
+    br i1 %cmp, label %for.body, label %for.end, !llvm.loop !0
+for.end:
+    ret i64 %inc
+}
+
+!0 = metadata !{metadata !0, metadata !1}
+!1 = metadata !{metadata !"llvm.loop.vectorize.enable", i1 true}