[InstCombine] do not shrink switch conditions to illegal types (PR29009)

[dendibakh]

Summary

This patch makes shrinking switch conditions less aggressive which was introduced by https://reviews.llvm.org/rL274233.

[lebedev.ri]

lib/Transforms/InstCombine/InstructionCombining.cpp

2485–2486

The comments here and in the beginning of the test file say the same thing.
I remember there were a few mails about this on the mailing list.
Were you able to come to an conclusion that this is *certainly* not a backend problem?

[dendibakh]

lib/Transforms/InstCombine/InstructionCombining.cpp

2485–2486

Let me quote @spatel:

The backend isn't likely to produce good code for that anytime soon

That's why we decide to fix it on InstCombine, not the backend.
Anyway, I think I need to change the comment as well.

[lebedev.ri]

lib/Transforms/InstCombine/InstructionCombining.cpp

2485–2486

Okay, makes sense i guess.
Please also make sure to file a bug for backends, and for this regression,
and highly ideally make sure that there are backend tests showing their deficiency.

[dendibakh]

Changed the comment.

[lebedev.ri]

Please do reference the backend bug№ in the comments.

test/Transforms/InstCombine/narrow-switch.ll

6–7

Here too.

[spatel]

To provide more background/motivation for why I don't think we will solve the underlying problem soon, we can fork this example into its own bug:
https://bugs.llvm.org/show_bug.cgi?id=29009#c4

I said that was an instcombine opportunity in that bug comment, but that was a mistake. It probably requires a GVN-level-of-complexity to see that kind of equivalence between the 2 different-sized masked values. But AFAICT, neither -gvn nor -newgvn optimizes that today (so we should file a 2nd bug to track that as an IR opportunity).

I'm not sure where/how we would catch that in the backend, but that's the kind of code we would see after legalization of non-power-of-2 types.

So that's the reason I think we're justified in limiting this transform with shouldChangeType(). In an ideal world, we could let instcombine go wild with illegal types, but as this example shows, getting optimal codegen from that is likely difficult (and it might not be handled well by other IR passes too), so that's why instcombine has this limitation.

[dendibakh]

Fixed comments.

[lebedev.ri]

Looks good.

lib/Transforms/InstCombine/InstructionCombining.cpp

2485–2486

Minor: when you fix the inline comment, please do mark it as fixed (the checkbox -------------------------------------------^)

[dendibakh]

@spatel, @lebedev.ri, if no other objections, can you please commit it on my behalf?

[spatel]

LGTM - I can commit this for you.

[spatel]

Bugs filed as a result of this patch:
https://bugs.llvm.org/show_bug.cgi?id=39569
https://bugs.llvm.org/show_bug.cgi?id=39578

lib/Transforms/InstCombine/InstructionCombining.cpp

LeadingKnownZeros = std::min(
         LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros());
     LeadingKnownOnes = std::min(
         LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes());
   }
 
   unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
 
   // 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.
-  if (NewWidth > 0 && NewWidth < Known.getBitWidth()) {
+  if (NewWidth > 0 && NewWidth < Known.getBitWidth() &&
+      shouldChangeType(Known.getBitWidth(), NewWidth)) {
     IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
     Builder.SetInsertPoint(&SI);
     Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");
     SI.setCondition(NewCond);
 
     for (auto Case : SI.cases()) {
       APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
       Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));

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 -data-layout=n32    | FileCheck %s --check-prefix=ALL --check-prefix=CHECK32
 ; RUN: opt < %s -instcombine -S -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) {
 ; 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:    ]

 }
 
 ; 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) {
 ; ALL-LABEL: @trunc64to59(
-; ALL:         switch i59
-; ALL-NEXT:    i59 0, label %sw.bb1
-; ALL-NEXT:    i59 18717182647723699, label %sw.bb2
-; ALL-NEXT:    ]
+; ALL-CHECK32:         switch i59
+; ALL-CHECK32-NEXT:    i59 0, label %sw.bb1
+; ALL-CHECK32-NEXT:    i59 18717182647723699, label %sw.bb2
+; ALL-CHECK32-NEXT:    ]
+; ALL-CHECK64:         switch i64
+; ALL-CHECK64-NEXT:    i64 0, label %sw.bb1
+; ALL-CHECK64-NEXT:    i64 18717182647723699, label %sw.bb2
+; ALL-CHECK64-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
sw.epilog:                                        ; preds = %entry
   store i32 113, i32* %retval, align 4
   br label %return
 
 return:                                           ; preds = %sw.epilog, %sw.bb2,
   %rval = load i32, i32* %retval, align 4
   ret i32 %rval
 }
 
+; https://llvm.org/bugs/show_bug.cgi?id=29009
+
+@a = global i32 0, align 4
+@njob = global i32 0, align 4
+
+declare i32 @goo()
+
+; Make sure we do not shrink to illegal types (i3 in this case)
+; if original type is legal (i32 in this case)
+
+define void @PR29009() {
+; ALL-LABEL: @PR29009(
+; ALL:         switch i32
+; ALL-NEXT:    i32 0, label
+; ALL-NEXT:    i32 3, label
+; ALL-NEXT:    ]
+;
+  br label %1
+
+; <label>:1:                                      ; preds = %10, %0
+  %2 = load volatile i32, i32* @njob, align 4
+  %3 = icmp ne i32 %2, 0
+  br i1 %3, label %4, label %11
+
+; <label>:4:                                      ; preds = %1
+  %5 = call i32 @goo()
+  %6 = and i32 %5, 7
+  switch i32 %6, label %7 [
+    i32 0, label %8
+    i32 3, label %9
+  ]
+
+; <label>:7:                                      ; preds = %4
+  store i32 6, i32* @a, align 4
+  br label %10
+
+; <label>:8:                                      ; preds = %4
+  store i32 1, i32* @a, align 4
+  br label %10
+
+; <label>:9:                                      ; preds = %4
+  store i32 2, i32* @a, align 4
+  br label %10
+
+; <label>:10:                                     ; preds = %13, %12, %11, %10, %9, %8, %7
+  br label %1
+
+; <label>:11:                                     ; preds = %1
+  ret void
+}
+