[InstCombine] shrink switch conditions better (PR24766)

[spatel]

Summary

As noted in PR24766:
https://llvm.org/bugs/show_bug.cgi?id=24766#c2

...we're not doing a great job of optimizing/shrinking switch conditions in InstCombine. If we do better, we could remove bogus case statements.

Step 1 to solving this is to remove a hack that was added for the benefit of x86 codegen. It prevented shrinking the switch condition even to smaller legal types.

FWIW, I don't see any perf difference on test-suite on x86 with this change, and I'm not sure how the supposed extra zext x86 instructions would hurt anyway.

[hfinkel]

FWIW, I don't see any perf difference on test-suite on x86 with this change, and I'm not sure how the supposed extra zext x86 instructions would hurt anyway.

Okay, but I'm still hesitant to generate unnecessary instructions. Do we still end up with the unnecessary zext instructions with this patch?

lib/Transforms/InstCombine/InstructionCombining.cpp

2213

I think it would be better to refactor InstCombiner::ShouldChangeType to have a version that directly takes the bit widths. ShouldChangeType just calls getPrimitiveSizeInBits on the provided types anyway, and that prevents the need to speculatively call Type::getIntNTy.

[spatel]

Patch updated:
Use new version (r248170) of "ShouldChangeType()".

[spatel]

In D12965#249222, @hfinkel wrote:

Okay, but I'm still hesitant to generate unnecessary instructions. Do we still end up with the unnecessary zext instructions with this patch?

Yes, we're producing unnecessary zexts. Based on that comment in InstCombine, I thought this was just a quirk of x86 (possibly related to bug 22473), but it's a target-independent problem for SelectionDAGBuilder::visitSwitch(). It causes unnecessary mask instructions for PPC and ARM64 too:

Optimized lowered selection DAG: BB#8 'positive1:entry'
         t0: i32 = Register %vreg3
       t1: i32,ch = CopyFromReg t0, t0
     t2: i16 = truncate t1
     t3: i16 = Constant<1001>
     t4: ch = seteq
   t5: i1 = setcc t2, t3, t4

Type-legalized selection DAG: BB#8 'positive1:entry'
           t0: i32 = Register %vreg3
         t1: i32,ch = CopyFromReg t0, t0
         t15: i32 = Constant<65535>
       t16: i32 = and t1, t15
       t10: i32 = Constant<1001>
       t4: ch = seteq
     t11: i32 = setcc t16, t10, t4

I think the root problem is that I'm mixing up the legal types specified by the datalayout with the codegen definition of legality based on the register width. So I'm not sure if we should just hack around this limitation here in InstCombine's visitSwitchInst() or shrink as much as possible here without regard for legality and then fix it up in CodeGenPrepare?

[hfinkel]

In D12965#250155, @spatel wrote:

In D12965#249222, @hfinkel wrote:

Okay, but I'm still hesitant to generate unnecessary instructions. Do we still end up with the unnecessary zext instructions with this patch?

Yes, we're producing unnecessary zexts. Based on that comment in InstCombine, I thought this was just a quirk of x86 (possibly related to bug 22473), but it's a target-independent problem for SelectionDAGBuilder::visitSwitch(). It causes unnecessary mask instructions for PPC and ARM64 too:

Optimized lowered selection DAG: BB#8 'positive1:entry'
         t0: i32 = Register %vreg3
       t1: i32,ch = CopyFromReg t0, t0
     t2: i16 = truncate t1
     t3: i16 = Constant<1001>
     t4: ch = seteq
   t5: i1 = setcc t2, t3, t4

Type-legalized selection DAG: BB#8 'positive1:entry'
           t0: i32 = Register %vreg3
         t1: i32,ch = CopyFromReg t0, t0
         t15: i32 = Constant<65535>
       t16: i32 = and t1, t15
       t10: i32 = Constant<1001>
       t4: ch = seteq
     t11: i32 = setcc t16, t10, t4

I think the root problem is that I'm mixing up the legal types specified by the datalayout with the codegen definition of legality based on the register width. So I'm not sure if we should just hack around this limitation here in InstCombine's visitSwitchInst() or shrink as much as possible here without regard for legality and then fix it up in CodeGenPrepare?

On theoretical grounds, I favor the latter. We should shrink aggressively for our canonical form because smaller types convey the most information at the IR level; we tend to lose information when we promote. If we can do this, and then fix it up later based on actual target-type-legality information later, I think that's better.

[sanjoy]

Resigning from old patch to get it off my queue. Feel free to add me back if this is revived at some point.

[spatel]

