Deleted Added
sdiff udiff text old ( 210299 ) new ( 212904 )
full compact
InstCombineShifts.cpp (210299) InstCombineShifts.cpp (212904)
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//===----------------------------------------------------------------------===//

--- 42 unchanged lines hidden (view full) ---

51 return R;
52
53 if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1))
54 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
55 return Res;
56 return 0;
57}
58
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//===----------------------------------------------------------------------===//

--- 42 unchanged lines hidden (view full) ---

51 return R;
52
53 if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1))
54 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
55 return Res;
56 return 0;
57}
58
59/// CanEvaluateShifted - See if we can compute the specified value, but shifted
60/// logically to the left or right by some number of bits. This should return
61/// true if the expression can be computed for the same cost as the current
62/// expression tree. This is used to eliminate extraneous shifting from things
63/// like:
64/// %C = shl i128 %A, 64
65/// %D = shl i128 %B, 96
66/// %E = or i128 %C, %D
67/// %F = lshr i128 %E, 64
68/// where the client will ask if E can be computed shifted right by 64-bits. If
69/// this succeeds, the GetShiftedValue function will be called to produce the
70/// value.
71static bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift,
72 InstCombiner &IC) {
73 // We can always evaluate constants shifted.
74 if (isa<Constant>(V))
75 return true;
76
77 Instruction *I = dyn_cast<Instruction>(V);
78 if (!I) return false;
79
80 // If this is the opposite shift, we can directly reuse the input of the shift
81 // if the needed bits are already zero in the input. This allows us to reuse
82 // the value which means that we don't care if the shift has multiple uses.
83 // TODO: Handle opposite shift by exact value.
84 ConstantInt *CI;
85 if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
86 (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
87 if (CI->getZExtValue() == NumBits) {
88 // TODO: Check that the input bits are already zero with MaskedValueIsZero
89#if 0
90 // If this is a truncate of a logical shr, we can truncate it to a smaller
91 // lshr iff we know that the bits we would otherwise be shifting in are
92 // already zeros.
93 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
94 uint32_t BitWidth = Ty->getScalarSizeInBits();
95 if (MaskedValueIsZero(I->getOperand(0),
96 APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
97 CI->getLimitedValue(BitWidth) < BitWidth) {
98 return CanEvaluateTruncated(I->getOperand(0), Ty);
99 }
100#endif
101
102 }
103 }
104
105 // We can't mutate something that has multiple uses: doing so would
106 // require duplicating the instruction in general, which isn't profitable.
107 if (!I->hasOneUse()) return false;
108
109 switch (I->getOpcode()) {
110 default: return false;
111 case Instruction::And:
112 case Instruction::Or:
113 case Instruction::Xor:
114 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
115 return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC) &&
116 CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC);
117
118 case Instruction::Shl: {
119 // We can often fold the shift into shifts-by-a-constant.
120 CI = dyn_cast<ConstantInt>(I->getOperand(1));
121 if (CI == 0) return false;
122
123 // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
124 if (isLeftShift) return true;
125
126 // We can always turn shl(c)+shr(c) -> and(c2).
127 if (CI->getValue() == NumBits) return true;
128
129 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
130
131 // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't
132 // profitable unless we know the and'd out bits are already zero.
133 if (CI->getZExtValue() > NumBits) {
134 unsigned HighBits = CI->getZExtValue() - NumBits;
135 if (MaskedValueIsZero(I->getOperand(0),
136 APInt::getHighBitsSet(TypeWidth, HighBits)))
137 return true;
138 }
139
140 return false;
141 }
142 case Instruction::LShr: {
143 // We can often fold the shift into shifts-by-a-constant.
144 CI = dyn_cast<ConstantInt>(I->getOperand(1));
145 if (CI == 0) return false;
146
147 // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
148 if (!isLeftShift) return true;
149
150 // We can always turn lshr(c)+shl(c) -> and(c2).
151 if (CI->getValue() == NumBits) return true;
152
153 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
154
155 // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't
156 // profitable unless we know the and'd out bits are already zero.
157 if (CI->getZExtValue() > NumBits) {
158 unsigned LowBits = CI->getZExtValue() - NumBits;
159 if (MaskedValueIsZero(I->getOperand(0),
160 APInt::getLowBitsSet(TypeWidth, LowBits)))
161 return true;
162 }
163
164 return false;
165 }
166 case Instruction::Select: {
167 SelectInst *SI = cast<SelectInst>(I);
168 return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, IC) &&
169 CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC);
170 }
171 case Instruction::PHI: {
172 // We can change a phi if we can change all operands. Note that we never
173 // get into trouble with cyclic PHIs here because we only consider
174 // instructions with a single use.
175 PHINode *PN = cast<PHINode>(I);
176 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
177 if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift,IC))
178 return false;
179 return true;
180 }
181 }
182}
183
184/// GetShiftedValue - When CanEvaluateShifted returned true for an expression,
185/// this value inserts the new computation that produces the shifted value.
186static Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
187 InstCombiner &IC) {
188 // We can always evaluate constants shifted.
189 if (Constant *C = dyn_cast<Constant>(V)) {
190 if (isLeftShift)
191 V = IC.Builder->CreateShl(C, NumBits);
192 else
193 V = IC.Builder->CreateLShr(C, NumBits);
194 // If we got a constantexpr back, try to simplify it with TD info.
195 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
196 V = ConstantFoldConstantExpression(CE, IC.getTargetData());
197 return V;
198 }
199
200 Instruction *I = cast<Instruction>(V);
201 IC.Worklist.Add(I);
202
203 switch (I->getOpcode()) {
204 default: assert(0 && "Inconsistency with CanEvaluateShifted");
205 case Instruction::And:
206 case Instruction::Or:
207 case Instruction::Xor:
208 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
209 I->setOperand(0, GetShiftedValue(I->getOperand(0), NumBits,isLeftShift,IC));
210 I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
211 return I;
212
213 case Instruction::Shl: {
214 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
215
216 // We only accept shifts-by-a-constant in CanEvaluateShifted.
217 ConstantInt *CI = cast<ConstantInt>(I->getOperand(1));
218
219 // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
220 if (isLeftShift) {
221 // If this is oversized composite shift, then unsigned shifts get 0.
222 unsigned NewShAmt = NumBits+CI->getZExtValue();
223 if (NewShAmt >= TypeWidth)
224 return Constant::getNullValue(I->getType());
225
226 I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt));
227 return I;
228 }
229
230 // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have
231 // zeros.
232 if (CI->getValue() == NumBits) {
233 APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits));
234 V = IC.Builder->CreateAnd(I->getOperand(0),
235 ConstantInt::get(I->getContext(), Mask));
236 if (Instruction *VI = dyn_cast<Instruction>(V)) {
237 VI->moveBefore(I);
238 VI->takeName(I);
239 }
240 return V;
241 }
242
243 // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that
244 // the and won't be needed.
245 assert(CI->getZExtValue() > NumBits);
246 I->setOperand(1, ConstantInt::get(I->getType(),
247 CI->getZExtValue() - NumBits));
248 return I;
249 }
250 case Instruction::LShr: {
251 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
252 // We only accept shifts-by-a-constant in CanEvaluateShifted.
253 ConstantInt *CI = cast<ConstantInt>(I->getOperand(1));
254
255 // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
256 if (!isLeftShift) {
257 // If this is oversized composite shift, then unsigned shifts get 0.
258 unsigned NewShAmt = NumBits+CI->getZExtValue();
259 if (NewShAmt >= TypeWidth)
260 return Constant::getNullValue(I->getType());
261
262 I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt));
263 return I;
264 }
265
266 // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have
267 // zeros.
268 if (CI->getValue() == NumBits) {
269 APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits));
270 V = IC.Builder->CreateAnd(I->getOperand(0),
271 ConstantInt::get(I->getContext(), Mask));
272 if (Instruction *VI = dyn_cast<Instruction>(V)) {
273 VI->moveBefore(I);
274 VI->takeName(I);
275 }
276 return V;
277 }
278
279 // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that
280 // the and won't be needed.
281 assert(CI->getZExtValue() > NumBits);
282 I->setOperand(1, ConstantInt::get(I->getType(),
283 CI->getZExtValue() - NumBits));
284 return I;
285 }
286
287 case Instruction::Select:
288 I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
289 I->setOperand(2, GetShiftedValue(I->getOperand(2), NumBits,isLeftShift,IC));
290 return I;
291 case Instruction::PHI: {
292 // We can change a phi if we can change all operands. Note that we never
293 // get into trouble with cyclic PHIs here because we only consider
294 // instructions with a single use.
295 PHINode *PN = cast<PHINode>(I);
296 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
297 PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i),
298 NumBits, isLeftShift, IC));
299 return PN;
300 }
301 }
302}
303
304
305
59Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
60 BinaryOperator &I) {
61 bool isLeftShift = I.getOpcode() == Instruction::Shl;
306Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
307 BinaryOperator &I) {
308 bool isLeftShift = I.getOpcode() == Instruction::Shl;
62
309
310
311 // See if we can propagate this shift into the input, this covers the trivial
312 // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
313 if (I.getOpcode() != Instruction::AShr &&
314 CanEvaluateShifted(Op0, Op1->getZExtValue(), isLeftShift, *this)) {
315 DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression"
316 " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n");
317
318 return ReplaceInstUsesWith(I,
319 GetShiftedValue(Op0, Op1->getZExtValue(), isLeftShift, *this));
320 }
321
322
63 // See if we can simplify any instructions used by the instruction whose sole
64 // purpose is to compute bits we don't care about.
65 uint32_t TypeBits = Op0->getType()->getScalarSizeInBits();
66
67 // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate
68 // a signed shift.
69 //
70 if (Op1->uge(TypeBits)) {

--- 212 unchanged lines hidden (view full) ---

283 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
284 AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr.
285 }
286
287 return BinaryOperator::Create(I.getOpcode(), X,
288 ConstantInt::get(Ty, AmtSum));
289 }
290
323 // See if we can simplify any instructions used by the instruction whose sole
324 // purpose is to compute bits we don't care about.
325 uint32_t TypeBits = Op0->getType()->getScalarSizeInBits();
326
327 // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate
328 // a signed shift.
329 //
330 if (Op1->uge(TypeBits)) {

--- 212 unchanged lines hidden (view full) ---

543 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
544 AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr.
545 }
546
547 return BinaryOperator::Create(I.getOpcode(), X,
548 ConstantInt::get(Ty, AmtSum));
549 }
550
291 if (ShiftOp->getOpcode() == Instruction::LShr &&
292 I.getOpcode() == Instruction::AShr) {
293 if (AmtSum >= TypeBits)
294 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
295
296 // ((X >>u C1) >>s C2) -> (X >>u (C1+C2)) since C1 != 0.
297 return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum));
298 }
299
300 if (ShiftOp->getOpcode() == Instruction::AShr &&
301 I.getOpcode() == Instruction::LShr) {
302 // ((X >>s C1) >>u C2) -> ((X >>s (C1+C2)) & mask) since C1 != 0.
303 if (AmtSum >= TypeBits)
304 AmtSum = TypeBits-1;
305
306 Value *Shift = Builder->CreateAShr(X, ConstantInt::get(Ty, AmtSum));
307
308 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
309 return BinaryOperator::CreateAnd(Shift,
310 ConstantInt::get(I.getContext(), Mask));
311 }
312
313 // Okay, if we get here, one shift must be left, and the other shift must be
314 // right. See if the amounts are equal.
315 if (ShiftAmt1 == ShiftAmt2) {
316 // If we have ((X >>? C) << C), turn this into X & (-1 << C).
551 if (ShiftAmt1 == ShiftAmt2) {
552 // If we have ((X >>? C) << C), turn this into X & (-1 << C).
317 if (I.getOpcode() == Instruction::Shl) {
553 if (I.getOpcode() == Instruction::Shl &&
554 ShiftOp->getOpcode() != Instruction::Shl) {
318 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1));
319 return BinaryOperator::CreateAnd(X,
320 ConstantInt::get(I.getContext(),Mask));
321 }
322 // If we have ((X << C) >>u C), turn this into X & (-1 >>u C).
555 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1));
556 return BinaryOperator::CreateAnd(X,
557 ConstantInt::get(I.getContext(),Mask));
558 }
559 // If we have ((X << C) >>u C), turn this into X & (-1 >>u C).
323 if (I.getOpcode() == Instruction::LShr) {
560 if (I.getOpcode() == Instruction::LShr &&
561 ShiftOp->getOpcode() == Instruction::Shl) {
324 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1));
325 return BinaryOperator::CreateAnd(X,
326 ConstantInt::get(I.getContext(), Mask));
327 }
328 } else if (ShiftAmt1 < ShiftAmt2) {
329 uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1;
330
331 // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)
562 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1));
563 return BinaryOperator::CreateAnd(X,
564 ConstantInt::get(I.getContext(), Mask));
565 }
566 } else if (ShiftAmt1 < ShiftAmt2) {
567 uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1;
568
569 // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)
332 if (I.getOpcode() == Instruction::Shl) {
570 if (I.getOpcode() == Instruction::Shl &&
571 ShiftOp->getOpcode() != Instruction::Shl) {
333 assert(ShiftOp->getOpcode() == Instruction::LShr ||
334 ShiftOp->getOpcode() == Instruction::AShr);
335 Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
336
337 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
338 return BinaryOperator::CreateAnd(Shift,
339 ConstantInt::get(I.getContext(),Mask));
340 }
341
342 // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2)
572 assert(ShiftOp->getOpcode() == Instruction::LShr ||
573 ShiftOp->getOpcode() == Instruction::AShr);
574 Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
575
576 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
577 return BinaryOperator::CreateAnd(Shift,
578 ConstantInt::get(I.getContext(),Mask));
579 }
580
581 // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2)
343 if (I.getOpcode() == Instruction::LShr) {
582 if (I.getOpcode() == Instruction::LShr &&
583 ShiftOp->getOpcode() == Instruction::Shl) {
344 assert(ShiftOp->getOpcode() == Instruction::Shl);
345 Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff));
346
347 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
348 return BinaryOperator::CreateAnd(Shift,
349 ConstantInt::get(I.getContext(),Mask));
350 }
351
352 // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in.
353 } else {
354 assert(ShiftAmt2 < ShiftAmt1);
355 uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2;
356
357 // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)
584 assert(ShiftOp->getOpcode() == Instruction::Shl);
585 Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff));
586
587 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
588 return BinaryOperator::CreateAnd(Shift,
589 ConstantInt::get(I.getContext(),Mask));
590 }
591
592 // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in.
593 } else {
594 assert(ShiftAmt2 < ShiftAmt1);
595 uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2;
596
597 // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)
358 if (I.getOpcode() == Instruction::Shl) {
359 assert(ShiftOp->getOpcode() == Instruction::LShr ||
360 ShiftOp->getOpcode() == Instruction::AShr);
598 if (I.getOpcode() == Instruction::Shl &&
599 ShiftOp->getOpcode() != Instruction::Shl) {
361 Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X,
362 ConstantInt::get(Ty, ShiftDiff));
363
364 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
365 return BinaryOperator::CreateAnd(Shift,
366 ConstantInt::get(I.getContext(),Mask));
367 }
368
369 // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2)
600 Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X,
601 ConstantInt::get(Ty, ShiftDiff));
602
603 APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
604 return BinaryOperator::CreateAnd(Shift,
605 ConstantInt::get(I.getContext(),Mask));
606 }
607
608 // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2)
370 if (I.getOpcode() == Instruction::LShr) {
371 assert(ShiftOp->getOpcode() == Instruction::Shl);
609 if (I.getOpcode() == Instruction::LShr &&
610 ShiftOp->getOpcode() == Instruction::Shl) {
372 Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
373
374 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
375 return BinaryOperator::CreateAnd(Shift,
376 ConstantInt::get(I.getContext(),Mask));
377 }
378
379 // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in.

--- 84 unchanged lines hidden --- 		611 Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff));
612
613 APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
614 return BinaryOperator::CreateAnd(Shift,
615 ConstantInt::get(I.getContext(),Mask));
616 }
617
618 // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in.

--- 84 unchanged lines hidden ---