[InstCombine] Fix visitSwitchInst to use right operand types for sub cstexpr.

[bruno]

Summary

visitSwitchInst generates SUB constant expressions to recompute the switch
condition. When truncating the condition to a smaller type, SUB expressions
should use the previous type (before trunc) for both operands. This fixes an
assertion crash.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

2107–2108

InstCombine methods are supposed to return the original instruction if they modify the instruction. It seems visitSwitchInst isn't doing this here.

2120–2123

Isn't this equivalent to:
Constant *LHS = ConstantExpr::getSExt(CaseVal, BitWidth);

2124

Might as well make this Constant * since you are changing the right hand side.

2124

Might as well put the pointer on the right hand side.

[bruno]

lib/Transforms/InstCombine/InstructionCombining.cpp

2107–2108

Good catch, in case where Trunc instruction is generated but no ADD instruction is found we're returning null. Will address that in a next patch since this is not related to this fix.

2120–2123

Likely, but only after a series of constant fold lookups/calls for the common cases, I guess the current version is uglier but faster.

2124

Ok!

[bruno]

Updated patch!

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

2122

Is there any particular reason why you chose to sext instead of zext?

[bruno]

lib/Transforms/InstCombine/InstructionCombining.cpp

2122

Being conservative to perform the right extension when coming back from the truncated negative condition cases. Would that be somehow redundant in this scenario?

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

2122

I don't think it will actually be faster.

ConstantExpr::getSExt(CaseVal, Cond->getType()) will call getFoldedCast which will call ConstantFoldCastInstruction which will do the following:

case Instruction::SExt:
  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
    uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
    return ConstantInt::get(V->getContext(),
                            CI->getValue().sext(BitWidth));
  }

Seems like it will do the exact same thing. No table lookups involved.

[bruno]

lib/Transforms/InstCombine/InstructionCombining.cpp

2122

---

As I said before, it takes additional calls for every case statement. We don't need to bikeshed on that though, I guess that won't make that much difference either.

[bruno]

Updated patch after David's comments/suggestions.

[majnemer]

LGTM with the above changes and one comment (I'd make it inline but parts of the diff are missing).

Would it be reasonable to zext instead of sext if the bits you trimmed off were all zeros?

lib/Transforms/InstCombine/InstructionCombining.cpp

2121

ConstantExpr::getSExt returns a Constant *, the cast<Constant> should be redundant.

2122–2123

Likewise. Also, please stick the pointer on the RHS.

[bruno]

Use zext when appropriate as suggested and committed in r224574.

Thanks David.

lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
   }
 
   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.
+  bool TruncCond = false;
   if (DL && 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(
           SI.getContext(), C.getCaseValue()->getValue().trunc(NewWidth)));
+    TruncCond = true;
   }
 
   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();
-          Constant* NewCaseVal = ConstantExpr::getSub(cast<Constant>(CaseVal),
-                                                      AddRHS);
+          Constant *LHS = cast<Constant>(
+              TruncCond ? ConstantInt::get(SI.getContext(),
+                                           CaseVal->getValue().sext(BitWidth))
+                        : CaseVal);
+          Constant* NewCaseVal = cast<Constant>(
+              ConstantExpr::getSub(LHS, cast<Constant>(AddRHS)));
           assert(isa<ConstantInt>(NewCaseVal) &&
                  "Result of expression should be constant");
           i.setValue(cast<ConstantInt>(NewCaseVal));
         }
         SI.setCondition(I->getOperand(0));
         Worklist.Add(I);
         return &SI;
       }

test/Transforms/InstCombine/narrow-switch.ll

 
 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
 }
+
+; Make sure to avoid assertion crashes and use the type before
+; truncation to generate the sub constant expressions that leads
+; to the recomputed condition.
+;
+; CHECK-LABEL: @trunc64to59
+; CHECK: switch i59
+; CHECK: i59 0, label
+; CHECK: i59 18717182647723699, label
+
+define void @trunc64to59(i64 %a) {
+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
+    i64 866231301959785189, label %sw.bb2
+  ]
+
+sw.bb1:
+  br label %sw.default
+
+sw.bb2:
+  br label %sw.default
+
+sw.default:
+  ret void
+}