1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // InstructionCombining - Combine instructions to form fewer, simple
11 // instructions. This pass does not modify the CFG This pass is where algebraic
12 // simplification happens.
14 // This pass combines things like:
20 // This is a simple worklist driven algorithm.
22 // This pass guarantees that the following canonicalizations are performed on
24 // 1. If a binary operator has a constant operand, it is moved to the RHS
25 // 2. Bitwise operators with constant operands are always grouped so that
26 // shifts are performed first, then or's, then and's, then xor's.
27 // 3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible
28 // 4. All SetCC instructions on boolean values are replaced with logical ops
29 // 5. add X, X is represented as (X*2) => (X << 1)
30 // 6. Multiplies with a power-of-two constant argument are transformed into
32 // N. This list is incomplete
34 //===----------------------------------------------------------------------===//
36 #include "llvm/Transforms/Scalar.h"
37 #include "llvm/Instructions.h"
38 #include "llvm/Intrinsics.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Constants.h"
41 #include "llvm/DerivedTypes.h"
42 #include "llvm/GlobalVariable.h"
43 #include "llvm/Target/TargetData.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Transforms/Utils/Local.h"
46 #include "llvm/Support/InstIterator.h"
47 #include "llvm/Support/InstVisitor.h"
48 #include "llvm/Support/CallSite.h"
49 #include "Support/Statistic.h"
54 Statistic<> NumCombined ("instcombine", "Number of insts combined");
55 Statistic<> NumConstProp("instcombine", "Number of constant folds");
56 Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
58 class InstCombiner : public FunctionPass,
59 public InstVisitor<InstCombiner, Instruction*> {
60 // Worklist of all of the instructions that need to be simplified.
61 std::vector<Instruction*> WorkList;
64 /// AddUsersToWorkList - When an instruction is simplified, add all users of
65 /// the instruction to the work lists because they might get more simplified
68 void AddUsersToWorkList(Instruction &I) {
69 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
71 WorkList.push_back(cast<Instruction>(*UI));
74 /// AddUsesToWorkList - When an instruction is simplified, add operands to
75 /// the work lists because they might get more simplified now.
77 void AddUsesToWorkList(Instruction &I) {
78 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
79 if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i)))
80 WorkList.push_back(Op);
83 // removeFromWorkList - remove all instances of I from the worklist.
84 void removeFromWorkList(Instruction *I);
86 virtual bool runOnFunction(Function &F);
88 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
89 AU.addRequired<TargetData>();
93 // Visitation implementation - Implement instruction combining for different
94 // instruction types. The semantics are as follows:
96 // null - No change was made
97 // I - Change was made, I is still valid, I may be dead though
98 // otherwise - Change was made, replace I with returned instruction
100 Instruction *visitAdd(BinaryOperator &I);
101 Instruction *visitSub(BinaryOperator &I);
102 Instruction *visitMul(BinaryOperator &I);
103 Instruction *visitDiv(BinaryOperator &I);
104 Instruction *visitRem(BinaryOperator &I);
105 Instruction *visitAnd(BinaryOperator &I);
106 Instruction *visitOr (BinaryOperator &I);
107 Instruction *visitXor(BinaryOperator &I);
108 Instruction *visitSetCondInst(BinaryOperator &I);
109 Instruction *visitShiftInst(ShiftInst &I);
110 Instruction *visitCastInst(CastInst &CI);
111 Instruction *visitCallInst(CallInst &CI);
112 Instruction *visitInvokeInst(InvokeInst &II);
113 Instruction *visitPHINode(PHINode &PN);
114 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
115 Instruction *visitAllocationInst(AllocationInst &AI);
116 Instruction *visitFreeInst(FreeInst &FI);
117 Instruction *visitLoadInst(LoadInst &LI);
118 Instruction *visitBranchInst(BranchInst &BI);
120 // visitInstruction - Specify what to return for unhandled instructions...
121 Instruction *visitInstruction(Instruction &I) { return 0; }
124 Instruction *visitCallSite(CallSite CS);
125 bool transformConstExprCastCall(CallSite CS);
127 // InsertNewInstBefore - insert an instruction New before instruction Old
128 // in the program. Add the new instruction to the worklist.
130 Value *InsertNewInstBefore(Instruction *New, Instruction &Old) {
131 assert(New && New->getParent() == 0 &&
132 "New instruction already inserted into a basic block!");
133 BasicBlock *BB = Old.getParent();
134 BB->getInstList().insert(&Old, New); // Insert inst
135 WorkList.push_back(New); // Add to worklist
140 // ReplaceInstUsesWith - This method is to be used when an instruction is
141 // found to be dead, replacable with another preexisting expression. Here
142 // we add all uses of I to the worklist, replace all uses of I with the new
143 // value, then return I, so that the inst combiner will know that I was
146 Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
147 AddUsersToWorkList(I); // Add all modified instrs to worklist
148 I.replaceAllUsesWith(V);
152 // EraseInstFromFunction - When dealing with an instruction that has side
153 // effects or produces a void value, we can't rely on DCE to delete the
154 // instruction. Instead, visit methods should return the value returned by
156 Instruction *EraseInstFromFunction(Instruction &I) {
157 assert(I.use_empty() && "Cannot erase instruction that is used!");
158 AddUsesToWorkList(I);
159 removeFromWorkList(&I);
160 I.getParent()->getInstList().erase(&I);
161 return 0; // Don't do anything with FI
166 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
167 /// InsertBefore instruction. This is specialized a bit to avoid inserting
168 /// casts that are known to not do anything...
170 Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
171 Instruction *InsertBefore);
173 // SimplifyCommutative - This performs a few simplifications for commutative
175 bool SimplifyCommutative(BinaryOperator &I);
177 Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS,
178 ConstantIntegral *AndRHS, BinaryOperator &TheAnd);
181 RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
184 // getComplexity: Assign a complexity or rank value to LLVM Values...
185 // 0 -> Constant, 1 -> Other, 2 -> Argument, 2 -> Unary, 3 -> OtherInst
186 static unsigned getComplexity(Value *V) {
187 if (isa<Instruction>(V)) {
188 if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
192 if (isa<Argument>(V)) return 2;
193 return isa<Constant>(V) ? 0 : 1;
196 // isOnlyUse - Return true if this instruction will be deleted if we stop using
198 static bool isOnlyUse(Value *V) {
199 return V->hasOneUse() || isa<Constant>(V);
202 // getSignedIntegralType - Given an unsigned integral type, return the signed
203 // version of it that has the same size.
204 static const Type *getSignedIntegralType(const Type *Ty) {
205 switch (Ty->getPrimitiveID()) {
206 default: assert(0 && "Invalid unsigned integer type!"); abort();
207 case Type::UByteTyID: return Type::SByteTy;
208 case Type::UShortTyID: return Type::ShortTy;
209 case Type::UIntTyID: return Type::IntTy;
210 case Type::ULongTyID: return Type::LongTy;
214 // getPromotedType - Return the specified type promoted as it would be to pass
215 // though a va_arg area...
216 static const Type *getPromotedType(const Type *Ty) {
217 switch (Ty->getPrimitiveID()) {
218 case Type::SByteTyID:
219 case Type::ShortTyID: return Type::IntTy;
220 case Type::UByteTyID:
221 case Type::UShortTyID: return Type::UIntTy;
222 case Type::FloatTyID: return Type::DoubleTy;
227 // SimplifyCommutative - This performs a few simplifications for commutative
230 // 1. Order operands such that they are listed from right (least complex) to
231 // left (most complex). This puts constants before unary operators before
234 // 2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
235 // 3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
237 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
238 bool Changed = false;
239 if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
240 Changed = !I.swapOperands();
242 if (!I.isAssociative()) return Changed;
243 Instruction::BinaryOps Opcode = I.getOpcode();
244 if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
245 if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
246 if (isa<Constant>(I.getOperand(1))) {
247 Constant *Folded = ConstantExpr::get(I.getOpcode(),
248 cast<Constant>(I.getOperand(1)),
249 cast<Constant>(Op->getOperand(1)));
250 I.setOperand(0, Op->getOperand(0));
251 I.setOperand(1, Folded);
253 } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
254 if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
255 isOnlyUse(Op) && isOnlyUse(Op1)) {
256 Constant *C1 = cast<Constant>(Op->getOperand(1));
257 Constant *C2 = cast<Constant>(Op1->getOperand(1));
259 // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
260 Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
261 Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
264 WorkList.push_back(New);
265 I.setOperand(0, New);
266 I.setOperand(1, Folded);
273 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
274 // if the LHS is a constant zero (which is the 'negate' form).
276 static inline Value *dyn_castNegVal(Value *V) {
277 if (BinaryOperator::isNeg(V))
278 return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
280 // Constants can be considered to be negated values if they can be folded...
281 if (Constant *C = dyn_cast<Constant>(V))
282 return ConstantExpr::get(Instruction::Sub,
283 Constant::getNullValue(V->getType()), C);
287 static Constant *NotConstant(Constant *C) {
288 return ConstantExpr::get(Instruction::Xor, C,
289 ConstantIntegral::getAllOnesValue(C->getType()));
292 static inline Value *dyn_castNotVal(Value *V) {
293 if (BinaryOperator::isNot(V))
294 return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
296 // Constants can be considered to be not'ed values...
297 if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
298 return NotConstant(C);
302 // dyn_castFoldableMul - If this value is a multiply that can be folded into
303 // other computations (because it has a constant operand), return the
304 // non-constant operand of the multiply.
306 static inline Value *dyn_castFoldableMul(Value *V) {
307 if (V->hasOneUse() && V->getType()->isInteger())
308 if (Instruction *I = dyn_cast<Instruction>(V))
309 if (I->getOpcode() == Instruction::Mul)
310 if (isa<Constant>(I->getOperand(1)))
311 return I->getOperand(0);
315 // dyn_castMaskingAnd - If this value is an And instruction masking a value with
316 // a constant, return the constant being anded with.
318 template<class ValueType>
319 static inline Constant *dyn_castMaskingAnd(ValueType *V) {
320 if (Instruction *I = dyn_cast<Instruction>(V))
321 if (I->getOpcode() == Instruction::And)
322 return dyn_cast<Constant>(I->getOperand(1));
324 // If this is a constant, it acts just like we were masking with it.
325 return dyn_cast<Constant>(V);
328 // Log2 - Calculate the log base 2 for the specified value if it is exactly a
330 static unsigned Log2(uint64_t Val) {
331 assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!");
334 if (Val & 1) return 0; // Multiple bits set?
342 /// AssociativeOpt - Perform an optimization on an associative operator. This
343 /// function is designed to check a chain of associative operators for a
344 /// potential to apply a certain optimization. Since the optimization may be
345 /// applicable if the expression was reassociated, this checks the chain, then
346 /// reassociates the expression as necessary to expose the optimization
347 /// opportunity. This makes use of a special Functor, which must define
348 /// 'shouldApply' and 'apply' methods.
350 template<typename Functor>
351 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) {
352 unsigned Opcode = Root.getOpcode();
353 Value *LHS = Root.getOperand(0);
355 // Quick check, see if the immediate LHS matches...
356 if (F.shouldApply(LHS))
357 return F.apply(Root);
359 // Otherwise, if the LHS is not of the same opcode as the root, return.
360 Instruction *LHSI = dyn_cast<Instruction>(LHS);
361 while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) {
362 // Should we apply this transform to the RHS?
363 bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
365 // If not to the RHS, check to see if we should apply to the LHS...
366 if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) {
367 cast<BinaryOperator>(LHSI)->swapOperands(); // Make the LHS the RHS
371 // If the functor wants to apply the optimization to the RHS of LHSI,
372 // reassociate the expression from ((? op A) op B) to (? op (A op B))
374 BasicBlock *BB = Root.getParent();
375 // All of the instructions have a single use and have no side-effects,
376 // because of this, we can pull them all into the current basic block.
377 if (LHSI->getParent() != BB) {
378 // Move all of the instructions from root to LHSI into the current
380 Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
381 Instruction *LastUse = &Root;
382 while (TmpLHSI->getParent() == BB) {
384 TmpLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
387 // Loop over all of the instructions in other blocks, moving them into
389 Value *TmpLHS = TmpLHSI;
391 TmpLHSI = cast<Instruction>(TmpLHS);
392 // Remove from current block...
393 TmpLHSI->getParent()->getInstList().remove(TmpLHSI);
394 // Insert before the last instruction...
395 BB->getInstList().insert(LastUse, TmpLHSI);
396 TmpLHS = TmpLHSI->getOperand(0);
397 } while (TmpLHSI != LHSI);
400 // Now all of the instructions are in the current basic block, go ahead
401 // and perform the reassociation.
402 Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
404 // First move the selected RHS to the LHS of the root...
405 Root.setOperand(0, LHSI->getOperand(1));
407 // Make what used to be the LHS of the root be the user of the root...
408 Value *ExtraOperand = TmpLHSI->getOperand(1);
409 Root.replaceAllUsesWith(TmpLHSI); // Users now use TmpLHSI
410 TmpLHSI->setOperand(1, &Root); // TmpLHSI now uses the root
411 BB->getInstList().remove(&Root); // Remove root from the BB
412 BB->getInstList().insert(TmpLHSI, &Root); // Insert root before TmpLHSI
414 // Now propagate the ExtraOperand down the chain of instructions until we
416 while (TmpLHSI != LHSI) {
417 Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
418 Value *NextOp = NextLHSI->getOperand(1);
419 NextLHSI->setOperand(1, ExtraOperand);
421 ExtraOperand = NextOp;
424 // Now that the instructions are reassociated, have the functor perform
425 // the transformation...
426 return F.apply(Root);
429 LHSI = dyn_cast<Instruction>(LHSI->getOperand(0));
435 // AddRHS - Implements: X + X --> X << 1
438 AddRHS(Value *rhs) : RHS(rhs) {}
439 bool shouldApply(Value *LHS) const { return LHS == RHS; }
440 Instruction *apply(BinaryOperator &Add) const {
441 return new ShiftInst(Instruction::Shl, Add.getOperand(0),
442 ConstantInt::get(Type::UByteTy, 1));
446 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2)
448 struct AddMaskingAnd {
450 AddMaskingAnd(Constant *c) : C2(c) {}
451 bool shouldApply(Value *LHS) const {
452 if (Constant *C1 = dyn_castMaskingAnd(LHS))
453 return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue();
456 Instruction *apply(BinaryOperator &Add) const {
457 return BinaryOperator::create(Instruction::Or, Add.getOperand(0),
464 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
465 bool Changed = SimplifyCommutative(I);
466 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
469 if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop
470 RHS == Constant::getNullValue(I.getType()))
471 return ReplaceInstUsesWith(I, LHS);
474 if (I.getType()->isInteger())
475 if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
478 if (Value *V = dyn_castNegVal(LHS))
479 return BinaryOperator::create(Instruction::Sub, RHS, V);
482 if (!isa<Constant>(RHS))
483 if (Value *V = dyn_castNegVal(RHS))
484 return BinaryOperator::create(Instruction::Sub, LHS, V);
486 // X*C + X --> X * (C+1)
487 if (dyn_castFoldableMul(LHS) == RHS) {
489 ConstantExpr::get(Instruction::Add,
490 cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
491 ConstantInt::get(I.getType(), 1));
492 return BinaryOperator::create(Instruction::Mul, RHS, CP1);
495 // X + X*C --> X * (C+1)
496 if (dyn_castFoldableMul(RHS) == LHS) {
498 ConstantExpr::get(Instruction::Add,
499 cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
500 ConstantInt::get(I.getType(), 1));
501 return BinaryOperator::create(Instruction::Mul, LHS, CP1);
504 // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
505 if (Constant *C2 = dyn_castMaskingAnd(RHS))
506 if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
508 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
509 if (Instruction *ILHS = dyn_cast<Instruction>(LHS)) {
510 switch (ILHS->getOpcode()) {
511 case Instruction::Xor:
512 // ~X + C --> (C-1) - X
513 if (ConstantInt *XorRHS = dyn_cast<ConstantInt>(ILHS->getOperand(1)))
514 if (XorRHS->isAllOnesValue())
515 return BinaryOperator::create(Instruction::Sub,
516 ConstantExpr::get(Instruction::Sub,
517 CRHS, ConstantInt::get(I.getType(), 1)),
518 ILHS->getOperand(0));
525 return Changed ? &I : 0;
528 // isSignBit - Return true if the value represented by the constant only has the
529 // highest order bit set.
530 static bool isSignBit(ConstantInt *CI) {
531 unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
532 return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1));
535 static unsigned getTypeSizeInBits(const Type *Ty) {
536 return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8;
539 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
540 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
542 if (Op0 == Op1) // sub X, X -> 0
543 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
545 // If this is a 'B = x-(-A)', change to B = x+A...
546 if (Value *V = dyn_castNegVal(Op1))
547 return BinaryOperator::create(Instruction::Add, Op0, V);
549 if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
550 // Replace (-1 - A) with (~A)...
551 if (C->isAllOnesValue())
552 return BinaryOperator::createNot(Op1);
554 // C - ~X == X + (1+C)
555 if (BinaryOperator::isNot(Op1))
556 return BinaryOperator::create(Instruction::Add,
557 BinaryOperator::getNotArgument(cast<BinaryOperator>(Op1)),
558 ConstantExpr::get(Instruction::Add, C,
559 ConstantInt::get(I.getType(), 1)));
562 if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
563 if (Op1I->hasOneUse()) {
564 // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
565 // is not used by anyone else...
567 if (Op1I->getOpcode() == Instruction::Sub &&
568 !Op1I->getType()->isFloatingPoint()) {
569 // Swap the two operands of the subexpr...
570 Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
571 Op1I->setOperand(0, IIOp1);
572 Op1I->setOperand(1, IIOp0);
574 // Create the new top level add instruction...
575 return BinaryOperator::create(Instruction::Add, Op0, Op1);
578 // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
580 if (Op1I->getOpcode() == Instruction::And &&
581 (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
582 Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
584 Instruction *NewNot = BinaryOperator::createNot(OtherOp, "B.not", &I);
585 return BinaryOperator::create(Instruction::And, Op0, NewNot);
588 // X - X*C --> X * (1-C)
589 if (dyn_castFoldableMul(Op1I) == Op0) {
591 ConstantExpr::get(Instruction::Sub,
592 ConstantInt::get(I.getType(), 1),
593 cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
594 assert(CP1 && "Couldn't constant fold 1-C?");
595 return BinaryOperator::create(Instruction::Mul, Op0, CP1);
599 // X*C - X --> X * (C-1)
600 if (dyn_castFoldableMul(Op0) == Op1) {
602 ConstantExpr::get(Instruction::Sub,
603 cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
604 ConstantInt::get(I.getType(), 1));
605 assert(CP1 && "Couldn't constant fold C - 1?");
606 return BinaryOperator::create(Instruction::Mul, Op1, CP1);
612 /// isSignBitCheck - Given an exploded setcc instruction, return true if it is
613 /// really just returns true if the most significant (sign) bit is set.
614 static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) {
615 if (RHS->getType()->isSigned()) {
616 // True if source is LHS < 0 or LHS <= -1
617 return Opcode == Instruction::SetLT && RHS->isNullValue() ||
618 Opcode == Instruction::SetLE && RHS->isAllOnesValue();
620 ConstantUInt *RHSC = cast<ConstantUInt>(RHS);
621 // True if source is LHS > 127 or LHS >= 128, where the constants depend on
622 // the size of the integer type.
623 if (Opcode == Instruction::SetGE)
624 return RHSC->getValue() == 1ULL<<(RHS->getType()->getPrimitiveSize()*8-1);
625 if (Opcode == Instruction::SetGT)
626 return RHSC->getValue() ==
627 (1ULL << (RHS->getType()->getPrimitiveSize()*8-1))-1;
632 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
633 bool Changed = SimplifyCommutative(I);
634 Value *Op0 = I.getOperand(0);
636 // Simplify mul instructions with a constant RHS...
637 if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
638 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
640 // ((X << C1)*C2) == (X * (C2 << C1))
641 if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
642 if (SI->getOpcode() == Instruction::Shl)
643 if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
644 return BinaryOperator::create(Instruction::Mul, SI->getOperand(0),
645 ConstantExpr::get(Instruction::Shl, CI, ShOp));
647 if (CI->isNullValue())
648 return ReplaceInstUsesWith(I, Op1); // X * 0 == 0
649 if (CI->equalsInt(1)) // X * 1 == X
650 return ReplaceInstUsesWith(I, Op0);
651 if (CI->isAllOnesValue()) // X * -1 == 0 - X
652 return BinaryOperator::createNeg(Op0, I.getName());
654 int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
655 if (uint64_t C = Log2(Val)) // Replace X*(2^C) with X << C
656 return new ShiftInst(Instruction::Shl, Op0,
657 ConstantUInt::get(Type::UByteTy, C));
659 ConstantFP *Op1F = cast<ConstantFP>(Op1);
660 if (Op1F->isNullValue())
661 return ReplaceInstUsesWith(I, Op1);
663 // "In IEEE floating point, x*1 is not equivalent to x for nans. However,
664 // ANSI says we can drop signals, so we can do this anyway." (from GCC)
665 if (Op1F->getValue() == 1.0)
666 return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0'
670 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y
671 if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
672 return BinaryOperator::create(Instruction::Mul, Op0v, Op1v);
674 // If one of the operands of the multiply is a cast from a boolean value, then
675 // we know the bool is either zero or one, so this is a 'masking' multiply.
676 // See if we can simplify things based on how the boolean was originally
678 CastInst *BoolCast = 0;
679 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(0)))
680 if (CI->getOperand(0)->getType() == Type::BoolTy)
683 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(1)))
684 if (CI->getOperand(0)->getType() == Type::BoolTy)
687 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BoolCast->getOperand(0))) {
688 Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1);
689 const Type *SCOpTy = SCIOp0->getType();
691 // If the setcc is true iff the sign bit of X is set, then convert this
692 // multiply into a shift/and combination.
693 if (isa<ConstantInt>(SCIOp1) &&
694 isSignBitCheck(SCI->getOpcode(), SCIOp0, cast<ConstantInt>(SCIOp1))) {
695 // Shift the X value right to turn it into "all signbits".
696 Constant *Amt = ConstantUInt::get(Type::UByteTy,
697 SCOpTy->getPrimitiveSize()*8-1);
698 if (SCIOp0->getType()->isUnsigned()) {
699 const Type *NewTy = getSignedIntegralType(SCIOp0->getType());
700 SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy,
701 SCIOp0->getName()), I);
705 InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt,
706 BoolCast->getOperand(0)->getName()+
709 // If the multiply type is not the same as the source type, sign extend
710 // or truncate to the multiply type.
711 if (I.getType() != V->getType())
712 V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I);
714 Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
715 return BinaryOperator::create(Instruction::And, V, OtherOp);
720 return Changed ? &I : 0;
723 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
725 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
726 if (RHS->equalsInt(1))
727 return ReplaceInstUsesWith(I, I.getOperand(0));
729 // Check to see if this is an unsigned division with an exact power of 2,
730 // if so, convert to a right shift.
731 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
732 if (uint64_t Val = C->getValue()) // Don't break X / 0
733 if (uint64_t C = Log2(Val))
734 return new ShiftInst(Instruction::Shr, I.getOperand(0),
735 ConstantUInt::get(Type::UByteTy, C));
738 // 0 / X == 0, we don't need to preserve faults!
739 if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
740 if (LHS->equalsInt(0))
741 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
747 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
748 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
749 if (RHS->equalsInt(1)) // X % 1 == 0
750 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
752 // Check to see if this is an unsigned remainder with an exact power of 2,
753 // if so, convert to a bitwise and.
754 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
755 if (uint64_t Val = C->getValue()) // Don't break X % 0 (divide by zero)
757 return BinaryOperator::create(Instruction::And, I.getOperand(0),
758 ConstantUInt::get(I.getType(), Val-1));
761 // 0 % X == 0, we don't need to preserve faults!
762 if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
763 if (LHS->equalsInt(0))
764 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
769 // isMaxValueMinusOne - return true if this is Max-1
770 static bool isMaxValueMinusOne(const ConstantInt *C) {
771 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
772 // Calculate -1 casted to the right type...
773 unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
774 uint64_t Val = ~0ULL; // All ones
775 Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
776 return CU->getValue() == Val-1;
779 const ConstantSInt *CS = cast<ConstantSInt>(C);
781 // Calculate 0111111111..11111
782 unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
783 int64_t Val = INT64_MAX; // All ones
784 Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
785 return CS->getValue() == Val-1;
788 // isMinValuePlusOne - return true if this is Min+1
789 static bool isMinValuePlusOne(const ConstantInt *C) {
790 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
791 return CU->getValue() == 1;
793 const ConstantSInt *CS = cast<ConstantSInt>(C);
795 // Calculate 1111111111000000000000
796 unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
797 int64_t Val = -1; // All ones
798 Val <<= TypeBits-1; // Shift over to the right spot
799 return CS->getValue() == Val+1;
802 /// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits
803 /// are carefully arranged to allow folding of expressions such as:
805 /// (A < B) | (A > B) --> (A != B)
807 /// Bit value '4' represents that the comparison is true if A > B, bit value '2'
808 /// represents that the comparison is true if A == B, and bit value '1' is true
811 static unsigned getSetCondCode(const SetCondInst *SCI) {
812 switch (SCI->getOpcode()) {
814 case Instruction::SetGT: return 1;
815 case Instruction::SetEQ: return 2;
816 case Instruction::SetGE: return 3;
817 case Instruction::SetLT: return 4;
818 case Instruction::SetNE: return 5;
819 case Instruction::SetLE: return 6;
822 assert(0 && "Invalid SetCC opcode!");
827 /// getSetCCValue - This is the complement of getSetCondCode, which turns an
828 /// opcode and two operands into either a constant true or false, or a brand new
829 /// SetCC instruction.
830 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
832 case 0: return ConstantBool::False;
833 case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
834 case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
835 case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
836 case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
837 case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
838 case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
839 case 7: return ConstantBool::True;
840 default: assert(0 && "Illegal SetCCCode!"); return 0;
844 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
845 struct FoldSetCCLogical {
848 FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
849 : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
850 bool shouldApply(Value *V) const {
851 if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
852 return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
853 SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
856 Instruction *apply(BinaryOperator &Log) const {
857 SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
858 if (SCI->getOperand(0) != LHS) {
859 assert(SCI->getOperand(1) == LHS);
860 SCI->swapOperands(); // Swap the LHS and RHS of the SetCC
863 unsigned LHSCode = getSetCondCode(SCI);
864 unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
866 switch (Log.getOpcode()) {
867 case Instruction::And: Code = LHSCode & RHSCode; break;
868 case Instruction::Or: Code = LHSCode | RHSCode; break;
869 case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
870 default: assert(0 && "Illegal logical opcode!"); return 0;
873 Value *RV = getSetCCValue(Code, LHS, RHS);
874 if (Instruction *I = dyn_cast<Instruction>(RV))
876 // Otherwise, it's a constant boolean value...
877 return IC.ReplaceInstUsesWith(Log, RV);
882 // OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where
883 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
884 // guaranteed to be either a shift instruction or a binary operator.
885 Instruction *InstCombiner::OptAndOp(Instruction *Op,
886 ConstantIntegral *OpRHS,
887 ConstantIntegral *AndRHS,
888 BinaryOperator &TheAnd) {
889 Value *X = Op->getOperand(0);
890 Constant *Together = 0;
891 if (!isa<ShiftInst>(Op))
892 Together = ConstantExpr::get(Instruction::And, AndRHS, OpRHS);
894 switch (Op->getOpcode()) {
895 case Instruction::Xor:
896 if (Together->isNullValue()) {
897 // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
898 return BinaryOperator::create(Instruction::And, X, AndRHS);
899 } else if (Op->hasOneUse()) {
900 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
901 std::string OpName = Op->getName(); Op->setName("");
902 Instruction *And = BinaryOperator::create(Instruction::And,
904 InsertNewInstBefore(And, TheAnd);
905 return BinaryOperator::create(Instruction::Xor, And, Together);
908 case Instruction::Or:
909 // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
910 if (Together->isNullValue())
911 return BinaryOperator::create(Instruction::And, X, AndRHS);
913 if (Together == AndRHS) // (X | C) & C --> C
914 return ReplaceInstUsesWith(TheAnd, AndRHS);
916 if (Op->hasOneUse() && Together != OpRHS) {
917 // (X | C1) & C2 --> (X | (C1&C2)) & C2
918 std::string Op0Name = Op->getName(); Op->setName("");
919 Instruction *Or = BinaryOperator::create(Instruction::Or, X,
921 InsertNewInstBefore(Or, TheAnd);
922 return BinaryOperator::create(Instruction::And, Or, AndRHS);
926 case Instruction::Add:
927 if (Op->hasOneUse()) {
928 // Adding a one to a single bit bit-field should be turned into an XOR
929 // of the bit. First thing to check is to see if this AND is with a
930 // single bit constant.
931 unsigned long long AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
933 // Clear bits that are not part of the constant.
934 AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1;
936 // If there is only one bit set...
937 if ((AndRHSV & (AndRHSV-1)) == 0) {
938 // Ok, at this point, we know that we are masking the result of the
939 // ADD down to exactly one bit. If the constant we are adding has
940 // no bits set below this bit, then we can eliminate the ADD.
941 unsigned long long AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
943 // Check to see if any bits below the one bit set in AndRHSV are set.
944 if ((AddRHS & (AndRHSV-1)) == 0) {
945 // If not, the only thing that can effect the output of the AND is
946 // the bit specified by AndRHSV. If that bit is set, the effect of
947 // the XOR is to toggle the bit. If it is clear, then the ADD has
949 if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
950 TheAnd.setOperand(0, X);
953 std::string Name = Op->getName(); Op->setName("");
954 // Pull the XOR out of the AND.
955 Instruction *NewAnd =
956 BinaryOperator::create(Instruction::And, X, AndRHS, Name);
957 InsertNewInstBefore(NewAnd, TheAnd);
958 return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS);
965 case Instruction::Shl: {
966 // We know that the AND will not produce any of the bits shifted in, so if
967 // the anded constant includes them, clear them now!
969 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
970 Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
971 ConstantExpr::get(Instruction::Shl, AllOne, OpRHS));
973 TheAnd.setOperand(1, CI);
978 case Instruction::Shr:
979 // We know that the AND will not produce any of the bits shifted in, so if
980 // the anded constant includes them, clear them now! This only applies to
981 // unsigned shifts, because a signed shr may bring in set bits!
983 if (AndRHS->getType()->isUnsigned()) {
984 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
985 Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
986 ConstantExpr::get(Instruction::Shr, AllOne, OpRHS));
988 TheAnd.setOperand(1, CI);
998 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
999 bool Changed = SimplifyCommutative(I);
1000 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1002 // and X, X = X and X, 0 == 0
1003 if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1004 return ReplaceInstUsesWith(I, Op1);
1007 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1008 if (RHS->isAllOnesValue())
1009 return ReplaceInstUsesWith(I, Op0);
1011 // Optimize a variety of ((val OP C1) & C2) combinations...
1012 if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
1013 Instruction *Op0I = cast<Instruction>(Op0);
1014 Value *X = Op0I->getOperand(0);
1015 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1016 if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I))
1021 Value *Op0NotVal = dyn_castNotVal(Op0);
1022 Value *Op1NotVal = dyn_castNotVal(Op1);
1024 // (~A & ~B) == (~(A | B)) - Demorgan's Law
1025 if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1026 Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal,
1027 Op1NotVal,I.getName()+".demorgan");
1028 InsertNewInstBefore(Or, I);
1029 return BinaryOperator::createNot(Or);
1032 if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0
1033 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1035 // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1036 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1037 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1040 return Changed ? &I : 0;
1045 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
1046 bool Changed = SimplifyCommutative(I);
1047 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1049 // or X, X = X or X, 0 == X
1050 if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1051 return ReplaceInstUsesWith(I, Op0);
1054 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1055 if (RHS->isAllOnesValue())
1056 return ReplaceInstUsesWith(I, Op1);
1058 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1059 // (X & C1) | C2 --> (X | C2) & (C1|C2)
1060 if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0))
1061 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
1062 std::string Op0Name = Op0I->getName(); Op0I->setName("");
1063 Instruction *Or = BinaryOperator::create(Instruction::Or,
1064 Op0I->getOperand(0), RHS,
1066 InsertNewInstBefore(Or, I);
1067 return BinaryOperator::create(Instruction::And, Or,
1068 ConstantExpr::get(Instruction::Or, RHS, Op0CI));
1071 // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
1072 if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0))
1073 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
1074 std::string Op0Name = Op0I->getName(); Op0I->setName("");
1075 Instruction *Or = BinaryOperator::create(Instruction::Or,
1076 Op0I->getOperand(0), RHS,
1078 InsertNewInstBefore(Or, I);
1079 return BinaryOperator::create(Instruction::Xor, Or,
1080 ConstantExpr::get(Instruction::And, Op0CI,
1086 // (A & C1)|(A & C2) == A & (C1|C2)
1087 if (Instruction *LHS = dyn_cast<BinaryOperator>(Op0))
1088 if (Instruction *RHS = dyn_cast<BinaryOperator>(Op1))
1089 if (LHS->getOperand(0) == RHS->getOperand(0))
1090 if (Constant *C0 = dyn_castMaskingAnd(LHS))
1091 if (Constant *C1 = dyn_castMaskingAnd(RHS))
1092 return BinaryOperator::create(Instruction::And, LHS->getOperand(0),
1093 ConstantExpr::get(Instruction::Or, C0, C1));
1095 Value *Op0NotVal = dyn_castNotVal(Op0);
1096 Value *Op1NotVal = dyn_castNotVal(Op1);
1098 if (Op1 == Op0NotVal) // ~A | A == -1
1099 return ReplaceInstUsesWith(I,
1100 ConstantIntegral::getAllOnesValue(I.getType()));
1102 if (Op0 == Op1NotVal) // A | ~A == -1
1103 return ReplaceInstUsesWith(I,
1104 ConstantIntegral::getAllOnesValue(I.getType()));
1106 // (~A | ~B) == (~(A & B)) - Demorgan's Law
1107 if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1108 Instruction *And = BinaryOperator::create(Instruction::And, Op0NotVal,
1109 Op1NotVal,I.getName()+".demorgan",
1111 WorkList.push_back(And);
1112 return BinaryOperator::createNot(And);
1115 // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
1116 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1117 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1120 return Changed ? &I : 0;
1123 // XorSelf - Implements: X ^ X --> 0
1126 XorSelf(Value *rhs) : RHS(rhs) {}
1127 bool shouldApply(Value *LHS) const { return LHS == RHS; }
1128 Instruction *apply(BinaryOperator &Xor) const {
1134 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
1135 bool Changed = SimplifyCommutative(I);
1136 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1138 // xor X, X = 0, even if X is nested in a sequence of Xor's.
1139 if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) {
1140 assert(Result == &I && "AssociativeOpt didn't work?");
1141 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1144 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1146 if (RHS->isNullValue())
1147 return ReplaceInstUsesWith(I, Op0);
1149 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1150 // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
1151 if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
1152 if (RHS == ConstantBool::True && SCI->hasOneUse())
1153 return new SetCondInst(SCI->getInverseCondition(),
1154 SCI->getOperand(0), SCI->getOperand(1));
1156 // ~(c-X) == X-c-1 == X+(-c-1)
1157 if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
1158 if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
1159 Constant *NegOp0I0C = ConstantExpr::get(Instruction::Sub,
1160 Constant::getNullValue(Op0I0C->getType()), Op0I0C);
1161 Constant *ConstantRHS = ConstantExpr::get(Instruction::Sub, NegOp0I0C,
1162 ConstantInt::get(I.getType(), 1));
1163 return BinaryOperator::create(Instruction::Add, Op0I->getOperand(1),
1167 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1168 switch (Op0I->getOpcode()) {
1169 case Instruction::Add:
1170 // ~(X-c) --> (-c-1)-X
1171 if (RHS->isAllOnesValue()) {
1172 Constant *NegOp0CI = ConstantExpr::get(Instruction::Sub,
1173 Constant::getNullValue(Op0CI->getType()), Op0CI);
1174 return BinaryOperator::create(Instruction::Sub,
1175 ConstantExpr::get(Instruction::Sub, NegOp0CI,
1176 ConstantInt::get(I.getType(), 1)),
1177 Op0I->getOperand(0));
1180 case Instruction::And:
1181 // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
1182 if (ConstantExpr::get(Instruction::And, RHS, Op0CI)->isNullValue())
1183 return BinaryOperator::create(Instruction::Or, Op0, RHS);
1185 case Instruction::Or:
1186 // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
1187 if (ConstantExpr::get(Instruction::And, RHS, Op0CI) == RHS)
1188 return BinaryOperator::create(Instruction::And, Op0,
1196 if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1
1198 return ReplaceInstUsesWith(I,
1199 ConstantIntegral::getAllOnesValue(I.getType()));
1201 if (Value *X = dyn_castNotVal(Op1)) // A ^ ~A == -1
1203 return ReplaceInstUsesWith(I,
1204 ConstantIntegral::getAllOnesValue(I.getType()));
1206 if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
1207 if (Op1I->getOpcode() == Instruction::Or) {
1208 if (Op1I->getOperand(0) == Op0) { // B^(B|A) == (A|B)^B
1209 cast<BinaryOperator>(Op1I)->swapOperands();
1211 std::swap(Op0, Op1);
1212 } else if (Op1I->getOperand(1) == Op0) { // B^(A|B) == (A|B)^B
1214 std::swap(Op0, Op1);
1216 } else if (Op1I->getOpcode() == Instruction::Xor) {
1217 if (Op0 == Op1I->getOperand(0)) // A^(A^B) == B
1218 return ReplaceInstUsesWith(I, Op1I->getOperand(1));
1219 else if (Op0 == Op1I->getOperand(1)) // A^(B^A) == B
1220 return ReplaceInstUsesWith(I, Op1I->getOperand(0));
1223 if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
1224 if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) {
1225 if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B
1226 cast<BinaryOperator>(Op0I)->swapOperands();
1227 if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B
1228 Value *NotB = BinaryOperator::createNot(Op1, Op1->getName()+".not", &I);
1229 WorkList.push_back(cast<Instruction>(NotB));
1230 return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
1233 } else if (Op0I->getOpcode() == Instruction::Xor) {
1234 if (Op1 == Op0I->getOperand(0)) // (A^B)^A == B
1235 return ReplaceInstUsesWith(I, Op0I->getOperand(1));
1236 else if (Op1 == Op0I->getOperand(1)) // (B^A)^A == B
1237 return ReplaceInstUsesWith(I, Op0I->getOperand(0));
1240 // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0
1241 if (Constant *C1 = dyn_castMaskingAnd(Op0))
1242 if (Constant *C2 = dyn_castMaskingAnd(Op1))
1243 if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
1244 return BinaryOperator::create(Instruction::Or, Op0, Op1);
1246 // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
1247 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1248 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1251 return Changed ? &I : 0;
1254 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
1255 static Constant *AddOne(ConstantInt *C) {
1256 Constant *Result = ConstantExpr::get(Instruction::Add, C,
1257 ConstantInt::get(C->getType(), 1));
1258 assert(Result && "Constant folding integer addition failed!");
1261 static Constant *SubOne(ConstantInt *C) {
1262 Constant *Result = ConstantExpr::get(Instruction::Sub, C,
1263 ConstantInt::get(C->getType(), 1));
1264 assert(Result && "Constant folding integer addition failed!");
1268 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
1269 // true when both operands are equal...
1271 static bool isTrueWhenEqual(Instruction &I) {
1272 return I.getOpcode() == Instruction::SetEQ ||
1273 I.getOpcode() == Instruction::SetGE ||
1274 I.getOpcode() == Instruction::SetLE;
1277 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
1278 bool Changed = SimplifyCommutative(I);
1279 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1280 const Type *Ty = Op0->getType();
1284 return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
1286 // setcc <global/alloca*>, 0 - Global/Stack value addresses are never null!
1287 if (isa<ConstantPointerNull>(Op1) &&
1288 (isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0)))
1289 return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
1292 // setcc's with boolean values can always be turned into bitwise operations
1293 if (Ty == Type::BoolTy) {
1294 // If this is <, >, or !=, we can change this into a simple xor instruction
1295 if (!isTrueWhenEqual(I))
1296 return BinaryOperator::create(Instruction::Xor, Op0, Op1);
1298 // Otherwise we need to make a temporary intermediate instruction and insert
1299 // it into the instruction stream. This is what we are after:
1301 // seteq bool %A, %B -> ~(A^B)
1302 // setle bool %A, %B -> ~A | B
1303 // setge bool %A, %B -> A | ~B
1305 if (I.getOpcode() == Instruction::SetEQ) { // seteq case
1306 Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
1308 InsertNewInstBefore(Xor, I);
1309 return BinaryOperator::createNot(Xor);
1312 // Handle the setXe cases...
1313 assert(I.getOpcode() == Instruction::SetGE ||
1314 I.getOpcode() == Instruction::SetLE);
1316 if (I.getOpcode() == Instruction::SetGE)
1317 std::swap(Op0, Op1); // Change setge -> setle
1319 // Now we just have the SetLE case.
1320 Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
1321 InsertNewInstBefore(Not, I);
1322 return BinaryOperator::create(Instruction::Or, Not, Op1);
1325 // Check to see if we are doing one of many comparisons against constant
1326 // integers at the end of their ranges...
1328 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1329 // Simplify seteq and setne instructions...
1330 if (I.getOpcode() == Instruction::SetEQ ||
1331 I.getOpcode() == Instruction::SetNE) {
1332 bool isSetNE = I.getOpcode() == Instruction::SetNE;
1334 // If the first operand is (and|or|xor) with a constant, and the second
1335 // operand is a constant, simplify a bit.
1336 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
1337 switch (BO->getOpcode()) {
1338 case Instruction::Add:
1339 if (CI->isNullValue()) {
1340 // Replace ((add A, B) != 0) with (A != -B) if A or B is
1341 // efficiently invertible, or if the add has just this one use.
1342 Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
1343 if (Value *NegVal = dyn_castNegVal(BOp1))
1344 return new SetCondInst(I.getOpcode(), BOp0, NegVal);
1345 else if (Value *NegVal = dyn_castNegVal(BOp0))
1346 return new SetCondInst(I.getOpcode(), NegVal, BOp1);
1347 else if (BO->hasOneUse()) {
1348 Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
1350 InsertNewInstBefore(Neg, I);
1351 return new SetCondInst(I.getOpcode(), BOp0, Neg);
1355 case Instruction::Xor:
1356 // For the xor case, we can xor two constants together, eliminating
1357 // the explicit xor.
1358 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1359 return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
1360 ConstantExpr::get(Instruction::Xor, CI, BOC));
1363 case Instruction::Sub:
1364 // Replace (([sub|xor] A, B) != 0) with (A != B)
1365 if (CI->isNullValue())
1366 return new SetCondInst(I.getOpcode(), BO->getOperand(0),
1370 case Instruction::Or:
1371 // If bits are being or'd in that are not present in the constant we
1372 // are comparing against, then the comparison could never succeed!
1373 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
1374 Constant *NotCI = NotConstant(CI);
1375 if (!ConstantExpr::get(Instruction::And, BOC, NotCI)->isNullValue())
1376 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1380 case Instruction::And:
1381 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1382 // If bits are being compared against that are and'd out, then the
1383 // comparison can never succeed!
1384 if (!ConstantExpr::get(Instruction::And, CI,
1385 NotConstant(BOC))->isNullValue())
1386 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1388 // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
1389 // to be a signed value as appropriate.
1390 if (isSignBit(BOC)) {
1391 Value *X = BO->getOperand(0);
1392 // If 'X' is not signed, insert a cast now...
1393 if (!BOC->getType()->isSigned()) {
1394 const Type *DestTy = getSignedIntegralType(BOC->getType());
1395 CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed");
1396 InsertNewInstBefore(NewCI, I);
1399 return new SetCondInst(isSetNE ? Instruction::SetLT :
1400 Instruction::SetGE, X,
1401 Constant::getNullValue(X->getType()));
1407 } else { // Not a SetEQ/SetNE
1408 // If the LHS is a cast from an integral value of the same size,
1409 if (CastInst *Cast = dyn_cast<CastInst>(Op0)) {
1410 Value *CastOp = Cast->getOperand(0);
1411 const Type *SrcTy = CastOp->getType();
1412 unsigned SrcTySize = SrcTy->getPrimitiveSize();
1413 if (SrcTy != Cast->getType() && SrcTy->isInteger() &&
1414 SrcTySize == Cast->getType()->getPrimitiveSize()) {
1415 assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) &&
1416 "Source and destination signednesses should differ!");
1417 if (Cast->getType()->isSigned()) {
1418 // If this is a signed comparison, check for comparisons in the
1419 // vicinity of zero.
1420 if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
1422 return BinaryOperator::create(Instruction::SetGT, CastOp,
1423 ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1));
1424 else if (I.getOpcode() == Instruction::SetGT &&
1425 cast<ConstantSInt>(CI)->getValue() == -1)
1426 // X > -1 => x < 128
1427 return BinaryOperator::create(Instruction::SetLT, CastOp,
1428 ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1)));
1430 ConstantUInt *CUI = cast<ConstantUInt>(CI);
1431 if (I.getOpcode() == Instruction::SetLT &&
1432 CUI->getValue() == 1ULL << (SrcTySize*8-1))
1433 // X < 128 => X > -1
1434 return BinaryOperator::create(Instruction::SetGT, CastOp,
1435 ConstantSInt::get(SrcTy, -1));
1436 else if (I.getOpcode() == Instruction::SetGT &&
1437 CUI->getValue() == (1ULL << (SrcTySize*8-1))-1)
1439 return BinaryOperator::create(Instruction::SetLT, CastOp,
1440 Constant::getNullValue(SrcTy));
1446 // Check to see if we are comparing against the minimum or maximum value...
1447 if (CI->isMinValue()) {
1448 if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE
1449 return ReplaceInstUsesWith(I, ConstantBool::False);
1450 if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
1451 return ReplaceInstUsesWith(I, ConstantBool::True);
1452 if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
1453 return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
1454 if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
1455 return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
1457 } else if (CI->isMaxValue()) {
1458 if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
1459 return ReplaceInstUsesWith(I, ConstantBool::False);
1460 if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE
1461 return ReplaceInstUsesWith(I, ConstantBool::True);
1462 if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX
1463 return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
1464 if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
1465 return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
1467 // Comparing against a value really close to min or max?
1468 } else if (isMinValuePlusOne(CI)) {
1469 if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN
1470 return BinaryOperator::create(Instruction::SetEQ, Op0, SubOne(CI));
1471 if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
1472 return BinaryOperator::create(Instruction::SetNE, Op0, SubOne(CI));
1474 } else if (isMaxValueMinusOne(CI)) {
1475 if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
1476 return BinaryOperator::create(Instruction::SetEQ, Op0, AddOne(CI));
1477 if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
1478 return BinaryOperator::create(Instruction::SetNE, Op0, AddOne(CI));
1481 // If we still have a setle or setge instruction, turn it into the
1482 // appropriate setlt or setgt instruction. Since the border cases have
1483 // already been handled above, this requires little checking.
1485 if (I.getOpcode() == Instruction::SetLE)
1486 return BinaryOperator::create(Instruction::SetLT, Op0, AddOne(CI));
1487 if (I.getOpcode() == Instruction::SetGE)
1488 return BinaryOperator::create(Instruction::SetGT, Op0, SubOne(CI));
1491 // Test to see if the operands of the setcc are casted versions of other
1492 // values. If the cast can be stripped off both arguments, we do so now.
1493 if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
1494 Value *CastOp0 = CI->getOperand(0);
1495 if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
1496 !isa<Argument>(Op1) &&
1497 (I.getOpcode() == Instruction::SetEQ ||
1498 I.getOpcode() == Instruction::SetNE)) {
1499 // We keep moving the cast from the left operand over to the right
1500 // operand, where it can often be eliminated completely.
1503 // If operand #1 is a cast instruction, see if we can eliminate it as
1505 if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
1506 if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
1508 Op1 = CI2->getOperand(0);
1510 // If Op1 is a constant, we can fold the cast into the constant.
1511 if (Op1->getType() != Op0->getType())
1512 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1513 Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
1515 // Otherwise, cast the RHS right before the setcc
1516 Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
1517 InsertNewInstBefore(cast<Instruction>(Op1), I);
1519 return BinaryOperator::create(I.getOpcode(), Op0, Op1);
1522 // Handle the special case of: setcc (cast bool to X), <cst>
1523 // This comes up when you have code like
1526 // For generality, we handle any zero-extension of any operand comparison
1528 if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) {
1529 const Type *SrcTy = CastOp0->getType();
1530 const Type *DestTy = Op0->getType();
1531 if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
1532 (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) {
1533 // Ok, we have an expansion of operand 0 into a new type. Get the
1534 // constant value, masink off bits which are not set in the RHS. These
1535 // could be set if the destination value is signed.
1536 uint64_t ConstVal = ConstantRHS->getRawValue();
1537 ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1;
1539 // If the constant we are comparing it with has high bits set, which
1540 // don't exist in the original value, the values could never be equal,
1541 // because the source would be zero extended.
1543 SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8;
1544 bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1));
1545 if (ConstVal & ~((1ULL << SrcBits)-1)) {
1546 switch (I.getOpcode()) {
1547 default: assert(0 && "Unknown comparison type!");
1548 case Instruction::SetEQ:
1549 return ReplaceInstUsesWith(I, ConstantBool::False);
1550 case Instruction::SetNE:
1551 return ReplaceInstUsesWith(I, ConstantBool::True);
1552 case Instruction::SetLT:
1553 case Instruction::SetLE:
1554 if (DestTy->isSigned() && HasSignBit)
1555 return ReplaceInstUsesWith(I, ConstantBool::False);
1556 return ReplaceInstUsesWith(I, ConstantBool::True);
1557 case Instruction::SetGT:
1558 case Instruction::SetGE:
1559 if (DestTy->isSigned() && HasSignBit)
1560 return ReplaceInstUsesWith(I, ConstantBool::True);
1561 return ReplaceInstUsesWith(I, ConstantBool::False);
1565 // Otherwise, we can replace the setcc with a setcc of the smaller
1567 Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy);
1568 return BinaryOperator::create(I.getOpcode(), CastOp0, Op1);
1572 return Changed ? &I : 0;
1577 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
1578 assert(I.getOperand(1)->getType() == Type::UByteTy);
1579 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1580 bool isLeftShift = I.getOpcode() == Instruction::Shl;
1582 // shl X, 0 == X and shr X, 0 == X
1583 // shl 0, X == 0 and shr 0, X == 0
1584 if (Op1 == Constant::getNullValue(Type::UByteTy) ||
1585 Op0 == Constant::getNullValue(Op0->getType()))
1586 return ReplaceInstUsesWith(I, Op0);
1588 // shr int -1, X = -1 (for any arithmetic shift rights of ~0)
1590 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
1591 if (CSI->isAllOnesValue())
1592 return ReplaceInstUsesWith(I, CSI);
1594 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
1595 // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
1596 // of a signed value.
1598 unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
1599 if (CUI->getValue() >= TypeBits) {
1600 if (!Op0->getType()->isSigned() || isLeftShift)
1601 return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
1603 I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1));
1608 // ((X*C1) << C2) == (X * (C1 << C2))
1609 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
1610 if (BO->getOpcode() == Instruction::Mul && isLeftShift)
1611 if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
1612 return BinaryOperator::create(Instruction::Mul, BO->getOperand(0),
1613 ConstantExpr::get(Instruction::Shl, BOOp, CUI));
1616 // If the operand is an bitwise operator with a constant RHS, and the
1617 // shift is the only use, we can pull it out of the shift.
1618 if (Op0->hasOneUse())
1619 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
1620 if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
1621 bool isValid = true; // Valid only for And, Or, Xor
1622 bool highBitSet = false; // Transform if high bit of constant set?
1624 switch (Op0BO->getOpcode()) {
1625 default: isValid = false; break; // Do not perform transform!
1626 case Instruction::Or:
1627 case Instruction::Xor:
1630 case Instruction::And:
1635 // If this is a signed shift right, and the high bit is modified
1636 // by the logical operation, do not perform the transformation.
1637 // The highBitSet boolean indicates the value of the high bit of
1638 // the constant which would cause it to be modified for this
1641 if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
1642 uint64_t Val = Op0C->getRawValue();
1643 isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
1647 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI);
1649 Instruction *NewShift =
1650 new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
1653 InsertNewInstBefore(NewShift, I);
1655 return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
1660 // If this is a shift of a shift, see if we can fold the two together...
1661 if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
1662 if (ConstantUInt *ShiftAmt1C =
1663 dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
1664 unsigned ShiftAmt1 = ShiftAmt1C->getValue();
1665 unsigned ShiftAmt2 = CUI->getValue();
1667 // Check for (A << c1) << c2 and (A >> c1) >> c2
1668 if (I.getOpcode() == Op0SI->getOpcode()) {
1669 unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift...
1670 if (Op0->getType()->getPrimitiveSize()*8 < Amt)
1671 Amt = Op0->getType()->getPrimitiveSize()*8;
1672 return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
1673 ConstantUInt::get(Type::UByteTy, Amt));
1676 // Check for (A << c1) >> c2 or visaversa. If we are dealing with
1677 // signed types, we can only support the (A >> c1) << c2 configuration,
1678 // because it can not turn an arbitrary bit of A into a sign bit.
1679 if (I.getType()->isUnsigned() || isLeftShift) {
1680 // Calculate bitmask for what gets shifted off the edge...
1681 Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
1683 C = ConstantExpr::get(Instruction::Shl, C, ShiftAmt1C);
1685 C = ConstantExpr::get(Instruction::Shr, C, ShiftAmt1C);
1688 BinaryOperator::create(Instruction::And, Op0SI->getOperand(0),
1689 C, Op0SI->getOperand(0)->getName()+".mask");
1690 InsertNewInstBefore(Mask, I);
1692 // Figure out what flavor of shift we should use...
1693 if (ShiftAmt1 == ShiftAmt2)
1694 return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2
1695 else if (ShiftAmt1 < ShiftAmt2) {
1696 return new ShiftInst(I.getOpcode(), Mask,
1697 ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
1699 return new ShiftInst(Op0SI->getOpcode(), Mask,
1700 ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
1710 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
1713 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
1714 const Type *DstTy) {
1716 // It is legal to eliminate the instruction if casting A->B->A if the sizes
1717 // are identical and the bits don't get reinterpreted (for example
1718 // int->float->int would not be allowed)
1719 if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
1722 // Allow free casting and conversion of sizes as long as the sign doesn't
1724 if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
1725 unsigned SrcSize = SrcTy->getPrimitiveSize();
1726 unsigned MidSize = MidTy->getPrimitiveSize();
1727 unsigned DstSize = DstTy->getPrimitiveSize();
1729 // Cases where we are monotonically decreasing the size of the type are
1730 // always ok, regardless of what sign changes are going on.
1732 if (SrcSize >= MidSize && MidSize >= DstSize)
1735 // Cases where the source and destination type are the same, but the middle
1736 // type is bigger are noops.
1738 if (SrcSize == DstSize && MidSize > SrcSize)
1741 // If we are monotonically growing, things are more complex.
1743 if (SrcSize <= MidSize && MidSize <= DstSize) {
1744 // We have eight combinations of signedness to worry about. Here's the
1746 static const int SignTable[8] = {
1747 // CODE, SrcSigned, MidSigned, DstSigned, Comment
1748 1, // U U U Always ok
1749 1, // U U S Always ok
1750 3, // U S U Ok iff SrcSize != MidSize
1751 3, // U S S Ok iff SrcSize != MidSize
1752 0, // S U U Never ok
1753 2, // S U S Ok iff MidSize == DstSize
1754 1, // S S U Always ok
1755 1, // S S S Always ok
1758 // Choose an action based on the current entry of the signtable that this
1759 // cast of cast refers to...
1760 unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
1761 switch (SignTable[Row]) {
1762 case 0: return false; // Never ok
1763 case 1: return true; // Always ok
1764 case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
1765 case 3: // Ok iff SrcSize != MidSize
1766 return SrcSize != MidSize || SrcTy == Type::BoolTy;
1767 default: assert(0 && "Bad entry in sign table!");
1772 // Otherwise, we cannot succeed. Specifically we do not want to allow things
1773 // like: short -> ushort -> uint, because this can create wrong results if
1774 // the input short is negative!
1779 static bool ValueRequiresCast(const Value *V, const Type *Ty) {
1780 if (V->getType() == Ty || isa<Constant>(V)) return false;
1781 if (const CastInst *CI = dyn_cast<CastInst>(V))
1782 if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty))
1787 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
1788 /// InsertBefore instruction. This is specialized a bit to avoid inserting
1789 /// casts that are known to not do anything...
1791 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
1792 Instruction *InsertBefore) {
1793 if (V->getType() == DestTy) return V;
1794 if (Constant *C = dyn_cast<Constant>(V))
1795 return ConstantExpr::getCast(C, DestTy);
1797 CastInst *CI = new CastInst(V, DestTy, V->getName());
1798 InsertNewInstBefore(CI, *InsertBefore);
1802 // CastInst simplification
1804 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
1805 Value *Src = CI.getOperand(0);
1807 // If the user is casting a value to the same type, eliminate this cast
1809 if (CI.getType() == Src->getType())
1810 return ReplaceInstUsesWith(CI, Src);
1812 // If casting the result of another cast instruction, try to eliminate this
1815 if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
1816 if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
1817 CSrc->getType(), CI.getType())) {
1818 // This instruction now refers directly to the cast's src operand. This
1819 // has a good chance of making CSrc dead.
1820 CI.setOperand(0, CSrc->getOperand(0));
1824 // If this is an A->B->A cast, and we are dealing with integral types, try
1825 // to convert this into a logical 'and' instruction.
1827 if (CSrc->getOperand(0)->getType() == CI.getType() &&
1828 CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
1829 CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
1830 CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
1831 assert(CSrc->getType() != Type::ULongTy &&
1832 "Cannot have type bigger than ulong!");
1833 uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
1834 Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
1835 return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
1840 // If casting the result of a getelementptr instruction with no offset, turn
1841 // this into a cast of the original pointer!
1843 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
1844 bool AllZeroOperands = true;
1845 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
1846 if (!isa<Constant>(GEP->getOperand(i)) ||
1847 !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
1848 AllZeroOperands = false;
1851 if (AllZeroOperands) {
1852 CI.setOperand(0, GEP->getOperand(0));
1857 // If we are casting a malloc or alloca to a pointer to a type of the same
1858 // size, rewrite the allocation instruction to allocate the "right" type.
1860 if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
1861 if (AI->hasOneUse() && !AI->isArrayAllocation())
1862 if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
1863 // Get the type really allocated and the type casted to...
1864 const Type *AllocElTy = AI->getAllocatedType();
1865 unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
1866 const Type *CastElTy = PTy->getElementType();
1867 unsigned CastElTySize = TD->getTypeSize(CastElTy);
1869 // If the allocation is for an even multiple of the cast type size
1870 if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
1871 Value *Amt = ConstantUInt::get(Type::UIntTy,
1872 AllocElTySize/CastElTySize);
1873 std::string Name = AI->getName(); AI->setName("");
1874 AllocationInst *New;
1875 if (isa<MallocInst>(AI))
1876 New = new MallocInst(CastElTy, Amt, Name);
1878 New = new AllocaInst(CastElTy, Amt, Name);
1879 InsertNewInstBefore(New, CI);
1880 return ReplaceInstUsesWith(CI, New);
1884 // If the source value is an instruction with only this use, we can attempt to
1885 // propagate the cast into the instruction. Also, only handle integral types
1887 if (Instruction *SrcI = dyn_cast<Instruction>(Src))
1888 if (SrcI->hasOneUse() && Src->getType()->isIntegral() &&
1889 CI.getType()->isInteger()) { // Don't mess with casts to bool here
1890 const Type *DestTy = CI.getType();
1891 unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
1892 unsigned DestBitSize = getTypeSizeInBits(DestTy);
1894 Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
1895 Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
1897 switch (SrcI->getOpcode()) {
1898 case Instruction::Add:
1899 case Instruction::Mul:
1900 case Instruction::And:
1901 case Instruction::Or:
1902 case Instruction::Xor:
1903 // If we are discarding information, or just changing the sign, rewrite.
1904 if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
1905 // Don't insert two casts if they cannot be eliminated. We allow two
1906 // casts to be inserted if the sizes are the same. This could only be
1907 // converting signedness, which is a noop.
1908 if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) ||
1909 !ValueRequiresCast(Op0, DestTy)) {
1910 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1911 Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
1912 return BinaryOperator::create(cast<BinaryOperator>(SrcI)
1913 ->getOpcode(), Op0c, Op1c);
1917 case Instruction::Shl:
1918 // Allow changing the sign of the source operand. Do not allow changing
1919 // the size of the shift, UNLESS the shift amount is a constant. We
1920 // mush not change variable sized shifts to a smaller size, because it
1921 // is undefined to shift more bits out than exist in the value.
1922 if (DestBitSize == SrcBitSize ||
1923 (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
1924 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1925 return new ShiftInst(Instruction::Shl, Op0c, Op1);
1934 // CallInst simplification
1936 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
1937 // Intrinsics cannot occur in an invoke, so handle them here instead of in
1939 if (Function *F = CI.getCalledFunction())
1940 switch (F->getIntrinsicID()) {
1941 case Intrinsic::memmove:
1942 case Intrinsic::memcpy:
1943 case Intrinsic::memset:
1944 // memmove/cpy/set of zero bytes is a noop.
1945 if (Constant *NumBytes = dyn_cast<Constant>(CI.getOperand(3))) {
1946 if (NumBytes->isNullValue())
1947 return EraseInstFromFunction(CI);
1954 return visitCallSite(&CI);
1957 // InvokeInst simplification
1959 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
1960 return visitCallSite(&II);
1963 // visitCallSite - Improvements for call and invoke instructions.
1965 Instruction *InstCombiner::visitCallSite(CallSite CS) {
1966 bool Changed = false;
1968 // If the callee is a constexpr cast of a function, attempt to move the cast
1969 // to the arguments of the call/invoke.
1970 if (transformConstExprCastCall(CS)) return 0;
1972 Value *Callee = CS.getCalledValue();
1973 const PointerType *PTy = cast<PointerType>(Callee->getType());
1974 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
1975 if (FTy->isVarArg()) {
1976 // See if we can optimize any arguments passed through the varargs area of
1978 for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(),
1979 E = CS.arg_end(); I != E; ++I)
1980 if (CastInst *CI = dyn_cast<CastInst>(*I)) {
1981 // If this cast does not effect the value passed through the varargs
1982 // area, we can eliminate the use of the cast.
1983 Value *Op = CI->getOperand(0);
1984 if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) {
1991 return Changed ? CS.getInstruction() : 0;
1994 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
1995 // attempt to move the cast to the arguments of the call/invoke.
1997 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
1998 if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
1999 ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
2000 if (CE->getOpcode() != Instruction::Cast ||
2001 !isa<ConstantPointerRef>(CE->getOperand(0)))
2003 ConstantPointerRef *CPR = cast<ConstantPointerRef>(CE->getOperand(0));
2004 if (!isa<Function>(CPR->getValue())) return false;
2005 Function *Callee = cast<Function>(CPR->getValue());
2006 Instruction *Caller = CS.getInstruction();
2008 // Okay, this is a cast from a function to a different type. Unless doing so
2009 // would cause a type conversion of one of our arguments, change this call to
2010 // be a direct call with arguments casted to the appropriate types.
2012 const FunctionType *FT = Callee->getFunctionType();
2013 const Type *OldRetTy = Caller->getType();
2015 // Check to see if we are changing the return type...
2016 if (OldRetTy != FT->getReturnType()) {
2017 if (Callee->isExternal() &&
2018 !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) &&
2019 !Caller->use_empty())
2020 return false; // Cannot transform this return value...
2022 // If the callsite is an invoke instruction, and the return value is used by
2023 // a PHI node in a successor, we cannot change the return type of the call
2024 // because there is no place to put the cast instruction (without breaking
2025 // the critical edge). Bail out in this case.
2026 if (!Caller->use_empty())
2027 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller))
2028 for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
2030 if (PHINode *PN = dyn_cast<PHINode>(*UI))
2031 if (PN->getParent() == II->getNormalDest() ||
2032 PN->getParent() == II->getUnwindDest())
2036 unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
2037 unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
2039 CallSite::arg_iterator AI = CS.arg_begin();
2040 for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
2041 const Type *ParamTy = FT->getParamType(i);
2042 bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
2043 if (Callee->isExternal() && !isConvertible) return false;
2046 if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
2047 Callee->isExternal())
2048 return false; // Do not delete arguments unless we have a function body...
2050 // Okay, we decided that this is a safe thing to do: go ahead and start
2051 // inserting cast instructions as necessary...
2052 std::vector<Value*> Args;
2053 Args.reserve(NumActualArgs);
2055 AI = CS.arg_begin();
2056 for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
2057 const Type *ParamTy = FT->getParamType(i);
2058 if ((*AI)->getType() == ParamTy) {
2059 Args.push_back(*AI);
2061 Instruction *Cast = new CastInst(*AI, ParamTy, "tmp");
2062 InsertNewInstBefore(Cast, *Caller);
2063 Args.push_back(Cast);
2067 // If the function takes more arguments than the call was taking, add them
2069 for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
2070 Args.push_back(Constant::getNullValue(FT->getParamType(i)));
2072 // If we are removing arguments to the function, emit an obnoxious warning...
2073 if (FT->getNumParams() < NumActualArgs)
2074 if (!FT->isVarArg()) {
2075 std::cerr << "WARNING: While resolving call to function '"
2076 << Callee->getName() << "' arguments were dropped!\n";
2078 // Add all of the arguments in their promoted form to the arg list...
2079 for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
2080 const Type *PTy = getPromotedType((*AI)->getType());
2081 if (PTy != (*AI)->getType()) {
2082 // Must promote to pass through va_arg area!
2083 Instruction *Cast = new CastInst(*AI, PTy, "tmp");
2084 InsertNewInstBefore(Cast, *Caller);
2085 Args.push_back(Cast);
2087 Args.push_back(*AI);
2092 if (FT->getReturnType() == Type::VoidTy)
2093 Caller->setName(""); // Void type should not have a name...
2096 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
2097 NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
2098 Args, Caller->getName(), Caller);
2100 NC = new CallInst(Callee, Args, Caller->getName(), Caller);
2103 // Insert a cast of the return type as necessary...
2105 if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
2106 if (NV->getType() != Type::VoidTy) {
2107 NV = NC = new CastInst(NC, Caller->getType(), "tmp");
2109 // If this is an invoke instruction, we should insert it after the first
2110 // non-phi, instruction in the normal successor block.
2111 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
2112 BasicBlock::iterator I = II->getNormalDest()->begin();
2113 while (isa<PHINode>(I)) ++I;
2114 InsertNewInstBefore(NC, *I);
2116 // Otherwise, it's a call, just insert cast right after the call instr
2117 InsertNewInstBefore(NC, *Caller);
2119 AddUsersToWorkList(*Caller);
2121 NV = Constant::getNullValue(Caller->getType());
2125 if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
2126 Caller->replaceAllUsesWith(NV);
2127 Caller->getParent()->getInstList().erase(Caller);
2128 removeFromWorkList(Caller);
2134 // PHINode simplification
2136 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
2137 if (Value *V = hasConstantValue(&PN))
2138 return ReplaceInstUsesWith(PN, V);
2140 // If the only user of this instruction is a cast instruction, and all of the
2141 // incoming values are constants, change this PHI to merge together the casted
2144 if (CastInst *CI = dyn_cast<CastInst>(PN.use_back()))
2145 if (CI->getType() != PN.getType()) { // noop casts will be folded
2146 bool AllConstant = true;
2147 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2148 if (!isa<Constant>(PN.getIncomingValue(i))) {
2149 AllConstant = false;
2153 // Make a new PHI with all casted values.
2154 PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN);
2155 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
2156 Constant *OldArg = cast<Constant>(PN.getIncomingValue(i));
2157 New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()),
2158 PN.getIncomingBlock(i));
2161 // Update the cast instruction.
2162 CI->setOperand(0, New);
2163 WorkList.push_back(CI); // revisit the cast instruction to fold.
2164 WorkList.push_back(New); // Make sure to revisit the new Phi
2165 return &PN; // PN is now dead!
2172 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
2173 // Is it 'getelementptr %P, long 0' or 'getelementptr %P'
2174 // If so, eliminate the noop.
2175 if (GEP.getNumOperands() == 1)
2176 return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
2178 bool HasZeroPointerIndex = false;
2179 if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
2180 HasZeroPointerIndex = C->isNullValue();
2182 if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
2183 return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
2185 // Combine Indices - If the source pointer to this getelementptr instruction
2186 // is a getelementptr instruction, combine the indices of the two
2187 // getelementptr instructions into a single instruction.
2189 if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
2190 std::vector<Value *> Indices;
2192 // Can we combine the two pointer arithmetics offsets?
2193 if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
2194 isa<Constant>(GEP.getOperand(1))) {
2195 // Replace: gep (gep %P, long C1), long C2, ...
2196 // With: gep %P, long (C1+C2), ...
2197 Value *Sum = ConstantExpr::get(Instruction::Add,
2198 cast<Constant>(Src->getOperand(1)),
2199 cast<Constant>(GEP.getOperand(1)));
2200 assert(Sum && "Constant folding of longs failed!?");
2201 GEP.setOperand(0, Src->getOperand(0));
2202 GEP.setOperand(1, Sum);
2203 AddUsersToWorkList(*Src); // Reduce use count of Src
2205 } else if (Src->getNumOperands() == 2) {
2206 // Replace: gep (gep %P, long B), long A, ...
2207 // With: T = long A+B; gep %P, T, ...
2209 // Note that if our source is a gep chain itself that we wait for that
2210 // chain to be resolved before we perform this transformation. This
2211 // avoids us creating a TON of code in some cases.
2213 if (isa<GetElementPtrInst>(Src->getOperand(0)) &&
2214 cast<Instruction>(Src->getOperand(0))->getNumOperands() == 2)
2215 return 0; // Wait until our source is folded to completion.
2217 Value *Sum = BinaryOperator::create(Instruction::Add, Src->getOperand(1),
2219 Src->getName()+".sum", &GEP);
2220 GEP.setOperand(0, Src->getOperand(0));
2221 GEP.setOperand(1, Sum);
2222 WorkList.push_back(cast<Instruction>(Sum));
2224 } else if (*GEP.idx_begin() == Constant::getNullValue(Type::LongTy) &&
2225 Src->getNumOperands() != 1) {
2226 // Otherwise we can do the fold if the first index of the GEP is a zero
2227 Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
2228 Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
2229 } else if (Src->getOperand(Src->getNumOperands()-1) ==
2230 Constant::getNullValue(Type::LongTy)) {
2231 // If the src gep ends with a constant array index, merge this get into
2232 // it, even if we have a non-zero array index.
2233 Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()-1);
2234 Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
2237 if (!Indices.empty())
2238 return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
2240 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
2241 // GEP of global variable. If all of the indices for this GEP are
2242 // constants, we can promote this to a constexpr instead of an instruction.
2244 // Scan for nonconstants...
2245 std::vector<Constant*> Indices;
2246 User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
2247 for (; I != E && isa<Constant>(*I); ++I)
2248 Indices.push_back(cast<Constant>(*I));
2250 if (I == E) { // If they are all constants...
2252 ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
2254 // Replace all uses of the GEP with the new constexpr...
2255 return ReplaceInstUsesWith(GEP, CE);
2257 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP.getOperand(0))) {
2258 if (CE->getOpcode() == Instruction::Cast) {
2259 if (HasZeroPointerIndex) {
2260 // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
2261 // into : GEP [10 x ubyte]* X, long 0, ...
2263 // This occurs when the program declares an array extern like "int X[];"
2265 Constant *X = CE->getOperand(0);
2266 const PointerType *CPTy = cast<PointerType>(CE->getType());
2267 if (const PointerType *XTy = dyn_cast<PointerType>(X->getType()))
2268 if (const ArrayType *XATy =
2269 dyn_cast<ArrayType>(XTy->getElementType()))
2270 if (const ArrayType *CATy =
2271 dyn_cast<ArrayType>(CPTy->getElementType()))
2272 if (CATy->getElementType() == XATy->getElementType()) {
2273 // At this point, we know that the cast source type is a pointer
2274 // to an array of the same type as the destination pointer
2275 // array. Because the array type is never stepped over (there
2276 // is a leading zero) we can fold the cast into this GEP.
2277 GEP.setOperand(0, X);
2287 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
2288 // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
2289 if (AI.isArrayAllocation()) // Check C != 1
2290 if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
2291 const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
2292 AllocationInst *New = 0;
2294 // Create and insert the replacement instruction...
2295 if (isa<MallocInst>(AI))
2296 New = new MallocInst(NewTy, 0, AI.getName(), &AI);
2298 assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
2299 New = new AllocaInst(NewTy, 0, AI.getName(), &AI);
2302 // Scan to the end of the allocation instructions, to skip over a block of
2303 // allocas if possible...
2305 BasicBlock::iterator It = New;
2306 while (isa<AllocationInst>(*It)) ++It;
2308 // Now that I is pointing to the first non-allocation-inst in the block,
2309 // insert our getelementptr instruction...
2311 std::vector<Value*> Idx(2, Constant::getNullValue(Type::LongTy));
2312 Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
2314 // Now make everything use the getelementptr instead of the original
2316 ReplaceInstUsesWith(AI, V);
2322 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) {
2323 Value *Op = FI.getOperand(0);
2325 // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X
2326 if (CastInst *CI = dyn_cast<CastInst>(Op))
2327 if (isa<PointerType>(CI->getOperand(0)->getType())) {
2328 FI.setOperand(0, CI->getOperand(0));
2332 // If we have 'free null' delete the instruction. This can happen in stl code
2333 // when lots of inlining happens.
2334 if (isa<ConstantPointerNull>(Op))
2335 return EraseInstFromFunction(FI);
2341 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
2342 /// constantexpr, return the constant value being addressed by the constant
2343 /// expression, or null if something is funny.
2345 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
2346 if (CE->getOperand(1) != Constant::getNullValue(Type::LongTy))
2347 return 0; // Do not allow stepping over the value!
2349 // Loop over all of the operands, tracking down which value we are
2351 for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
2352 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
2353 ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
2354 if (CS == 0) return 0;
2355 if (CU->getValue() >= CS->getValues().size()) return 0;
2356 C = cast<Constant>(CS->getValues()[CU->getValue()]);
2357 } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
2358 ConstantArray *CA = dyn_cast<ConstantArray>(C);
2359 if (CA == 0) return 0;
2360 if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
2361 C = cast<Constant>(CA->getValues()[CS->getValue()]);
2367 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
2368 Value *Op = LI.getOperand(0);
2369 if (LI.isVolatile()) return 0;
2371 if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Op))
2372 Op = CPR->getValue();
2374 // Instcombine load (constant global) into the value loaded...
2375 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
2376 if (GV->isConstant() && !GV->isExternal())
2377 return ReplaceInstUsesWith(LI, GV->getInitializer());
2379 // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
2380 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
2381 if (CE->getOpcode() == Instruction::GetElementPtr)
2382 if (ConstantPointerRef *G=dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
2383 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
2384 if (GV->isConstant() && !GV->isExternal())
2385 if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
2386 return ReplaceInstUsesWith(LI, V);
2391 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
2392 // Change br (not X), label True, label False to: br X, label False, True
2393 if (BI.isConditional() && !isa<Constant>(BI.getCondition())) {
2394 if (Value *V = dyn_castNotVal(BI.getCondition())) {
2395 BasicBlock *TrueDest = BI.getSuccessor(0);
2396 BasicBlock *FalseDest = BI.getSuccessor(1);
2397 // Swap Destinations and condition...
2399 BI.setSuccessor(0, FalseDest);
2400 BI.setSuccessor(1, TrueDest);
2402 } else if (SetCondInst *I = dyn_cast<SetCondInst>(BI.getCondition())) {
2403 // Cannonicalize setne -> seteq
2404 if ((I->getOpcode() == Instruction::SetNE ||
2405 I->getOpcode() == Instruction::SetLE ||
2406 I->getOpcode() == Instruction::SetGE) && I->hasOneUse()) {
2407 std::string Name = I->getName(); I->setName("");
2408 Instruction::BinaryOps NewOpcode =
2409 SetCondInst::getInverseCondition(I->getOpcode());
2410 Value *NewSCC = BinaryOperator::create(NewOpcode, I->getOperand(0),
2411 I->getOperand(1), Name, I);
2412 BasicBlock *TrueDest = BI.getSuccessor(0);
2413 BasicBlock *FalseDest = BI.getSuccessor(1);
2414 // Swap Destinations and condition...
2415 BI.setCondition(NewSCC);
2416 BI.setSuccessor(0, FalseDest);
2417 BI.setSuccessor(1, TrueDest);
2418 removeFromWorkList(I);
2419 I->getParent()->getInstList().erase(I);
2420 WorkList.push_back(cast<Instruction>(NewSCC));
2429 void InstCombiner::removeFromWorkList(Instruction *I) {
2430 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
2434 bool InstCombiner::runOnFunction(Function &F) {
2435 bool Changed = false;
2436 TD = &getAnalysis<TargetData>();
2438 WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
2440 while (!WorkList.empty()) {
2441 Instruction *I = WorkList.back(); // Get an instruction from the worklist
2442 WorkList.pop_back();
2444 // Check to see if we can DCE or ConstantPropagate the instruction...
2445 // Check to see if we can DIE the instruction...
2446 if (isInstructionTriviallyDead(I)) {
2447 // Add operands to the worklist...
2448 if (I->getNumOperands() < 4)
2449 AddUsesToWorkList(*I);
2452 I->getParent()->getInstList().erase(I);
2453 removeFromWorkList(I);
2457 // Instruction isn't dead, see if we can constant propagate it...
2458 if (Constant *C = ConstantFoldInstruction(I)) {
2459 // Add operands to the worklist...
2460 AddUsesToWorkList(*I);
2461 ReplaceInstUsesWith(*I, C);
2464 I->getParent()->getInstList().erase(I);
2465 removeFromWorkList(I);
2469 // Now that we have an instruction, try combining it to simplify it...
2470 if (Instruction *Result = visit(*I)) {
2472 // Should we replace the old instruction with a new one?
2474 // Instructions can end up on the worklist more than once. Make sure
2475 // we do not process an instruction that has been deleted.
2476 removeFromWorkList(I);
2478 // Move the name to the new instruction first...
2479 std::string OldName = I->getName(); I->setName("");
2480 Result->setName(OldName);
2482 // Insert the new instruction into the basic block...
2483 BasicBlock *InstParent = I->getParent();
2484 InstParent->getInstList().insert(I, Result);
2486 // Everything uses the new instruction now...
2487 I->replaceAllUsesWith(Result);
2489 // Erase the old instruction.
2490 InstParent->getInstList().erase(I);
2492 BasicBlock::iterator II = I;
2494 // If the instruction was modified, it's possible that it is now dead.
2495 // if so, remove it.
2496 if (dceInstruction(II)) {
2497 // Instructions may end up in the worklist more than once. Erase them
2499 removeFromWorkList(I);
2505 WorkList.push_back(Result);
2506 AddUsersToWorkList(*Result);
2515 Pass *llvm::createInstructionCombiningPass() {
2516 return new InstCombiner();