Patch (finally) updated:
Sorry for letting this sit for so long.
We added the CGP safety harness in D13532 / rL251857 , so we're now free to shrink in InstCombine without regard for the target.

Note that we still don't catch the '9999' case that Nick mentioned in https://llvm.org/bugs/show_bug.cgi?id=24766#c2 ; I think there must be a hole in SimplifyCFG's EliminateDeadSwitchCases() or computeKnownBits() itself. I'll investigate that next.

[spatel]

In D12965#429864, @spatel wrote:

Note that we still don't catch the '9999' case that Nick mentioned in https://llvm.org/bugs/show_bug.cgi?id=24766#c2 ; I think there must be a hole in SimplifyCFG's EliminateDeadSwitchCases() or computeKnownBits() itself. I'll investigate that next.

A possible fix for that problem: D20275

[spatel]

Ping.

Note that D20275 / rL270222 used ComputeNumSignBits() to eliminate cases. We could probably do something similar here in InstCombine as a follow-on.

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[majnemer]

Hmm. My understanding was that InstCombine was not supposed to create IR with illegal types if it could help it.

[spatel]

In D12965#457658, @majnemer wrote:

Hmm. My understanding was that InstCombine was not supposed to create IR with illegal types if it could help it.

Do we state that anywhere? Should we make an exception for cases where we know that we have a fixup in a later pass (as we do for this in CGP)?

I was proceeding based on Hal's earlier comment:
"We should shrink aggressively for our canonical form because smaller types convey the most information at the IR level."

[majnemer]

In D12965#457687, @spatel wrote:

In D12965#457658, @majnemer wrote:

Hmm. My understanding was that InstCombine was not supposed to create IR with illegal types if it could help it.

Do we state that anywhere? Should we make an exception for cases where we know that we have a fixup in a later pass (as we do for this in CGP)?

I was proceeding based on Hal's earlier comment:
"We should shrink aggressively for our canonical form because smaller types convey the most information at the IR level."

https://github.com/llvm-mirror/llvm/blob/a2bdb6de81cd1de9daaeac9fa8bd24b6e0a48263/lib/Transforms/InstCombine/InstructionCombining.cpp#L91

[spatel]

In D12965#457693, @majnemer wrote:

In D12965#457687, @spatel wrote:

In D12965#457658, @majnemer wrote:

Hmm. My understanding was that InstCombine was not supposed to create IR with illegal types if it could help it.

Do we state that anywhere? Should we make an exception for cases where we know that we have a fixup in a later pass (as we do for this in CGP)?

I was proceeding based on Hal's earlier comment:
"We should shrink aggressively for our canonical form because smaller types convey the most information at the IR level."

https://github.com/llvm-mirror/llvm/blob/a2bdb6de81cd1de9daaeac9fa8bd24b6e0a48263/lib/Transforms/InstCombine/InstructionCombining.cpp#L91

Ha...I should've remembered that. I added the alternate flavor of that function for the earlier/weaker version of *this* patch!
So then we're on to my 2nd question: we have a safety mechanism in place for this transform; does that change the outcome?
I understand the general reluctance for weird types given the disaster potential, but I don't see the downside for this specific case.

Note that we already got SimplifyCFG to remove the dead case for the example in PR24766, but I wonder if this transform might come into play for something like PR27555:
https://llvm.org/bugs/show_bug.cgi?id=27555

[spatel]

Ping * 4.

[spatel]

Ping * 5.

[majnemer]

LGTM

lib/Transforms/InstCombine/InstructionCombining.cpp

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-extension instructions if the operand is
-  // truncated to i8 or i16.
+  // Shrink the condition operand if the new type is smaller than the old type.
+  // This may produce a non-standard type for the switch, but that's ok because
+  // the backend should extend back to a legal type for the target.
   bool TruncCond = false;
