Teach SimplifyCFG to Create Switches from InstCombine Or Mask'd Comparisons

[tjablin]

Summary

I am following Chandler's suggestion by teaching SimplifyCFG to recognize the Or-Mask trick that InstCombine uses to reduce the number of comparisons. Specifically, InstCombine can turn:

(i == 5334 || i == 5335)

into:

((i | 1) == 5335)

SimplifyCFG was already able to detect the pattern:

(i == 5334 || i == 5335)

to:

((i & -2) == 5334)

This patch supersedes D21315 and resolves PR27555 (https://llvm.org/bugs/show_bug.cgi?id=27555).

[chandlerc]

Wow, thanks for digging into this.

Can you separate out the bug fix for the current pattern matching and send that first? Then we can have a second patch that just extends to handle the new pattern(s).

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

492–493

Why not use m_APInt?

496

Please clang-format this.

514

Ditto.

[tjablin]

I have split out and applied the bug fix and m_ConstantInt => m_APInt portions of the past separately. What remains is just the new functionality.

[tjablin]

Ping?

[majnemer]

LGTM

[cycheng]

Committed r273639 (On behalf of Tom)

lib/Transforms/Utils/SimplifyCFG.cpp

if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
          ONE  : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63);
          x    : BITVECTOR(64);
          y    : BITVECTOR(64);
          z    : BITVECTOR(64);
          mask : BITVECTOR(64) = BVSHL(ONE, z);
          QUERY( (y & ~mask = y) =>
                 ((x & ~mask = y) <=> (x = y OR x = (y |  mask)))
          );
+         QUERY( (y |  mask = y) =>
+                ((x |  mask = y) <=> (x = y OR x = (y & ~mask)))
+         );
       */
 
       // Please note that each pattern must be a dual implication (<--> or
       // iff). One directional implication can create spurious matches. If the
       // implication is only one-way, an unsatisfiable condition on the left
       // side can imply a satisfiable condition on the right side. Dual
       // implication ensures that satisfiable conditions are transformed to
       // other satisfiable conditions and unsatisfiable conditions are
if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
       // (x & -2) == 3 --> (x == 3 || x == 2)
 
       // Pattern match a special case:
       /*
         QUERY( (y & ~mask = y) =>
                ((x & ~mask = y) <=> (x = y OR x = (y |  mask)))
         );
       */
       if (match(ICI->getOperand(0),
                 m_And(m_Value(RHSVal), m_APInt(RHSC)))) {
         APInt Mask = ~*RHSC;
         if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) {
           // If we already have a value for the switch, it has to match!
           if (!setValueOnce(RHSVal))
             return false;
 
           Vals.push_back(C);
           Vals.push_back(
               ConstantInt::get(C->getContext(),
                                C->getValue() | Mask));
           UsedICmps++;
           return true;
         }
       }
 
+      // Pattern match a special case:
+      /*
+         QUERY( (y |  mask = y) =>
+                ((x |  mask = y) <=> (x = y OR x = (y & ~mask)))
+         );       
+      */
+      if (match(ICI->getOperand(0),
+                m_Or(m_Value(RHSVal), m_APInt(RHSC)))) {
+        APInt Mask = *RHSC;
+        if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) {
+          // If we already have a value for the switch, it has to match!
+           if (!setValueOnce(RHSVal))
+             return false;
+ 
+           Vals.push_back(C);
+           Vals.push_back(ConstantInt::get(C->getContext(),
+                                           C->getValue() & ~Mask));
+           UsedICmps++;
+           return true;
+        }
+      }
+
       // If we already have a value for the switch, it has to match!
       if (!setValueOnce(ICI->getOperand(0)))
         return false;
 
       UsedICmps++;
       Vals.push_back(C);
       return ICI->getOperand(0);
     }

test/Transforms/SimplifyCFG/switch_create.ll

define void @test20(i32 %arg) {
   br i1 %pred, label %if, label %else
 
 if:
   call void @foo1()
   ret void
 
 else:
   ret void
+}
+
+; Form a switch when or'ing a power of two
+; CHECK-LABEL: define void @test21
+; CHECK: i32 32, label %else
+; CHECK: i32 13, label %else
+; CHECK: i32 12, label %else
+define void @test21(i32 %arg) {
+  %and = or i32 %arg, 1
+  %cmp1 = icmp ne i32 %and, 13
+  %cmp2 = icmp ne i32 %arg, 32
+  %pred = and i1 %cmp1, %cmp2
+  br i1 %pred, label %if, label %else
+
+if:
+  call void @foo1()
+  ret void
+
+else:
+  ret void
+}
+
+; Since %cmp1 is always false, a switch is never formed
+; CHECK-LABEL: define void @test22
+; CHECK-NOT: switch
+; CHECK: ret void
+define void @test22(i32 %arg) {
+  %and = or i32 %arg, 1
+  %cmp1 = icmp ne i32 %and, 12
+  %cmp2 = icmp ne i32 %arg, 32
+  %pred = and i1 %cmp1, %cmp2
+  br i1 %pred, label %if, label %else
+
+if:
+  call void @foo1()
+  ret void
+
+else:
+  ret void
 }
 No newline at end of file