[GVNHoist] Fix: PR35222 gvn-hoist incorrectly erases load

[hiraditya]

Summary

CHI should only be inserted to a basic block properly dominating its successor.

[efriedma]

lib/Transforms/Scalar/GVNHoist.cpp

802 ↗

(On Diff #122030)

I haven't reviewed in detail, but I'm skeptical this check actually does the right thing in general. A "Loop*" is specifically a loop with a single entry point, so this check won't handle irreducible control flow correctly.

[efriedma]

lib/Transforms/Scalar/GVNHoist.cpp

802 ↗

(On Diff #122030)

Looking a little more, it might not be relevant... I'm not following the algorithm for insertion points, and I don't really have time to dig deeper, so please ignore me. :)

[hiraditya]

Added a testcase for irreducible control flow.

[hiraditya]

lib/Transforms/Scalar/GVNHoist.cpp

802 ↗

(On Diff #122030)

Thanks!

[• dberlin]

lib/Transforms/Scalar/GVNHoist.cpp

801 ↗

(On Diff #122030)

I don't think this check is overall safe.

The definition of loop here is not going to be sufficient either.

I think if you want to avoid spurious CHI's, you need to do the equivalent of what you see in "A Practical Improvement to the Partial Redundancy Elimination in SSA Form" (https://sites.google.com/site/jongsoopark/home/ssapre.pdf)

which precisely defines which will be unnecessary and the safety conditions.

[hiraditya]

lib/Transforms/Scalar/GVNHoist.cpp

801 ↗

(On Diff #122030)

Thanks for the reference, I'll study the paper and find out if they have some extra safety checks.

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

for (const auto &R : Ranks) {
       for (unsigned i = 0; i < V.size(); ++i) {
         InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
       }
       // Insert empty CHI node for this VN. This is used to factor out
       // basic blocks where the ANTIC can potentially change.
       for (auto IDFB : IDFBlocks) { // TODO: Prune out useless CHI insertions.
         for (unsigned i = 0; i < V.size(); ++i) {
           CHIArg C = {VN, nullptr, nullptr};
-          if (DT->dominates(IDFB, V[i]->getParent())) { // Ignore spurious PDFs.
-            // InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
+           // Ignore spurious PDFs.
+          if (DT->properlyDominates(IDFB, V[i]->getParent())) {
             OutValue[IDFB].push_back(C);
             DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
                          << ", for Insn: " << *V[i]);
           }
         }
       }
     }
 

llvm/trunk/test/Transforms/GVNHoist/pr35222-hoist-load.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+; CHECK: load
+; CHECK: load
+; Check that the load is not hoisted because the call can potentially
+; modify the global
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+@heap = external global i32, align 4
+
+define i32 @build_tree() unnamed_addr {
+entry:
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %tmp9 = load i32, i32* @heap, align 4
+  %cmp = call i1 @pqdownheap(i32 %tmp9)
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  %tmp20 = load i32, i32* @heap, align 4
+  ret i32 %tmp20
+}
+
+declare i1 @pqdownheap(i32)