[GVN] Prevent ScalarPRE from hoisting across instructions that don't pass control flow to successors

[mkazantsev]

Summary

This is to address a problem similar to those in D37460 for Scalar PRE. We should not
PRE across an instruction that may not pass execution to its successor unless it is safe
to speculatively execute it.

[mkazantsev]

Ping

[mkazantsev]

Ping

[efriedma]

LGTM

[efriedma]

lib/Transforms/Scalar/GVN.cpp

2214

Err, wait, sorry, I wasn't reading carefully enough.

What are you trying to check for here? I can't see why it matters if "P" has an implicit control flow instruction; we insert the new instruction at the end of the predecessor, so implicit control flow isn't a problem unless the terminator is an invoke.

[mkazantsev]

lib/Transforms/Scalar/GVN.cpp

2214

You're right, I misinterpreted this part. Invoke is also not a problem because if the terminator was an invoke, then we have a critical edge, and we don't PRE across critical edges without splitting them. This check is obsolete, I'll remove it.

[mkazantsev]

lib/Transforms/Scalar/GVN.cpp

2214

It also seems that it's OK to do it if we don't need to insert a new instruction, i.e. when NumWithout == 0.

[mkazantsev]

1. Removed over-restrictive check;
2. Allowed PRE across implicit control flow if it only takes to insert a Phi from existing instructons and not create new instructions.
3. Added a new test against item 2.

[efriedma]

lib/Transforms/Scalar/GVN.cpp

2261

"prevent us from that" isn't correct grammar. And you misspelled "implicit".

Maybe move the comment inside the if statement?

[mkazantsev]

Ping

[mkazantsev]

@efriedma , can I have it landed? :)

[efriedma]

LGTM

lib/Transforms/Scalar/GVN.cpp

