[InstCombineCasts] Add cost model to decide which truncates are worth removing

[igor-laevsky]

Summary

This is based on http://reviews.llvm.org/D12012

Currently InstCombiner will eliminate truncate only when entire expression tree can be evaluated in a narrower type without adding additional instructions.

However there are some cases when it is profitable to evaluate expression in a narrower type, even if it will require adding additional instructions. (See test case in the patch)

In this patch I split "CanEvaluateTruncated" function into two: "EstimateCostForTruncatedEvaluation" and "IsProfitableToEvaluateTruncated". First one is basically an old "CanEvaluateTruncated", but it also calculates cost for truncating expression tree. Second function calls "EstimateCostForTruncatedEvaluation" and compares cost of the truncation with constant threshold. Cost model is very simple - we want to truncate expression tree only if we will remove more instructions than we will add.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

341

Currently cost model is simple -> Currently, the cost model is simple

457

This does not seem right. Arbitrary instructions don't commute with truncation, by which I mean trunc(arbitrary(x, y)) != arbitrary(trunc(x), trunc(y)) in general. Also, for many instructions you'd hit the llvm_unreachable in the default case in EvaluateInDifferentType.

[igor-laevsky]

lib/Transforms/InstCombine/InstCombineCasts.cpp

457

Thanks for taking a look.

You are right, but I am not relying on trunc's associativity. When we visit unknown instruction, we will stop looking deeper into expression tree and truncate it right before problematic instruction. For example say we have something like this:
add i64 (i64 bad_inst1(a, b), i64 bad_inst2(c, d))
EstimateCostForTruncatedEvaluation we will return true for this expression, and EvaluateInDifferentType will do the following transform:
add i32 (trunc (i64 bad_inst1(a, b)), trunc (i64 bad_inst2(c, d)))

Regarding your second question. Sorry, I should have better emphasise that this revision is based on http://reviews.llvm.org/D12012 which extends default case in EvaluateInDifferentType to allow it to insert truncates.

lib/Transforms/InstCombine/InstCombineCasts.cpp

if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
         ShouldChangeType(CI.getType(), Src->getType()))
       if (Instruction *NV = FoldOpIntoPhi(CI))
         return NV;
   }
 
   return nullptr;
 }
 
-/// CanEvaluateTruncated - Return true if we can evaluate the specified
-/// expression tree as type Ty instead of its larger type, and arrive with the
-/// same value.  This is used by code that tries to eliminate truncates.
-///
-/// Ty will always be a type smaller than V.  We should return true if trunc(V)
-/// can be computed by computing V in the smaller type.  If V is an instruction,
-/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
-/// makes sense if x and y can be efficiently truncated.
-///
-/// This function works on both vectors and scalars.
-///
-static bool CanEvaluateTruncated(Value *V, Type *Ty, InstCombiner &IC,
+/// EstimateCostForTruncatedEvaluation - Return true if we can evaluate the
+/// specified expression tree as type Ty instead of its larger type, and
+/// arrive at the same value. Also calculate cost of this transformation
+/// and store it into the "Cost" argument.
+/// Currently cost model is simple - increase cost by one for each additional
+/// instruction required, decrease cost by one for each instruction that
+/// will be removed after truncating expression tree.
+bool InstCombiner::EstimateCostForTruncatedEvaluation(int &Cost, Value *V,
+                                                      Type *Ty,
                                                       Instruction *CxtI) {
   // We can always evaluate constants in another type.
   if (isa<Constant>(V))
     return true;
 
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return false;
 
   Type *OrigTy = V->getType();
 
-  // If this is an extension from the dest type, we can eliminate it, even if it
-  // has multiple uses.
+  // If this is an extension from the dest type, we will not need any additional
+  // instructions to truncate it, even if it has multiple uses.
   if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) &&
-      I->getOperand(0)->getType() == Ty)
+      I->getOperand(0)->getType() == Ty) {
+
+    // Add a cost bonus if we can eliminate this cast.
+    if (I->hasOneUse())
+      Cost -= 1;
+
     return true;
+  }
 
   // We can't extend or shrink something that has multiple uses: doing so would
   // require duplicating the instruction in general, which isn't profitable.
   if (!I->hasOneUse()) return false;
 
   unsigned Opc = I->getOpcode();
   switch (Opc) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor:
     // These operators can all arbitrarily be extended or truncated.
