Enhance instcombine to reason more strongly about promoting computation

that feeds into a zext, similar to the patch I did yesterday for sext.
There is a lot of room for extension beyond this patch.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92962 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 144 insertions, 51 deletions

diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp
index d49c5a1..6fbe795 100644
--- a/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -167,7 +167,8 @@ Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
 static bool CanEvaluateInDifferentType(Value *V, const Type *Ty,
                                        unsigned CastOpc,
                                        unsigned &NumCastsRemoved) {
-  assert(CastOpc == Instruction::ZExt || CastOpc == Instruction::Trunc);
+  // FIXME: Eliminate CastOpc
+  assert(CastOpc == Instruction::Trunc);
   
   // We can always evaluate constants in another type.
   if (isa<Constant>(V))
@@ -293,6 +294,111 @@ static bool CanEvaluateInDifferentType(Value *V, const Type *Ty,
   return false;
 }
 
+/// GetLeadingZeros - Compute the number of known-zero leading bits.
+static unsigned GetLeadingZeros(Value *V, const TargetData *TD) {
+  unsigned Bits = V->getType()->getScalarSizeInBits();
+  APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
+  ComputeMaskedBits(V, APInt::getAllOnesValue(Bits), KnownZero, KnownOne, TD);
+  return KnownZero.countLeadingOnes();
+}
+
+/// CanEvaluateZExtd - Determine if the specified value can be computed in the
+/// specified wider type and produce the same low bits.  If not, return -1.  If
+/// it is possible, return the number of high bits that are known to be zero in
+/// the promoted value.
+static int CanEvaluateZExtd(Value *V, const Type *Ty,unsigned &NumCastsRemoved,
+                            const TargetData *TD) {
+  const Type *OrigTy = V->getType();
+
+  if (isa<Constant>(V)) {
+    unsigned Extended = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
+
+    // Constants can always be zero ext'd, even if it requires a ConstantExpr.
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+      return Extended + CI->getValue().countLeadingZeros();
+    return Extended;
+  }
+  
+  Instruction *I = dyn_cast<Instruction>(V);
+  if (!I) return -1;
+  
+  // If the input is a truncate from the destination type, we can trivially
+  // eliminate it, and this will remove a cast overall.
+  if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
+    // If the first operand is itself a cast, and is eliminable, do not count
+    // this as an eliminable cast.  We would prefer to eliminate those two
+    // casts first.
+    if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
+      ++NumCastsRemoved;
+    
+    // Figure out the number of known-zero bits coming in.
+    return GetLeadingZeros(I->getOperand(0), TD);
+  }
+  
+  // 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 -1;
+  
+  int Tmp1, Tmp2;
+  unsigned Opc = I->getOpcode();
+  switch (Opc) {
+  case Instruction::And:
+    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
+    if (Tmp1 == -1) return -1;
+    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
+    if (Tmp2 == -1) return -1;
+    return std::max(Tmp1, Tmp2);
+  case Instruction::Or:
+  case Instruction::Xor:
+    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
+    if (Tmp1 == -1) return -1;
+    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
+    return std::min(Tmp1, Tmp2);
+
+  case Instruction::Add:
+  case Instruction::Sub:
+  case Instruction::Mul:
+    Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
+    if (Tmp1 == -1) return -1;
+    Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
+    if (Tmp2 == -1) return -1;
+    return 0;
+      
+  //case Instruction::Shl:
+  //case Instruction::LShr:
+  case Instruction::ZExt:
+    // zext(zext(x)) -> zext(x).  Since we're replacing it, it isn't eliminated.
+    Tmp1 = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
+    return GetLeadingZeros(I, TD)+Tmp1;
+      
+  //case Instruction::SExt:  zext(sext(x)) -> sext(x) with no upper bits known.
+  //case Instruction::Trunc:
+  case Instruction::Select:
+    Tmp1 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
+    if (Tmp1 == -1) return -1;
+    Tmp2 = CanEvaluateZExtd(I->getOperand(2), Ty, NumCastsRemoved, TD);
+    return std::min(Tmp1, Tmp2);
+      
+  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);
+    int Result = CanEvaluateZExtd(PN->getIncomingValue(0), Ty,
+                                  NumCastsRemoved, TD);
+    for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
+      if (Result == -1) return -1;
+      Tmp1 = CanEvaluateZExtd(PN->getIncomingValue(i), Ty, NumCastsRemoved, TD);
+      Result = std::min(Result, Tmp1);
+    }
+    return Result;
+  }
+  default:
+    // TODO: Can handle more cases here.
+    return -1;
+  }
+}
+
 /// CanEvaluateSExtd - Return true if we can take the specified value
 /// and return it as type Ty without inserting any new casts and without
 /// changing the value of the common low bits.  This is used by code that tries
@@ -585,29 +691,55 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
   if (!isa<VectorType>(DestTy) && !ShouldChangeType(SrcTy, DestTy))
     return 0;
   
