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