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