-    return CanEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
-           CanEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
+    return EstimateCostForTruncatedEvaluation(Cost, I->getOperand(0), Ty,
+                                              CxtI) &&
+           EstimateCostForTruncatedEvaluation(Cost, I->getOperand(1), Ty, CxtI);
 
   case Instruction::UDiv:
   case Instruction::URem: {
     // UDiv and URem can be truncated if all the truncated bits are zero.
     uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
     uint32_t BitWidth = Ty->getScalarSizeInBits();
     if (BitWidth < OrigBitWidth) {
       APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
-      if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) &&
-          IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) {
-        return CanEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
-               CanEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
+      if (MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) &&
+          MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) {
+        return EstimateCostForTruncatedEvaluation(Cost, I->getOperand(0), Ty,
+                                                  CxtI) &&
+               EstimateCostForTruncatedEvaluation(Cost, I->getOperand(1), Ty,
+                                                  CxtI);
       }
     }
     break;
   }
   case Instruction::Shl:
     // If we are truncating the result of this SHL, and if it's a shift of a
     // constant amount, we can always perform a SHL in a smaller type.
     if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
       uint32_t BitWidth = Ty->getScalarSizeInBits();
       if (CI->getLimitedValue(BitWidth) < BitWidth)
-        return CanEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
+        return EstimateCostForTruncatedEvaluation(Cost, I->getOperand(0), Ty,
+                                                  CxtI);
     }
     break;
   case Instruction::LShr:
     // If this is a truncate of a logical shr, we can truncate it to a smaller
     // lshr iff we know that the bits we would otherwise be shifting in are
     // already zeros.
     if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
       uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
       uint32_t BitWidth = Ty->getScalarSizeInBits();
-      if (IC.MaskedValueIsZero(I->getOperand(0),
+      if (MaskedValueIsZero(I->getOperand(0),
             APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth), 0, CxtI) &&
           CI->getLimitedValue(BitWidth) < BitWidth) {
-        return CanEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
+        return EstimateCostForTruncatedEvaluation(Cost, I->getOperand(0), Ty,
+                                                  CxtI);
       }
     }
     break;
   case Instruction::Trunc:
     // trunc(trunc(x)) -> trunc(x)
     return true;
   case Instruction::ZExt:
   case Instruction::SExt:
     // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
     // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest
     return true;
   case Instruction::Select: {
     SelectInst *SI = cast<SelectInst>(I);
-    return CanEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) &&
-           CanEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI);
+    return EstimateCostForTruncatedEvaluation(Cost, SI->getTrueValue(), Ty,
+                                              CxtI) &&
+           EstimateCostForTruncatedEvaluation(Cost, SI->getFalseValue(), Ty,
+                                              CxtI);
   }
   case Instruction::PHI: {
     // We can change a phi if we can change all operands.  Note that we never
     // get into trouble with cyclic PHIs here because we only consider
     // instructions with a single use.
     PHINode *PN = cast<PHINode>(I);
     for (Value *IncValue : PN->incoming_values())
-      if (!CanEvaluateTruncated(IncValue, Ty, IC, CxtI))
+      if (!EstimateCostForTruncatedEvaluation(Cost, IncValue, Ty, CxtI))
         return false;
     return true;
   }
-  default:
-    // TODO: Can handle more cases here.
-    break;
+
   }
 
+  // This is not a recognized instruction, but we can always truncate it by
+  // adding additional explicit trunc.
+  Cost += 1;
+  return true;
+}
+
+/// IsProfitableToEvaluateTruncated - Given the expression tree starting with
+/// truncate instruction return true if it would be profitable to remove
+/// this truncate and evaluate expression in a narrower type. This is used by
+/// code that tries to eliminate truncates.
+///
+/// This function works on both vectors and scalars.
+///
+bool InstCombiner::IsProfitableToEvaluateTruncated(TruncInst *Trunc) {
+  Type *DestTy = Trunc->getType(), *SrcTy = Trunc->getOperand(0)->getType();
+
+  // Only truncate if the dest type is a simple type, don't convert the
+  // expression tree to something weird like i93 unless the source is also
+  // strange.
+  if (!DestTy->isVectorTy() && !ShouldChangeType(SrcTy, DestTy))
     return false;
+
+  int Cost = 0;
+  bool CanTruncate = EstimateCostForTruncatedEvaluation(
+      Cost, Trunc->getOperand(0), DestTy, Trunc);
+
+  // Threshold picked in a way that it will allow only cases when number of
+  // removed instructions is strictly greater than number of the additional
+  // instructions required.
+  const int CostThreshold = 1;
+  return CanTruncate && Cost < CostThreshold;
 }
 
 Instruction *InstCombiner::visitTrunc(TruncInst &CI) {
   if (Instruction *Result = commonCastTransforms(CI))
     return Result;
 
   // Test if the trunc is the user of a select which is part of a
   // minimum or maximum operation. If so, don't do any more simplification.
   // Even simplifying demanded bits can break the canonical form of a 
   // min/max.
   Value *LHS, *RHS;
   if (SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)))
     if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN)
       return nullptr;
   
   // See if we can simplify any instructions used by the input whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(CI))
     return &CI;
 
   Value *Src = CI.getOperand(0);
