[InstCombine] Allow InstCombine to merge adjacent guards

[mkazantsev]

Summary

If there are two adjacent guards with different conditions, we can
remove one of them and include its condition into the condition of
another one. This patch allows InstCombine to merge them by the
following pattern:

guard(a); guard(b) -> guard(a & b).

[sanjoy]

lib/Transforms/InstCombine/InstCombineCalls.cpp

3269

There's a subtle problem here -- we can transform

guard(a) [ "deopt"(X) ]
guard(b) [ "deopt"(Y) ]

to

;; Widen the first guard
guard(a & b) [ "deopt"(X) ]

but not to

;; Widen the second guard
guard(a & b) [ "deopt"(Y) ]

since the deopt state of the second guard (represented as "Y" here
for simplicity) may have been optimized under the assumption that a
is true.

For instance, say we started with

guard(a) [ "deopt"(a) ]
guard(b) [ "deopt"(a) ]

which first got optimized to

guard(a) [ "deopt"(a) ]
guard(b) [ "deopt"(true) ]

and then due to this change is optimized to

;; guard(a) [ "deopt"(a) ]
guard(a && b) [ "deopt"(true) ]

Now if a is false at runtime then the expected behavior was to
deoptimize with the deopt state (a) == (false), but in the
optimized program we will deoptimize with the deopt state (true).

The right transform here is to widen the first guard, not the second
one.

3273

I'd not bother with the !a && !b => !(a && b). I think it is better to leave it as !a && !b (i.e. not special case m_Not at all), and have InstCombine re-canonicalize it (in a later iteration) to !(a || b) if that's more canonical.

[mkazantsev]

Fixed

[sanjoy]

lgtm! Checking in on your behalf.

[mkazantsev]

lib/Transforms/InstCombine/InstCombineCalls.cpp

3269

Thanks for pointing that out: wasn't obvious indeed.

3273

Yeah, it is actually done by DeMorgan's Law transformation. :)

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::experimental_gc_relocate: {
     // TODO: bitcast(relocate(p)) -> relocate(bitcast(p))
     // Canonicalize on the type from the uses to the defs
 
     // TODO: relocate((gep p, C, C2, ...)) -> gep(relocate(p), C, C2, ...)
     break;
   }
 
   case Intrinsic::experimental_guard: {
-    Value *IIOperand = II->getArgOperand(0);
+    // Is this guard followed by another guard?
+    Value *NextInst = II->getNextNode();
+    Value *NextCond = nullptr;
+    if (match(NextInst,
+              m_Intrinsic<Intrinsic::experimental_guard>(m_Value(NextCond)))) {
+      Value *CurrCond = II->getArgOperand(0);
 
       // Remove a guard if it is immediately followed by an identical guard.
-    if (match(II->getNextNode(),
-              m_Intrinsic<Intrinsic::experimental_guard>(m_Specific(IIOperand))))
+      if (CurrCond == NextCond)
         return eraseInstFromFunction(*II);
+
+      // Otherwise we try to widen the next guard and remove the current.
+      Value *A, *B, *NewCond;
+      if (match(CurrCond, m_Not(m_Value(A))) &&
+          match(NextCond, m_Not(m_Value(B))))
+        // Canonicalize guard(!a); guard(!b) -> guard(!(a | b)).
+        NewCond = Builder->CreateNot(Builder->CreateOr(A, B));
+      else
+        // Otherwise canonicalize guard(a); guard(b) -> guard(a & b).
+        NewCond = Builder->CreateAnd(CurrCond, NextCond);
+
+      cast<IntrinsicInst>(NextInst)->setArgOperand(0, NewCond);
+      return eraseInstFromFunction(*II);
+    }
     break;
   }
   }
 
   return visitCallSite(II);
 }
 
 // Fence instruction simplification

test/Transforms/InstCombine/call-guard.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
-define void @test_guard_adjacent(i1 %A) {
-; CHECK-LABEL: @test_guard_adjacent(
+define void @test_guard_adjacent_same_cond(i1 %A) {
+; CHECK-LABEL: @test_guard_adjacent_same_cond(
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %A) [ "deopt"() ]
 ; CHECK-NEXT:    ret void
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
   ret void
 }
 
-define void @test_guard_adjacent_neg(i1 %A, i1 %B) {
-; CHECK-LABEL: @test_guard_adjacent_neg(
-; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %A) [ "deopt"() ]
-; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %B) [ "deopt"() ]
+define void @test_guard_adjacent_diff_cond(i1 %A, i1 %B, i1 %C) {
+; CHECK-LABEL: @test_guard_adjacent_diff_cond(
+; CHECK-NEXT:    %1 = and i1 %A, %B
+; CHECK-NEXT:    %2 = and i1 %1, %C
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %2, i32 789) [ "deopt"() ]
 ; CHECK-NEXT:    ret void
-  call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
-  call void(i1, ...) @llvm.experimental.guard( i1 %B )[ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard( i1 %A, i32 123 )[ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard( i1 %B, i32 456 )[ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard( i1 %C, i32 789 )[ "deopt"() ]
+  ret void
+}
+
+define void @test_guard_adjacent_not_cond(i1 %A, i1 %B) {
+; CHECK-LABEL: @test_guard_adjacent_not_cond(
+; CHECK-NEXT:    %1 = or i1 %A, %B
+; CHECK-NEXT:    %2 = xor i1 %1, true
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %2, i32 456) [ "deopt"() ]
+; CHECK-NEXT:    ret void
+  %C = xor i1 %A, true
+  %D = xor i1 %B, true
+  call void(i1, ...) @llvm.experimental.guard( i1 %C, i32 123 )[ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard( i1 %D, i32 456 )[ "deopt"() ]
   ret void
 }