-  if (NewWidth > 0 && BitWidth > NewWidth &&
-      NewWidth >= DL.getLargestLegalIntTypeSize()) {
+  if (NewWidth > 0 && NewWidth < BitWidth) {
     TruncCond = true;
     IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
     Builder->SetInsertPoint(&SI);
-    Value *NewCond = Builder->CreateTrunc(SI.getCondition(), Ty, "trunc");
+    Value *NewCond = Builder->CreateTrunc(Cond, Ty, "trunc");
     SI.setCondition(NewCond);
 
     for (auto &C : SI.cases())
       static_cast<SwitchInst::CaseIt *>(&C)->setValue(ConstantInt::get(
           SI.getContext(), C.getCaseValue()->getValue().trunc(NewWidth)));
   }
 
   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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Vary legal integer types in data layout.
 ; RUN: opt < %s -instcombine -S -default-data-layout=n32    | FileCheck %s --check-prefix=ALL --check-prefix=CHECK32
 ; RUN: opt < %s -instcombine -S -default-data-layout=n32:64 | FileCheck %s --check-prefix=ALL --check-prefix=CHECK64
 
+; In all cases, the data-layout is irrelevant. We should shrink as much as possible in InstCombine
+; and allow the backend to expand as much as needed to ensure optimal codegen for any target.
+
 define i32 @positive1(i64 %a) {
-; CHECK32-LABEL: @positive1(
-; CHECK32:         switch i32
-; CHECK32-NEXT:    i32 10, label %return
-; CHECK32-NEXT:    i32 100, label %sw.bb1
-; CHECK32-NEXT:    i32 1001, label %sw.bb2
-; CHECK32-NEXT:    ]
-;
-; CHECK64-LABEL: @positive1(
-; CHECK64:         switch i64
-; CHECK64-NEXT:    i64 10, label %return
-; CHECK64-NEXT:    i64 100, label %sw.bb1
-; CHECK64-NEXT:    i64 1001, label %sw.bb2
-; CHECK64-NEXT:    ]
+; ALL-LABEL: @positive1(
+; ALL:         switch i32
+; ALL-NEXT:    i32 10, label %return
+; ALL-NEXT:    i32 100, label %sw.bb1
+; ALL-NEXT:    i32 1001, label %sw.bb2
+; ALL-NEXT:    ]
 ;
 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
 }
 
 define i32 @negative1(i64 %a) {
-; CHECK32-LABEL: @negative1(
-; CHECK32:         switch i32
-; CHECK32-NEXT:    i32 -10, label %return
-; CHECK32-NEXT:    i32 -100, label %sw.bb1
-; CHECK32-NEXT:    i32 -1001, label %sw.bb2
-; CHECK32-NEXT:    ]
-;
-; CHECK64-LABEL: @negative1(
-; CHECK64:         switch i64
-; CHECK64-NEXT:    i64 -10, label %return
-; CHECK64-NEXT:    i64 -100, label %sw.bb1
-; CHECK64-NEXT:    i64 -1001, label %sw.bb2
-; CHECK64-NEXT:    ]
+; ALL-LABEL: @negative1(
+; ALL:         switch i32
+; ALL-NEXT:    i32 -10, label %return
+; ALL-NEXT:    i32 -100, label %sw.bb1
+; ALL-NEXT:    i32 -1001, label %sw.bb2
+; ALL-NEXT:    ]
 ;
 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
   ]
return:
   ret i32 %retval.0
 }
 
 ; Make sure to avoid assertion crashes and use the type before
 ; truncation to generate the sub constant expressions that leads
 ; to the recomputed condition.
 
 define void @trunc64to59(i64 %a) {
-; CHECK32-LABEL: @trunc64to59(
-; CHECK32:         switch i59
-; CHECK32-NEXT:    i59 0, label %sw.bb1
-; CHECK32-NEXT:    i59 18717182647723699, label %sw.bb2
-; CHECK32-NEXT:    ]
-;
-; CHECK64-LABEL: @trunc64to59(
-; CHECK64:         switch i64
-; CHECK64-NEXT:    i64 0, label %sw.bb1
-; CHECK64-NEXT:    i64 18717182647723699, label %sw.bb2
-; CHECK64-NEXT:    ]
+; ALL-LABEL: @trunc64to59(
+; ALL:         switch i59
+; ALL-NEXT:    i59 0, label %sw.bb1
+; ALL-NEXT:    i59 18717182647723699, label %sw.bb2
+; ALL-NEXT:    ]
 ;
 entry:
   %tmp0 = and i64 %a, 15
   %tmp1 = mul i64 %tmp0, -6425668444178048401
   %tmp2 = add i64 %tmp1, 5170979678563097242
   %tmp3 = mul i64 %tmp2, 1627972535142754813
   switch i64 %tmp3, label %sw.default [
   i64 847514119312061490, label %sw.bb1

test/Transforms/InstCombine/pr21651.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 define void @PR21651() {
 ; CHECK-LABEL: @PR21651(
-; CHECK-NEXT:    switch i2 0, label %out [
-; CHECK-NEXT:    i2 0, label %out
-; CHECK-NEXT:    i2 1, label %out
+; CHECK-NEXT:    switch i1 false, label %out [
+; CHECK-NEXT:    i1 false, label %out
+; CHECK-NEXT:    i1 true, label %out
 ; CHECK-NEXT:    ]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret void
 ;
   switch i2 0, label %out [
   i2 0, label %out
   i2 1, label %out
   ]
 
 out:
   ret void
 }