-  Type *DestTy = CI.getType(), *SrcTy = Src->getType();
+  Type *DestTy = CI.getType();
 
   // Attempt to truncate the entire input expression tree to the destination
-  // type.   Only do this if the dest type is a simple type, don't convert the
-  // expression tree to something weird like i93 unless the source is also
-  // strange.
-  if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) &&
-      CanEvaluateTruncated(Src, DestTy, *this, &CI)) {
-
+  // type.
+  if (IsProfitableToEvaluateTruncated(&CI)) {
     // If this cast is a truncate, evaluting in a different type always
     // eliminates the cast, so it is always a win.
     DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
           " to avoid cast: " << CI << '\n');
     Value *Res = EvaluateInDifferentType(Src, DestTy, false);
     assert(Res->getType() == DestTy);
     return ReplaceInstUsesWith(CI, Res);
   }

lib/Transforms/InstCombine/InstCombineInternal.h

Value *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, bool isSigned,
                          bool Inside);
   Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
   Instruction *MatchBSwap(BinaryOperator &I);
   bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
   Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
   Instruction *SimplifyMemSet(MemSetInst *MI);
 
   Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
+  bool EstimateCostForTruncatedEvaluation(int &Cost, Value *V, Type *Ty,
+                                          Instruction *CxtI);
+  bool IsProfitableToEvaluateTruncated(TruncInst *Trunc);
 
   /// \brief Returns a value X such that Val = X * Scale, or null if none.
   ///
   /// If the multiplication is known not to overflow then NoSignedWrap is set.
   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 };
 
 } // end namespace llvm.
 
 #undef DEBUG_TYPE
 
 #endif

test/Transforms/InstCombine/trunc.ll

define i8 @test10(i32 %X) {
   %Y = trunc i32 %X to i8
   %Z = and i8 %Y, 42
   ret i8 %Z
 ; CHECK-LABEL: @test10(
 ; CHECK: trunc
 ; CHECK: and
 ; CHECK: ret
 }
+
+; Here by eliminating trunc we can get rid of a redundant zext. However
+; additional trunc should also be inserted. Check that we consider this
+; transform to be profitable.
+define void @test11(i8 *%res, i32* %t, i8* %s) {
+ entry:
+  %m = load i32, i32* %t
+  %n = load i8, i8* %s
+
+  %n.i32 = zext i8 %n to i32
+  %v = sub i32 %n.i32, %m
+  %v.i8 = trunc i32 %v to i8
+
+  store i8 %v.i8, i8* %res
+  ret void
+; CHECK-LABEL: @test11(
+; CHECK: %m = load i32, i32* %t
+; CHECK: %m.truncated = trunc i32 %m to i8
+; CHECK: %n = load i8, i8* %s
+; CHECK: %v = sub i8 %n, %m.truncated
+; CHECK: store i8 %v, i8* %res
+}
+
+; Here by eliminating trunc we will not remove any additional instructions.
+; Check that this case considered to be not profitable.
+define void @test12(i8 *%res, i32* %t, i32* %s) {
+ entry:
+  %m = load i32, i32* %t
+  %n = load i32, i32* %s
+
+  %v = sub i32 %n, %m
+  %v.i8 = trunc i32 %v to i8
+
+  store i8 %v.i8, i8* %res
+  ret void
+; CHECK-LABEL: @test12(
+; CHECK: %m = load i32, i32* %t
+; CHECK: %n = load i32, i32* %s
+; CHECK: %v = sub i32 %n, %m
+; CHECK: %v.i8 = trunc i32 %v to i8
+; CHECK: store i8 %v.i8, i8* %res
+}
+
+; Check that casts with multiple uses are considered not possible to remove.
+declare void @use.test13(i32)
+define void @test13(i8 *%res, i32* %t, i8* %s) {
+ entry:
+  %m = load i32, i32* %t
+  %n = load i8, i8* %s
+
+  %n.i32 = zext i8 %n to i32
+  %v = sub i32 %n.i32, %m
+  %v.i8 = trunc i32 %v to i8
+
+  store i8 %v.i8, i8* %res
+  call void @use.test13(i32 %n.i32)
+  ret void
+; CHECK-LABEL: @test13(
+; CHECK: %m = load i32, i32* %t
+; CHECK: %n = load i8, i8* %s
+; CHECK: %n.i32 = zext i8 %n to i32
+; CHECK: %v = sub i32 %n.i32, %m
+; CHECK: %v.i8 = trunc i32 %v to i8
+; CHECK: store i8 %v.i8, i8* %res
+; CHECK: call void @use.test13(i32 %n.i32)
+; CHECK: ret void
+}