bool GVN::performScalarPRE(Instruction *CurInst) {
   unsigned NumWithout = 0;
   BasicBlock *PREPred = nullptr;
   BasicBlock *CurrentBlock = CurInst->getParent();
 
   SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
   for (BasicBlock *P : predecessors(CurrentBlock)) {
     // We're not interested in PRE where blocks with predecessors that are
     // not reachable.
     if (!DT->isReachableFromEntry(P)) {
       NumWithout = 2;
       break;
     }
     // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and
     // when CurInst has operand defined in CurrentBlock (so it may be defined
     // by phi in the loop header).
     if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&
         llvm::any_of(CurInst->operands(), [&](const Use &U) {
if (NumWithout > 1 || NumWith == 0)
     return false;
 
   // We may have a case where all predecessors have the instruction,
   // and we just need to insert a phi node. Otherwise, perform
   // insertion.
   Instruction *PREInstr = nullptr;
 
   if (NumWithout != 0) {
+    bool IsSafeToSpeculativelyExecute = isSafeToSpeculativelyExecute(CurInst);
+    if (!IsSafeToSpeculativelyExecute) {
+      // It is only valid to insert a new instruction if the current instruction
+      // is always executed. An instruction with implicit control flow could
+      // prevent us from doing it. If we cannot speculate the execution, then
+      // PRE should be prohibited.
+      auto It = FirstImplicitControlFlowInsts.find(CurrentBlock);
+      if (It != FirstImplicitControlFlowInsts.end()) {
+        assert(It->second->getParent() == CurrentBlock &&
+               "Implicit control flow map broken?");
+        if (OI->dominates(It->second, CurInst))
+          return false;
+      }
+    }
+
     // Don't do PRE across indirect branch.
     if (isa<IndirectBrInst>(PREPred->getTerminator()))
       return false;
 
     // We can't do PRE safely on a critical edge, so instead we schedule
     // the edge to be split and perform the PRE the next time we iterate
     // on the function.
     unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);

test/Transforms/GVN/PRE/local-pre.ll

 ; RUN: opt < %s -gvn -enable-pre -S | FileCheck %s
 
+declare void @may_exit() nounwind
+
+declare void @may_exit_1(i32) nounwind
+
 define i32 @main(i32 %p, i32 %q) {
+
+; CHECK-LABEL: @main(
+
 block1:
     %cmp = icmp eq i32 %p, %q 
   br i1 %cmp, label %block2, label %block3
 
 block2:
  %a = add i32 %p, 1
  br label %block4
 
 block3:
   br label %block4
 ; CHECK: %.pre = add i32 %p, 1
 ; CHECK-NEXT: br label %block4
 
 block4:
   %b = add i32 %p, 1
   ret i32 %b
 ; CHECK: %b.pre-phi = phi i32 [ %.pre, %block3 ], [ %a, %block2 ]
 ; CHECK-NEXT: ret i32 %b.pre-phi
 }
+
+; Don't PRE across implicit control flow.
+define i32 @test2(i32 %p, i32 %q) {
+
+; CHECK-LABEL: @test2
+; CHECK: block1:
+
+block1:
+  %cmp = icmp eq i32 %p, %q
+  br i1 %cmp, label %block2, label %block3
+
+block2:
+ %a = sdiv i32 %p, %q
+ br label %block4
+
+block3:
+  br label %block4
+
+; CHECK: block4:
+; CHECK-NEXT: call void @may_exit(
+; CHECK-NEXT: %b = sdiv
+; CHECK-NEXT: ret i32 %b
+
+block4:
+  call void @may_exit() nounwind
+  %b = sdiv i32 %p, %q
+  ret i32 %b
+}
+
+; Don't PRE across implicit control flow.
+define i32 @test3(i32 %p, i32 %q, i1 %r) {
+
+; CHECK-LABEL: @test3
+; CHECK: block1:
+
+block1:
+  br i1 %r, label %block2, label %block3
+
+block2:
+ %a = sdiv i32 %p, %q
+ br label %block4
+
+block3:
+  br label %block4
+
+block4:
+
+; CHECK: block4:
+; CHECK-NEXT: phi i32
+; CHECK-NEXT: call void @may_exit_1(
+; CHECK-NEXT: %b = sdiv
+; CHECK-NEXT: ret i32 %b
+
+  %phi = phi i32 [ 0, %block3 ], [ %a, %block2 ]
+  call void @may_exit_1(i32 %phi) nounwind
+  %b = sdiv i32 %p, %q
+  ret i32 %b
+
+}
+
+; It's OK to PRE an instruction that is guaranteed to be safe to execute
+; speculatively.
+; TODO: Does it make any sense in this case?
+define i32 @test4(i32 %p, i32 %q) {
+
+; CHECK-LABEL: @test4
+; CHECK: block1:
+
+block1:
+  %cmp = icmp eq i32 %p, %q
+  br i1 %cmp, label %block2, label %block3
+
+block2:
+ %a = sdiv i32 %p, 6
+ br label %block4
+
+block3:
+  br label %block4
+
+; CHECK: block4:
+; CHECK-NEXT: %b.pre-phi = phi i32
+; CHECK-NEXT: call void @may_exit(
+; CHECK-NEXT: ret i32 %b
+
+block4:
+  call void @may_exit() nounwind
+  %b = sdiv i32 %p, 6
+  ret i32 %b
+}
+
+; It is OK to PRE across implicit control flow if we don't insert new
+; instructions.
+define i32 @test5(i1 %cond, i32 %p, i32 %q) {
+
+; CHECK-LABEL: @test5
+; CHECK: block1:
+
+block1:
+  br i1 %cond, label %block2, label %block3
+
+block2:
+ %a = sdiv i32 %p, %q
+ br label %block4
+
+block3:
+  %b = sdiv i32 %p, %q
+  br label %block4
+
+; CHECK: block4:
+; CHECK-NEXT: %c.pre-phi = phi i32 [ %b, %block3 ], [ %a, %block2 ]
+; CHECK-NEXT: call void @may_exit()
+; CHECK-NEXT: ret i32 %c.pre-phi
+
+block4:
+  call void @may_exit() nounwind
+  %c = sdiv i32 %p, %q
+  ret i32 %c
+}