+  uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
+  uint32_t DestBitSize = DestTy->getScalarSizeInBits();
+      
   // Attempt to propagate the cast into the instruction for int->int casts.
   unsigned NumCastsRemoved = 0;
   switch (CI.getOpcode()) {
   default: assert(0 && "not an integer cast");
-  case Instruction::Trunc:
+  case Instruction::Trunc: {
     if (!CanEvaluateInDifferentType(Src, DestTy,
                                     Instruction::Trunc, NumCastsRemoved))
       return 0;
       
     // If this cast is a truncate, evaluting in a different type always
     // eliminates the cast, so it is always a win.
-    break;
-  case Instruction::ZExt:
-    if (!CanEvaluateInDifferentType(Src, DestTy,
-                                    Instruction::ZExt, NumCastsRemoved))
-      return 0;
-      
+    DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
+          " to avoid cast: " << CI);
+    Value *Res = EvaluateInDifferentType(Src, DestTy, false);
+    assert(Res->getType() == DestTy);
+    return ReplaceInstUsesWith(CI, Res);
+  }
+  case Instruction::ZExt: {
+    int BitsZExt = CanEvaluateZExtd(Src, DestTy, NumCastsRemoved, TD);
+    if (BitsZExt == -1) return 0;
+
     // If this is a zero-extension, we need to do an AND to maintain the clear
-    // top-part of the computation, so we require that the input have eliminated
-    // at least one cast.  
-    if (NumCastsRemoved < 1)
+    // top-part of the computation.  If we know the result will be zero 
+    // extended enough already, we don't need the and.
+    if (NumCastsRemoved < 1 &&
+        unsigned(BitsZExt) < DestBitSize-SrcBitSize)
       return 0;
-    break;
+
+    // Okay, we can transform this!  Insert the new expression now.
+    DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
+          " to avoid zero extend: " << CI);
+    Value *Res = EvaluateInDifferentType(Src, DestTy, false);
+    assert(Res->getType() == DestTy);
+
+    // If the high bits are already filled with zeros, just replace this
+    // cast with the result.
+    if (unsigned(BitsZExt) >= DestBitSize-SrcBitSize ||
+        MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize,
+                                                     DestBitSize-SrcBitSize)))
+      return ReplaceInstUsesWith(CI, Res);
+
+    // We need to emit an AND to clear the high bits.
+    Constant *C = ConstantInt::get(CI.getContext(), 
+                             APInt::getLowBitsSet(DestBitSize, SrcBitSize));
+    return BinaryOperator::CreateAnd(Res, C);
+  }
   case Instruction::SExt: {
     // Check to see if we can do this transformation, and if so, how many bits
     // of the promoted expression will be known copies of the sign bit in the
@@ -616,9 +748,6 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
     if (NumBitsSExt == 0)
       return 0;
 
-    uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
-    uint32_t DestBitSize = DestTy->getScalarSizeInBits();
-
     // Because this is a sign extension, we can always transform it by inserting
     // two new shifts (to do the extension).  However, this is only profitable
     // if we've eliminated two or more casts from the input.  If we know the
@@ -644,42 +773,6 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
     return new SExtInst(Builder->CreateTrunc(Res, Src->getType()), DestTy);
   }
   }
-  
-  DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
-        " to avoid cast: " << CI);
-  Value *Res = EvaluateInDifferentType(Src, DestTy, false);
-  assert(Res->getType() == DestTy);
-
-  uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
-  uint32_t DestBitSize = DestTy->getScalarSizeInBits();
-  switch (CI.getOpcode()) {
-  default: assert(0 && "Unknown cast type!");
-  case Instruction::Trunc:
-    // Just replace this cast with the result.
-    return ReplaceInstUsesWith(CI, Res);
-  case Instruction::ZExt: {
-    // If the high bits are already zero, just replace this cast with the
-    // result.
-    APInt Mask(APInt::getBitsSet(DestBitSize, SrcBitSize, DestBitSize));
-    if (MaskedValueIsZero(Res, Mask))
-      return ReplaceInstUsesWith(CI, Res);
-
-    // We need to emit an AND to clear the high bits.
-    Constant *C = ConstantInt::get(CI.getContext(), 
-                             APInt::getLowBitsSet(DestBitSize, SrcBitSize));
-    return BinaryOperator::CreateAnd(Res, C);
-  }
-  case Instruction::SExt: {
-    // If the high bits are already filled with sign bit, just replace this
-    // cast with the result.
-    unsigned NumSignBits = ComputeNumSignBits(Res);
-    if (NumSignBits > (DestBitSize - SrcBitSize))
-      return ReplaceInstUsesWith(CI, Res);
-
-    // We need to emit a cast to truncate, then a cast to sext.
-    return new SExtInst(Builder->CreateTrunc(Res, Src->getType()), DestTy);
-  }
-  }
 }
 
 Instruction *InstCombiner::visitTrunc(TruncInst &CI) {