InstCombine: Narrow switch instruction operands using known bits

[ahatanak]

Summary

This patch adds an inst-combine optimization which narrows the operands of a switch instruction if the upper bits are known to be all 1 or 0.

For example, since the upper 32-bits are all zero in the following switch instruction,

%and = and i64 %a, 4294967295
switch i64 %and, label %sw.default [

i64 10, label %return
i64 100, label %sw.bb1
i64 1001, label %sw.bb2

]

we can turn it into a 32-bit instruction:

switch i32 %and, label %sw.default [

i32 10, label %return
i32 100, label %sw.bb1
i32 1001, label %sw.bb2

]

[zinovy.nis]

I'd recommend to add @majnemer as reviewer.

[ahatanak]

add @majnemer as reviewer.

[pete]

I think it makes sense to truncate down to the largest legal type as you've done here. Anything lower than that gets tricky to reason about the quality of code in the backends.

LGTM.

[ahatanak]

Thanks Pete. Committed r219832.

lib/Transforms/InstCombine/InstructionCombining.cpp

if (IPred == ICmpInst::ICMP_NE  || IPred == ICmpInst::ICMP_ULE ||
       return &BI;
     }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
   Value *Cond = SI.getCondition();
+  unsigned BitWidth = cast<IntegerType>(Cond->getType())->getBitWidth();
+  APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+  computeKnownBits(Cond, KnownZero, KnownOne);
+  unsigned LeadingKnownZeros = KnownZero.countLeadingOnes();
+  unsigned LeadingKnownOnes = KnownOne.countLeadingOnes();
+
+  // Compute the number of leading bits we can ignore.
+  for (auto &C : SI.cases()) {
+    LeadingKnownZeros = std::min(
+        LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros());
+    LeadingKnownOnes = std::min(
+        LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes());
+  }
+
+  unsigned NewWidth = BitWidth - std::max(LeadingKnownZeros, LeadingKnownOnes);
+
+  // Truncate the condition operand if the new type is equal to or larger than
+  // the largest legal integer type. We need to be conservative here since
+  // x86 generates redundant zero-extenstion instructions if the operand is
+  // truncated to i8 or i16.
+  if (BitWidth > NewWidth && NewWidth >= DL->getLargestLegalIntTypeSize()) {
+    IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
+    Builder->SetInsertPoint(&SI);
+    Value *NewCond = Builder->CreateTrunc(SI.getCondition(), Ty, "trunc");
+    SI.setCondition(NewCond);
+
+    for (auto &C : SI.cases())
+      static_cast<SwitchInst::CaseIt *>(&C)->setValue(
+          ConstantInt::get(Ty, C.getCaseValue()->getValue().getZExtValue()));
+  }
+
   if (Instruction *I = dyn_cast<Instruction>(Cond)) {
     if (I->getOpcode() == Instruction::Add)
       if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
         // change 'switch (X+4) case 1:' into 'switch (X) case -3'
         // Skip the first item since that's the default case.
         for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end();
              i != e; ++i) {
           ConstantInt* CaseVal = i.getCaseValue();

test/Transforms/InstCombine/narrow-switch.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32"
+
+; CHECK-LABEL: define i32 @positive1
+; CHECK: switch i32
+; CHECK: i32 10, label
+; CHECK: i32 100, label
+; CHECK: i32 1001, label
+
+define i32 @positive1(i64 %a) {
+entry:
+  %and = and i64 %a, 4294967295
+  switch i64 %and, label %sw.default [
+    i64 10, label %return
+    i64 100, label %sw.bb1
+    i64 1001, label %sw.bb2
+  ]
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 24, %sw.default ], [ 123, %sw.bb2 ], [ 213, %sw.bb1 ], [ 231, %entry ]
+  ret i32 %retval.0
+}
+
+; CHECK-LABEL: define i32 @negative1
+; CHECK: switch i32
+; CHECK: i32 -10, label
+; CHECK: i32 -100, label
+; CHECK: i32 -1001, label
+
+define i32 @negative1(i64 %a) {
+entry:
+  %or = or i64 %a, -4294967296
+  switch i64 %or, label %sw.default [
+    i64 -10, label %return
+    i64 -100, label %sw.bb1
+    i64 -1001, label %sw.bb2
+  ]
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 24, %sw.default ], [ 123, %sw.bb2 ], [ 213, %sw.bb1 ], [ 231, %entry ]
+  ret i32 %retval.0
+}