lib/Transforms/InstCombine/InstCombineShifts.cpp

   1 //===- InstCombineShifts.cpp ----------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the visitShl, visitLShr, and visitAShr functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "InstCombine.h"
  15 #include "llvm/IntrinsicInst.h"
  16 #include "llvm/Support/PatternMatch.h"
  17 using namespace llvm;
  18 using namespace PatternMatch;
  19
  20 Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
  21   assert(I.getOperand(1)->getType() == I.getOperand(0)->getType());
  22   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
  23
  24   // shl X, 0 == X and shr X, 0 == X
  25   // shl 0, X == 0 and shr 0, X == 0
  26   if (Op1 == Constant::getNullValue(Op1->getType()) ||
  27       Op0 == Constant::getNullValue(Op0->getType()))
  28     return ReplaceInstUsesWith(I, Op0);
  29
  30   if (isa<UndefValue>(Op0)) {
  31     if (I.getOpcode() == Instruction::AShr) // undef >>s X -> undef
  32       return ReplaceInstUsesWith(I, Op0);
  33     else                                    // undef << X -> 0, undef >>u X -> 0
  34       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
  35   }
  36   if (isa<UndefValue>(Op1)) {
  37     if (I.getOpcode() == Instruction::AShr)  // X >>s undef -> X
  38       return ReplaceInstUsesWith(I, Op0);
  39     else                                     // X << undef, X >>u undef -> 0
  40       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
  41   }
  42
  43   // See if we can fold away this shift.
  44   if (SimplifyDemandedInstructionBits(I))
  45     return &I;
  46
  47   // Try to fold constant and into select arguments.
  48   if (isa<Constant>(Op0))
  49     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
  50       if (Instruction *R = FoldOpIntoSelect(I, SI))
  51         return R;
  52
  53   if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1))
  54     if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
  55       return Res;
  56
  57   // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2.
  58   // Because shifts by negative values are undefined.
  59   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op1))
  60     if (BO->hasOneUse() && BO->getOpcode() == Instruction::SRem)
  61       if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1)))
  62         if (CI->getValue().isPowerOf2()) {
  63           Constant *C = ConstantInt::get(BO->getType(), CI->getValue()-1);
  64           Value *Rem = Builder->CreateAnd(BO->getOperand(0), C, BO->getName());
  65           I.setOperand(1, Rem);
  66           return &I;
  67         }
  68
  69   return 0;
  70 }
  71
  72 /// CanEvaluateShifted - See if we can compute the specified value, but shifted
  73 /// logically to the left or right by some number of bits.  This should return
  74 /// true if the expression can be computed for the same cost as the current
  75 /// expression tree.  This is used to eliminate extraneous shifting from things
  76 /// like:
  77 ///      %C = shl i128 %A, 64
  78 ///      %D = shl i128 %B, 96
  79 ///      %E = or i128 %C, %D
  80 ///      %F = lshr i128 %E, 64
  81 /// where the client will ask if E can be computed shifted right by 64-bits.  If
  82 /// this succeeds, the GetShiftedValue function will be called to produce the
  83 /// value.
  84 static bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift,
  85                                InstCombiner &IC) {
  86   // We can always evaluate constants shifted.
  87   if (isa<Constant>(V))
  88     return true;
  89
  90   Instruction *I = dyn_cast<Instruction>(V);
  91   if (!I) return false;
  92
  93   // If this is the opposite shift, we can directly reuse the input of the shift
  94   // if the needed bits are already zero in the input.  This allows us to reuse
  95   // the value which means that we don't care if the shift has multiple uses.
  96   //  TODO:  Handle opposite shift by exact value.
  97   ConstantInt *CI;
  98   if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
  99       (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
 100     if (CI->getZExtValue() == NumBits) {
 101       // TODO: Check that the input bits are already zero with MaskedValueIsZero
 102 #if 0
 103       // If this is a truncate of a logical shr, we can truncate it to a smaller
 104       // lshr iff we know that the bits we would otherwise be shifting in are
 105       // already zeros.
 106       uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
 107       uint32_t BitWidth = Ty->getScalarSizeInBits();
 108       if (MaskedValueIsZero(I->getOperand(0),
 109             APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
 110           CI->getLimitedValue(BitWidth) < BitWidth) {
 111         return CanEvaluateTruncated(I->getOperand(0), Ty);
 112       }
 113 #endif
 114
 115     }
 116   }
 117
 118   // We can't mutate something that has multiple uses: doing so would
 119   // require duplicating the instruction in general, which isn't profitable.
 120   if (!I->hasOneUse()) return false;
 121
 122   switch (I->getOpcode()) {
 123   default: return false;
 124   case Instruction::And:
 125   case Instruction::Or:
 126   case Instruction::Xor:
 127     // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
 128     return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC) &&
 129            CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC);
 130
 131   case Instruction::Shl: {
 132     // We can often fold the shift into shifts-by-a-constant.
 133     CI = dyn_cast<ConstantInt>(I->getOperand(1));
 134     if (CI == 0) return false;
 135
 136     // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
 137     if (isLeftShift) return true;
 138
 139     // We can always turn shl(c)+shr(c) -> and(c2).
 140     if (CI->getValue() == NumBits) return true;
 141
 142     unsigned TypeWidth = I->getType()->getScalarSizeInBits();
 143
 144     // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't
 145     // profitable unless we know the and'd out bits are already zero.
 146     if (CI->getZExtValue() > NumBits) {
 147       unsigned LowBits = TypeWidth - CI->getZExtValue();
 148       if (MaskedValueIsZero(I->getOperand(0),
 149                        APInt::getLowBitsSet(TypeWidth, NumBits) << LowBits))
 150         return true;
 151     }
 152
 153     return false;
 154   }
 155   case Instruction::LShr: {
 156     // We can often fold the shift into shifts-by-a-constant.
 157     CI = dyn_cast<ConstantInt>(I->getOperand(1));
 158     if (CI == 0) return false;
 159
 160     // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
 161     if (!isLeftShift) return true;
 162
 163     // We can always turn lshr(c)+shl(c) -> and(c2).
 164     if (CI->getValue() == NumBits) return true;
 165
 166     unsigned TypeWidth = I->getType()->getScalarSizeInBits();
 167
 168     // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't
 169     // profitable unless we know the and'd out bits are already zero.
 170     if (CI->getZExtValue() > NumBits) {
 171       unsigned LowBits = CI->getZExtValue() - NumBits;
 172       if (MaskedValueIsZero(I->getOperand(0),
 173                           APInt::getLowBitsSet(TypeWidth, LowBits) << NumBits))
 174         return true;
 175     }
 176
 177     return false;
 178   }
 179   case Instruction::Select: {
 180     SelectInst *SI = cast<SelectInst>(I);
 181     return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, IC) &&
 182            CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC);
 183   }
 184   case Instruction::PHI: {
 185     // We can change a phi if we can change all operands.  Note that we never
 186     // get into trouble with cyclic PHIs here because we only consider
 187     // instructions with a single use.
 188     PHINode *PN = cast<PHINode>(I);
 189     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 190       if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift,IC))
 191         return false;
 192     return true;
 193   }
 194   }
 195 }
 196
 197 /// GetShiftedValue - When CanEvaluateShifted returned true for an expression,
 198 /// this value inserts the new computation that produces the shifted value.
 199 static Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
 200                               InstCombiner &IC) {
 201   // We can always evaluate constants shifted.
 202   if (Constant *C = dyn_cast<Constant>(V)) {
 203     if (isLeftShift)
 204       V = IC.Builder->CreateShl(C, NumBits);
 205     else
 206       V = IC.Builder->CreateLShr(C, NumBits);
 207     // If we got a constantexpr back, try to simplify it with TD info.
 208     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 209       V = ConstantFoldConstantExpression(CE, IC.getTargetData());
 210     return V;
 211   }
 212
 213   Instruction *I = cast<Instruction>(V);
 214   IC.Worklist.Add(I);
 215
 216   switch (I->getOpcode()) {
 217   default: assert(0 && "Inconsistency with CanEvaluateShifted");
 218   case Instruction::And:
 219   case Instruction::Or:
 220   case Instruction::Xor:
 221     // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
 222     I->setOperand(0, GetShiftedValue(I->getOperand(0), NumBits,isLeftShift,IC));
 223     I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
 224     return I;
 225
 226   case Instruction::Shl: {
 227     unsigned TypeWidth = I->getType()->getScalarSizeInBits();
 228
 229     // We only accept shifts-by-a-constant in CanEvaluateShifted.
 230     ConstantInt *CI = cast<ConstantInt>(I->getOperand(1));
 231
 232     // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
 233     if (isLeftShift) {
 234       // If this is oversized composite shift, then unsigned shifts get 0.
 235       unsigned NewShAmt = NumBits+CI->getZExtValue();
 236       if (NewShAmt >= TypeWidth)
 237         return Constant::getNullValue(I->getType());
 238
 239       I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt));
 240       return I;
 241     }
 242
 243     // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have
 244     // zeros.
 245     if (CI->getValue() == NumBits) {
 246       APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits));
 247       V = IC.Builder->CreateAnd(I->getOperand(0),
 248                                 ConstantInt::get(I->getContext(), Mask));
 249       if (Instruction *VI = dyn_cast<Instruction>(V)) {
 250         VI->moveBefore(I);
 251         VI->takeName(I);
 252       }
 253       return V;
 254     }
 255
 256     // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that
 257     // the and won't be needed.
 258     assert(CI->getZExtValue() > NumBits);
 259     I->setOperand(1, ConstantInt::get(I->getType(),
 260                                       CI->getZExtValue() - NumBits));
 261     return I;
 262   }
 263   case Instruction::LShr: {
 264     unsigned TypeWidth = I->getType()->getScalarSizeInBits();
 265     // We only accept shifts-by-a-constant in CanEvaluateShifted.
 266     ConstantInt *CI = cast<ConstantInt>(I->getOperand(1));
 267
 268     // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
 269     if (!isLeftShift) {
 270       // If this is oversized composite shift, then unsigned shifts get 0.
 271       unsigned NewShAmt = NumBits+CI->getZExtValue();
 272       if (NewShAmt >= TypeWidth)
 273         return Constant::getNullValue(I->getType());
 274
 275       I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt));
 276       return I;
 277     }
 278
 279     // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have
 280     // zeros.
 281     if (CI->getValue() == NumBits) {
 282       APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits));
 283       V = IC.Builder->CreateAnd(I->getOperand(0),
 284                                 ConstantInt::get(I->getContext(), Mask));
 285       if (Instruction *VI = dyn_cast<Instruction>(V)) {
 286         VI->moveBefore(I);
 287         VI->takeName(I);
 288       }
 289       return V;
 290     }
 291
 292     // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that
 293     // the and won't be needed.
 294     assert(CI->getZExtValue() > NumBits);
 295     I->setOperand(1, ConstantInt::get(I->getType(),
 296                                       CI->getZExtValue() - NumBits));
 297     return I;
 298   }
 299
 300   case Instruction::Select:
 301     I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
 302     I->setOperand(2, GetShiftedValue(I->getOperand(2), NumBits,isLeftShift,IC));
 303     return I;
 304   case Instruction::PHI: {
 305     // We can change a phi if we can change all operands.  Note that we never
 306     // get into trouble with cyclic PHIs here because we only consider
 307     // instructions with a single use.
 308     PHINode *PN = cast<PHINode>(I);
 309     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 310       PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i),
 311                                               NumBits, isLeftShift, IC));
 312     return PN;
 313   }
 314   }
 315 }
 316
 317
 318
 319 Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
 320                                                BinaryOperator &I) {
 321   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 322
 323
 324   // See if we can propagate this shift into the input, this covers the trivial
 325   // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
 326   if (I.getOpcode() != Instruction::AShr &&
 327       CanEvaluateShifted(Op0, Op1->getZExtValue(), isLeftShift, *this)) {
 328     DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression"
 329               " to eliminate shift:\n  IN: " << *Op0 << "\n  SH: " << I <<"\n");
 330
 331     return ReplaceInstUsesWith(I,
 332                  GetShiftedValue(Op0, Op1->getZExtValue(), isLeftShift, *this));
 333   }
 334
 335
 336   // See if we can simplify any instructions used by the instruction whose sole
 337   // purpose is to compute bits we don't care about.
 338   uint32_t TypeBits = Op0->getType()->getScalarSizeInBits();
 339
 340   // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate
 341   // a signed shift.
 342   //
 343   if (Op1->uge(TypeBits)) {
 344     if (I.getOpcode() != Instruction::AShr)
 345       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
 346     // ashr i32 X, 32 --> ashr i32 X, 31
 347     I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1));
 348     return &I;
 349   }
 350
 351   // ((X*C1) << C2) == (X * (C1 << C2))
 352   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
 353     if (BO->getOpcode() == Instruction::Mul && isLeftShift)
 354       if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
 355         return BinaryOperator::CreateMul(BO->getOperand(0),
 356                                         ConstantExpr::getShl(BOOp, Op1));
 357
 358   // Try to fold constant and into select arguments.
 359   if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 360     if (Instruction *R = FoldOpIntoSelect(I, SI))
 361       return R;
 362   if (isa<PHINode>(Op0))
 363     if (Instruction *NV = FoldOpIntoPhi(I))
 364       return NV;
 365
 366   // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2))
 367   if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
 368     Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0));
 369     // If 'shift2' is an ashr, we would have to get the sign bit into a funny
 370     // place.  Don't try to do this transformation in this case.  Also, we
 371     // require that the input operand is a shift-by-constant so that we have
 372     // confidence that the shifts will get folded together.  We could do this
 373     // xform in more cases, but it is unlikely to be profitable.
 374     if (TrOp && I.isLogicalShift() && TrOp->isShift() &&
 375         isa<ConstantInt>(TrOp->getOperand(1))) {
 376       // Okay, we'll do this xform.  Make the shift of shift.
 377       Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType());
 378       // (shift2 (shift1 & 0x00FF), c2)
 379       Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName());
 380
 381       // For logical shifts, the truncation has the effect of making the high
 382       // part of the register be zeros.  Emulate this by inserting an AND to
 383       // clear the top bits as needed.  This 'and' will usually be zapped by
 384       // other xforms later if dead.
 385       unsigned SrcSize = TrOp->getType()->getScalarSizeInBits();
 386       unsigned DstSize = TI->getType()->getScalarSizeInBits();
 387       APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize));
 388
 389       // The mask we constructed says what the trunc would do if occurring
 390       // between the shifts.  We want to know the effect *after* the second
 391       // shift.  We know that it is a logical shift by a constant, so adjust the
 392       // mask as appropriate.
 393       if (I.getOpcode() == Instruction::Shl)
 394         MaskV <<= Op1->getZExtValue();
 395       else {
 396         assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift");
 397         MaskV = MaskV.lshr(Op1->getZExtValue());
 398       }
 399
 400       // shift1 & 0x00FF
 401       Value *And = Builder->CreateAnd(NSh,
 402                                       ConstantInt::get(I.getContext(), MaskV),
 403                                       TI->getName());
 404
 405       // Return the value truncated to the interesting size.
 406       return new TruncInst(And, I.getType());
 407     }
 408   }
 409
 410   if (Op0->hasOneUse()) {
 411     if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
 412       // Turn ((X >> C) + Y) << C  ->  (X + (Y << C)) & (~0 << C)
 413       Value *V1, *V2;
 414       ConstantInt *CC;
 415       switch (Op0BO->getOpcode()) {
 416       default: break;
 417       case Instruction::Add:
 418       case Instruction::And:
 419       case Instruction::Or:
 420       case Instruction::Xor: {
 421         // These operators commute.
 422         // Turn (Y + (X >> C)) << C  ->  (X + (Y << C)) & (~0 << C)
 423         if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
 424             match(Op0BO->getOperand(1), m_Shr(m_Value(V1),
 425                   m_Specific(Op1)))) {
 426           Value *YS =         // (Y << C)
 427             Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
 428           // (X + (Y << C))
 429           Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1,
 430                                           Op0BO->getOperand(1)->getName());
 431           uint32_t Op1Val = Op1->getLimitedValue(TypeBits);
 432           return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(),
 433                      APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val)));
 434         }
 435
 436         // Turn (Y + ((X >> C) & CC)) << C  ->  ((X & (CC << C)) + (Y << C))
 437         Value *Op0BOOp1 = Op0BO->getOperand(1);
 438         if (isLeftShift && Op0BOOp1->hasOneUse() &&
 439             match(Op0BOOp1,
 440                   m_And(m_Shr(m_Value(V1), m_Specific(Op1)),
 441                         m_ConstantInt(CC))) &&
 442             cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) {
 443           Value *YS =   // (Y << C)
 444             Builder->CreateShl(Op0BO->getOperand(0), Op1,
 445                                          Op0BO->getName());
 446           // X & (CC << C)
 447           Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
 448                                          V1->getName()+".mask");
 449           return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM);
 450         }
 451       }
 452
 453       // FALL THROUGH.
 454       case Instruction::Sub: {
 455         // Turn ((X >> C) + Y) << C  ->  (X + (Y << C)) & (~0 << C)
 456         if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
 457             match(Op0BO->getOperand(0), m_Shr(m_Value(V1),
 458                   m_Specific(Op1)))) {
 459           Value *YS =  // (Y << C)
 460             Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
 461           // (X + (Y << C))
 462           Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS,
 463                                           Op0BO->getOperand(0)->getName());
 464           uint32_t Op1Val = Op1->getLimitedValue(TypeBits);
 465           return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(),
 466                      APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val)));
 467         }
 468
 469         // Turn (((X >> C)&CC) + Y) << C  ->  (X + (Y << C)) & (CC << C)
 470         if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
 471             match(Op0BO->getOperand(0),
 472                   m_And(m_Shr(m_Value(V1), m_Value(V2)),
 473                         m_ConstantInt(CC))) && V2 == Op1 &&
 474             cast<BinaryOperator>(Op0BO->getOperand(0))
 475                 ->getOperand(0)->hasOneUse()) {
 476           Value *YS = // (Y << C)
 477             Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
 478           // X & (CC << C)
 479           Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
 480                                          V1->getName()+".mask");
 481
 482           return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS);
 483         }
 484
 485         break;
 486       }
 487       }
 488
 489
 490       // If the operand is an bitwise operator with a constant RHS, and the
 491       // shift is the only use, we can pull it out of the shift.
 492       if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
 493         bool isValid = true;     // Valid only for And, Or, Xor
 494         bool highBitSet = false; // Transform if high bit of constant set?
 495
 496         switch (Op0BO->getOpcode()) {
 497         default: isValid = false; break;   // Do not perform transform!
 498         case Instruction::Add:
 499           isValid = isLeftShift;
 500           break;
 501         case Instruction::Or:
 502         case Instruction::Xor:
 503           highBitSet = false;
 504           break;
 505         case Instruction::And:
 506           highBitSet = true;
 507           break;
 508         }
 509
 510         // If this is a signed shift right, and the high bit is modified
 511         // by the logical operation, do not perform the transformation.
 512         // The highBitSet boolean indicates the value of the high bit of
 513         // the constant which would cause it to be modified for this
 514         // operation.
 515         //
 516         if (isValid && I.getOpcode() == Instruction::AShr)
 517           isValid = Op0C->getValue()[TypeBits-1] == highBitSet;
 518
 519         if (isValid) {
 520           Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1);
 521
 522           Value *NewShift =
 523             Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
 524           NewShift->takeName(Op0BO);
 525
 526           return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
 527                                         NewRHS);
 528         }
 529       }
 530     }
 531   }
 532
 533   // Find out if this is a shift of a shift by a constant.
 534   BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0);
 535   if (ShiftOp && !ShiftOp->isShift())
 536     ShiftOp = 0;
 537
 538   if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) {
 539     ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1));
 540     uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits);
 541     uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits);
 542     assert(ShiftAmt2 != 0 && "Should have been simplified earlier");
 543     if (ShiftAmt1 == 0) return 0;  // Will be simplified in the future.
 544     Value *X = ShiftOp->getOperand(0);
 545
 546     uint32_t AmtSum = ShiftAmt1+ShiftAmt2;   // Fold into one big shift.
 547
 548     const IntegerType *Ty = cast<IntegerType>(I.getType());
 549
 550     // Check for (X << c1) << c2  and  (X >> c1) >> c2
 551     if (I.getOpcode() == ShiftOp->getOpcode()) {
 552       // If this is oversized composite shift, then unsigned shifts get 0, ashr
 553       // saturates.
 554       if (AmtSum >= TypeBits) {
 555         if (I.getOpcode() != Instruction::AShr)
 556           return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 557         AmtSum = TypeBits-1;  // Saturate to 31 for i32 ashr.
 558       }
 559
 560       return BinaryOperator::Create(I.getOpcode(), X,
 561                                     ConstantInt::get(Ty, AmtSum));
 562     }
 563
 564     if (ShiftAmt1 == ShiftAmt2) {
 565       // If we have ((X >>? C) << C), turn this into X & (-1 << C).
 566       if (I.getOpcode() == Instruction::Shl &&
 567           ShiftOp->getOpcode() != Instruction::Shl) {
 568         APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1));
 569         return BinaryOperator::CreateAnd(X,
 570                                          ConstantInt::get(I.getContext(),Mask));
 571       }
 572       // If we have ((X << C) >>u C), turn this into X & (-1 >>u C).
 573       if (I.getOpcode() == Instruction::LShr &&
 574           ShiftOp->getOpcode() == Instruction::Shl) {
 575         APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1));
 576         return BinaryOperator::CreateAnd(X,
 577                                         ConstantInt::get(I.getContext(), Mask));
 578       }
 579     } else if (ShiftAmt1 < ShiftAmt2) {
 580       uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1;
 581
 582       // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)
 583       if (I.getOpcode() == Instruction::Shl &&
 584           ShiftOp->getOpcode() != Instruction::Shl) {
 585         assert(ShiftOp->getOpcode() == Instruction::LShr ||
 586                ShiftOp->getOpcode() == Instruction::AShr);
 587         Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
 588
 589         APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
 590         return BinaryOperator::CreateAnd(Shift,
 591                                          ConstantInt::get(I.getContext(),Mask));
 592       }
 593
 594       // (X << C1) >>u C2  --> X >>u (C2-C1) & (-1 >> C2)
 595       if (I.getOpcode() == Instruction::LShr &&
 596           ShiftOp->getOpcode() == Instruction::Shl) {
 597         assert(ShiftOp->getOpcode() == Instruction::Shl);
 598         Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff));
 599
 600         APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
 601         return BinaryOperator::CreateAnd(Shift,
 602                                          ConstantInt::get(I.getContext(),Mask));
 603       }
 604
 605       // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in.
 606     } else {
 607       assert(ShiftAmt2 < ShiftAmt1);
 608       uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2;
 609
 610       // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)
 611       if (I.getOpcode() == Instruction::Shl &&
 612           ShiftOp->getOpcode() != Instruction::Shl) {
 613         Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X,
 614                                             ConstantInt::get(Ty, ShiftDiff));
 615
 616         APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
 617         return BinaryOperator::CreateAnd(Shift,
 618                                          ConstantInt::get(I.getContext(),Mask));
 619       }
 620
 621       // (X << C1) >>u C2  --> X << (C1-C2) & (-1 >> C2)
 622       if (I.getOpcode() == Instruction::LShr &&
 623           ShiftOp->getOpcode() == Instruction::Shl) {
 624         Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
 625
 626         APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
 627         return BinaryOperator::CreateAnd(Shift,
 628                                          ConstantInt::get(I.getContext(),Mask));
 629       }
 630
 631       // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in.
 632     }
 633   }
 634   return 0;
 635 }
 636
 637 Instruction *InstCombiner::visitShl(BinaryOperator &I) {
 638   return commonShiftTransforms(I);
 639 }
 640
 641 Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
 642   if (Instruction *R = commonShiftTransforms(I))
 643     return R;
 644
 645   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 646
 647   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1))
 648     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) {
 649       unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
 650       // ctlz.i32(x)>>5  --> zext(x == 0)
 651       // cttz.i32(x)>>5  --> zext(x == 0)
 652       // ctpop.i32(x)>>5 --> zext(x == -1)
 653       if ((II->getIntrinsicID() == Intrinsic::ctlz ||
 654            II->getIntrinsicID() == Intrinsic::cttz ||
 655            II->getIntrinsicID() == Intrinsic::ctpop) &&
 656           isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == Op1C->getZExtValue()){
 657         bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop;
 658         Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0);
 659         Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS);
 660         return new ZExtInst(Cmp, II->getType());
 661       }
 662     }
 663
 664   return 0;
 665 }
 666
 667 Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
 668   if (Instruction *R = commonShiftTransforms(I))
 669     return R;
 670
 671   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 672
 673   if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) {
 674     // ashr int -1, X = -1   (for any arithmetic shift rights of ~0)
 675     if (CSI->isAllOnesValue())
 676       return ReplaceInstUsesWith(I, CSI);
 677   }
 678
 679   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
 680     // If the input is a SHL by the same constant (ashr (shl X, C), C), then we
 681     // have a sign-extend idiom.
 682     Value *X;
 683     if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) {
 684       // If the input value is known to already be sign extended enough, delete
 685       // the extension.
 686       if (ComputeNumSignBits(X) > Op1C->getZExtValue())
 687         return ReplaceInstUsesWith(I, X);
 688
 689       // If the input is an extension from the shifted amount value, e.g.
 690       //   %x = zext i8 %A to i32
 691       //   %y = shl i32 %x, 24
 692       //   %z = ashr %y, 24
 693       // then turn this into "z = sext i8 A to i32".
 694       if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) {
 695         uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits();
 696         uint32_t DestBits = ZI->getType()->getScalarSizeInBits();
 697         if (Op1C->getZExtValue() == DestBits-SrcBits)
 698           return new SExtInst(ZI->getOperand(0), ZI->getType());
 699       }
 700     }
 701   }
 702
 703   // See if we can turn a signed shr into an unsigned shr.
 704   if (MaskedValueIsZero(Op0,
 705                         APInt::getSignBit(I.getType()->getScalarSizeInBits())))
 706     return BinaryOperator::CreateLShr(Op0, Op1);
 707
 708   // Arithmetic shifting an all-sign-bit value is a no-op.
 709   unsigned NumSignBits = ComputeNumSignBits(Op0);
 710   if (NumSignBits == Op0->getType()->getScalarSizeInBits())
 711     return ReplaceInstUsesWith(I, Op0);
 712
 713   return 0;
 714 }
 715