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
34 //===----------------------------------------------------------------------===//
36 #define DEBUG_TYPE "instcombine"
37 #include "llvm/Transforms/Scalar.h"
38 #include "llvm/IntrinsicInst.h"
39 #include "llvm/Pass.h"
40 #include "llvm/DerivedTypes.h"
41 #include "llvm/GlobalVariable.h"
42 #include "llvm/Target/TargetData.h"
43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
44 #include "llvm/Transforms/Utils/Local.h"
45 #include "llvm/Support/CallSite.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/GetElementPtrTypeIterator.h"
48 #include "llvm/Support/InstVisitor.h"
49 #include "llvm/Support/MathExtras.h"
50 #include "llvm/Support/PatternMatch.h"
51 #include "llvm/ADT/DepthFirstIterator.h"
52 #include "llvm/ADT/Statistic.h"
53 #include "llvm/ADT/STLExtras.h"
56 using namespace llvm::PatternMatch;
59 Statistic<> NumCombined ("instcombine", "Number of insts combined");
60 Statistic<> NumConstProp("instcombine", "Number of constant folds");
61 Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
62 Statistic<> NumSunkInst ("instcombine", "Number of instructions sunk");
64 class InstCombiner : public FunctionPass,
65 public InstVisitor<InstCombiner, Instruction*> {
66 // Worklist of all of the instructions that need to be simplified.
67 std::vector<Instruction*> WorkList;
70 /// AddUsersToWorkList - When an instruction is simplified, add all users of
71 /// the instruction to the work lists because they might get more simplified
74 void AddUsersToWorkList(Instruction &I) {
75 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
77 WorkList.push_back(cast<Instruction>(*UI));
80 /// AddUsesToWorkList - When an instruction is simplified, add operands to
81 /// the work lists because they might get more simplified now.
83 void AddUsesToWorkList(Instruction &I) {
84 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
85 if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i)))
86 WorkList.push_back(Op);
89 // removeFromWorkList - remove all instances of I from the worklist.
90 void removeFromWorkList(Instruction *I);
92 virtual bool runOnFunction(Function &F);
94 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
95 AU.addRequired<TargetData>();
99 TargetData &getTargetData() const { return *TD; }
101 // Visitation implementation - Implement instruction combining for different
102 // instruction types. The semantics are as follows:
104 // null - No change was made
105 // I - Change was made, I is still valid, I may be dead though
106 // otherwise - Change was made, replace I with returned instruction
108 Instruction *visitAdd(BinaryOperator &I);
109 Instruction *visitSub(BinaryOperator &I);
110 Instruction *visitMul(BinaryOperator &I);
111 Instruction *visitDiv(BinaryOperator &I);
112 Instruction *visitRem(BinaryOperator &I);
113 Instruction *visitAnd(BinaryOperator &I);
114 Instruction *visitOr (BinaryOperator &I);
115 Instruction *visitXor(BinaryOperator &I);
116 Instruction *visitSetCondInst(SetCondInst &I);
117 Instruction *visitSetCondInstWithCastAndCast(SetCondInst &SCI);
119 Instruction *FoldGEPSetCC(User *GEPLHS, Value *RHS,
120 Instruction::BinaryOps Cond, Instruction &I);
121 Instruction *visitShiftInst(ShiftInst &I);
122 Instruction *visitCastInst(CastInst &CI);
123 Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI,
125 Instruction *visitSelectInst(SelectInst &CI);
126 Instruction *visitCallInst(CallInst &CI);
127 Instruction *visitInvokeInst(InvokeInst &II);
128 Instruction *visitPHINode(PHINode &PN);
129 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
130 Instruction *visitAllocationInst(AllocationInst &AI);
131 Instruction *visitFreeInst(FreeInst &FI);
132 Instruction *visitLoadInst(LoadInst &LI);
133 Instruction *visitStoreInst(StoreInst &SI);
134 Instruction *visitBranchInst(BranchInst &BI);
135 Instruction *visitSwitchInst(SwitchInst &SI);
137 // visitInstruction - Specify what to return for unhandled instructions...
138 Instruction *visitInstruction(Instruction &I) { return 0; }
141 Instruction *visitCallSite(CallSite CS);
142 bool transformConstExprCastCall(CallSite CS);
145 // InsertNewInstBefore - insert an instruction New before instruction Old
146 // in the program. Add the new instruction to the worklist.
148 Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
149 assert(New && New->getParent() == 0 &&
150 "New instruction already inserted into a basic block!");
151 BasicBlock *BB = Old.getParent();
152 BB->getInstList().insert(&Old, New); // Insert inst
153 WorkList.push_back(New); // Add to worklist
157 /// InsertCastBefore - Insert a cast of V to TY before the instruction POS.
158 /// This also adds the cast to the worklist. Finally, this returns the
160 Value *InsertCastBefore(Value *V, const Type *Ty, Instruction &Pos) {
161 if (V->getType() == Ty) return V;
163 Instruction *C = new CastInst(V, Ty, V->getName(), &Pos);
164 WorkList.push_back(C);
168 // ReplaceInstUsesWith - This method is to be used when an instruction is
169 // found to be dead, replacable with another preexisting expression. Here
170 // we add all uses of I to the worklist, replace all uses of I with the new
171 // value, then return I, so that the inst combiner will know that I was
174 Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
175 AddUsersToWorkList(I); // Add all modified instrs to worklist
177 I.replaceAllUsesWith(V);
180 // If we are replacing the instruction with itself, this must be in a
181 // segment of unreachable code, so just clobber the instruction.
182 I.replaceAllUsesWith(UndefValue::get(I.getType()));
187 // EraseInstFromFunction - When dealing with an instruction that has side
188 // effects or produces a void value, we can't rely on DCE to delete the
189 // instruction. Instead, visit methods should return the value returned by
191 Instruction *EraseInstFromFunction(Instruction &I) {
192 assert(I.use_empty() && "Cannot erase instruction that is used!");
193 AddUsesToWorkList(I);
194 removeFromWorkList(&I);
196 return 0; // Don't do anything with FI
201 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
202 /// InsertBefore instruction. This is specialized a bit to avoid inserting
203 /// casts that are known to not do anything...
205 Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
206 Instruction *InsertBefore);
208 // SimplifyCommutative - This performs a few simplifications for commutative
210 bool SimplifyCommutative(BinaryOperator &I);
213 // FoldOpIntoPhi - Given a binary operator or cast instruction which has a
214 // PHI node as operand #0, see if we can fold the instruction into the PHI
215 // (which is only possible if all operands to the PHI are constants).
216 Instruction *FoldOpIntoPhi(Instruction &I);
218 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
219 // operator and they all are only used by the PHI, PHI together their
220 // inputs, and do the operation once, to the result of the PHI.
221 Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
223 Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS,
224 ConstantIntegral *AndRHS, BinaryOperator &TheAnd);
226 Value *FoldLogicalPlusAnd(Value *LHS, Value *RHS, ConstantIntegral *Mask,
227 bool isSub, Instruction &I);
229 Instruction *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
230 bool Inside, Instruction &IB);
233 RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
236 // getComplexity: Assign a complexity or rank value to LLVM Values...
237 // 0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst
238 static unsigned getComplexity(Value *V) {
239 if (isa<Instruction>(V)) {
240 if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
244 if (isa<Argument>(V)) return 3;
245 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
248 // isOnlyUse - Return true if this instruction will be deleted if we stop using
250 static bool isOnlyUse(Value *V) {
251 return V->hasOneUse() || isa<Constant>(V);
254 // getPromotedType - Return the specified type promoted as it would be to pass
255 // though a va_arg area...
256 static const Type *getPromotedType(const Type *Ty) {
257 switch (Ty->getTypeID()) {
258 case Type::SByteTyID:
259 case Type::ShortTyID: return Type::IntTy;
260 case Type::UByteTyID:
261 case Type::UShortTyID: return Type::UIntTy;
262 case Type::FloatTyID: return Type::DoubleTy;
267 /// isCast - If the specified operand is a CastInst or a constant expr cast,
268 /// return the operand value, otherwise return null.
269 static Value *isCast(Value *V) {
270 if (CastInst *I = dyn_cast<CastInst>(V))
271 return I->getOperand(0);
272 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
273 if (CE->getOpcode() == Instruction::Cast)
274 return CE->getOperand(0);
278 // SimplifyCommutative - This performs a few simplifications for commutative
281 // 1. Order operands such that they are listed from right (least complex) to
282 // left (most complex). This puts constants before unary operators before
285 // 2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
286 // 3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
288 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
289 bool Changed = false;
290 if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
291 Changed = !I.swapOperands();
293 if (!I.isAssociative()) return Changed;
294 Instruction::BinaryOps Opcode = I.getOpcode();
295 if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
296 if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
297 if (isa<Constant>(I.getOperand(1))) {
298 Constant *Folded = ConstantExpr::get(I.getOpcode(),
299 cast<Constant>(I.getOperand(1)),
300 cast<Constant>(Op->getOperand(1)));
301 I.setOperand(0, Op->getOperand(0));
302 I.setOperand(1, Folded);
304 } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
305 if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
306 isOnlyUse(Op) && isOnlyUse(Op1)) {
307 Constant *C1 = cast<Constant>(Op->getOperand(1));
308 Constant *C2 = cast<Constant>(Op1->getOperand(1));
310 // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
311 Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
312 Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
315 WorkList.push_back(New);
316 I.setOperand(0, New);
317 I.setOperand(1, Folded);
324 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
325 // if the LHS is a constant zero (which is the 'negate' form).
327 static inline Value *dyn_castNegVal(Value *V) {
328 if (BinaryOperator::isNeg(V))
329 return BinaryOperator::getNegArgument(V);
331 // Constants can be considered to be negated values if they can be folded.
332 if (ConstantInt *C = dyn_cast<ConstantInt>(V))
333 return ConstantExpr::getNeg(C);
337 static inline Value *dyn_castNotVal(Value *V) {
338 if (BinaryOperator::isNot(V))
339 return BinaryOperator::getNotArgument(V);
341 // Constants can be considered to be not'ed values...
342 if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
343 return ConstantExpr::getNot(C);
347 // dyn_castFoldableMul - If this value is a multiply that can be folded into
348 // other computations (because it has a constant operand), return the
349 // non-constant operand of the multiply, and set CST to point to the multiplier.
350 // Otherwise, return null.
352 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
353 if (V->hasOneUse() && V->getType()->isInteger())
354 if (Instruction *I = dyn_cast<Instruction>(V)) {
355 if (I->getOpcode() == Instruction::Mul)
356 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
357 return I->getOperand(0);
358 if (I->getOpcode() == Instruction::Shl)
359 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
360 // The multiplier is really 1 << CST.
361 Constant *One = ConstantInt::get(V->getType(), 1);
362 CST = cast<ConstantInt>(ConstantExpr::getShl(One, CST));
363 return I->getOperand(0);
369 /// dyn_castGetElementPtr - If this is a getelementptr instruction or constant
370 /// expression, return it.
371 static User *dyn_castGetElementPtr(Value *V) {
372 if (isa<GetElementPtrInst>(V)) return cast<User>(V);
373 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
374 if (CE->getOpcode() == Instruction::GetElementPtr)
375 return cast<User>(V);
379 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
380 static ConstantInt *AddOne(ConstantInt *C) {
381 return cast<ConstantInt>(ConstantExpr::getAdd(C,
382 ConstantInt::get(C->getType(), 1)));
384 static ConstantInt *SubOne(ConstantInt *C) {
385 return cast<ConstantInt>(ConstantExpr::getSub(C,
386 ConstantInt::get(C->getType(), 1)));
389 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
390 // true when both operands are equal...
392 static bool isTrueWhenEqual(Instruction &I) {
393 return I.getOpcode() == Instruction::SetEQ ||
394 I.getOpcode() == Instruction::SetGE ||
395 I.getOpcode() == Instruction::SetLE;
398 /// AssociativeOpt - Perform an optimization on an associative operator. This
399 /// function is designed to check a chain of associative operators for a
400 /// potential to apply a certain optimization. Since the optimization may be
401 /// applicable if the expression was reassociated, this checks the chain, then
402 /// reassociates the expression as necessary to expose the optimization
403 /// opportunity. This makes use of a special Functor, which must define
404 /// 'shouldApply' and 'apply' methods.
406 template<typename Functor>
407 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) {
408 unsigned Opcode = Root.getOpcode();
409 Value *LHS = Root.getOperand(0);
411 // Quick check, see if the immediate LHS matches...
412 if (F.shouldApply(LHS))
413 return F.apply(Root);
415 // Otherwise, if the LHS is not of the same opcode as the root, return.
416 Instruction *LHSI = dyn_cast<Instruction>(LHS);
417 while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) {
418 // Should we apply this transform to the RHS?
419 bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
421 // If not to the RHS, check to see if we should apply to the LHS...
422 if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) {
423 cast<BinaryOperator>(LHSI)->swapOperands(); // Make the LHS the RHS
427 // If the functor wants to apply the optimization to the RHS of LHSI,
428 // reassociate the expression from ((? op A) op B) to (? op (A op B))
430 BasicBlock *BB = Root.getParent();
432 // Now all of the instructions are in the current basic block, go ahead
433 // and perform the reassociation.
434 Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
436 // First move the selected RHS to the LHS of the root...
437 Root.setOperand(0, LHSI->getOperand(1));
439 // Make what used to be the LHS of the root be the user of the root...
440 Value *ExtraOperand = TmpLHSI->getOperand(1);
441 if (&Root == TmpLHSI) {
442 Root.replaceAllUsesWith(Constant::getNullValue(TmpLHSI->getType()));
445 Root.replaceAllUsesWith(TmpLHSI); // Users now use TmpLHSI
446 TmpLHSI->setOperand(1, &Root); // TmpLHSI now uses the root
447 TmpLHSI->getParent()->getInstList().remove(TmpLHSI);
448 BasicBlock::iterator ARI = &Root; ++ARI;
449 BB->getInstList().insert(ARI, TmpLHSI); // Move TmpLHSI to after Root
452 // Now propagate the ExtraOperand down the chain of instructions until we
454 while (TmpLHSI != LHSI) {
455 Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
456 // Move the instruction to immediately before the chain we are
457 // constructing to avoid breaking dominance properties.
458 NextLHSI->getParent()->getInstList().remove(NextLHSI);
459 BB->getInstList().insert(ARI, NextLHSI);
462 Value *NextOp = NextLHSI->getOperand(1);
463 NextLHSI->setOperand(1, ExtraOperand);
465 ExtraOperand = NextOp;
468 // Now that the instructions are reassociated, have the functor perform
469 // the transformation...
470 return F.apply(Root);
473 LHSI = dyn_cast<Instruction>(LHSI->getOperand(0));
479 // AddRHS - Implements: X + X --> X << 1
482 AddRHS(Value *rhs) : RHS(rhs) {}
483 bool shouldApply(Value *LHS) const { return LHS == RHS; }
484 Instruction *apply(BinaryOperator &Add) const {
485 return new ShiftInst(Instruction::Shl, Add.getOperand(0),
486 ConstantInt::get(Type::UByteTy, 1));
490 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2)
492 struct AddMaskingAnd {
494 AddMaskingAnd(Constant *c) : C2(c) {}
495 bool shouldApply(Value *LHS) const {
497 return match(LHS, m_And(m_Value(), m_ConstantInt(C1))) &&
498 ConstantExpr::getAnd(C1, C2)->isNullValue();
500 Instruction *apply(BinaryOperator &Add) const {
501 return BinaryOperator::createOr(Add.getOperand(0), Add.getOperand(1));
505 static Value *FoldOperationIntoSelectOperand(Instruction &I, Value *SO,
507 if (isa<CastInst>(I)) {
508 if (Constant *SOC = dyn_cast<Constant>(SO))
509 return ConstantExpr::getCast(SOC, I.getType());
511 return IC->InsertNewInstBefore(new CastInst(SO, I.getType(),
512 SO->getName() + ".cast"), I);
515 // Figure out if the constant is the left or the right argument.
516 bool ConstIsRHS = isa<Constant>(I.getOperand(1));
517 Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS));
519 if (Constant *SOC = dyn_cast<Constant>(SO)) {
521 return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand);
522 return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC);
525 Value *Op0 = SO, *Op1 = ConstOperand;
529 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&I))
530 New = BinaryOperator::create(BO->getOpcode(), Op0, Op1,SO->getName()+".op");
531 else if (ShiftInst *SI = dyn_cast<ShiftInst>(&I))
532 New = new ShiftInst(SI->getOpcode(), Op0, Op1, SO->getName()+".sh");
534 assert(0 && "Unknown binary instruction type!");
537 return IC->InsertNewInstBefore(New, I);
540 // FoldOpIntoSelect - Given an instruction with a select as one operand and a
541 // constant as the other operand, try to fold the binary operator into the
542 // select arguments. This also works for Cast instructions, which obviously do
543 // not have a second operand.
544 static Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
546 // Don't modify shared select instructions
547 if (!SI->hasOneUse()) return 0;
548 Value *TV = SI->getOperand(1);
549 Value *FV = SI->getOperand(2);
551 if (isa<Constant>(TV) || isa<Constant>(FV)) {
552 // Bool selects with constant operands can be folded to logical ops.
553 if (SI->getType() == Type::BoolTy) return 0;
555 Value *SelectTrueVal = FoldOperationIntoSelectOperand(Op, TV, IC);
556 Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, IC);
558 return new SelectInst(SI->getCondition(), SelectTrueVal,
565 /// FoldOpIntoPhi - Given a binary operator or cast instruction which has a PHI
566 /// node as operand #0, see if we can fold the instruction into the PHI (which
567 /// is only possible if all operands to the PHI are constants).
568 Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
569 PHINode *PN = cast<PHINode>(I.getOperand(0));
570 unsigned NumPHIValues = PN->getNumIncomingValues();
571 if (!PN->hasOneUse() || NumPHIValues == 0 ||
572 !isa<Constant>(PN->getIncomingValue(0))) return 0;
574 // Check to see if all of the operands of the PHI are constants. If not, we
575 // cannot do the transformation.
576 for (unsigned i = 1; i != NumPHIValues; ++i)
577 if (!isa<Constant>(PN->getIncomingValue(i)))
580 // Okay, we can do the transformation: create the new PHI node.
581 PHINode *NewPN = new PHINode(I.getType(), I.getName());
583 NewPN->reserveOperandSpace(PN->getNumOperands()/2);
584 InsertNewInstBefore(NewPN, *PN);
586 // Next, add all of the operands to the PHI.
587 if (I.getNumOperands() == 2) {
588 Constant *C = cast<Constant>(I.getOperand(1));
589 for (unsigned i = 0; i != NumPHIValues; ++i) {
590 Constant *InV = cast<Constant>(PN->getIncomingValue(i));
591 NewPN->addIncoming(ConstantExpr::get(I.getOpcode(), InV, C),
592 PN->getIncomingBlock(i));
595 assert(isa<CastInst>(I) && "Unary op should be a cast!");
596 const Type *RetTy = I.getType();
597 for (unsigned i = 0; i != NumPHIValues; ++i) {
598 Constant *InV = cast<Constant>(PN->getIncomingValue(i));
599 NewPN->addIncoming(ConstantExpr::getCast(InV, RetTy),
600 PN->getIncomingBlock(i));
603 return ReplaceInstUsesWith(I, NewPN);
606 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
607 bool Changed = SimplifyCommutative(I);
608 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
610 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
611 // X + undef -> undef
612 if (isa<UndefValue>(RHS))
613 return ReplaceInstUsesWith(I, RHS);
616 if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop
618 return ReplaceInstUsesWith(I, LHS);
620 // X + (signbit) --> X ^ signbit
621 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) {
622 unsigned NumBits = CI->getType()->getPrimitiveSizeInBits();
623 uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1;
624 if (Val == (1ULL << (NumBits-1)))
625 return BinaryOperator::createXor(LHS, RHS);
628 if (isa<PHINode>(LHS))
629 if (Instruction *NV = FoldOpIntoPhi(I))
634 if (I.getType()->isInteger()) {
635 if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
637 if (Instruction *RHSI = dyn_cast<Instruction>(RHS)) {
638 if (RHSI->getOpcode() == Instruction::Sub)
639 if (LHS == RHSI->getOperand(1)) // A + (B - A) --> B
640 return ReplaceInstUsesWith(I, RHSI->getOperand(0));
642 if (Instruction *LHSI = dyn_cast<Instruction>(LHS)) {
643 if (LHSI->getOpcode() == Instruction::Sub)
644 if (RHS == LHSI->getOperand(1)) // (B - A) + A --> B
645 return ReplaceInstUsesWith(I, LHSI->getOperand(0));
650 if (Value *V = dyn_castNegVal(LHS))
651 return BinaryOperator::createSub(RHS, V);
654 if (!isa<Constant>(RHS))
655 if (Value *V = dyn_castNegVal(RHS))
656 return BinaryOperator::createSub(LHS, V);
660 if (Value *X = dyn_castFoldableMul(LHS, C2)) {
661 if (X == RHS) // X*C + X --> X * (C+1)
662 return BinaryOperator::createMul(RHS, AddOne(C2));
664 // X*C1 + X*C2 --> X * (C1+C2)
666 if (X == dyn_castFoldableMul(RHS, C1))
667 return BinaryOperator::createMul(X, ConstantExpr::getAdd(C1, C2));
670 // X + X*C --> X * (C+1)
671 if (dyn_castFoldableMul(RHS, C2) == LHS)
672 return BinaryOperator::createMul(LHS, AddOne(C2));
675 // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
676 if (match(RHS, m_And(m_Value(), m_ConstantInt(C2))))
677 if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
679 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
681 if (match(LHS, m_Not(m_Value(X)))) { // ~X + C --> (C-1) - X
682 Constant *C= ConstantExpr::getSub(CRHS, ConstantInt::get(I.getType(), 1));
683 return BinaryOperator::createSub(C, X);
686 // (X & FF00) + xx00 -> (X+xx00) & FF00
687 if (LHS->hasOneUse() && match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) {
688 Constant *Anded = ConstantExpr::getAnd(CRHS, C2);
690 // See if all bits from the first bit set in the Add RHS up are included
691 // in the mask. First, get the rightmost bit.
692 uint64_t AddRHSV = CRHS->getRawValue();
694 // Form a mask of all bits from the lowest bit added through the top.
695 uint64_t AddRHSHighBits = ~((AddRHSV & -AddRHSV)-1);
696 AddRHSHighBits &= ~0ULL >> (64-C2->getType()->getPrimitiveSizeInBits());
698 // See if the and mask includes all of these bits.
699 uint64_t AddRHSHighBitsAnd = AddRHSHighBits & C2->getRawValue();
701 if (AddRHSHighBits == AddRHSHighBitsAnd) {
702 // Okay, the xform is safe. Insert the new add pronto.
703 Value *NewAdd = InsertNewInstBefore(BinaryOperator::createAdd(X, CRHS,
705 return BinaryOperator::createAnd(NewAdd, C2);
710 // Try to fold constant add into select arguments.
711 if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
712 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
716 return Changed ? &I : 0;
719 // isSignBit - Return true if the value represented by the constant only has the
720 // highest order bit set.
721 static bool isSignBit(ConstantInt *CI) {
722 unsigned NumBits = CI->getType()->getPrimitiveSizeInBits();
723 return (CI->getRawValue() & (~0ULL >> (64-NumBits))) == (1ULL << (NumBits-1));
726 /// RemoveNoopCast - Strip off nonconverting casts from the value.
728 static Value *RemoveNoopCast(Value *V) {
729 if (CastInst *CI = dyn_cast<CastInst>(V)) {
730 const Type *CTy = CI->getType();
731 const Type *OpTy = CI->getOperand(0)->getType();
732 if (CTy->isInteger() && OpTy->isInteger()) {
733 if (CTy->getPrimitiveSizeInBits() == OpTy->getPrimitiveSizeInBits())
734 return RemoveNoopCast(CI->getOperand(0));
735 } else if (isa<PointerType>(CTy) && isa<PointerType>(OpTy))
736 return RemoveNoopCast(CI->getOperand(0));
741 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
742 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
744 if (Op0 == Op1) // sub X, X -> 0
745 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
747 // If this is a 'B = x-(-A)', change to B = x+A...
748 if (Value *V = dyn_castNegVal(Op1))
749 return BinaryOperator::createAdd(Op0, V);
751 if (isa<UndefValue>(Op0))
752 return ReplaceInstUsesWith(I, Op0); // undef - X -> undef
753 if (isa<UndefValue>(Op1))
754 return ReplaceInstUsesWith(I, Op1); // X - undef -> undef
756 if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
757 // Replace (-1 - A) with (~A)...
758 if (C->isAllOnesValue())
759 return BinaryOperator::createNot(Op1);
761 // C - ~X == X + (1+C)
763 if (match(Op1, m_Not(m_Value(X))))
764 return BinaryOperator::createAdd(X,
765 ConstantExpr::getAdd(C, ConstantInt::get(I.getType(), 1)));
766 // -((uint)X >> 31) -> ((int)X >> 31)
767 // -((int)X >> 31) -> ((uint)X >> 31)
768 if (C->isNullValue()) {
769 Value *NoopCastedRHS = RemoveNoopCast(Op1);
770 if (ShiftInst *SI = dyn_cast<ShiftInst>(NoopCastedRHS))
771 if (SI->getOpcode() == Instruction::Shr)
772 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(SI->getOperand(1))) {
774 if (SI->getType()->isSigned())
775 NewTy = SI->getType()->getUnsignedVersion();
777 NewTy = SI->getType()->getSignedVersion();
778 // Check to see if we are shifting out everything but the sign bit.
779 if (CU->getValue() == SI->getType()->getPrimitiveSizeInBits()-1) {
780 // Ok, the transformation is safe. Insert a cast of the incoming
781 // value, then the new shift, then the new cast.
782 Instruction *FirstCast = new CastInst(SI->getOperand(0), NewTy,
783 SI->getOperand(0)->getName());
784 Value *InV = InsertNewInstBefore(FirstCast, I);
785 Instruction *NewShift = new ShiftInst(Instruction::Shr, FirstCast,
787 if (NewShift->getType() == I.getType())
790 InV = InsertNewInstBefore(NewShift, I);
791 return new CastInst(NewShift, I.getType());
797 // Try to fold constant sub into select arguments.
798 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
799 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
802 if (isa<PHINode>(Op0))
803 if (Instruction *NV = FoldOpIntoPhi(I))
807 if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) {
808 if (Op1I->getOpcode() == Instruction::Add &&
809 !Op0->getType()->isFloatingPoint()) {
810 if (Op1I->getOperand(0) == Op0) // X-(X+Y) == -Y
811 return BinaryOperator::createNeg(Op1I->getOperand(1), I.getName());
812 else if (Op1I->getOperand(1) == Op0) // X-(Y+X) == -Y
813 return BinaryOperator::createNeg(Op1I->getOperand(0), I.getName());
814 else if (ConstantInt *CI1 = dyn_cast<ConstantInt>(I.getOperand(0))) {
815 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(Op1I->getOperand(1)))
816 // C1-(X+C2) --> (C1-C2)-X
817 return BinaryOperator::createSub(ConstantExpr::getSub(CI1, CI2),
818 Op1I->getOperand(0));
822 if (Op1I->hasOneUse()) {
823 // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
824 // is not used by anyone else...
826 if (Op1I->getOpcode() == Instruction::Sub &&
827 !Op1I->getType()->isFloatingPoint()) {
828 // Swap the two operands of the subexpr...
829 Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
830 Op1I->setOperand(0, IIOp1);
831 Op1I->setOperand(1, IIOp0);
833 // Create the new top level add instruction...
834 return BinaryOperator::createAdd(Op0, Op1);
837 // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
839 if (Op1I->getOpcode() == Instruction::And &&
840 (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
841 Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
844 InsertNewInstBefore(BinaryOperator::createNot(OtherOp, "B.not"), I);
845 return BinaryOperator::createAnd(Op0, NewNot);
848 // -(X sdiv C) -> (X sdiv -C)
849 if (Op1I->getOpcode() == Instruction::Div)
850 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
851 if (CSI->isNullValue())
852 if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1)))
853 return BinaryOperator::createDiv(Op1I->getOperand(0),
854 ConstantExpr::getNeg(DivRHS));
856 // X - X*C --> X * (1-C)
858 if (dyn_castFoldableMul(Op1I, C2) == Op0) {
860 ConstantExpr::getSub(ConstantInt::get(I.getType(), 1), C2);
861 return BinaryOperator::createMul(Op0, CP1);
866 if (!Op0->getType()->isFloatingPoint())
867 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0))
868 if (Op0I->getOpcode() == Instruction::Add) {
869 if (Op0I->getOperand(0) == Op1) // (Y+X)-Y == X
870 return ReplaceInstUsesWith(I, Op0I->getOperand(1));
871 else if (Op0I->getOperand(1) == Op1) // (X+Y)-Y == X
872 return ReplaceInstUsesWith(I, Op0I->getOperand(0));
873 } else if (Op0I->getOpcode() == Instruction::Sub) {
874 if (Op0I->getOperand(0) == Op1) // (X-Y)-X == -Y
875 return BinaryOperator::createNeg(Op0I->getOperand(1), I.getName());
879 if (Value *X = dyn_castFoldableMul(Op0, C1)) {
880 if (X == Op1) { // X*C - X --> X * (C-1)
881 Constant *CP1 = ConstantExpr::getSub(C1, ConstantInt::get(I.getType(),1));
882 return BinaryOperator::createMul(Op1, CP1);
885 ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2)
886 if (X == dyn_castFoldableMul(Op1, C2))
887 return BinaryOperator::createMul(Op1, ConstantExpr::getSub(C1, C2));
892 /// isSignBitCheck - Given an exploded setcc instruction, return true if it is
893 /// really just returns true if the most significant (sign) bit is set.
894 static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) {
895 if (RHS->getType()->isSigned()) {
896 // True if source is LHS < 0 or LHS <= -1
897 return Opcode == Instruction::SetLT && RHS->isNullValue() ||
898 Opcode == Instruction::SetLE && RHS->isAllOnesValue();
900 ConstantUInt *RHSC = cast<ConstantUInt>(RHS);
901 // True if source is LHS > 127 or LHS >= 128, where the constants depend on
902 // the size of the integer type.
903 if (Opcode == Instruction::SetGE)
904 return RHSC->getValue() ==
905 1ULL << (RHS->getType()->getPrimitiveSizeInBits()-1);
906 if (Opcode == Instruction::SetGT)
907 return RHSC->getValue() ==
908 (1ULL << (RHS->getType()->getPrimitiveSizeInBits()-1))-1;
913 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
914 bool Changed = SimplifyCommutative(I);
915 Value *Op0 = I.getOperand(0);
917 if (isa<UndefValue>(I.getOperand(1))) // undef * X -> 0
918 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
920 // Simplify mul instructions with a constant RHS...
921 if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
922 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
924 // ((X << C1)*C2) == (X * (C2 << C1))
925 if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
926 if (SI->getOpcode() == Instruction::Shl)
927 if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
928 return BinaryOperator::createMul(SI->getOperand(0),
929 ConstantExpr::getShl(CI, ShOp));
931 if (CI->isNullValue())
932 return ReplaceInstUsesWith(I, Op1); // X * 0 == 0
933 if (CI->equalsInt(1)) // X * 1 == X
934 return ReplaceInstUsesWith(I, Op0);
935 if (CI->isAllOnesValue()) // X * -1 == 0 - X
936 return BinaryOperator::createNeg(Op0, I.getName());
938 int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
939 if (isPowerOf2_64(Val)) { // Replace X*(2^C) with X << C
940 uint64_t C = Log2_64(Val);
941 return new ShiftInst(Instruction::Shl, Op0,
942 ConstantUInt::get(Type::UByteTy, C));
944 } else if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1)) {
945 if (Op1F->isNullValue())
946 return ReplaceInstUsesWith(I, Op1);
948 // "In IEEE floating point, x*1 is not equivalent to x for nans. However,
949 // ANSI says we can drop signals, so we can do this anyway." (from GCC)
950 if (Op1F->getValue() == 1.0)
951 return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0'
954 // Try to fold constant mul into select arguments.
955 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
956 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
959 if (isa<PHINode>(Op0))
960 if (Instruction *NV = FoldOpIntoPhi(I))
964 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y
965 if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
966 return BinaryOperator::createMul(Op0v, Op1v);
968 // If one of the operands of the multiply is a cast from a boolean value, then
969 // we know the bool is either zero or one, so this is a 'masking' multiply.
970 // See if we can simplify things based on how the boolean was originally
972 CastInst *BoolCast = 0;
973 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(0)))
974 if (CI->getOperand(0)->getType() == Type::BoolTy)
977 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(1)))
978 if (CI->getOperand(0)->getType() == Type::BoolTy)
981 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BoolCast->getOperand(0))) {
982 Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1);
983 const Type *SCOpTy = SCIOp0->getType();
985 // If the setcc is true iff the sign bit of X is set, then convert this
986 // multiply into a shift/and combination.
987 if (isa<ConstantInt>(SCIOp1) &&
988 isSignBitCheck(SCI->getOpcode(), SCIOp0, cast<ConstantInt>(SCIOp1))) {
989 // Shift the X value right to turn it into "all signbits".
990 Constant *Amt = ConstantUInt::get(Type::UByteTy,
991 SCOpTy->getPrimitiveSizeInBits()-1);
992 if (SCIOp0->getType()->isUnsigned()) {
993 const Type *NewTy = SCIOp0->getType()->getSignedVersion();
994 SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy,
995 SCIOp0->getName()), I);
999 InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt,
1000 BoolCast->getOperand(0)->getName()+
1003 // If the multiply type is not the same as the source type, sign extend
1004 // or truncate to the multiply type.
1005 if (I.getType() != V->getType())
1006 V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I);
1008 Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
1009 return BinaryOperator::createAnd(V, OtherOp);
1014 return Changed ? &I : 0;
1017 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
1018 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1020 if (isa<UndefValue>(Op0)) // undef / X -> 0
1021 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1022 if (isa<UndefValue>(Op1))
1023 return ReplaceInstUsesWith(I, Op1); // X / undef -> undef
1025 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
1027 if (RHS->equalsInt(1))
1028 return ReplaceInstUsesWith(I, Op0);
1031 if (RHS->isAllOnesValue())
1032 return BinaryOperator::createNeg(Op0);
1034 if (Instruction *LHS = dyn_cast<Instruction>(Op0))
1035 if (LHS->getOpcode() == Instruction::Div)
1036 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
1037 // (X / C1) / C2 -> X / (C1*C2)
1038 return BinaryOperator::createDiv(LHS->getOperand(0),
1039 ConstantExpr::getMul(RHS, LHSRHS));
1042 // Check to see if this is an unsigned division with an exact power of 2,
1043 // if so, convert to a right shift.
1044 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
1045 if (uint64_t Val = C->getValue()) // Don't break X / 0
1046 if (isPowerOf2_64(Val)) {
1047 uint64_t C = Log2_64(Val);
1048 return new ShiftInst(Instruction::Shr, Op0,
1049 ConstantUInt::get(Type::UByteTy, C));
1053 if (RHS->getType()->isSigned())
1054 if (Value *LHSNeg = dyn_castNegVal(Op0))
1055 return BinaryOperator::createDiv(LHSNeg, ConstantExpr::getNeg(RHS));
1057 if (!RHS->isNullValue()) {
1058 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1059 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1061 if (isa<PHINode>(Op0))
1062 if (Instruction *NV = FoldOpIntoPhi(I))
1067 // If this is 'udiv X, (Cond ? C1, C2)' where C1&C2 are powers of two,
1068 // transform this into: '(Cond ? (udiv X, C1) : (udiv X, C2))'.
1069 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1070 if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
1071 if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
1072 if (STO->getValue() == 0) { // Couldn't be this argument.
1073 I.setOperand(1, SFO);
1075 } else if (SFO->getValue() == 0) {
1076 I.setOperand(1, STO);
1080 uint64_t TVA = STO->getValue(), FVA = SFO->getValue();
1081 if (isPowerOf2_64(TVA) && isPowerOf2_64(FVA)) {
1082 unsigned TSA = Log2_64(TVA), FSA = Log2_64(FVA);
1083 Constant *TC = ConstantUInt::get(Type::UByteTy, TSA);
1084 Instruction *TSI = new ShiftInst(Instruction::Shr, Op0,
1085 TC, SI->getName()+".t");
1086 TSI = InsertNewInstBefore(TSI, I);
1088 Constant *FC = ConstantUInt::get(Type::UByteTy, FSA);
1089 Instruction *FSI = new ShiftInst(Instruction::Shr, Op0,
1090 FC, SI->getName()+".f");
1091 FSI = InsertNewInstBefore(FSI, I);
1092 return new SelectInst(SI->getOperand(0), TSI, FSI);
1096 // 0 / X == 0, we don't need to preserve faults!
1097 if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
1098 if (LHS->equalsInt(0))
1099 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1105 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
1106 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1107 if (I.getType()->isSigned())
1108 if (Value *RHSNeg = dyn_castNegVal(Op1))
1109 if (!isa<ConstantSInt>(RHSNeg) ||
1110 cast<ConstantSInt>(RHSNeg)->getValue() > 0) {
1112 AddUsesToWorkList(I);
1113 I.setOperand(1, RHSNeg);
1117 if (isa<UndefValue>(Op0)) // undef % X -> 0
1118 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1119 if (isa<UndefValue>(Op1))
1120 return ReplaceInstUsesWith(I, Op1); // X % undef -> undef
1122 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
1123 if (RHS->equalsInt(1)) // X % 1 == 0
1124 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1126 // Check to see if this is an unsigned remainder with an exact power of 2,
1127 // if so, convert to a bitwise and.
1128 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
1129 if (uint64_t Val = C->getValue()) // Don't break X % 0 (divide by zero)
1130 if (!(Val & (Val-1))) // Power of 2
1131 return BinaryOperator::createAnd(Op0,
1132 ConstantUInt::get(I.getType(), Val-1));
1134 if (!RHS->isNullValue()) {
1135 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1136 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1138 if (isa<PHINode>(Op0))
1139 if (Instruction *NV = FoldOpIntoPhi(I))
1144 // If this is 'urem X, (Cond ? C1, C2)' where C1&C2 are powers of two,
1145 // transform this into: '(Cond ? (urem X, C1) : (urem X, C2))'.
1146 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1147 if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
1148 if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
1149 if (STO->getValue() == 0) { // Couldn't be this argument.
1150 I.setOperand(1, SFO);
1152 } else if (SFO->getValue() == 0) {
1153 I.setOperand(1, STO);
1157 if (!(STO->getValue() & (STO->getValue()-1)) &&
1158 !(SFO->getValue() & (SFO->getValue()-1))) {
1159 Value *TrueAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
1160 SubOne(STO), SI->getName()+".t"), I);
1161 Value *FalseAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
1162 SubOne(SFO), SI->getName()+".f"), I);
1163 return new SelectInst(SI->getOperand(0), TrueAnd, FalseAnd);
1167 // 0 % X == 0, we don't need to preserve faults!
1168 if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
1169 if (LHS->equalsInt(0))
1170 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1175 // isMaxValueMinusOne - return true if this is Max-1
1176 static bool isMaxValueMinusOne(const ConstantInt *C) {
1177 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
1178 // Calculate -1 casted to the right type...
1179 unsigned TypeBits = C->getType()->getPrimitiveSizeInBits();
1180 uint64_t Val = ~0ULL; // All ones
1181 Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
1182 return CU->getValue() == Val-1;
1185 const ConstantSInt *CS = cast<ConstantSInt>(C);
1187 // Calculate 0111111111..11111
1188 unsigned TypeBits = C->getType()->getPrimitiveSizeInBits();
1189 int64_t Val = INT64_MAX; // All ones
1190 Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
1191 return CS->getValue() == Val-1;
1194 // isMinValuePlusOne - return true if this is Min+1
1195 static bool isMinValuePlusOne(const ConstantInt *C) {
1196 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
1197 return CU->getValue() == 1;
1199 const ConstantSInt *CS = cast<ConstantSInt>(C);
1201 // Calculate 1111111111000000000000
1202 unsigned TypeBits = C->getType()->getPrimitiveSizeInBits();
1203 int64_t Val = -1; // All ones
1204 Val <<= TypeBits-1; // Shift over to the right spot
1205 return CS->getValue() == Val+1;
1208 // isOneBitSet - Return true if there is exactly one bit set in the specified
1210 static bool isOneBitSet(const ConstantInt *CI) {
1211 uint64_t V = CI->getRawValue();
1212 return V && (V & (V-1)) == 0;
1215 #if 0 // Currently unused
1216 // isLowOnes - Return true if the constant is of the form 0+1+.
1217 static bool isLowOnes(const ConstantInt *CI) {
1218 uint64_t V = CI->getRawValue();
1220 // There won't be bits set in parts that the type doesn't contain.
1221 V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
1223 uint64_t U = V+1; // If it is low ones, this should be a power of two.
1224 return U && V && (U & V) == 0;
1228 // isHighOnes - Return true if the constant is of the form 1+0+.
1229 // This is the same as lowones(~X).
1230 static bool isHighOnes(const ConstantInt *CI) {
1231 uint64_t V = ~CI->getRawValue();
1232 if (~V == 0) return false; // 0's does not match "1+"
1234 // There won't be bits set in parts that the type doesn't contain.
1235 V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
1237 uint64_t U = V+1; // If it is low ones, this should be a power of two.
1238 return U && V && (U & V) == 0;
1242 /// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits
1243 /// are carefully arranged to allow folding of expressions such as:
1245 /// (A < B) | (A > B) --> (A != B)
1247 /// Bit value '4' represents that the comparison is true if A > B, bit value '2'
1248 /// represents that the comparison is true if A == B, and bit value '1' is true
1251 static unsigned getSetCondCode(const SetCondInst *SCI) {
1252 switch (SCI->getOpcode()) {
1254 case Instruction::SetGT: return 1;
1255 case Instruction::SetEQ: return 2;
1256 case Instruction::SetGE: return 3;
1257 case Instruction::SetLT: return 4;
1258 case Instruction::SetNE: return 5;
1259 case Instruction::SetLE: return 6;
1262 assert(0 && "Invalid SetCC opcode!");
1267 /// getSetCCValue - This is the complement of getSetCondCode, which turns an
1268 /// opcode and two operands into either a constant true or false, or a brand new
1269 /// SetCC instruction.
1270 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
1272 case 0: return ConstantBool::False;
1273 case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
1274 case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
1275 case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
1276 case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
1277 case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
1278 case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
1279 case 7: return ConstantBool::True;
1280 default: assert(0 && "Illegal SetCCCode!"); return 0;
1284 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1285 struct FoldSetCCLogical {
1288 FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
1289 : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
1290 bool shouldApply(Value *V) const {
1291 if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
1292 return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
1293 SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
1296 Instruction *apply(BinaryOperator &Log) const {
1297 SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
1298 if (SCI->getOperand(0) != LHS) {
1299 assert(SCI->getOperand(1) == LHS);
1300 SCI->swapOperands(); // Swap the LHS and RHS of the SetCC
1303 unsigned LHSCode = getSetCondCode(SCI);
1304 unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
1306 switch (Log.getOpcode()) {
1307 case Instruction::And: Code = LHSCode & RHSCode; break;
1308 case Instruction::Or: Code = LHSCode | RHSCode; break;
1309 case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
1310 default: assert(0 && "Illegal logical opcode!"); return 0;
1313 Value *RV = getSetCCValue(Code, LHS, RHS);
1314 if (Instruction *I = dyn_cast<Instruction>(RV))
1316 // Otherwise, it's a constant boolean value...
1317 return IC.ReplaceInstUsesWith(Log, RV);
1322 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1323 /// this predicate to simplify operations downstream. V and Mask are known to
1324 /// be the same type.
1325 static bool MaskedValueIsZero(Value *V, ConstantIntegral *Mask) {
1326 // Note, we cannot consider 'undef' to be "IsZero" here. The problem is that
1327 // we cannot optimize based on the assumption that it is zero without changing
1328 // to to an explicit zero. If we don't change it to zero, other code could
1329 // optimized based on the contradictory assumption that it is non-zero.
1330 // Because instcombine aggressively folds operations with undef args anyway,
1331 // this won't lose us code quality.
1332 if (Mask->isNullValue())
1334 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(V))
1335 return ConstantExpr::getAnd(CI, Mask)->isNullValue();
1337 if (Instruction *I = dyn_cast<Instruction>(V)) {
1338 switch (I->getOpcode()) {
1339 case Instruction::And:
1340 // (X & C1) & C2 == 0 iff C1 & C2 == 0.
1341 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(I->getOperand(1)))
1342 if (ConstantExpr::getAnd(CI, Mask)->isNullValue())
1345 case Instruction::Or:
1346 // If the LHS and the RHS are MaskedValueIsZero, the result is also zero.
1347 return MaskedValueIsZero(I->getOperand(1), Mask) &&
1348 MaskedValueIsZero(I->getOperand(0), Mask);
1349 case Instruction::Select:
1350 // If the T and F values are MaskedValueIsZero, the result is also zero.
1351 return MaskedValueIsZero(I->getOperand(2), Mask) &&
1352 MaskedValueIsZero(I->getOperand(1), Mask);
1353 case Instruction::Cast: {
1354 const Type *SrcTy = I->getOperand(0)->getType();
1355 if (SrcTy == Type::BoolTy)
1356 return (Mask->getRawValue() & 1) == 0;
1358 if (SrcTy->isInteger()) {
1359 // (cast <ty> X to int) & C2 == 0 iff <ty> could not have contained C2.
1360 if (SrcTy->isUnsigned() && // Only handle zero ext.
1361 ConstantExpr::getCast(Mask, SrcTy)->isNullValue())
1364 // If this is a noop cast, recurse.
1365 if ((SrcTy->isSigned() && SrcTy->getUnsignedVersion() == I->getType())||
1366 SrcTy->getSignedVersion() == I->getType()) {
1368 ConstantExpr::getCast(Mask, I->getOperand(0)->getType());
1369 return MaskedValueIsZero(I->getOperand(0),
1370 cast<ConstantIntegral>(NewMask));
1375 case Instruction::Shl:
1376 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1377 if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
1378 return MaskedValueIsZero(I->getOperand(0),
1379 cast<ConstantIntegral>(ConstantExpr::getUShr(Mask, SA)));
1381 case Instruction::Shr:
1382 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1383 if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
1384 if (I->getType()->isUnsigned()) {
1385 Constant *C1 = ConstantIntegral::getAllOnesValue(I->getType());
1386 C1 = ConstantExpr::getShr(C1, SA);
1387 C1 = ConstantExpr::getAnd(C1, Mask);
1388 if (C1->isNullValue())
1398 // OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where
1399 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
1400 // guaranteed to be either a shift instruction or a binary operator.
1401 Instruction *InstCombiner::OptAndOp(Instruction *Op,
1402 ConstantIntegral *OpRHS,
1403 ConstantIntegral *AndRHS,
1404 BinaryOperator &TheAnd) {
1405 Value *X = Op->getOperand(0);
1406 Constant *Together = 0;
1407 if (!isa<ShiftInst>(Op))
1408 Together = ConstantExpr::getAnd(AndRHS, OpRHS);
1410 switch (Op->getOpcode()) {
1411 case Instruction::Xor:
1412 if (Op->hasOneUse()) {
1413 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1414 std::string OpName = Op->getName(); Op->setName("");
1415 Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName);
1416 InsertNewInstBefore(And, TheAnd);
1417 return BinaryOperator::createXor(And, Together);
1420 case Instruction::Or:
1421 if (Together == AndRHS) // (X | C) & C --> C
1422 return ReplaceInstUsesWith(TheAnd, AndRHS);
1424 if (Op->hasOneUse() && Together != OpRHS) {
1425 // (X | C1) & C2 --> (X | (C1&C2)) & C2
1426 std::string Op0Name = Op->getName(); Op->setName("");
1427 Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name);
1428 InsertNewInstBefore(Or, TheAnd);
1429 return BinaryOperator::createAnd(Or, AndRHS);
1432 case Instruction::Add:
1433 if (Op->hasOneUse()) {
1434 // Adding a one to a single bit bit-field should be turned into an XOR
1435 // of the bit. First thing to check is to see if this AND is with a
1436 // single bit constant.
1437 uint64_t AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
1439 // Clear bits that are not part of the constant.
1440 AndRHSV &= ~0ULL >> (64-AndRHS->getType()->getPrimitiveSizeInBits());
1442 // If there is only one bit set...
1443 if (isOneBitSet(cast<ConstantInt>(AndRHS))) {
1444 // Ok, at this point, we know that we are masking the result of the
1445 // ADD down to exactly one bit. If the constant we are adding has
1446 // no bits set below this bit, then we can eliminate the ADD.
1447 uint64_t AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
1449 // Check to see if any bits below the one bit set in AndRHSV are set.
1450 if ((AddRHS & (AndRHSV-1)) == 0) {
1451 // If not, the only thing that can effect the output of the AND is
1452 // the bit specified by AndRHSV. If that bit is set, the effect of
1453 // the XOR is to toggle the bit. If it is clear, then the ADD has
1455 if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
1456 TheAnd.setOperand(0, X);
1459 std::string Name = Op->getName(); Op->setName("");
1460 // Pull the XOR out of the AND.
1461 Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS, Name);
1462 InsertNewInstBefore(NewAnd, TheAnd);
1463 return BinaryOperator::createXor(NewAnd, AndRHS);
1470 case Instruction::Shl: {
1471 // We know that the AND will not produce any of the bits shifted in, so if
1472 // the anded constant includes them, clear them now!
1474 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1475 Constant *ShlMask = ConstantExpr::getShl(AllOne, OpRHS);
1476 Constant *CI = ConstantExpr::getAnd(AndRHS, ShlMask);
1478 if (CI == ShlMask) { // Masking out bits that the shift already masks
1479 return ReplaceInstUsesWith(TheAnd, Op); // No need for the and.
1480 } else if (CI != AndRHS) { // Reducing bits set in and.
1481 TheAnd.setOperand(1, CI);
1486 case Instruction::Shr:
1487 // We know that the AND will not produce any of the bits shifted in, so if
1488 // the anded constant includes them, clear them now! This only applies to
1489 // unsigned shifts, because a signed shr may bring in set bits!
1491 if (AndRHS->getType()->isUnsigned()) {
1492 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1493 Constant *ShrMask = ConstantExpr::getShr(AllOne, OpRHS);
1494 Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
1496 if (CI == ShrMask) { // Masking out bits that the shift already masks.
1497 return ReplaceInstUsesWith(TheAnd, Op);
1498 } else if (CI != AndRHS) {
1499 TheAnd.setOperand(1, CI); // Reduce bits set in and cst.
1502 } else { // Signed shr.
1503 // See if this is shifting in some sign extension, then masking it out
1505 if (Op->hasOneUse()) {
1506 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1507 Constant *ShrMask = ConstantExpr::getUShr(AllOne, OpRHS);
1508 Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
1509 if (CI == AndRHS) { // Masking out bits shifted in.
1510 // Make the argument unsigned.
1511 Value *ShVal = Op->getOperand(0);
1512 ShVal = InsertCastBefore(ShVal,
1513 ShVal->getType()->getUnsignedVersion(),
1515 ShVal = InsertNewInstBefore(new ShiftInst(Instruction::Shr, ShVal,
1516 OpRHS, Op->getName()),
1518 Value *AndRHS2 = ConstantExpr::getCast(AndRHS, ShVal->getType());
1519 ShVal = InsertNewInstBefore(BinaryOperator::createAnd(ShVal, AndRHS2,
1522 return new CastInst(ShVal, Op->getType());
1532 /// InsertRangeTest - Emit a computation of: (V >= Lo && V < Hi) if Inside is
1533 /// true, otherwise (V < Lo || V >= Hi). In pratice, we emit the more efficient
1534 /// (V-Lo) <u Hi-Lo. This method expects that Lo <= Hi. IB is the location to
1535 /// insert new instructions.
1536 Instruction *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
1537 bool Inside, Instruction &IB) {
1538 assert(cast<ConstantBool>(ConstantExpr::getSetLE(Lo, Hi))->getValue() &&
1539 "Lo is not <= Hi in range emission code!");
1541 if (Lo == Hi) // Trivially false.
1542 return new SetCondInst(Instruction::SetNE, V, V);
1543 if (cast<ConstantIntegral>(Lo)->isMinValue())
1544 return new SetCondInst(Instruction::SetLT, V, Hi);
1546 Constant *AddCST = ConstantExpr::getNeg(Lo);
1547 Instruction *Add = BinaryOperator::createAdd(V, AddCST,V->getName()+".off");
1548 InsertNewInstBefore(Add, IB);
1549 // Convert to unsigned for the comparison.
1550 const Type *UnsType = Add->getType()->getUnsignedVersion();
1551 Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
1552 AddCST = ConstantExpr::getAdd(AddCST, Hi);
1553 AddCST = ConstantExpr::getCast(AddCST, UnsType);
1554 return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
1557 if (Lo == Hi) // Trivially true.
1558 return new SetCondInst(Instruction::SetEQ, V, V);
1560 Hi = SubOne(cast<ConstantInt>(Hi));
1561 if (cast<ConstantIntegral>(Lo)->isMinValue()) // V < 0 || V >= Hi ->'V > Hi-1'
1562 return new SetCondInst(Instruction::SetGT, V, Hi);
1564 // Emit X-Lo > Hi-Lo-1
1565 Constant *AddCST = ConstantExpr::getNeg(Lo);
1566 Instruction *Add = BinaryOperator::createAdd(V, AddCST, V->getName()+".off");
1567 InsertNewInstBefore(Add, IB);
1568 // Convert to unsigned for the comparison.
1569 const Type *UnsType = Add->getType()->getUnsignedVersion();
1570 Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
1571 AddCST = ConstantExpr::getAdd(AddCST, Hi);
1572 AddCST = ConstantExpr::getCast(AddCST, UnsType);
1573 return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
1576 /// FoldLogicalPlusAnd - We know that Mask is of the form 0+1+, and that this is
1577 /// part of an expression (LHS +/- RHS) & Mask, where isSub determines whether
1578 /// the operator is a sub. If we can fold one of the following xforms:
1580 /// ((A & N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == Mask
1581 /// ((A | N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0
1582 /// ((A ^ N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0
1584 /// return (A +/- B).
1586 Value *InstCombiner::FoldLogicalPlusAnd(Value *LHS, Value *RHS,
1587 ConstantIntegral *Mask, bool isSub,
1589 Instruction *LHSI = dyn_cast<Instruction>(LHS);
1590 if (!LHSI || LHSI->getNumOperands() != 2 ||
1591 !isa<ConstantInt>(LHSI->getOperand(1))) return 0;
1593 ConstantInt *N = cast<ConstantInt>(LHSI->getOperand(1));
1595 switch (LHSI->getOpcode()) {
1597 case Instruction::And:
1598 if (ConstantExpr::getAnd(N, Mask) == Mask)
1601 case Instruction::Or:
1602 case Instruction::Xor:
1603 if (ConstantExpr::getAnd(N, Mask)->isNullValue())
1610 New = BinaryOperator::createSub(LHSI->getOperand(0), RHS, "fold");
1612 New = BinaryOperator::createAdd(LHSI->getOperand(0), RHS, "fold");
1613 return InsertNewInstBefore(New, I);
1617 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
1618 bool Changed = SimplifyCommutative(I);
1619 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1621 if (isa<UndefValue>(Op1)) // X & undef -> 0
1622 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1626 return ReplaceInstUsesWith(I, Op1);
1628 if (ConstantIntegral *AndRHS = dyn_cast<ConstantIntegral>(Op1)) {
1630 if (AndRHS->isAllOnesValue())
1631 return ReplaceInstUsesWith(I, Op0);
1633 if (MaskedValueIsZero(Op0, AndRHS)) // LHS & RHS == 0
1634 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1636 // If the mask is not masking out any bits, there is no reason to do the
1637 // and in the first place.
1638 ConstantIntegral *NotAndRHS =
1639 cast<ConstantIntegral>(ConstantExpr::getNot(AndRHS));
1640 if (MaskedValueIsZero(Op0, NotAndRHS))
1641 return ReplaceInstUsesWith(I, Op0);
1643 // Optimize a variety of ((val OP C1) & C2) combinations...
1644 if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
1645 Instruction *Op0I = cast<Instruction>(Op0);
1646 Value *Op0LHS = Op0I->getOperand(0);
1647 Value *Op0RHS = Op0I->getOperand(1);
1648 switch (Op0I->getOpcode()) {
1649 case Instruction::Xor:
1650 case Instruction::Or:
1651 // (X ^ V) & C2 --> (X & C2) iff (V & C2) == 0
1652 // (X | V) & C2 --> (X & C2) iff (V & C2) == 0
1653 if (MaskedValueIsZero(Op0LHS, AndRHS))
1654 return BinaryOperator::createAnd(Op0RHS, AndRHS);
1655 if (MaskedValueIsZero(Op0RHS, AndRHS))
1656 return BinaryOperator::createAnd(Op0LHS, AndRHS);
1658 // If the mask is only needed on one incoming arm, push it up.
1659 if (Op0I->hasOneUse()) {
1660 if (MaskedValueIsZero(Op0LHS, NotAndRHS)) {
1661 // Not masking anything out for the LHS, move to RHS.
1662 Instruction *NewRHS = BinaryOperator::createAnd(Op0RHS, AndRHS,
1663 Op0RHS->getName()+".masked");
1664 InsertNewInstBefore(NewRHS, I);
1665 return BinaryOperator::create(
1666 cast<BinaryOperator>(Op0I)->getOpcode(), Op0LHS, NewRHS);
1668 if (!isa<Constant>(NotAndRHS) &&
1669 MaskedValueIsZero(Op0RHS, NotAndRHS)) {
1670 // Not masking anything out for the RHS, move to LHS.
1671 Instruction *NewLHS = BinaryOperator::createAnd(Op0LHS, AndRHS,
1672 Op0LHS->getName()+".masked");
1673 InsertNewInstBefore(NewLHS, I);
1674 return BinaryOperator::create(
1675 cast<BinaryOperator>(Op0I)->getOpcode(), NewLHS, Op0RHS);
1680 case Instruction::And:
1681 // (X & V) & C2 --> 0 iff (V & C2) == 0
1682 if (MaskedValueIsZero(Op0LHS, AndRHS) ||
1683 MaskedValueIsZero(Op0RHS, AndRHS))
1684 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1686 case Instruction::Add:
1687 // If the AndRHS is a power of two minus one (0+1+).
1688 if ((AndRHS->getRawValue() & AndRHS->getRawValue()+1) == 0) {
1689 // ((A & N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == AndRHS.
1690 // ((A | N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0
1691 // ((A ^ N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0
1692 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, false, I))
1693 return BinaryOperator::createAnd(V, AndRHS);
1694 if (Value *V = FoldLogicalPlusAnd(Op0RHS, Op0LHS, AndRHS, false, I))
1695 return BinaryOperator::createAnd(V, AndRHS); // Add commutes
1699 case Instruction::Sub:
1700 // If the AndRHS is a power of two minus one (0+1+).
1701 if ((AndRHS->getRawValue() & AndRHS->getRawValue()+1) == 0) {
1702 // ((A & N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == AndRHS.
1703 // ((A | N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
1704 // ((A ^ N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
1705 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I))
1706 return BinaryOperator::createAnd(V, AndRHS);
1711 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1712 if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1714 } else if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
1715 const Type *SrcTy = CI->getOperand(0)->getType();
1717 // If this is an integer truncation or change from signed-to-unsigned, and
1718 // if the source is an and/or with immediate, transform it. This
1719 // frequently occurs for bitfield accesses.
1720 if (Instruction *CastOp = dyn_cast<Instruction>(CI->getOperand(0))) {
1721 if (SrcTy->getPrimitiveSizeInBits() >=
1722 I.getType()->getPrimitiveSizeInBits() &&
1723 CastOp->getNumOperands() == 2)
1724 if (ConstantInt *AndCI =dyn_cast<ConstantInt>(CastOp->getOperand(1)))
1725 if (CastOp->getOpcode() == Instruction::And) {
1726 // Change: and (cast (and X, C1) to T), C2
1727 // into : and (cast X to T), trunc(C1)&C2
1728 // This will folds the two ands together, which may allow other
1730 Instruction *NewCast =
1731 new CastInst(CastOp->getOperand(0), I.getType(),
1732 CastOp->getName()+".shrunk");
1733 NewCast = InsertNewInstBefore(NewCast, I);
1735 Constant *C3=ConstantExpr::getCast(AndCI, I.getType());//trunc(C1)
1736 C3 = ConstantExpr::getAnd(C3, AndRHS); // trunc(C1)&C2
1737 return BinaryOperator::createAnd(NewCast, C3);
1738 } else if (CastOp->getOpcode() == Instruction::Or) {
1739 // Change: and (cast (or X, C1) to T), C2
1740 // into : trunc(C1)&C2 iff trunc(C1)&C2 == C2
1741 Constant *C3=ConstantExpr::getCast(AndCI, I.getType());//trunc(C1)
1742 if (ConstantExpr::getAnd(C3, AndRHS) == AndRHS) // trunc(C1)&C2
1743 return ReplaceInstUsesWith(I, AndRHS);
1748 // If this is an integer sign or zero extension instruction.
1749 if (SrcTy->isIntegral() &&
1750 SrcTy->getPrimitiveSizeInBits() <
1751 CI->getType()->getPrimitiveSizeInBits()) {
1753 if (SrcTy->isUnsigned()) {
1754 // See if this and is clearing out bits that are known to be zero
1755 // anyway (due to the zero extension).
1756 Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
1757 Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
1758 Constant *Result = ConstantExpr::getAnd(Mask, AndRHS);
1759 if (Result == Mask) // The "and" isn't doing anything, remove it.
1760 return ReplaceInstUsesWith(I, CI);
1761 if (Result != AndRHS) { // Reduce the and RHS constant.
1762 I.setOperand(1, Result);
1767 if (CI->hasOneUse() && SrcTy->isInteger()) {
1768 // We can only do this if all of the sign bits brought in are masked
1769 // out. Compute this by first getting 0000011111, then inverting
1771 Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
1772 Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
1773 Mask = ConstantExpr::getNot(Mask); // 1's in the new bits.
1774 if (ConstantExpr::getAnd(Mask, AndRHS)->isNullValue()) {
1775 // If the and is clearing all of the sign bits, change this to a
1776 // zero extension cast. To do this, cast the cast input to
1777 // unsigned, then to the requested size.
1778 Value *CastOp = CI->getOperand(0);
1780 new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
1781 CI->getName()+".uns");
1782 NC = InsertNewInstBefore(NC, I);
1783 // Finally, insert a replacement for CI.
1784 NC = new CastInst(NC, CI->getType(), CI->getName());
1786 NC = InsertNewInstBefore(NC, I);
1787 WorkList.push_back(CI); // Delete CI later.
1788 I.setOperand(0, NC);
1789 return &I; // The AND operand was modified.
1796 // Try to fold constant and into select arguments.
1797 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1798 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1800 if (isa<PHINode>(Op0))
1801 if (Instruction *NV = FoldOpIntoPhi(I))
1805 Value *Op0NotVal = dyn_castNotVal(Op0);
1806 Value *Op1NotVal = dyn_castNotVal(Op1);
1808 if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0
1809 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1811 // (~A & ~B) == (~(A | B)) - De Morgan's Law
1812 if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1813 Instruction *Or = BinaryOperator::createOr(Op0NotVal, Op1NotVal,
1814 I.getName()+".demorgan");
1815 InsertNewInstBefore(Or, I);
1816 return BinaryOperator::createNot(Or);
1819 if (SetCondInst *RHS = dyn_cast<SetCondInst>(Op1)) {
1820 // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1821 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1824 Value *LHSVal, *RHSVal;
1825 ConstantInt *LHSCst, *RHSCst;
1826 Instruction::BinaryOps LHSCC, RHSCC;
1827 if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
1828 if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
1829 if (LHSVal == RHSVal && // Found (X setcc C1) & (X setcc C2)
1830 // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
1831 LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
1832 RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
1833 // Ensure that the larger constant is on the RHS.
1834 Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
1835 SetCondInst *LHS = cast<SetCondInst>(Op0);
1836 if (cast<ConstantBool>(Cmp)->getValue()) {
1837 std::swap(LHS, RHS);
1838 std::swap(LHSCst, RHSCst);
1839 std::swap(LHSCC, RHSCC);
1842 // At this point, we know we have have two setcc instructions
1843 // comparing a value against two constants and and'ing the result
1844 // together. Because of the above check, we know that we only have
1845 // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the
1846 // FoldSetCCLogical check above), that the two constants are not
1848 assert(LHSCst != RHSCst && "Compares not folded above?");
1851 default: assert(0 && "Unknown integer condition code!");
1852 case Instruction::SetEQ:
1854 default: assert(0 && "Unknown integer condition code!");
1855 case Instruction::SetEQ: // (X == 13 & X == 15) -> false
1856 case Instruction::SetGT: // (X == 13 & X > 15) -> false
1857 return ReplaceInstUsesWith(I, ConstantBool::False);
1858 case Instruction::SetNE: // (X == 13 & X != 15) -> X == 13
1859 case Instruction::SetLT: // (X == 13 & X < 15) -> X == 13
1860 return ReplaceInstUsesWith(I, LHS);
1862 case Instruction::SetNE:
1864 default: assert(0 && "Unknown integer condition code!");
1865 case Instruction::SetLT:
1866 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X < 14) -> X < 13
1867 return new SetCondInst(Instruction::SetLT, LHSVal, LHSCst);
1868 break; // (X != 13 & X < 15) -> no change
1869 case Instruction::SetEQ: // (X != 13 & X == 15) -> X == 15
1870 case Instruction::SetGT: // (X != 13 & X > 15) -> X > 15
1871 return ReplaceInstUsesWith(I, RHS);
1872 case Instruction::SetNE:
1873 if (LHSCst == SubOne(RHSCst)) {// (X != 13 & X != 14) -> X-13 >u 1
1874 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
1875 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
1876 LHSVal->getName()+".off");
1877 InsertNewInstBefore(Add, I);
1878 const Type *UnsType = Add->getType()->getUnsignedVersion();
1879 Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
1880 AddCST = ConstantExpr::getSub(RHSCst, LHSCst);
1881 AddCST = ConstantExpr::getCast(AddCST, UnsType);
1882 return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
1884 break; // (X != 13 & X != 15) -> no change
1887 case Instruction::SetLT:
1889 default: assert(0 && "Unknown integer condition code!");
1890 case Instruction::SetEQ: // (X < 13 & X == 15) -> false
1891 case Instruction::SetGT: // (X < 13 & X > 15) -> false
1892 return ReplaceInstUsesWith(I, ConstantBool::False);
1893 case Instruction::SetNE: // (X < 13 & X != 15) -> X < 13
1894 case Instruction::SetLT: // (X < 13 & X < 15) -> X < 13
1895 return ReplaceInstUsesWith(I, LHS);
1897 case Instruction::SetGT:
1899 default: assert(0 && "Unknown integer condition code!");
1900 case Instruction::SetEQ: // (X > 13 & X == 15) -> X > 13
1901 return ReplaceInstUsesWith(I, LHS);
1902 case Instruction::SetGT: // (X > 13 & X > 15) -> X > 15
1903 return ReplaceInstUsesWith(I, RHS);
1904 case Instruction::SetNE:
1905 if (RHSCst == AddOne(LHSCst)) // (X > 13 & X != 14) -> X > 14
1906 return new SetCondInst(Instruction::SetGT, LHSVal, RHSCst);
1907 break; // (X > 13 & X != 15) -> no change
1908 case Instruction::SetLT: // (X > 13 & X < 15) -> (X-14) <u 1
1909 return InsertRangeTest(LHSVal, AddOne(LHSCst), RHSCst, true, I);
1915 return Changed ? &I : 0;
1918 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
1919 bool Changed = SimplifyCommutative(I);
1920 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1922 if (isa<UndefValue>(Op1))
1923 return ReplaceInstUsesWith(I, // X | undef -> -1
1924 ConstantIntegral::getAllOnesValue(I.getType()));
1926 // or X, X = X or X, 0 == X
1927 if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1928 return ReplaceInstUsesWith(I, Op0);
1931 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1932 // If X is known to only contain bits that already exist in RHS, just
1933 // replace this instruction with RHS directly.
1934 if (MaskedValueIsZero(Op0,
1935 cast<ConstantIntegral>(ConstantExpr::getNot(RHS))))
1936 return ReplaceInstUsesWith(I, RHS);
1938 ConstantInt *C1; Value *X;
1939 // (X & C1) | C2 --> (X | C2) & (C1|C2)
1940 if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
1941 Instruction *Or = BinaryOperator::createOr(X, RHS, Op0->getName());
1943 InsertNewInstBefore(Or, I);
1944 return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, C1));
1947 // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
1948 if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
1949 std::string Op0Name = Op0->getName(); Op0->setName("");
1950 Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
1951 InsertNewInstBefore(Or, I);
1952 return BinaryOperator::createXor(Or,
1953 ConstantExpr::getAnd(C1, ConstantExpr::getNot(RHS)));
1956 // Try to fold constant and into select arguments.
1957 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1958 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1960 if (isa<PHINode>(Op0))
1961 if (Instruction *NV = FoldOpIntoPhi(I))
1965 Value *A, *B; ConstantInt *C1, *C2;
1967 if (match(Op0, m_And(m_Value(A), m_Value(B))))
1968 if (A == Op1 || B == Op1) // (A & ?) | A --> A
1969 return ReplaceInstUsesWith(I, Op1);
1970 if (match(Op1, m_And(m_Value(A), m_Value(B))))
1971 if (A == Op0 || B == Op0) // A | (A & ?) --> A
1972 return ReplaceInstUsesWith(I, Op0);
1974 // (X^C)|Y -> (X|Y)^C iff Y&C == 0
1975 if (Op0->hasOneUse() && match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
1976 MaskedValueIsZero(Op1, C1)) {
1977 Instruction *NOr = BinaryOperator::createOr(A, Op1, Op0->getName());
1979 return BinaryOperator::createXor(InsertNewInstBefore(NOr, I), C1);
1982 // Y|(X^C) -> (X|Y)^C iff Y&C == 0
1983 if (Op1->hasOneUse() && match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
1984 MaskedValueIsZero(Op0, C1)) {
1985 Instruction *NOr = BinaryOperator::createOr(A, Op0, Op1->getName());
1987 return BinaryOperator::createXor(InsertNewInstBefore(NOr, I), C1);
1990 // (A & C1)|(B & C2)
1991 if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
1992 match(Op1, m_And(m_Value(B), m_ConstantInt(C2)))) {
1994 if (A == B) // (A & C1)|(A & C2) == A & (C1|C2)
1995 return BinaryOperator::createAnd(A, ConstantExpr::getOr(C1, C2));
1998 // if A == (add B, C3) or B == (add A, C4)
1999 ConstantInt *C3 = 0;
2001 if ((match(A, m_Add(m_Value(V), m_ConstantInt(C3))) && V == B ||
2002 match(B, m_Add(m_Value(V), m_ConstantInt(C3))) && V == A)) {
2003 if (V == A) std::swap(C1, C2);
2004 // We have: ((V + C3) & C1) | (V & C2)
2005 // if C2 = ~C1 and (C3 & C2) == 0 and C2 is 0+1+
2006 if (C1 == ConstantExpr::getNot(C2) &&
2007 ConstantExpr::getAnd(C3, C2)->isNullValue() &&
2008 (C2->getRawValue() & (C2->getRawValue()+1)) == 0) {
2010 return ReplaceInstUsesWith(I, V == A ? B : A);
2015 if (match(Op0, m_Not(m_Value(A)))) { // ~A | Op1
2016 if (A == Op1) // ~A | A == -1
2017 return ReplaceInstUsesWith(I,
2018 ConstantIntegral::getAllOnesValue(I.getType()));
2022 // Note, A is still live here!
2023 if (match(Op1, m_Not(m_Value(B)))) { // Op0 | ~B
2025 return ReplaceInstUsesWith(I,
2026 ConstantIntegral::getAllOnesValue(I.getType()));
2028 // (~A | ~B) == (~(A & B)) - De Morgan's Law
2029 if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) {
2030 Value *And = InsertNewInstBefore(BinaryOperator::createAnd(A, B,
2031 I.getName()+".demorgan"), I);
2032 return BinaryOperator::createNot(And);
2036 // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
2037 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1))) {
2038 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
2041 Value *LHSVal, *RHSVal;
2042 ConstantInt *LHSCst, *RHSCst;
2043 Instruction::BinaryOps LHSCC, RHSCC;
2044 if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
2045 if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
2046 if (LHSVal == RHSVal && // Found (X setcc C1) | (X setcc C2)
2047 // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
2048 LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
2049 RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
2050 // Ensure that the larger constant is on the RHS.
2051 Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
2052 SetCondInst *LHS = cast<SetCondInst>(Op0);
2053 if (cast<ConstantBool>(Cmp)->getValue()) {
2054 std::swap(LHS, RHS);
2055 std::swap(LHSCst, RHSCst);
2056 std::swap(LHSCC, RHSCC);
2059 // At this point, we know we have have two setcc instructions
2060 // comparing a value against two constants and or'ing the result
2061 // together. Because of the above check, we know that we only have
2062 // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the
2063 // FoldSetCCLogical check above), that the two constants are not
2065 assert(LHSCst != RHSCst && "Compares not folded above?");
2068 default: assert(0 && "Unknown integer condition code!");
2069 case Instruction::SetEQ:
2071 default: assert(0 && "Unknown integer condition code!");
2072 case Instruction::SetEQ:
2073 if (LHSCst == SubOne(RHSCst)) {// (X == 13 | X == 14) -> X-13 <u 2
2074 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
2075 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
2076 LHSVal->getName()+".off");
2077 InsertNewInstBefore(Add, I);
2078 const Type *UnsType = Add->getType()->getUnsignedVersion();
2079 Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
2080 AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst);
2081 AddCST = ConstantExpr::getCast(AddCST, UnsType);
2082 return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
2084 break; // (X == 13 | X == 15) -> no change
2086 case Instruction::SetGT: // (X == 13 | X > 14) -> no change
2088 case Instruction::SetNE: // (X == 13 | X != 15) -> X != 15
2089 case Instruction::SetLT: // (X == 13 | X < 15) -> X < 15
2090 return ReplaceInstUsesWith(I, RHS);
2093 case Instruction::SetNE:
2095 default: assert(0 && "Unknown integer condition code!");
2096 case Instruction::SetEQ: // (X != 13 | X == 15) -> X != 13
2097 case Instruction::SetGT: // (X != 13 | X > 15) -> X != 13
2098 return ReplaceInstUsesWith(I, LHS);
2099 case Instruction::SetNE: // (X != 13 | X != 15) -> true
2100 case Instruction::SetLT: // (X != 13 | X < 15) -> true
2101 return ReplaceInstUsesWith(I, ConstantBool::True);
2104 case Instruction::SetLT:
2106 default: assert(0 && "Unknown integer condition code!");
2107 case Instruction::SetEQ: // (X < 13 | X == 14) -> no change
2109 case Instruction::SetGT: // (X < 13 | X > 15) -> (X-13) > 2
2110 return InsertRangeTest(LHSVal, LHSCst, AddOne(RHSCst), false, I);
2111 case Instruction::SetNE: // (X < 13 | X != 15) -> X != 15
2112 case Instruction::SetLT: // (X < 13 | X < 15) -> X < 15
2113 return ReplaceInstUsesWith(I, RHS);
2116 case Instruction::SetGT:
2118 default: assert(0 && "Unknown integer condition code!");
2119 case Instruction::SetEQ: // (X > 13 | X == 15) -> X > 13
2120 case Instruction::SetGT: // (X > 13 | X > 15) -> X > 13
2121 return ReplaceInstUsesWith(I, LHS);
2122 case Instruction::SetNE: // (X > 13 | X != 15) -> true
2123 case Instruction::SetLT: // (X > 13 | X < 15) -> true
2124 return ReplaceInstUsesWith(I, ConstantBool::True);
2130 return Changed ? &I : 0;
2133 // XorSelf - Implements: X ^ X --> 0
2136 XorSelf(Value *rhs) : RHS(rhs) {}
2137 bool shouldApply(Value *LHS) const { return LHS == RHS; }
2138 Instruction *apply(BinaryOperator &Xor) const {
2144 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
2145 bool Changed = SimplifyCommutative(I);
2146 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2148 if (isa<UndefValue>(Op1))
2149 return ReplaceInstUsesWith(I, Op1); // X ^ undef -> undef
2151 // xor X, X = 0, even if X is nested in a sequence of Xor's.
2152 if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) {
2153 assert(Result == &I && "AssociativeOpt didn't work?");
2154 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
2157 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
2159 if (RHS->isNullValue())
2160 return ReplaceInstUsesWith(I, Op0);
2162 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2163 // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
2164 if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
2165 if (RHS == ConstantBool::True && SCI->hasOneUse())
2166 return new SetCondInst(SCI->getInverseCondition(),
2167 SCI->getOperand(0), SCI->getOperand(1));
2169 // ~(c-X) == X-c-1 == X+(-c-1)
2170 if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
2171 if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
2172 Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
2173 Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C,
2174 ConstantInt::get(I.getType(), 1));
2175 return BinaryOperator::createAdd(Op0I->getOperand(1), ConstantRHS);
2178 // ~(~X & Y) --> (X | ~Y)
2179 if (Op0I->getOpcode() == Instruction::And && RHS->isAllOnesValue()) {
2180 if (dyn_castNotVal(Op0I->getOperand(1))) Op0I->swapOperands();
2181 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) {
2183 BinaryOperator::createNot(Op0I->getOperand(1),
2184 Op0I->getOperand(1)->getName()+".not");
2185 InsertNewInstBefore(NotY, I);
2186 return BinaryOperator::createOr(Op0NotVal, NotY);
2190 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
2191 switch (Op0I->getOpcode()) {
2192 case Instruction::Add:
2193 // ~(X-c) --> (-c-1)-X
2194 if (RHS->isAllOnesValue()) {
2195 Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
2196 return BinaryOperator::createSub(
2197 ConstantExpr::getSub(NegOp0CI,
2198 ConstantInt::get(I.getType(), 1)),
2199 Op0I->getOperand(0));
2202 case Instruction::And:
2203 // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
2204 if (ConstantExpr::getAnd(RHS, Op0CI)->isNullValue())
2205 return BinaryOperator::createOr(Op0, RHS);
2207 case Instruction::Or:
2208 // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
2209 if (ConstantExpr::getAnd(RHS, Op0CI) == RHS)
2210 return BinaryOperator::createAnd(Op0, ConstantExpr::getNot(RHS));
2216 // Try to fold constant and into select arguments.
2217 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
2218 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
2220 if (isa<PHINode>(Op0))
2221 if (Instruction *NV = FoldOpIntoPhi(I))
2225 if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1
2227 return ReplaceInstUsesWith(I,
2228 ConstantIntegral::getAllOnesValue(I.getType()));
2230 if (Value *X = dyn_castNotVal(Op1)) // A ^ ~A == -1
2232 return ReplaceInstUsesWith(I,
2233 ConstantIntegral::getAllOnesValue(I.getType()));
2235 if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
2236 if (Op1I->getOpcode() == Instruction::Or) {
2237 if (Op1I->getOperand(0) == Op0) { // B^(B|A) == (A|B)^B
2238 cast<BinaryOperator>(Op1I)->swapOperands();
2240 std::swap(Op0, Op1);
2241 } else if (Op1I->getOperand(1) == Op0) { // B^(A|B) == (A|B)^B
2243 std::swap(Op0, Op1);
2245 } else if (Op1I->getOpcode() == Instruction::Xor) {
2246 if (Op0 == Op1I->getOperand(0)) // A^(A^B) == B
2247 return ReplaceInstUsesWith(I, Op1I->getOperand(1));
2248 else if (Op0 == Op1I->getOperand(1)) // A^(B^A) == B
2249 return ReplaceInstUsesWith(I, Op1I->getOperand(0));
2252 if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
2253 if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) {
2254 if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B
2255 cast<BinaryOperator>(Op0I)->swapOperands();
2256 if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B
2257 Value *NotB = InsertNewInstBefore(BinaryOperator::createNot(Op1,
2258 Op1->getName()+".not"), I);
2259 return BinaryOperator::createAnd(Op0I->getOperand(0), NotB);
2261 } else if (Op0I->getOpcode() == Instruction::Xor) {
2262 if (Op1 == Op0I->getOperand(0)) // (A^B)^A == B
2263 return ReplaceInstUsesWith(I, Op0I->getOperand(1));
2264 else if (Op1 == Op0I->getOperand(1)) // (B^A)^A == B
2265 return ReplaceInstUsesWith(I, Op0I->getOperand(0));
2268 // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
2269 Value *A, *B; ConstantInt *C1, *C2;
2270 if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
2271 match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) &&
2272 ConstantExpr::getAnd(C1, C2)->isNullValue())
2273 return BinaryOperator::createOr(Op0, Op1);
2275 // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
2276 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
2277 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
2280 return Changed ? &I : 0;
2283 /// MulWithOverflow - Compute Result = In1*In2, returning true if the result
2284 /// overflowed for this type.
2285 static bool MulWithOverflow(ConstantInt *&Result, ConstantInt *In1,
2287 Result = cast<ConstantInt>(ConstantExpr::getMul(In1, In2));
2288 return !In2->isNullValue() && ConstantExpr::getDiv(Result, In2) != In1;
2291 static bool isPositive(ConstantInt *C) {
2292 return cast<ConstantSInt>(C)->getValue() >= 0;
2295 /// AddWithOverflow - Compute Result = In1+In2, returning true if the result
2296 /// overflowed for this type.
2297 static bool AddWithOverflow(ConstantInt *&Result, ConstantInt *In1,
2299 Result = cast<ConstantInt>(ConstantExpr::getAdd(In1, In2));
2301 if (In1->getType()->isUnsigned())
2302 return cast<ConstantUInt>(Result)->getValue() <
2303 cast<ConstantUInt>(In1)->getValue();
2304 if (isPositive(In1) != isPositive(In2))
2306 if (isPositive(In1))
2307 return cast<ConstantSInt>(Result)->getValue() <
2308 cast<ConstantSInt>(In1)->getValue();
2309 return cast<ConstantSInt>(Result)->getValue() >
2310 cast<ConstantSInt>(In1)->getValue();
2313 /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
2314 /// code necessary to compute the offset from the base pointer (without adding
2315 /// in the base pointer). Return the result as a signed integer of intptr size.
2316 static Value *EmitGEPOffset(User *GEP, Instruction &I, InstCombiner &IC) {
2317 TargetData &TD = IC.getTargetData();
2318 gep_type_iterator GTI = gep_type_begin(GEP);
2319 const Type *UIntPtrTy = TD.getIntPtrType();
2320 const Type *SIntPtrTy = UIntPtrTy->getSignedVersion();
2321 Value *Result = Constant::getNullValue(SIntPtrTy);
2323 // Build a mask for high order bits.
2324 uint64_t PtrSizeMask = ~0ULL;
2325 PtrSizeMask >>= 64-(TD.getPointerSize()*8);
2327 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
2328 Value *Op = GEP->getOperand(i);
2329 uint64_t Size = TD.getTypeSize(GTI.getIndexedType()) & PtrSizeMask;
2330 Constant *Scale = ConstantExpr::getCast(ConstantUInt::get(UIntPtrTy, Size),
2332 if (Constant *OpC = dyn_cast<Constant>(Op)) {
2333 if (!OpC->isNullValue()) {
2334 OpC = ConstantExpr::getCast(OpC, SIntPtrTy);
2335 Scale = ConstantExpr::getMul(OpC, Scale);
2336 if (Constant *RC = dyn_cast<Constant>(Result))
2337 Result = ConstantExpr::getAdd(RC, Scale);
2339 // Emit an add instruction.
2340 Result = IC.InsertNewInstBefore(
2341 BinaryOperator::createAdd(Result, Scale,
2342 GEP->getName()+".offs"), I);
2346 // Convert to correct type.
2347 Op = IC.InsertNewInstBefore(new CastInst(Op, SIntPtrTy,
2348 Op->getName()+".c"), I);
2350 // We'll let instcombine(mul) convert this to a shl if possible.
2351 Op = IC.InsertNewInstBefore(BinaryOperator::createMul(Op, Scale,
2352 GEP->getName()+".idx"), I);
2354 // Emit an add instruction.
2355 Result = IC.InsertNewInstBefore(BinaryOperator::createAdd(Op, Result,
2356 GEP->getName()+".offs"), I);
2362 /// FoldGEPSetCC - Fold comparisons between a GEP instruction and something
2363 /// else. At this point we know that the GEP is on the LHS of the comparison.
2364 Instruction *InstCombiner::FoldGEPSetCC(User *GEPLHS, Value *RHS,
2365 Instruction::BinaryOps Cond,
2367 assert(dyn_castGetElementPtr(GEPLHS) && "LHS is not a getelementptr!");
2369 if (CastInst *CI = dyn_cast<CastInst>(RHS))
2370 if (isa<PointerType>(CI->getOperand(0)->getType()))
2371 RHS = CI->getOperand(0);
2373 Value *PtrBase = GEPLHS->getOperand(0);
2374 if (PtrBase == RHS) {
2375 // As an optimization, we don't actually have to compute the actual value of
2376 // OFFSET if this is a seteq or setne comparison, just return whether each
2377 // index is zero or not.
2378 if (Cond == Instruction::SetEQ || Cond == Instruction::SetNE) {
2379 Instruction *InVal = 0;
2380 gep_type_iterator GTI = gep_type_begin(GEPLHS);
2381 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i, ++GTI) {
2383 if (Constant *C = dyn_cast<Constant>(GEPLHS->getOperand(i))) {
2384 if (isa<UndefValue>(C)) // undef index -> undef.
2385 return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
2386 if (C->isNullValue())
2388 else if (TD->getTypeSize(GTI.getIndexedType()) == 0) {
2389 EmitIt = false; // This is indexing into a zero sized array?
2390 } else if (isa<ConstantInt>(C))
2391 return ReplaceInstUsesWith(I, // No comparison is needed here.
2392 ConstantBool::get(Cond == Instruction::SetNE));
2397 new SetCondInst(Cond, GEPLHS->getOperand(i),
2398 Constant::getNullValue(GEPLHS->getOperand(i)->getType()));
2402 InVal = InsertNewInstBefore(InVal, I);
2403 InsertNewInstBefore(Comp, I);
2404 if (Cond == Instruction::SetNE) // True if any are unequal
2405 InVal = BinaryOperator::createOr(InVal, Comp);
2406 else // True if all are equal
2407 InVal = BinaryOperator::createAnd(InVal, Comp);
2415 ReplaceInstUsesWith(I, // No comparison is needed here, all indexes = 0
2416 ConstantBool::get(Cond == Instruction::SetEQ));
2419 // Only lower this if the setcc is the only user of the GEP or if we expect
2420 // the result to fold to a constant!
2421 if (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) {
2422 // ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0).
2423 Value *Offset = EmitGEPOffset(GEPLHS, I, *this);
2424 return new SetCondInst(Cond, Offset,
2425 Constant::getNullValue(Offset->getType()));
2427 } else if (User *GEPRHS = dyn_castGetElementPtr(RHS)) {
2428 // If the base pointers are different, but the indices are the same, just
2429 // compare the base pointer.
2430 if (PtrBase != GEPRHS->getOperand(0)) {
2431 bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
2432 IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
2433 GEPRHS->getOperand(0)->getType();
2435 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
2436 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
2437 IndicesTheSame = false;
2441 // If all indices are the same, just compare the base pointers.
2443 return new SetCondInst(Cond, GEPLHS->getOperand(0),
2444 GEPRHS->getOperand(0));
2446 // Otherwise, the base pointers are different and the indices are
2447 // different, bail out.
2451 // If one of the GEPs has all zero indices, recurse.
2452 bool AllZeros = true;
2453 for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
2454 if (!isa<Constant>(GEPLHS->getOperand(i)) ||
2455 !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) {
2460 return FoldGEPSetCC(GEPRHS, GEPLHS->getOperand(0),
2461 SetCondInst::getSwappedCondition(Cond), I);
2463 // If the other GEP has all zero indices, recurse.
2465 for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
2466 if (!isa<Constant>(GEPRHS->getOperand(i)) ||
2467 !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) {
2472 return FoldGEPSetCC(GEPLHS, GEPRHS->getOperand(0), Cond, I);
2474 if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
2475 // If the GEPs only differ by one index, compare it.
2476 unsigned NumDifferences = 0; // Keep track of # differences.
2477 unsigned DiffOperand = 0; // The operand that differs.
2478 for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
2479 if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
2480 if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() !=
2481 GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) {
2482 // Irreconcilable differences.
2486 if (NumDifferences++) break;
2491 if (NumDifferences == 0) // SAME GEP?
2492 return ReplaceInstUsesWith(I, // No comparison is needed here.
2493 ConstantBool::get(Cond == Instruction::SetEQ));
2494 else if (NumDifferences == 1) {
2495 Value *LHSV = GEPLHS->getOperand(DiffOperand);
2496 Value *RHSV = GEPRHS->getOperand(DiffOperand);
2498 // Convert the operands to signed values to make sure to perform a
2499 // signed comparison.
2500 const Type *NewTy = LHSV->getType()->getSignedVersion();
2501 if (LHSV->getType() != NewTy)
2502 LHSV = InsertNewInstBefore(new CastInst(LHSV, NewTy,
2503 LHSV->getName()), I);
2504 if (RHSV->getType() != NewTy)
2505 RHSV = InsertNewInstBefore(new CastInst(RHSV, NewTy,
2506 RHSV->getName()), I);
2507 return new SetCondInst(Cond, LHSV, RHSV);
2511 // Only lower this if the setcc is the only user of the GEP or if we expect
2512 // the result to fold to a constant!
2513 if ((isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
2514 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
2515 // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2)
2516 Value *L = EmitGEPOffset(GEPLHS, I, *this);
2517 Value *R = EmitGEPOffset(GEPRHS, I, *this);
2518 return new SetCondInst(Cond, L, R);
2525 Instruction *InstCombiner::visitSetCondInst(SetCondInst &I) {
2526 bool Changed = SimplifyCommutative(I);
2527 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2528 const Type *Ty = Op0->getType();
2532 return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
2534 if (isa<UndefValue>(Op1)) // X setcc undef -> undef
2535 return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy));
2537 // setcc <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
2538 // addresses never equal each other! We already know that Op0 != Op1.
2539 if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
2540 isa<ConstantPointerNull>(Op0)) &&
2541 (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) ||
2542 isa<ConstantPointerNull>(Op1)))
2543 return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
2545 // setcc's with boolean values can always be turned into bitwise operations
2546 if (Ty == Type::BoolTy) {
2547 switch (I.getOpcode()) {
2548 default: assert(0 && "Invalid setcc instruction!");
2549 case Instruction::SetEQ: { // seteq bool %A, %B -> ~(A^B)
2550 Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp");
2551 InsertNewInstBefore(Xor, I);
2552 return BinaryOperator::createNot(Xor);
2554 case Instruction::SetNE:
2555 return BinaryOperator::createXor(Op0, Op1);
2557 case Instruction::SetGT:
2558 std::swap(Op0, Op1); // Change setgt -> setlt
2560 case Instruction::SetLT: { // setlt bool A, B -> ~X & Y
2561 Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2562 InsertNewInstBefore(Not, I);
2563 return BinaryOperator::createAnd(Not, Op1);
2565 case Instruction::SetGE:
2566 std::swap(Op0, Op1); // Change setge -> setle
2568 case Instruction::SetLE: { // setle bool %A, %B -> ~A | B
2569 Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2570 InsertNewInstBefore(Not, I);
2571 return BinaryOperator::createOr(Not, Op1);
2576 // See if we are doing a comparison between a constant and an instruction that
2577 // can be folded into the comparison.
2578 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2579 // Check to see if we are comparing against the minimum or maximum value...
2580 if (CI->isMinValue()) {
2581 if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE
2582 return ReplaceInstUsesWith(I, ConstantBool::False);
2583 if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
2584 return ReplaceInstUsesWith(I, ConstantBool::True);
2585 if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
2586 return BinaryOperator::createSetEQ(Op0, Op1);
2587 if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
2588 return BinaryOperator::createSetNE(Op0, Op1);
2590 } else if (CI->isMaxValue()) {
2591 if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
2592 return ReplaceInstUsesWith(I, ConstantBool::False);
2593 if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE
2594 return ReplaceInstUsesWith(I, ConstantBool::True);
2595 if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX
2596 return BinaryOperator::createSetEQ(Op0, Op1);
2597 if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
2598 return BinaryOperator::createSetNE(Op0, Op1);
2600 // Comparing against a value really close to min or max?
2601 } else if (isMinValuePlusOne(CI)) {
2602 if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN
2603 return BinaryOperator::createSetEQ(Op0, SubOne(CI));
2604 if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
2605 return BinaryOperator::createSetNE(Op0, SubOne(CI));
2607 } else if (isMaxValueMinusOne(CI)) {
2608 if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
2609 return BinaryOperator::createSetEQ(Op0, AddOne(CI));
2610 if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
2611 return BinaryOperator::createSetNE(Op0, AddOne(CI));
2614 // If we still have a setle or setge instruction, turn it into the
2615 // appropriate setlt or setgt instruction. Since the border cases have
2616 // already been handled above, this requires little checking.
2618 if (I.getOpcode() == Instruction::SetLE)
2619 return BinaryOperator::createSetLT(Op0, AddOne(CI));
2620 if (I.getOpcode() == Instruction::SetGE)
2621 return BinaryOperator::createSetGT(Op0, SubOne(CI));
2623 if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
2624 switch (LHSI->getOpcode()) {
2625 case Instruction::And:
2626 if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
2627 LHSI->getOperand(0)->hasOneUse()) {
2628 // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
2629 // could exist), turn it into (X & (C2 << C1)) != (C3 << C1). This
2630 // happens a LOT in code produced by the C front-end, for bitfield
2632 ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0));
2633 ConstantUInt *ShAmt;
2634 ShAmt = Shift ? dyn_cast<ConstantUInt>(Shift->getOperand(1)) : 0;
2635 ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
2636 const Type *Ty = LHSI->getType();
2638 // We can fold this as long as we can't shift unknown bits
2639 // into the mask. This can only happen with signed shift
2640 // rights, as they sign-extend.
2642 bool CanFold = Shift->getOpcode() != Instruction::Shr ||
2643 Shift->getType()->isUnsigned();
2645 // To test for the bad case of the signed shr, see if any
2646 // of the bits shifted in could be tested after the mask.
2647 int ShAmtVal = Ty->getPrimitiveSizeInBits()-ShAmt->getValue();
2648 if (ShAmtVal < 0) ShAmtVal = 0; // Out of range shift.
2650 Constant *OShAmt = ConstantUInt::get(Type::UByteTy, ShAmtVal);
2652 ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), OShAmt);
2653 if (ConstantExpr::getAnd(ShVal, AndCST)->isNullValue())
2659 if (Shift->getOpcode() == Instruction::Shl)
2660 NewCst = ConstantExpr::getUShr(CI, ShAmt);
2662 NewCst = ConstantExpr::getShl(CI, ShAmt);
2664 // Check to see if we are shifting out any of the bits being
2666 if (ConstantExpr::get(Shift->getOpcode(), NewCst, ShAmt) != CI){
2667 // If we shifted bits out, the fold is not going to work out.
2668 // As a special case, check to see if this means that the
2669 // result is always true or false now.
2670 if (I.getOpcode() == Instruction::SetEQ)
2671 return ReplaceInstUsesWith(I, ConstantBool::False);
2672 if (I.getOpcode() == Instruction::SetNE)
2673 return ReplaceInstUsesWith(I, ConstantBool::True);
2675 I.setOperand(1, NewCst);
2676 Constant *NewAndCST;
2677 if (Shift->getOpcode() == Instruction::Shl)
2678 NewAndCST = ConstantExpr::getUShr(AndCST, ShAmt);
2680 NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
2681 LHSI->setOperand(1, NewAndCST);
2682 LHSI->setOperand(0, Shift->getOperand(0));
2683 WorkList.push_back(Shift); // Shift is dead.
2684 AddUsesToWorkList(I);
2692 case Instruction::Shl: // (setcc (shl X, ShAmt), CI)
2693 if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2694 switch (I.getOpcode()) {
2696 case Instruction::SetEQ:
2697 case Instruction::SetNE: {
2698 unsigned TypeBits = CI->getType()->getPrimitiveSizeInBits();
2700 // Check that the shift amount is in range. If not, don't perform
2701 // undefined shifts. When the shift is visited it will be
2703 if (ShAmt->getValue() >= TypeBits)
2706 // If we are comparing against bits always shifted out, the
2707 // comparison cannot succeed.
2709 ConstantExpr::getShl(ConstantExpr::getShr(CI, ShAmt), ShAmt);
2710 if (Comp != CI) {// Comparing against a bit that we know is zero.
2711 bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2712 Constant *Cst = ConstantBool::get(IsSetNE);
2713 return ReplaceInstUsesWith(I, Cst);
2716 if (LHSI->hasOneUse()) {
2717 // Otherwise strength reduce the shift into an and.
2718 unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2719 uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1;
2722 if (CI->getType()->isUnsigned()) {
2723 Mask = ConstantUInt::get(CI->getType(), Val);
2724 } else if (ShAmtVal != 0) {
2725 Mask = ConstantSInt::get(CI->getType(), Val);
2727 Mask = ConstantInt::getAllOnesValue(CI->getType());
2731 BinaryOperator::createAnd(LHSI->getOperand(0),
2732 Mask, LHSI->getName()+".mask");
2733 Value *And = InsertNewInstBefore(AndI, I);
2734 return new SetCondInst(I.getOpcode(), And,
2735 ConstantExpr::getUShr(CI, ShAmt));
2742 case Instruction::Shr: // (setcc (shr X, ShAmt), CI)
2743 if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2744 switch (I.getOpcode()) {
2746 case Instruction::SetEQ:
2747 case Instruction::SetNE: {
2749 // Check that the shift amount is in range. If not, don't perform
2750 // undefined shifts. When the shift is visited it will be
2752 unsigned TypeBits = CI->getType()->getPrimitiveSizeInBits();
2753 if (ShAmt->getValue() >= TypeBits)
2756 // If we are comparing against bits always shifted out, the
2757 // comparison cannot succeed.
2759 ConstantExpr::getShr(ConstantExpr::getShl(CI, ShAmt), ShAmt);
2761 if (Comp != CI) {// Comparing against a bit that we know is zero.
2762 bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2763 Constant *Cst = ConstantBool::get(IsSetNE);
2764 return ReplaceInstUsesWith(I, Cst);
2767 if (LHSI->hasOneUse() || CI->isNullValue()) {
2768 unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2770 // Otherwise strength reduce the shift into an and.
2771 uint64_t Val = ~0ULL; // All ones.
2772 Val <<= ShAmtVal; // Shift over to the right spot.
2775 if (CI->getType()->isUnsigned()) {
2776 Val &= ~0ULL >> (64-TypeBits);
2777 Mask = ConstantUInt::get(CI->getType(), Val);
2779 Mask = ConstantSInt::get(CI->getType(), Val);
2783 BinaryOperator::createAnd(LHSI->getOperand(0),
2784 Mask, LHSI->getName()+".mask");
2785 Value *And = InsertNewInstBefore(AndI, I);
2786 return new SetCondInst(I.getOpcode(), And,
2787 ConstantExpr::getShl(CI, ShAmt));
2795 case Instruction::Div:
2796 // Fold: (div X, C1) op C2 -> range check
2797 if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
2798 // Fold this div into the comparison, producing a range check.
2799 // Determine, based on the divide type, what the range is being
2800 // checked. If there is an overflow on the low or high side, remember
2801 // it, otherwise compute the range [low, hi) bounding the new value.
2802 bool LoOverflow = false, HiOverflow = 0;
2803 ConstantInt *LoBound = 0, *HiBound = 0;
2806 bool ProdOV = MulWithOverflow(Prod, CI, DivRHS);
2808 Instruction::BinaryOps Opcode = I.getOpcode();
2810 if (DivRHS->isNullValue()) { // Don't hack on divide by zeros.
2811 } else if (LHSI->getType()->isUnsigned()) { // udiv
2813 LoOverflow = ProdOV;
2814 HiOverflow = ProdOV || AddWithOverflow(HiBound, LoBound, DivRHS);
2815 } else if (isPositive(DivRHS)) { // Divisor is > 0.
2816 if (CI->isNullValue()) { // (X / pos) op 0
2818 LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
2820 } else if (isPositive(CI)) { // (X / pos) op pos
2822 LoOverflow = ProdOV;
2823 HiOverflow = ProdOV || AddWithOverflow(HiBound, Prod, DivRHS);
2824 } else { // (X / pos) op neg
2825 Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
2826 LoOverflow = AddWithOverflow(LoBound, Prod,
2827 cast<ConstantInt>(DivRHSH));
2829 HiOverflow = ProdOV;
2831 } else { // Divisor is < 0.
2832 if (CI->isNullValue()) { // (X / neg) op 0
2833 LoBound = AddOne(DivRHS);
2834 HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
2835 if (HiBound == DivRHS)
2836 LoBound = 0; // - INTMIN = INTMIN
2837 } else if (isPositive(CI)) { // (X / neg) op pos
2838 HiOverflow = LoOverflow = ProdOV;
2840 LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS));
2841 HiBound = AddOne(Prod);
2842 } else { // (X / neg) op neg
2844 LoOverflow = HiOverflow = ProdOV;
2845 HiBound = cast<ConstantInt>(ConstantExpr::getSub(Prod, DivRHS));
2848 // Dividing by a negate swaps the condition.
2849 Opcode = SetCondInst::getSwappedCondition(Opcode);
2853 Value *X = LHSI->getOperand(0);
2855 default: assert(0 && "Unhandled setcc opcode!");
2856 case Instruction::SetEQ:
2857 if (LoOverflow && HiOverflow)
2858 return ReplaceInstUsesWith(I, ConstantBool::False);
2859 else if (HiOverflow)
2860 return new SetCondInst(Instruction::SetGE, X, LoBound);
2861 else if (LoOverflow)
2862 return new SetCondInst(Instruction::SetLT, X, HiBound);
2864 return InsertRangeTest(X, LoBound, HiBound, true, I);
2865 case Instruction::SetNE:
2866 if (LoOverflow && HiOverflow)
2867 return ReplaceInstUsesWith(I, ConstantBool::True);
2868 else if (HiOverflow)
2869 return new SetCondInst(Instruction::SetLT, X, LoBound);
2870 else if (LoOverflow)
2871 return new SetCondInst(Instruction::SetGE, X, HiBound);
2873 return InsertRangeTest(X, LoBound, HiBound, false, I);
2874 case Instruction::SetLT:
2876 return ReplaceInstUsesWith(I, ConstantBool::False);
2877 return new SetCondInst(Instruction::SetLT, X, LoBound);
2878 case Instruction::SetGT:
2880 return ReplaceInstUsesWith(I, ConstantBool::False);
2881 return new SetCondInst(Instruction::SetGE, X, HiBound);
2888 // Simplify seteq and setne instructions...
2889 if (I.getOpcode() == Instruction::SetEQ ||
2890 I.getOpcode() == Instruction::SetNE) {
2891 bool isSetNE = I.getOpcode() == Instruction::SetNE;
2893 // If the first operand is (and|or|xor) with a constant, and the second
2894 // operand is a constant, simplify a bit.
2895 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
2896 switch (BO->getOpcode()) {
2897 case Instruction::Rem:
2898 // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
2899 if (CI->isNullValue() && isa<ConstantSInt>(BO->getOperand(1)) &&
2901 cast<ConstantSInt>(BO->getOperand(1))->getValue() > 1) {
2902 int64_t V = cast<ConstantSInt>(BO->getOperand(1))->getValue();
2903 if (isPowerOf2_64(V)) {
2904 unsigned L2 = Log2_64(V);
2905 const Type *UTy = BO->getType()->getUnsignedVersion();
2906 Value *NewX = InsertNewInstBefore(new CastInst(BO->getOperand(0),
2908 Constant *RHSCst = ConstantUInt::get(UTy, 1ULL << L2);
2909 Value *NewRem =InsertNewInstBefore(BinaryOperator::createRem(NewX,
2910 RHSCst, BO->getName()), I);
2911 return BinaryOperator::create(I.getOpcode(), NewRem,
2912 Constant::getNullValue(UTy));
2917 case Instruction::Add:
2918 // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
2919 if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2920 if (BO->hasOneUse())
2921 return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2922 ConstantExpr::getSub(CI, BOp1C));
2923 } else if (CI->isNullValue()) {
2924 // Replace ((add A, B) != 0) with (A != -B) if A or B is
2925 // efficiently invertible, or if the add has just this one use.
2926 Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
2928 if (Value *NegVal = dyn_castNegVal(BOp1))
2929 return new SetCondInst(I.getOpcode(), BOp0, NegVal);
2930 else if (Value *NegVal = dyn_castNegVal(BOp0))
2931 return new SetCondInst(I.getOpcode(), NegVal, BOp1);
2932 else if (BO->hasOneUse()) {
2933 Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
2935 InsertNewInstBefore(Neg, I);
2936 return new SetCondInst(I.getOpcode(), BOp0, Neg);
2940 case Instruction::Xor:
2941 // For the xor case, we can xor two constants together, eliminating
2942 // the explicit xor.
2943 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
2944 return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
2945 ConstantExpr::getXor(CI, BOC));
2948 case Instruction::Sub:
2949 // Replace (([sub|xor] A, B) != 0) with (A != B)
2950 if (CI->isNullValue())
2951 return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2955 case Instruction::Or:
2956 // If bits are being or'd in that are not present in the constant we
2957 // are comparing against, then the comparison could never succeed!
2958 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
2959 Constant *NotCI = ConstantExpr::getNot(CI);
2960 if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
2961 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2965 case Instruction::And:
2966 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2967 // If bits are being compared against that are and'd out, then the
2968 // comparison can never succeed!
2969 if (!ConstantExpr::getAnd(CI,
2970 ConstantExpr::getNot(BOC))->isNullValue())
2971 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2973 // If we have ((X & C) == C), turn it into ((X & C) != 0).
2974 if (CI == BOC && isOneBitSet(CI))
2975 return new SetCondInst(isSetNE ? Instruction::SetEQ :
2976 Instruction::SetNE, Op0,
2977 Constant::getNullValue(CI->getType()));
2979 // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
2980 // to be a signed value as appropriate.
2981 if (isSignBit(BOC)) {
2982 Value *X = BO->getOperand(0);
2983 // If 'X' is not signed, insert a cast now...
2984 if (!BOC->getType()->isSigned()) {
2985 const Type *DestTy = BOC->getType()->getSignedVersion();
2986 X = InsertCastBefore(X, DestTy, I);
2988 return new SetCondInst(isSetNE ? Instruction::SetLT :
2989 Instruction::SetGE, X,
2990 Constant::getNullValue(X->getType()));
2993 // ((X & ~7) == 0) --> X < 8
2994 if (CI->isNullValue() && isHighOnes(BOC)) {
2995 Value *X = BO->getOperand(0);
2996 Constant *NegX = ConstantExpr::getNeg(BOC);
2998 // If 'X' is signed, insert a cast now.
2999 if (NegX->getType()->isSigned()) {
3000 const Type *DestTy = NegX->getType()->getUnsignedVersion();
3001 X = InsertCastBefore(X, DestTy, I);
3002 NegX = ConstantExpr::getCast(NegX, DestTy);
3005 return new SetCondInst(isSetNE ? Instruction::SetGE :
3006 Instruction::SetLT, X, NegX);
3013 } else { // Not a SetEQ/SetNE
3014 // If the LHS is a cast from an integral value of the same size,
3015 if (CastInst *Cast = dyn_cast<CastInst>(Op0)) {
3016 Value *CastOp = Cast->getOperand(0);
3017 const Type *SrcTy = CastOp->getType();
3018 unsigned SrcTySize = SrcTy->getPrimitiveSizeInBits();
3019 if (SrcTy != Cast->getType() && SrcTy->isInteger() &&
3020 SrcTySize == Cast->getType()->getPrimitiveSizeInBits()) {
3021 assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) &&
3022 "Source and destination signednesses should differ!");
3023 if (Cast->getType()->isSigned()) {
3024 // If this is a signed comparison, check for comparisons in the
3025 // vicinity of zero.
3026 if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
3028 return BinaryOperator::createSetGT(CastOp,
3029 ConstantUInt::get(SrcTy, (1ULL << (SrcTySize-1))-1));
3030 else if (I.getOpcode() == Instruction::SetGT &&
3031 cast<ConstantSInt>(CI)->getValue() == -1)
3032 // X > -1 => x < 128
3033 return BinaryOperator::createSetLT(CastOp,
3034 ConstantUInt::get(SrcTy, 1ULL << (SrcTySize-1)));
3036 ConstantUInt *CUI = cast<ConstantUInt>(CI);
3037 if (I.getOpcode() == Instruction::SetLT &&
3038 CUI->getValue() == 1ULL << (SrcTySize-1))
3039 // X < 128 => X > -1
3040 return BinaryOperator::createSetGT(CastOp,
3041 ConstantSInt::get(SrcTy, -1));
3042 else if (I.getOpcode() == Instruction::SetGT &&
3043 CUI->getValue() == (1ULL << (SrcTySize-1))-1)
3045 return BinaryOperator::createSetLT(CastOp,
3046 Constant::getNullValue(SrcTy));
3053 // Handle setcc with constant RHS's that can be integer, FP or pointer.
3054 if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
3055 if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
3056 switch (LHSI->getOpcode()) {
3057 case Instruction::GetElementPtr:
3058 if (RHSC->isNullValue()) {
3059 // Transform setcc GEP P, int 0, int 0, int 0, null -> setcc P, null
3060 bool isAllZeros = true;
3061 for (unsigned i = 1, e = LHSI->getNumOperands(); i != e; ++i)
3062 if (!isa<Constant>(LHSI->getOperand(i)) ||
3063 !cast<Constant>(LHSI->getOperand(i))->isNullValue()) {
3068 return new SetCondInst(I.getOpcode(), LHSI->getOperand(0),
3069 Constant::getNullValue(LHSI->getOperand(0)->getType()));
3073 case Instruction::PHI:
3074 if (Instruction *NV = FoldOpIntoPhi(I))
3077 case Instruction::Select:
3078 // If either operand of the select is a constant, we can fold the
3079 // comparison into the select arms, which will cause one to be
3080 // constant folded and the select turned into a bitwise or.
3081 Value *Op1 = 0, *Op2 = 0;
3082 if (LHSI->hasOneUse()) {
3083 if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
3084 // Fold the known value into the constant operand.
3085 Op1 = ConstantExpr::get(I.getOpcode(), C, RHSC);
3086 // Insert a new SetCC of the other select operand.
3087 Op2 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
3088 LHSI->getOperand(2), RHSC,
3090 } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
3091 // Fold the known value into the constant operand.
3092 Op2 = ConstantExpr::get(I.getOpcode(), C, RHSC);
3093 // Insert a new SetCC of the other select operand.
3094 Op1 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
3095 LHSI->getOperand(1), RHSC,
3101 return new SelectInst(LHSI->getOperand(0), Op1, Op2);
3106 // If we can optimize a 'setcc GEP, P' or 'setcc P, GEP', do so now.
3107 if (User *GEP = dyn_castGetElementPtr(Op0))
3108 if (Instruction *NI = FoldGEPSetCC(GEP, Op1, I.getOpcode(), I))
3110 if (User *GEP = dyn_castGetElementPtr(Op1))
3111 if (Instruction *NI = FoldGEPSetCC(GEP, Op0,
3112 SetCondInst::getSwappedCondition(I.getOpcode()), I))
3115 // Test to see if the operands of the setcc are casted versions of other
3116 // values. If the cast can be stripped off both arguments, we do so now.
3117 if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
3118 Value *CastOp0 = CI->getOperand(0);
3119 if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
3120 (isa<Constant>(Op1) || isa<CastInst>(Op1)) &&
3121 (I.getOpcode() == Instruction::SetEQ ||
3122 I.getOpcode() == Instruction::SetNE)) {
3123 // We keep moving the cast from the left operand over to the right
3124 // operand, where it can often be eliminated completely.
3127 // If operand #1 is a cast instruction, see if we can eliminate it as
3129 if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
3130 if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
3132 Op1 = CI2->getOperand(0);
3134 // If Op1 is a constant, we can fold the cast into the constant.
3135 if (Op1->getType() != Op0->getType())
3136 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
3137 Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
3139 // Otherwise, cast the RHS right before the setcc
3140 Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
3141 InsertNewInstBefore(cast<Instruction>(Op1), I);
3143 return BinaryOperator::create(I.getOpcode(), Op0, Op1);
3146 // Handle the special case of: setcc (cast bool to X), <cst>
3147 // This comes up when you have code like
3150 // For generality, we handle any zero-extension of any operand comparison
3151 // with a constant or another cast from the same type.
3152 if (isa<ConstantInt>(Op1) || isa<CastInst>(Op1))
3153 if (Instruction *R = visitSetCondInstWithCastAndCast(I))
3156 return Changed ? &I : 0;
3159 // visitSetCondInstWithCastAndCast - Handle setcond (cast x to y), (cast/cst).
3160 // We only handle extending casts so far.
3162 Instruction *InstCombiner::visitSetCondInstWithCastAndCast(SetCondInst &SCI) {
3163 Value *LHSCIOp = cast<CastInst>(SCI.getOperand(0))->getOperand(0);
3164 const Type *SrcTy = LHSCIOp->getType();
3165 const Type *DestTy = SCI.getOperand(0)->getType();
3168 if (!DestTy->isIntegral() || !SrcTy->isIntegral())
3171 unsigned SrcBits = SrcTy->getPrimitiveSizeInBits();
3172 unsigned DestBits = DestTy->getPrimitiveSizeInBits();
3173 if (SrcBits >= DestBits) return 0; // Only handle extending cast.
3175 // Is this a sign or zero extension?
3176 bool isSignSrc = SrcTy->isSigned();
3177 bool isSignDest = DestTy->isSigned();
3179 if (CastInst *CI = dyn_cast<CastInst>(SCI.getOperand(1))) {
3180 // Not an extension from the same type?
3181 RHSCIOp = CI->getOperand(0);
3182 if (RHSCIOp->getType() != LHSCIOp->getType()) return 0;
3183 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(SCI.getOperand(1))) {
3184 // Compute the constant that would happen if we truncated to SrcTy then
3185 // reextended to DestTy.
3186 Constant *Res = ConstantExpr::getCast(CI, SrcTy);
3188 if (ConstantExpr::getCast(Res, DestTy) == CI) {
3191 // If the value cannot be represented in the shorter type, we cannot emit
3192 // a simple comparison.
3193 if (SCI.getOpcode() == Instruction::SetEQ)
3194 return ReplaceInstUsesWith(SCI, ConstantBool::False);
3195 if (SCI.getOpcode() == Instruction::SetNE)
3196 return ReplaceInstUsesWith(SCI, ConstantBool::True);
3198 // Evaluate the comparison for LT.
3200 if (DestTy->isSigned()) {
3201 // We're performing a signed comparison.
3203 // Signed extend and signed comparison.
3204 if (cast<ConstantSInt>(CI)->getValue() < 0) // X < (small) --> false
3205 Result = ConstantBool::False;
3207 Result = ConstantBool::True; // X < (large) --> true
3209 // Unsigned extend and signed comparison.
3210 if (cast<ConstantSInt>(CI)->getValue() < 0)
3211 Result = ConstantBool::False;
3213 Result = ConstantBool::True;
3216 // We're performing an unsigned comparison.
3218 // Unsigned extend & compare -> always true.
3219 Result = ConstantBool::True;
3221 // We're performing an unsigned comp with a sign extended value.
3222 // This is true if the input is >= 0. [aka >s -1]
3223 Constant *NegOne = ConstantIntegral::getAllOnesValue(SrcTy);
3224 Result = InsertNewInstBefore(BinaryOperator::createSetGT(LHSCIOp,
3225 NegOne, SCI.getName()), SCI);
3229 // Finally, return the value computed.
3230 if (SCI.getOpcode() == Instruction::SetLT) {
3231 return ReplaceInstUsesWith(SCI, Result);
3233 assert(SCI.getOpcode()==Instruction::SetGT &&"SetCC should be folded!");
3234 if (Constant *CI = dyn_cast<Constant>(Result))
3235 return ReplaceInstUsesWith(SCI, ConstantExpr::getNot(CI));
3237 return BinaryOperator::createNot(Result);
3244 // Okay, just insert a compare of the reduced operands now!
3245 return BinaryOperator::create(SCI.getOpcode(), LHSCIOp, RHSCIOp);
3248 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
3249 assert(I.getOperand(1)->getType() == Type::UByteTy);
3250 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3251 bool isLeftShift = I.getOpcode() == Instruction::Shl;
3253 // shl X, 0 == X and shr X, 0 == X
3254 // shl 0, X == 0 and shr 0, X == 0
3255 if (Op1 == Constant::getNullValue(Type::UByteTy) ||
3256 Op0 == Constant::getNullValue(Op0->getType()))
3257 return ReplaceInstUsesWith(I, Op0);
3259 if (isa<UndefValue>(Op0)) { // undef >>s X -> undef
3260 if (!isLeftShift && I.getType()->isSigned())
3261 return ReplaceInstUsesWith(I, Op0);
3262 else // undef << X -> 0 AND undef >>u X -> 0
3263 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
3265 if (isa<UndefValue>(Op1)) {
3266 if (isLeftShift || I.getType()->isUnsigned())// X << undef, X >>u undef -> 0
3267 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
3269 return ReplaceInstUsesWith(I, Op0); // X >>s undef -> X
3272 // shr int -1, X = -1 (for any arithmetic shift rights of ~0)
3274 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
3275 if (CSI->isAllOnesValue())
3276 return ReplaceInstUsesWith(I, CSI);
3278 // Try to fold constant and into select arguments.
3279 if (isa<Constant>(Op0))
3280 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
3281 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
3284 // See if we can turn a signed shr into an unsigned shr.
3285 if (!isLeftShift && I.getType()->isSigned()) {
3286 if (MaskedValueIsZero(Op0, ConstantInt::getMinValue(I.getType()))) {
3287 Value *V = InsertCastBefore(Op0, I.getType()->getUnsignedVersion(), I);
3288 V = InsertNewInstBefore(new ShiftInst(Instruction::Shr, V, Op1,
3290 return new CastInst(V, I.getType());
3294 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
3295 // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
3296 // of a signed value.
3298 unsigned TypeBits = Op0->getType()->getPrimitiveSizeInBits();
3299 if (CUI->getValue() >= TypeBits) {
3300 if (!Op0->getType()->isSigned() || isLeftShift)
3301 return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
3303 I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1));
3308 // ((X*C1) << C2) == (X * (C1 << C2))
3309 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
3310 if (BO->getOpcode() == Instruction::Mul && isLeftShift)
3311 if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
3312 return BinaryOperator::createMul(BO->getOperand(0),
3313 ConstantExpr::getShl(BOOp, CUI));
3315 // Try to fold constant and into select arguments.
3316 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
3317 if (Instruction *R = FoldOpIntoSelect(I, SI, this))
3319 if (isa<PHINode>(Op0))
3320 if (Instruction *NV = FoldOpIntoPhi(I))
3323 if (Op0->hasOneUse()) {
3324 // If this is a SHL of a sign-extending cast, see if we can turn the input
3325 // into a zero extending cast (a simple strength reduction).
3326 if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
3327 const Type *SrcTy = CI->getOperand(0)->getType();
3328 if (isLeftShift && SrcTy->isInteger() && SrcTy->isSigned() &&
3329 SrcTy->getPrimitiveSizeInBits() <
3330 CI->getType()->getPrimitiveSizeInBits()) {
3331 // We can change it to a zero extension if we are shifting out all of
3332 // the sign extended bits. To check this, form a mask of all of the
3333 // sign extend bits, then shift them left and see if we have anything
3335 Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy); // 1111
3336 Mask = ConstantExpr::getZeroExtend(Mask, CI->getType()); // 00001111
3337 Mask = ConstantExpr::getNot(Mask); // 1's in the sign bits: 11110000
3338 if (ConstantExpr::getShl(Mask, CUI)->isNullValue()) {
3339 // If the shift is nuking all of the sign bits, change this to a
3340 // zero extension cast. To do this, cast the cast input to
3341 // unsigned, then to the requested size.
3342 Value *CastOp = CI->getOperand(0);
3344 new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
3345 CI->getName()+".uns");
3346 NC = InsertNewInstBefore(NC, I);
3347 // Finally, insert a replacement for CI.
3348 NC = new CastInst(NC, CI->getType(), CI->getName());
3350 NC = InsertNewInstBefore(NC, I);
3351 WorkList.push_back(CI); // Delete CI later.
3352 I.setOperand(0, NC);
3353 return &I; // The SHL operand was modified.
3358 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
3359 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
3360 switch (Op0BO->getOpcode()) {
3362 case Instruction::Add:
3363 case Instruction::And:
3364 case Instruction::Or:
3365 case Instruction::Xor:
3366 // These operators commute.
3367 // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C)
3368 if (ShiftInst *XS = dyn_cast<ShiftInst>(Op0BO->getOperand(1)))
3369 if (isLeftShift && XS->hasOneUse() && XS->getOperand(1) == CUI &&
3370 XS->getOpcode() == Instruction::Shr) {
3371 Instruction *YS = new ShiftInst(Instruction::Shl,
3372 Op0BO->getOperand(0), CUI,
3374 InsertNewInstBefore(YS, I); // (Y << C)
3375 Instruction *X = BinaryOperator::create(Op0BO->getOpcode(), YS,
3378 InsertNewInstBefore(X, I); // (X + (Y << C))
3379 Constant *C2 = ConstantInt::getAllOnesValue(X->getType());
3380 C2 = ConstantExpr::getShl(C2, CUI);
3381 return BinaryOperator::createAnd(X, C2);
3384 case Instruction::Sub:
3385 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
3386 if (ShiftInst *XS = dyn_cast<ShiftInst>(Op0BO->getOperand(0)))
3387 if (isLeftShift && XS->hasOneUse() && XS->getOperand(1) == CUI &&
3388 XS->getOpcode() == Instruction::Shr) {
3389 Instruction *YS = new ShiftInst(Instruction::Shl,
3390 Op0BO->getOperand(1), CUI,
3392 InsertNewInstBefore(YS, I); // (Y << C)
3393 Instruction *X = BinaryOperator::create(Op0BO->getOpcode(), YS,
3396 InsertNewInstBefore(X, I); // (X + (Y << C))
3397 Constant *C2 = ConstantInt::getAllOnesValue(X->getType());
3398 C2 = ConstantExpr::getShl(C2, CUI);
3399 return BinaryOperator::createAnd(X, C2);
3405 // If the operand is an bitwise operator with a constant RHS, and the
3406 // shift is the only use, we can pull it out of the shift.
3407 if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
3408 bool isValid = true; // Valid only for And, Or, Xor
3409 bool highBitSet = false; // Transform if high bit of constant set?
3411 switch (Op0BO->getOpcode()) {
3412 default: isValid = false; break; // Do not perform transform!
3413 case Instruction::Add:
3414 isValid = isLeftShift;
3416 case Instruction::Or:
3417 case Instruction::Xor:
3420 case Instruction::And:
3425 // If this is a signed shift right, and the high bit is modified
3426 // by the logical operation, do not perform the transformation.
3427 // The highBitSet boolean indicates the value of the high bit of
3428 // the constant which would cause it to be modified for this
3431 if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
3432 uint64_t Val = Op0C->getRawValue();
3433 isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
3437 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI);
3439 Instruction *NewShift =
3440 new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
3443 InsertNewInstBefore(NewShift, I);
3445 return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
3452 // If this is a shift of a shift, see if we can fold the two together...
3453 if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
3454 if (ConstantUInt *ShiftAmt1C =
3455 dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
3456 unsigned ShiftAmt1 = (unsigned)ShiftAmt1C->getValue();
3457 unsigned ShiftAmt2 = (unsigned)CUI->getValue();
3459 // Check for (A << c1) << c2 and (A >> c1) >> c2
3460 if (I.getOpcode() == Op0SI->getOpcode()) {
3461 unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift...
3462 if (Op0->getType()->getPrimitiveSizeInBits() < Amt)
3463 Amt = Op0->getType()->getPrimitiveSizeInBits();
3464 return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
3465 ConstantUInt::get(Type::UByteTy, Amt));
3468 // Check for (A << c1) >> c2 or visaversa. If we are dealing with
3469 // signed types, we can only support the (A >> c1) << c2 configuration,
3470 // because it can not turn an arbitrary bit of A into a sign bit.
3471 if (I.getType()->isUnsigned() || isLeftShift) {
3472 // Calculate bitmask for what gets shifted off the edge...
3473 Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
3475 C = ConstantExpr::getShl(C, ShiftAmt1C);
3477 C = ConstantExpr::getShr(C, ShiftAmt1C);
3480 BinaryOperator::createAnd(Op0SI->getOperand(0), C,
3481 Op0SI->getOperand(0)->getName()+".mask");
3482 InsertNewInstBefore(Mask, I);
3484 // Figure out what flavor of shift we should use...
3485 if (ShiftAmt1 == ShiftAmt2)
3486 return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2
3487 else if (ShiftAmt1 < ShiftAmt2) {
3488 return new ShiftInst(I.getOpcode(), Mask,
3489 ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
3491 return new ShiftInst(Op0SI->getOpcode(), Mask,
3492 ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
3508 /// getCastType - In the future, we will split the cast instruction into these
3509 /// various types. Until then, we have to do the analysis here.
3510 static CastType getCastType(const Type *Src, const Type *Dest) {
3511 assert(Src->isIntegral() && Dest->isIntegral() &&
3512 "Only works on integral types!");
3513 unsigned SrcSize = Src->getPrimitiveSizeInBits();
3514 unsigned DestSize = Dest->getPrimitiveSizeInBits();
3516 if (SrcSize == DestSize) return Noop;
3517 if (SrcSize > DestSize) return Truncate;
3518 if (Src->isSigned()) return Signext;
3523 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
3526 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
3527 const Type *DstTy, TargetData *TD) {
3529 // It is legal to eliminate the instruction if casting A->B->A if the sizes
3530 // are identical and the bits don't get reinterpreted (for example
3531 // int->float->int would not be allowed).
3532 if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
3535 // If we are casting between pointer and integer types, treat pointers as
3536 // integers of the appropriate size for the code below.
3537 if (isa<PointerType>(SrcTy)) SrcTy = TD->getIntPtrType();
3538 if (isa<PointerType>(MidTy)) MidTy = TD->getIntPtrType();
3539 if (isa<PointerType>(DstTy)) DstTy = TD->getIntPtrType();
3541 // Allow free casting and conversion of sizes as long as the sign doesn't
3543 if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
3544 CastType FirstCast = getCastType(SrcTy, MidTy);
3545 CastType SecondCast = getCastType(MidTy, DstTy);
3547 // Capture the effect of these two casts. If the result is a legal cast,
3548 // the CastType is stored here, otherwise a special code is used.
3549 static const unsigned CastResult[] = {
3550 // First cast is noop
3552 // First cast is a truncate
3553 1, 1, 4, 4, // trunc->extend is not safe to eliminate
3554 // First cast is a sign ext
3555 2, 5, 2, 4, // signext->zeroext never ok
3556 // First cast is a zero ext
3560 unsigned Result = CastResult[FirstCast*4+SecondCast];
3562 default: assert(0 && "Illegal table value!");
3567 // FIXME: in the future, when LLVM has explicit sign/zeroextends and
3568 // truncates, we could eliminate more casts.
3569 return (unsigned)getCastType(SrcTy, DstTy) == Result;
3571 return false; // Not possible to eliminate this here.
3573 // Sign or zero extend followed by truncate is always ok if the result
3574 // is a truncate or noop.
3575 CastType ResultCast = getCastType(SrcTy, DstTy);
3576 if (ResultCast == Noop || ResultCast == Truncate)
3578 // Otherwise we are still growing the value, we are only safe if the
3579 // result will match the sign/zeroextendness of the result.
3580 return ResultCast == FirstCast;
3586 static bool ValueRequiresCast(const Value *V, const Type *Ty, TargetData *TD) {
3587 if (V->getType() == Ty || isa<Constant>(V)) return false;
3588 if (const CastInst *CI = dyn_cast<CastInst>(V))
3589 if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty,
3595 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
3596 /// InsertBefore instruction. This is specialized a bit to avoid inserting
3597 /// casts that are known to not do anything...
3599 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
3600 Instruction *InsertBefore) {
3601 if (V->getType() == DestTy) return V;
3602 if (Constant *C = dyn_cast<Constant>(V))
3603 return ConstantExpr::getCast(C, DestTy);
3605 CastInst *CI = new CastInst(V, DestTy, V->getName());
3606 InsertNewInstBefore(CI, *InsertBefore);
3610 // CastInst simplification
3612 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
3613 Value *Src = CI.getOperand(0);
3615 // If the user is casting a value to the same type, eliminate this cast
3617 if (CI.getType() == Src->getType())
3618 return ReplaceInstUsesWith(CI, Src);
3620 if (isa<UndefValue>(Src)) // cast undef -> undef
3621 return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType()));
3623 // If casting the result of another cast instruction, try to eliminate this
3626 if (CastInst *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast
3627 Value *A = CSrc->getOperand(0);
3628 if (isEliminableCastOfCast(A->getType(), CSrc->getType(),
3629 CI.getType(), TD)) {
3630 // This instruction now refers directly to the cast's src operand. This
3631 // has a good chance of making CSrc dead.
3632 CI.setOperand(0, CSrc->getOperand(0));
3636 // If this is an A->B->A cast, and we are dealing with integral types, try
3637 // to convert this into a logical 'and' instruction.
3639 if (A->getType()->isInteger() &&
3640 CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
3641 CSrc->getType()->isUnsigned() && // B->A cast must zero extend
3642 CSrc->getType()->getPrimitiveSizeInBits() <
3643 CI.getType()->getPrimitiveSizeInBits()&&
3644 A->getType()->getPrimitiveSizeInBits() ==
3645 CI.getType()->getPrimitiveSizeInBits()) {
3646 assert(CSrc->getType() != Type::ULongTy &&
3647 "Cannot have type bigger than ulong!");
3648 uint64_t AndValue = ~0ULL>>(64-CSrc->getType()->getPrimitiveSizeInBits());
3649 Constant *AndOp = ConstantUInt::get(A->getType()->getUnsignedVersion(),
3651 AndOp = ConstantExpr::getCast(AndOp, A->getType());
3652 Instruction *And = BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
3653 if (And->getType() != CI.getType()) {
3654 And->setName(CSrc->getName()+".mask");
3655 InsertNewInstBefore(And, CI);
3656 And = new CastInst(And, CI.getType());
3662 // If this is a cast to bool, turn it into the appropriate setne instruction.
3663 if (CI.getType() == Type::BoolTy)
3664 return BinaryOperator::createSetNE(CI.getOperand(0),
3665 Constant::getNullValue(CI.getOperand(0)->getType()));
3667 // If casting the result of a getelementptr instruction with no offset, turn
3668 // this into a cast of the original pointer!
3670 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
3671 bool AllZeroOperands = true;
3672 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
3673 if (!isa<Constant>(GEP->getOperand(i)) ||
3674 !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
3675 AllZeroOperands = false;
3678 if (AllZeroOperands) {
3679 CI.setOperand(0, GEP->getOperand(0));
3684 // If we are casting a malloc or alloca to a pointer to a type of the same
3685 // size, rewrite the allocation instruction to allocate the "right" type.
3687 if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
3688 if (AI->hasOneUse() && !AI->isArrayAllocation())
3689 if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
3690 // Get the type really allocated and the type casted to...
3691 const Type *AllocElTy = AI->getAllocatedType();
3692 const Type *CastElTy = PTy->getElementType();
3693 if (AllocElTy->isSized() && CastElTy->isSized()) {
3694 uint64_t AllocElTySize = TD->getTypeSize(AllocElTy);
3695 uint64_t CastElTySize = TD->getTypeSize(CastElTy);
3697 // If the allocation is for an even multiple of the cast type size
3698 if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
3699 Value *Amt = ConstantUInt::get(Type::UIntTy,
3700 AllocElTySize/CastElTySize);
3701 std::string Name = AI->getName(); AI->setName("");
3702 AllocationInst *New;
3703 if (isa<MallocInst>(AI))
3704 New = new MallocInst(CastElTy, Amt, Name);
3706 New = new AllocaInst(CastElTy, Amt, Name);
3707 InsertNewInstBefore(New, *AI);
3708 return ReplaceInstUsesWith(CI, New);
3713 if (SelectInst *SI = dyn_cast<SelectInst>(Src))
3714 if (Instruction *NV = FoldOpIntoSelect(CI, SI, this))
3716 if (isa<PHINode>(Src))
3717 if (Instruction *NV = FoldOpIntoPhi(CI))
3720 // If the source value is an instruction with only this use, we can attempt to
3721 // propagate the cast into the instruction. Also, only handle integral types
3723 if (Instruction *SrcI = dyn_cast<Instruction>(Src))
3724 if (SrcI->hasOneUse() && Src->getType()->isIntegral() &&
3725 CI.getType()->isInteger()) { // Don't mess with casts to bool here
3726 const Type *DestTy = CI.getType();
3727 unsigned SrcBitSize = Src->getType()->getPrimitiveSizeInBits();
3728 unsigned DestBitSize = DestTy->getPrimitiveSizeInBits();
3730 Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
3731 Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
3733 switch (SrcI->getOpcode()) {
3734 case Instruction::Add:
3735 case Instruction::Mul:
3736 case Instruction::And:
3737 case Instruction::Or:
3738 case Instruction::Xor:
3739 // If we are discarding information, or just changing the sign, rewrite.
3740 if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
3741 // Don't insert two casts if they cannot be eliminated. We allow two
3742 // casts to be inserted if the sizes are the same. This could only be
3743 // converting signedness, which is a noop.
3744 if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy,TD) ||
3745 !ValueRequiresCast(Op0, DestTy, TD)) {
3746 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3747 Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
3748 return BinaryOperator::create(cast<BinaryOperator>(SrcI)
3749 ->getOpcode(), Op0c, Op1c);
3753 // cast (xor bool X, true) to int --> xor (cast bool X to int), 1
3754 if (SrcBitSize == 1 && SrcI->getOpcode() == Instruction::Xor &&
3755 Op1 == ConstantBool::True &&
3756 (!Op0->hasOneUse() || !isa<SetCondInst>(Op0))) {
3757 Value *New = InsertOperandCastBefore(Op0, DestTy, &CI);
3758 return BinaryOperator::createXor(New,
3759 ConstantInt::get(CI.getType(), 1));
3762 case Instruction::Shl:
3763 // Allow changing the sign of the source operand. Do not allow changing
3764 // the size of the shift, UNLESS the shift amount is a constant. We
3765 // mush not change variable sized shifts to a smaller size, because it
3766 // is undefined to shift more bits out than exist in the value.
3767 if (DestBitSize == SrcBitSize ||
3768 (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
3769 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3770 return new ShiftInst(Instruction::Shl, Op0c, Op1);
3773 case Instruction::Shr:
3774 // If this is a signed shr, and if all bits shifted in are about to be
3775 // truncated off, turn it into an unsigned shr to allow greater
3777 if (DestBitSize < SrcBitSize && Src->getType()->isSigned() &&
3778 isa<ConstantInt>(Op1)) {
3779 unsigned ShiftAmt = cast<ConstantUInt>(Op1)->getValue();
3780 if (SrcBitSize > ShiftAmt && SrcBitSize-ShiftAmt >= DestBitSize) {
3781 // Convert to unsigned.
3782 Value *N1 = InsertOperandCastBefore(Op0,
3783 Op0->getType()->getUnsignedVersion(), &CI);
3784 // Insert the new shift, which is now unsigned.
3785 N1 = InsertNewInstBefore(new ShiftInst(Instruction::Shr, N1,
3786 Op1, Src->getName()), CI);
3787 return new CastInst(N1, CI.getType());
3792 case Instruction::SetNE:
3793 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
3794 if (Op1C->getRawValue() == 0) {
3795 // If the input only has the low bit set, simplify directly.
3797 ConstantExpr::getNot(ConstantInt::get(Op0->getType(), 1));
3798 // cast (X != 0) to int --> X if X&~1 == 0
3799 if (MaskedValueIsZero(Op0, cast<ConstantIntegral>(Not1))) {
3800 if (CI.getType() == Op0->getType())
3801 return ReplaceInstUsesWith(CI, Op0);
3803 return new CastInst(Op0, CI.getType());
3806 // If the input is an and with a single bit, shift then simplify.
3807 ConstantInt *AndRHS;
3808 if (match(Op0, m_And(m_Value(), m_ConstantInt(AndRHS))))
3809 if (AndRHS->getRawValue() &&
3810 (AndRHS->getRawValue() & (AndRHS->getRawValue()-1)) == 0) {
3811 unsigned ShiftAmt = Log2_64(AndRHS->getRawValue());
3812 // Perform an unsigned shr by shiftamt. Convert input to
3813 // unsigned if it is signed.
3815 if (In->getType()->isSigned())
3816 In = InsertNewInstBefore(new CastInst(In,
3817 In->getType()->getUnsignedVersion(), In->getName()),CI);
3818 // Insert the shift to put the result in the low bit.
3819 In = InsertNewInstBefore(new ShiftInst(Instruction::Shr, In,
3820 ConstantInt::get(Type::UByteTy, ShiftAmt),
3821 In->getName()+".lobit"), CI);
3822 if (CI.getType() == In->getType())
3823 return ReplaceInstUsesWith(CI, In);
3825 return new CastInst(In, CI.getType());
3830 case Instruction::SetEQ:
3831 // We if we are just checking for a seteq of a single bit and casting it
3832 // to an integer. If so, shift the bit to the appropriate place then
3833 // cast to integer to avoid the comparison.
3834 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
3835 // Is Op1C a power of two or zero?
3836 if ((Op1C->getRawValue() & Op1C->getRawValue()-1) == 0) {
3837 // cast (X == 1) to int -> X iff X has only the low bit set.
3838 if (Op1C->getRawValue() == 1) {
3840 ConstantExpr::getNot(ConstantInt::get(Op0->getType(), 1));
3841 if (MaskedValueIsZero(Op0, cast<ConstantIntegral>(Not1))) {
3842 if (CI.getType() == Op0->getType())
3843 return ReplaceInstUsesWith(CI, Op0);
3845 return new CastInst(Op0, CI.getType());
3856 /// GetSelectFoldableOperands - We want to turn code that looks like this:
3858 /// %D = select %cond, %C, %A
3860 /// %C = select %cond, %B, 0
3863 /// Assuming that the specified instruction is an operand to the select, return
3864 /// a bitmask indicating which operands of this instruction are foldable if they
3865 /// equal the other incoming value of the select.
3867 static unsigned GetSelectFoldableOperands(Instruction *I) {
3868 switch (I->getOpcode()) {
3869 case Instruction::Add:
3870 case Instruction::Mul:
3871 case Instruction::And:
3872 case Instruction::Or:
3873 case Instruction::Xor:
3874 return 3; // Can fold through either operand.
3875 case Instruction::Sub: // Can only fold on the amount subtracted.
3876 case Instruction::Shl: // Can only fold on the shift amount.
3877 case Instruction::Shr:
3880 return 0; // Cannot fold
3884 /// GetSelectFoldableConstant - For the same transformation as the previous
3885 /// function, return the identity constant that goes into the select.
3886 static Constant *GetSelectFoldableConstant(Instruction *I) {
3887 switch (I->getOpcode()) {
3888 default: assert(0 && "This cannot happen!"); abort();
3889 case Instruction::Add:
3890 case Instruction::Sub:
3891 case Instruction::Or:
3892 case Instruction::Xor:
3893 return Constant::getNullValue(I->getType());
3894 case Instruction::Shl:
3895 case Instruction::Shr:
3896 return Constant::getNullValue(Type::UByteTy);
3897 case Instruction::And:
3898 return ConstantInt::getAllOnesValue(I->getType());
3899 case Instruction::Mul:
3900 return ConstantInt::get(I->getType(), 1);
3904 /// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI
3905 /// have the same opcode and only one use each. Try to simplify this.
3906 Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI,
3908 if (TI->getNumOperands() == 1) {
3909 // If this is a non-volatile load or a cast from the same type,
3911 if (TI->getOpcode() == Instruction::Cast) {
3912 if (TI->getOperand(0)->getType() != FI->getOperand(0)->getType())
3915 return 0; // unknown unary op.
3918 // Fold this by inserting a select from the input values.
3919 SelectInst *NewSI = new SelectInst(SI.getCondition(), TI->getOperand(0),
3920 FI->getOperand(0), SI.getName()+".v");
3921 InsertNewInstBefore(NewSI, SI);
3922 return new CastInst(NewSI, TI->getType());
3925 // Only handle binary operators here.
3926 if (!isa<ShiftInst>(TI) && !isa<BinaryOperator>(TI))
3929 // Figure out if the operations have any operands in common.
3930 Value *MatchOp, *OtherOpT, *OtherOpF;
3932 if (TI->getOperand(0) == FI->getOperand(0)) {
3933 MatchOp = TI->getOperand(0);
3934 OtherOpT = TI->getOperand(1);
3935 OtherOpF = FI->getOperand(1);
3936 MatchIsOpZero = true;
3937 } else if (TI->getOperand(1) == FI->getOperand(1)) {
3938 MatchOp = TI->getOperand(1);
3939 OtherOpT = TI->getOperand(0);
3940 OtherOpF = FI->getOperand(0);
3941 MatchIsOpZero = false;
3942 } else if (!TI->isCommutative()) {
3944 } else if (TI->getOperand(0) == FI->getOperand(1)) {
3945 MatchOp = TI->getOperand(0);
3946 OtherOpT = TI->getOperand(1);
3947 OtherOpF = FI->getOperand(0);
3948 MatchIsOpZero = true;
3949 } else if (TI->getOperand(1) == FI->getOperand(0)) {
3950 MatchOp = TI->getOperand(1);
3951 OtherOpT = TI->getOperand(0);
3952 OtherOpF = FI->getOperand(1);
3953 MatchIsOpZero = true;
3958 // If we reach here, they do have operations in common.
3959 SelectInst *NewSI = new SelectInst(SI.getCondition(), OtherOpT,
3960 OtherOpF, SI.getName()+".v");
3961 InsertNewInstBefore(NewSI, SI);
3963 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI)) {
3965 return BinaryOperator::create(BO->getOpcode(), MatchOp, NewSI);
3967 return BinaryOperator::create(BO->getOpcode(), NewSI, MatchOp);
3970 return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), MatchOp, NewSI);
3972 return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), NewSI, MatchOp);
3976 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
3977 Value *CondVal = SI.getCondition();
3978 Value *TrueVal = SI.getTrueValue();
3979 Value *FalseVal = SI.getFalseValue();
3981 // select true, X, Y -> X
3982 // select false, X, Y -> Y
3983 if (ConstantBool *C = dyn_cast<ConstantBool>(CondVal))
3984 if (C == ConstantBool::True)
3985 return ReplaceInstUsesWith(SI, TrueVal);
3987 assert(C == ConstantBool::False);
3988 return ReplaceInstUsesWith(SI, FalseVal);
3991 // select C, X, X -> X
3992 if (TrueVal == FalseVal)
3993 return ReplaceInstUsesWith(SI, TrueVal);
3995 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
3996 return ReplaceInstUsesWith(SI, FalseVal);
3997 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
3998 return ReplaceInstUsesWith(SI, TrueVal);
3999 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
4000 if (isa<Constant>(TrueVal))
4001 return ReplaceInstUsesWith(SI, TrueVal);
4003 return ReplaceInstUsesWith(SI, FalseVal);
4006 if (SI.getType() == Type::BoolTy)
4007 if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
4008 if (C == ConstantBool::True) {
4009 // Change: A = select B, true, C --> A = or B, C
4010 return BinaryOperator::createOr(CondVal, FalseVal);
4012 // Change: A = select B, false, C --> A = and !B, C
4014 InsertNewInstBefore(BinaryOperator::createNot(CondVal,
4015 "not."+CondVal->getName()), SI);
4016 return BinaryOperator::createAnd(NotCond, FalseVal);
4018 } else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) {
4019 if (C == ConstantBool::False) {
4020 // Change: A = select B, C, false --> A = and B, C
4021 return BinaryOperator::createAnd(CondVal, TrueVal);
4023 // Change: A = select B, C, true --> A = or !B, C
4025 InsertNewInstBefore(BinaryOperator::createNot(CondVal,
4026 "not."+CondVal->getName()), SI);
4027 return BinaryOperator::createOr(NotCond, TrueVal);
4031 // Selecting between two integer constants?
4032 if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal))
4033 if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) {
4034 // select C, 1, 0 -> cast C to int
4035 if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) {
4036 return new CastInst(CondVal, SI.getType());
4037 } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) {
4038 // select C, 0, 1 -> cast !C to int
4040 InsertNewInstBefore(BinaryOperator::createNot(CondVal,
4041 "not."+CondVal->getName()), SI);
4042 return new CastInst(NotCond, SI.getType());
4045 // If one of the constants is zero (we know they can't both be) and we
4046 // have a setcc instruction with zero, and we have an 'and' with the
4047 // non-constant value, eliminate this whole mess. This corresponds to
4048 // cases like this: ((X & 27) ? 27 : 0)
4049 if (TrueValC->isNullValue() || FalseValC->isNullValue())
4050 if (Instruction *IC = dyn_cast<Instruction>(SI.getCondition()))
4051 if ((IC->getOpcode() == Instruction::SetEQ ||
4052 IC->getOpcode() == Instruction::SetNE) &&
4053 isa<ConstantInt>(IC->getOperand(1)) &&
4054 cast<Constant>(IC->getOperand(1))->isNullValue())
4055 if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0)))
4056 if (ICA->getOpcode() == Instruction::And &&
4057 isa<ConstantInt>(ICA->getOperand(1)) &&
4058 (ICA->getOperand(1) == TrueValC ||
4059 ICA->getOperand(1) == FalseValC) &&
4060 isOneBitSet(cast<ConstantInt>(ICA->getOperand(1)))) {
4061 // Okay, now we know that everything is set up, we just don't
4062 // know whether we have a setne or seteq and whether the true or
4063 // false val is the zero.
4064 bool ShouldNotVal = !TrueValC->isNullValue();
4065 ShouldNotVal ^= IC->getOpcode() == Instruction::SetNE;
4068 V = InsertNewInstBefore(BinaryOperator::create(
4069 Instruction::Xor, V, ICA->getOperand(1)), SI);
4070 return ReplaceInstUsesWith(SI, V);
4074 // See if we are selecting two values based on a comparison of the two values.
4075 if (SetCondInst *SCI = dyn_cast<SetCondInst>(CondVal)) {
4076 if (SCI->getOperand(0) == TrueVal && SCI->getOperand(1) == FalseVal) {
4077 // Transform (X == Y) ? X : Y -> Y
4078 if (SCI->getOpcode() == Instruction::SetEQ)
4079 return ReplaceInstUsesWith(SI, FalseVal);
4080 // Transform (X != Y) ? X : Y -> X
4081 if (SCI->getOpcode() == Instruction::SetNE)
4082 return ReplaceInstUsesWith(SI, TrueVal);
4083 // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
4085 } else if (SCI->getOperand(0) == FalseVal && SCI->getOperand(1) == TrueVal){
4086 // Transform (X == Y) ? Y : X -> X
4087 if (SCI->getOpcode() == Instruction::SetEQ)
4088 return ReplaceInstUsesWith(SI, FalseVal);
4089 // Transform (X != Y) ? Y : X -> Y
4090 if (SCI->getOpcode() == Instruction::SetNE)
4091 return ReplaceInstUsesWith(SI, TrueVal);
4092 // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
4096 if (Instruction *TI = dyn_cast<Instruction>(TrueVal))
4097 if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
4098 if (TI->hasOneUse() && FI->hasOneUse()) {
4099 bool isInverse = false;
4100 Instruction *AddOp = 0, *SubOp = 0;
4102 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
4103 if (TI->getOpcode() == FI->getOpcode())
4104 if (Instruction *IV = FoldSelectOpOp(SI, TI, FI))
4107 // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))). This is
4108 // even legal for FP.
4109 if (TI->getOpcode() == Instruction::Sub &&
4110 FI->getOpcode() == Instruction::Add) {
4111 AddOp = FI; SubOp = TI;
4112 } else if (FI->getOpcode() == Instruction::Sub &&
4113 TI->getOpcode() == Instruction::Add) {
4114 AddOp = TI; SubOp = FI;
4118 Value *OtherAddOp = 0;
4119 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
4120 OtherAddOp = AddOp->getOperand(1);
4121 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
4122 OtherAddOp = AddOp->getOperand(0);
4126 // So at this point we know we have:
4127 // select C, (add X, Y), (sub X, ?)
4128 // We can do the transform profitably if either 'Y' = '?' or '?' is
4130 if (SubOp->getOperand(1) == AddOp ||
4131 isa<Constant>(SubOp->getOperand(1))) {
4133 if (Constant *C = dyn_cast<Constant>(SubOp->getOperand(1))) {
4134 NegVal = ConstantExpr::getNeg(C);
4136 NegVal = InsertNewInstBefore(
4137 BinaryOperator::createNeg(SubOp->getOperand(1)), SI);
4140 Value *NewTrueOp = OtherAddOp;
4141 Value *NewFalseOp = NegVal;
4143 std::swap(NewTrueOp, NewFalseOp);
4144 Instruction *NewSel =
4145 new SelectInst(CondVal, NewTrueOp,NewFalseOp,SI.getName()+".p");
4147 NewSel = InsertNewInstBefore(NewSel, SI);
4148 return BinaryOperator::createAdd(SubOp->getOperand(0), NewSel);
4154 // See if we can fold the select into one of our operands.
4155 if (SI.getType()->isInteger()) {
4156 // See the comment above GetSelectFoldableOperands for a description of the
4157 // transformation we are doing here.
4158 if (Instruction *TVI = dyn_cast<Instruction>(TrueVal))
4159 if (TVI->hasOneUse() && TVI->getNumOperands() == 2 &&
4160 !isa<Constant>(FalseVal))
4161 if (unsigned SFO = GetSelectFoldableOperands(TVI)) {
4162 unsigned OpToFold = 0;
4163 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
4165 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
4170 Constant *C = GetSelectFoldableConstant(TVI);
4171 std::string Name = TVI->getName(); TVI->setName("");
4172 Instruction *NewSel =
4173 new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C,
4175 InsertNewInstBefore(NewSel, SI);
4176 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
4177 return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel);
4178 else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI))
4179 return new ShiftInst(SI->getOpcode(), FalseVal, NewSel);
4181 assert(0 && "Unknown instruction!!");
4186 if (Instruction *FVI = dyn_cast<Instruction>(FalseVal))
4187 if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
4188 !isa<Constant>(TrueVal))
4189 if (unsigned SFO = GetSelectFoldableOperands(FVI)) {
4190 unsigned OpToFold = 0;
4191 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
4193 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
4198 Constant *C = GetSelectFoldableConstant(FVI);
4199 std::string Name = FVI->getName(); FVI->setName("");
4200 Instruction *NewSel =
4201 new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold),
4203 InsertNewInstBefore(NewSel, SI);
4204 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
4205 return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel);
4206 else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI))
4207 return new ShiftInst(SI->getOpcode(), TrueVal, NewSel);
4209 assert(0 && "Unknown instruction!!");
4215 if (BinaryOperator::isNot(CondVal)) {
4216 SI.setOperand(0, BinaryOperator::getNotArgument(CondVal));
4217 SI.setOperand(1, FalseVal);
4218 SI.setOperand(2, TrueVal);
4226 // CallInst simplification
4228 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
4229 // Intrinsics cannot occur in an invoke, so handle them here instead of in
4231 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&CI)) {
4232 bool Changed = false;
4234 // memmove/cpy/set of zero bytes is a noop.
4235 if (Constant *NumBytes = dyn_cast<Constant>(MI->getLength())) {
4236 if (NumBytes->isNullValue()) return EraseInstFromFunction(CI);
4238 // FIXME: Increase alignment here.
4240 if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes))
4241 if (CI->getRawValue() == 1) {
4242 // Replace the instruction with just byte operations. We would
4243 // transform other cases to loads/stores, but we don't know if
4244 // alignment is sufficient.
4248 // If we have a memmove and the source operation is a constant global,
4249 // then the source and dest pointers can't alias, so we can change this
4250 // into a call to memcpy.
4251 if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI))
4252 if (GlobalVariable *GVSrc = dyn_cast<GlobalVariable>(MMI->getSource()))
4253 if (GVSrc->isConstant()) {
4254 Module *M = CI.getParent()->getParent()->getParent();
4255 Function *MemCpy = M->getOrInsertFunction("llvm.memcpy",
4256 CI.getCalledFunction()->getFunctionType());
4257 CI.setOperand(0, MemCpy);
4261 if (Changed) return &CI;
4262 } else if (DbgStopPointInst *SPI = dyn_cast<DbgStopPointInst>(&CI)) {
4263 // If this stoppoint is at the same source location as the previous
4264 // stoppoint in the chain, it is not needed.
4265 if (DbgStopPointInst *PrevSPI =
4266 dyn_cast<DbgStopPointInst>(SPI->getChain()))
4267 if (SPI->getLineNo() == PrevSPI->getLineNo() &&
4268 SPI->getColNo() == PrevSPI->getColNo()) {
4269 SPI->replaceAllUsesWith(PrevSPI);
4270 return EraseInstFromFunction(CI);
4274 return visitCallSite(&CI);
4277 // InvokeInst simplification
4279 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
4280 return visitCallSite(&II);
4283 // visitCallSite - Improvements for call and invoke instructions.
4285 Instruction *InstCombiner::visitCallSite(CallSite CS) {
4286 bool Changed = false;
4288 // If the callee is a constexpr cast of a function, attempt to move the cast
4289 // to the arguments of the call/invoke.
4290 if (transformConstExprCastCall(CS)) return 0;
4292 Value *Callee = CS.getCalledValue();
4294 if (Function *CalleeF = dyn_cast<Function>(Callee))
4295 if (CalleeF->getCallingConv() != CS.getCallingConv()) {
4296 Instruction *OldCall = CS.getInstruction();
4297 // If the call and callee calling conventions don't match, this call must
4298 // be unreachable, as the call is undefined.
4299 new StoreInst(ConstantBool::True,
4300 UndefValue::get(PointerType::get(Type::BoolTy)), OldCall);
4301 if (!OldCall->use_empty())
4302 OldCall->replaceAllUsesWith(UndefValue::get(OldCall->getType()));
4303 if (isa<CallInst>(OldCall)) // Not worth removing an invoke here.
4304 return EraseInstFromFunction(*OldCall);
4308 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
4309 // This instruction is not reachable, just remove it. We insert a store to
4310 // undef so that we know that this code is not reachable, despite the fact
4311 // that we can't modify the CFG here.
4312 new StoreInst(ConstantBool::True,
4313 UndefValue::get(PointerType::get(Type::BoolTy)),
4314 CS.getInstruction());
4316 if (!CS.getInstruction()->use_empty())
4317 CS.getInstruction()->
4318 replaceAllUsesWith(UndefValue::get(CS.getInstruction()->getType()));
4320 if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
4321 // Don't break the CFG, insert a dummy cond branch.
4322 new BranchInst(II->getNormalDest(), II->getUnwindDest(),
4323 ConstantBool::True, II);
4325 return EraseInstFromFunction(*CS.getInstruction());
4328 const PointerType *PTy = cast<PointerType>(Callee->getType());
4329 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
4330 if (FTy->isVarArg()) {
4331 // See if we can optimize any arguments passed through the varargs area of
4333 for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(),
4334 E = CS.arg_end(); I != E; ++I)
4335 if (CastInst *CI = dyn_cast<CastInst>(*I)) {
4336 // If this cast does not effect the value passed through the varargs
4337 // area, we can eliminate the use of the cast.
4338 Value *Op = CI->getOperand(0);
4339 if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) {
4346 return Changed ? CS.getInstruction() : 0;
4349 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
4350 // attempt to move the cast to the arguments of the call/invoke.
4352 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
4353 if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
4354 ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
4355 if (CE->getOpcode() != Instruction::Cast || !isa<Function>(CE->getOperand(0)))
4357 Function *Callee = cast<Function>(CE->getOperand(0));
4358 Instruction *Caller = CS.getInstruction();
4360 // Okay, this is a cast from a function to a different type. Unless doing so
4361 // would cause a type conversion of one of our arguments, change this call to
4362 // be a direct call with arguments casted to the appropriate types.
4364 const FunctionType *FT = Callee->getFunctionType();
4365 const Type *OldRetTy = Caller->getType();
4367 // Check to see if we are changing the return type...
4368 if (OldRetTy != FT->getReturnType()) {
4369 if (Callee->isExternal() &&
4370 !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) &&
4371 !Caller->use_empty())
4372 return false; // Cannot transform this return value...
4374 // If the callsite is an invoke instruction, and the return value is used by
4375 // a PHI node in a successor, we cannot change the return type of the call
4376 // because there is no place to put the cast instruction (without breaking
4377 // the critical edge). Bail out in this case.
4378 if (!Caller->use_empty())
4379 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller))
4380 for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
4382 if (PHINode *PN = dyn_cast<PHINode>(*UI))
4383 if (PN->getParent() == II->getNormalDest() ||
4384 PN->getParent() == II->getUnwindDest())
4388 unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
4389 unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
4391 CallSite::arg_iterator AI = CS.arg_begin();
4392 for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
4393 const Type *ParamTy = FT->getParamType(i);
4394 bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
4395 if (Callee->isExternal() && !isConvertible) return false;
4398 if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
4399 Callee->isExternal())
4400 return false; // Do not delete arguments unless we have a function body...
4402 // Okay, we decided that this is a safe thing to do: go ahead and start
4403 // inserting cast instructions as necessary...
4404 std::vector<Value*> Args;
4405 Args.reserve(NumActualArgs);
4407 AI = CS.arg_begin();
4408 for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
4409 const Type *ParamTy = FT->getParamType(i);
4410 if ((*AI)->getType() == ParamTy) {
4411 Args.push_back(*AI);
4413 Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"),
4418 // If the function takes more arguments than the call was taking, add them
4420 for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
4421 Args.push_back(Constant::getNullValue(FT->getParamType(i)));
4423 // If we are removing arguments to the function, emit an obnoxious warning...
4424 if (FT->getNumParams() < NumActualArgs)
4425 if (!FT->isVarArg()) {
4426 std::cerr << "WARNING: While resolving call to function '"
4427 << Callee->getName() << "' arguments were dropped!\n";
4429 // Add all of the arguments in their promoted form to the arg list...
4430 for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
4431 const Type *PTy = getPromotedType((*AI)->getType());
4432 if (PTy != (*AI)->getType()) {
4433 // Must promote to pass through va_arg area!
4434 Instruction *Cast = new CastInst(*AI, PTy, "tmp");
4435 InsertNewInstBefore(Cast, *Caller);
4436 Args.push_back(Cast);
4438 Args.push_back(*AI);
4443 if (FT->getReturnType() == Type::VoidTy)
4444 Caller->setName(""); // Void type should not have a name...
4447 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
4448 NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
4449 Args, Caller->getName(), Caller);
4450 cast<InvokeInst>(II)->setCallingConv(II->getCallingConv());
4452 NC = new CallInst(Callee, Args, Caller->getName(), Caller);
4453 if (cast<CallInst>(Caller)->isTailCall())
4454 cast<CallInst>(NC)->setTailCall();
4455 cast<CallInst>(NC)->setCallingConv(cast<CallInst>(Caller)->getCallingConv());
4458 // Insert a cast of the return type as necessary...
4460 if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
4461 if (NV->getType() != Type::VoidTy) {
4462 NV = NC = new CastInst(NC, Caller->getType(), "tmp");
4464 // If this is an invoke instruction, we should insert it after the first
4465 // non-phi, instruction in the normal successor block.
4466 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
4467 BasicBlock::iterator I = II->getNormalDest()->begin();
4468 while (isa<PHINode>(I)) ++I;
4469 InsertNewInstBefore(NC, *I);
4471 // Otherwise, it's a call, just insert cast right after the call instr
4472 InsertNewInstBefore(NC, *Caller);
4474 AddUsersToWorkList(*Caller);
4476 NV = UndefValue::get(Caller->getType());
4480 if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
4481 Caller->replaceAllUsesWith(NV);
4482 Caller->getParent()->getInstList().erase(Caller);
4483 removeFromWorkList(Caller);
4488 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
4489 // operator and they all are only used by the PHI, PHI together their
4490 // inputs, and do the operation once, to the result of the PHI.
4491 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
4492 Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
4494 // Scan the instruction, looking for input operations that can be folded away.
4495 // If all input operands to the phi are the same instruction (e.g. a cast from
4496 // the same type or "+42") we can pull the operation through the PHI, reducing
4497 // code size and simplifying code.
4498 Constant *ConstantOp = 0;
4499 const Type *CastSrcTy = 0;
4500 if (isa<CastInst>(FirstInst)) {
4501 CastSrcTy = FirstInst->getOperand(0)->getType();
4502 } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst)) {
4503 // Can fold binop or shift if the RHS is a constant.
4504 ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
4505 if (ConstantOp == 0) return 0;
4507 return 0; // Cannot fold this operation.
4510 // Check to see if all arguments are the same operation.
4511 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
4512 if (!isa<Instruction>(PN.getIncomingValue(i))) return 0;
4513 Instruction *I = cast<Instruction>(PN.getIncomingValue(i));
4514 if (!I->hasOneUse() || I->getOpcode() != FirstInst->getOpcode())
4517 if (I->getOperand(0)->getType() != CastSrcTy)
4518 return 0; // Cast operation must match.
4519 } else if (I->getOperand(1) != ConstantOp) {
4524 // Okay, they are all the same operation. Create a new PHI node of the
4525 // correct type, and PHI together all of the LHS's of the instructions.
4526 PHINode *NewPN = new PHINode(FirstInst->getOperand(0)->getType(),
4527 PN.getName()+".in");
4528 NewPN->reserveOperandSpace(PN.getNumOperands()/2);
4530 Value *InVal = FirstInst->getOperand(0);
4531 NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
4533 // Add all operands to the new PHI.
4534 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
4535 Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
4536 if (NewInVal != InVal)
4538 NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
4543 // The new PHI unions all of the same values together. This is really
4544 // common, so we handle it intelligently here for compile-time speed.
4548 InsertNewInstBefore(NewPN, PN);
4552 // Insert and return the new operation.
4553 if (isa<CastInst>(FirstInst))
4554 return new CastInst(PhiVal, PN.getType());
4555 else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst))
4556 return BinaryOperator::create(BinOp->getOpcode(), PhiVal, ConstantOp);
4558 return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(),
4559 PhiVal, ConstantOp);
4562 /// DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle
4564 static bool DeadPHICycle(PHINode *PN, std::set<PHINode*> &PotentiallyDeadPHIs) {
4565 if (PN->use_empty()) return true;
4566 if (!PN->hasOneUse()) return false;
4568 // Remember this node, and if we find the cycle, return.
4569 if (!PotentiallyDeadPHIs.insert(PN).second)
4572 if (PHINode *PU = dyn_cast<PHINode>(PN->use_back()))
4573 return DeadPHICycle(PU, PotentiallyDeadPHIs);
4578 // PHINode simplification
4580 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
4581 if (Value *V = PN.hasConstantValue())
4582 return ReplaceInstUsesWith(PN, V);
4584 // If the only user of this instruction is a cast instruction, and all of the
4585 // incoming values are constants, change this PHI to merge together the casted
4588 if (CastInst *CI = dyn_cast<CastInst>(PN.use_back()))
4589 if (CI->getType() != PN.getType()) { // noop casts will be folded
4590 bool AllConstant = true;
4591 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
4592 if (!isa<Constant>(PN.getIncomingValue(i))) {
4593 AllConstant = false;
4597 // Make a new PHI with all casted values.
4598 PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN);
4599 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
4600 Constant *OldArg = cast<Constant>(PN.getIncomingValue(i));
4601 New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()),
4602 PN.getIncomingBlock(i));
4605 // Update the cast instruction.
4606 CI->setOperand(0, New);
4607 WorkList.push_back(CI); // revisit the cast instruction to fold.
4608 WorkList.push_back(New); // Make sure to revisit the new Phi
4609 return &PN; // PN is now dead!
4613 // If all PHI operands are the same operation, pull them through the PHI,
4614 // reducing code size.
4615 if (isa<Instruction>(PN.getIncomingValue(0)) &&
4616 PN.getIncomingValue(0)->hasOneUse())
4617 if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
4620 // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
4621 // this PHI only has a single use (a PHI), and if that PHI only has one use (a
4622 // PHI)... break the cycle.
4624 if (PHINode *PU = dyn_cast<PHINode>(PN.use_back())) {
4625 std::set<PHINode*> PotentiallyDeadPHIs;
4626 PotentiallyDeadPHIs.insert(&PN);
4627 if (DeadPHICycle(PU, PotentiallyDeadPHIs))
4628 return ReplaceInstUsesWith(PN, UndefValue::get(PN.getType()));
4634 static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy,
4635 Instruction *InsertPoint,
4637 unsigned PS = IC->getTargetData().getPointerSize();
4638 const Type *VTy = V->getType();
4639 if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS)
4640 // We must insert a cast to ensure we sign-extend.
4641 V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(),
4642 V->getName()), *InsertPoint);
4643 return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()),
4648 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
4649 Value *PtrOp = GEP.getOperand(0);
4650 // Is it 'getelementptr %P, long 0' or 'getelementptr %P'
4651 // If so, eliminate the noop.
4652 if (GEP.getNumOperands() == 1)
4653 return ReplaceInstUsesWith(GEP, PtrOp);
4655 if (isa<UndefValue>(GEP.getOperand(0)))
4656 return ReplaceInstUsesWith(GEP, UndefValue::get(GEP.getType()));
4658 bool HasZeroPointerIndex = false;
4659 if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
4660 HasZeroPointerIndex = C->isNullValue();
4662 if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
4663 return ReplaceInstUsesWith(GEP, PtrOp);
4665 // Eliminate unneeded casts for indices.
4666 bool MadeChange = false;
4667 gep_type_iterator GTI = gep_type_begin(GEP);
4668 for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI)
4669 if (isa<SequentialType>(*GTI)) {
4670 if (CastInst *CI = dyn_cast<CastInst>(GEP.getOperand(i))) {
4671 Value *Src = CI->getOperand(0);
4672 const Type *SrcTy = Src->getType();
4673 const Type *DestTy = CI->getType();
4674 if (Src->getType()->isInteger()) {
4675 if (SrcTy->getPrimitiveSizeInBits() ==
4676 DestTy->getPrimitiveSizeInBits()) {
4677 // We can always eliminate a cast from ulong or long to the other.
4678 // We can always eliminate a cast from uint to int or the other on
4679 // 32-bit pointer platforms.
4680 if (DestTy->getPrimitiveSizeInBits() >= TD->getPointerSizeInBits()){
4682 GEP.setOperand(i, Src);
4684 } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
4685 SrcTy->getPrimitiveSize() == 4) {
4686 // We can always eliminate a cast from int to [u]long. We can
4687 // eliminate a cast from uint to [u]long iff the target is a 32-bit
4689 if (SrcTy->isSigned() ||
4690 SrcTy->getPrimitiveSizeInBits() >= TD->getPointerSizeInBits()) {
4692 GEP.setOperand(i, Src);
4697 // If we are using a wider index than needed for this platform, shrink it
4698 // to what we need. If the incoming value needs a cast instruction,
4699 // insert it. This explicit cast can make subsequent optimizations more
4701 Value *Op = GEP.getOperand(i);
4702 if (Op->getType()->getPrimitiveSize() > TD->getPointerSize())
4703 if (Constant *C = dyn_cast<Constant>(Op)) {
4704 GEP.setOperand(i, ConstantExpr::getCast(C,
4705 TD->getIntPtrType()->getSignedVersion()));
4708 Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(),
4709 Op->getName()), GEP);
4710 GEP.setOperand(i, Op);
4714 // If this is a constant idx, make sure to canonicalize it to be a signed
4715 // operand, otherwise CSE and other optimizations are pessimized.
4716 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op)) {
4717 GEP.setOperand(i, ConstantExpr::getCast(CUI,
4718 CUI->getType()->getSignedVersion()));
4722 if (MadeChange) return &GEP;
4724 // Combine Indices - If the source pointer to this getelementptr instruction
4725 // is a getelementptr instruction, combine the indices of the two
4726 // getelementptr instructions into a single instruction.
4728 std::vector<Value*> SrcGEPOperands;
4729 if (User *Src = dyn_castGetElementPtr(PtrOp))
4730 SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
4732 if (!SrcGEPOperands.empty()) {
4733 // Note that if our source is a gep chain itself that we wait for that
4734 // chain to be resolved before we perform this transformation. This
4735 // avoids us creating a TON of code in some cases.
4737 if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
4738 cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
4739 return 0; // Wait until our source is folded to completion.
4741 std::vector<Value *> Indices;
4743 // Find out whether the last index in the source GEP is a sequential idx.
4744 bool EndsWithSequential = false;
4745 for (gep_type_iterator I = gep_type_begin(*cast<User>(PtrOp)),
4746 E = gep_type_end(*cast<User>(PtrOp)); I != E; ++I)
4747 EndsWithSequential = !isa<StructType>(*I);
4749 // Can we combine the two pointer arithmetics offsets?
4750 if (EndsWithSequential) {
4751 // Replace: gep (gep %P, long B), long A, ...
4752 // With: T = long A+B; gep %P, T, ...
4754 Value *Sum, *SO1 = SrcGEPOperands.back(), *GO1 = GEP.getOperand(1);
4755 if (SO1 == Constant::getNullValue(SO1->getType())) {
4757 } else if (GO1 == Constant::getNullValue(GO1->getType())) {
4760 // If they aren't the same type, convert both to an integer of the
4761 // target's pointer size.
4762 if (SO1->getType() != GO1->getType()) {
4763 if (Constant *SO1C = dyn_cast<Constant>(SO1)) {
4764 SO1 = ConstantExpr::getCast(SO1C, GO1->getType());
4765 } else if (Constant *GO1C = dyn_cast<Constant>(GO1)) {
4766 GO1 = ConstantExpr::getCast(GO1C, SO1->getType());
4768 unsigned PS = TD->getPointerSize();
4769 if (SO1->getType()->getPrimitiveSize() == PS) {
4770 // Convert GO1 to SO1's type.
4771 GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this);
4773 } else if (GO1->getType()->getPrimitiveSize() == PS) {
4774 // Convert SO1 to GO1's type.
4775 SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this);
4777 const Type *PT = TD->getIntPtrType();
4778 SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this);
4779 GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this);
4783 if (isa<Constant>(SO1) && isa<Constant>(GO1))
4784 Sum = ConstantExpr::getAdd(cast<Constant>(SO1), cast<Constant>(GO1));
4786 Sum = BinaryOperator::createAdd(SO1, GO1, PtrOp->getName()+".sum");
4787 InsertNewInstBefore(cast<Instruction>(Sum), GEP);
4791 // Recycle the GEP we already have if possible.
4792 if (SrcGEPOperands.size() == 2) {
4793 GEP.setOperand(0, SrcGEPOperands[0]);
4794 GEP.setOperand(1, Sum);
4797 Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4798 SrcGEPOperands.end()-1);
4799 Indices.push_back(Sum);
4800 Indices.insert(Indices.end(), GEP.op_begin()+2, GEP.op_end());
4802 } else if (isa<Constant>(*GEP.idx_begin()) &&
4803 cast<Constant>(*GEP.idx_begin())->isNullValue() &&
4804 SrcGEPOperands.size() != 1) {
4805 // Otherwise we can do the fold if the first index of the GEP is a zero
4806 Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4807 SrcGEPOperands.end());
4808 Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
4811 if (!Indices.empty())
4812 return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
4814 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
4815 // GEP of global variable. If all of the indices for this GEP are
4816 // constants, we can promote this to a constexpr instead of an instruction.
4818 // Scan for nonconstants...
4819 std::vector<Constant*> Indices;
4820 User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
4821 for (; I != E && isa<Constant>(*I); ++I)
4822 Indices.push_back(cast<Constant>(*I));
4824 if (I == E) { // If they are all constants...
4825 Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices);
4827 // Replace all uses of the GEP with the new constexpr...
4828 return ReplaceInstUsesWith(GEP, CE);
4830 } else if (Value *X = isCast(PtrOp)) { // Is the operand a cast?
4831 if (!isa<PointerType>(X->getType())) {
4832 // Not interesting. Source pointer must be a cast from pointer.
4833 } else if (HasZeroPointerIndex) {
4834 // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
4835 // into : GEP [10 x ubyte]* X, long 0, ...
4837 // This occurs when the program declares an array extern like "int X[];"
4839 const PointerType *CPTy = cast<PointerType>(PtrOp->getType());
4840 const PointerType *XTy = cast<PointerType>(X->getType());
4841 if (const ArrayType *XATy =
4842 dyn_cast<ArrayType>(XTy->getElementType()))
4843 if (const ArrayType *CATy =
4844 dyn_cast<ArrayType>(CPTy->getElementType()))
4845 if (CATy->getElementType() == XATy->getElementType()) {
4846 // At this point, we know that the cast source type is a pointer
4847 // to an array of the same type as the destination pointer
4848 // array. Because the array type is never stepped over (there
4849 // is a leading zero) we can fold the cast into this GEP.
4850 GEP.setOperand(0, X);
4853 } else if (GEP.getNumOperands() == 2) {
4854 // Transform things like:
4855 // %t = getelementptr ubyte* cast ([2 x int]* %str to uint*), uint %V
4856 // into: %t1 = getelementptr [2 x int*]* %str, int 0, uint %V; cast
4857 const Type *SrcElTy = cast<PointerType>(X->getType())->getElementType();
4858 const Type *ResElTy=cast<PointerType>(PtrOp->getType())->getElementType();
4859 if (isa<ArrayType>(SrcElTy) &&
4860 TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) ==
4861 TD->getTypeSize(ResElTy)) {
4862 Value *V = InsertNewInstBefore(
4863 new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy),
4864 GEP.getOperand(1), GEP.getName()), GEP);
4865 return new CastInst(V, GEP.getType());
4868 // Transform things like:
4869 // getelementptr sbyte* cast ([100 x double]* X to sbyte*), int %tmp
4870 // (where tmp = 8*tmp2) into:
4871 // getelementptr [100 x double]* %arr, int 0, int %tmp.2
4873 if (isa<ArrayType>(SrcElTy) &&
4874 (ResElTy == Type::SByteTy || ResElTy == Type::UByteTy)) {
4875 uint64_t ArrayEltSize =
4876 TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType());
4878 // Check to see if "tmp" is a scale by a multiple of ArrayEltSize. We
4879 // allow either a mul, shift, or constant here.
4881 ConstantInt *Scale = 0;
4882 if (ArrayEltSize == 1) {
4883 NewIdx = GEP.getOperand(1);
4884 Scale = ConstantInt::get(NewIdx->getType(), 1);
4885 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP.getOperand(1))) {
4886 NewIdx = ConstantInt::get(CI->getType(), 1);
4888 } else if (Instruction *Inst =dyn_cast<Instruction>(GEP.getOperand(1))){
4889 if (Inst->getOpcode() == Instruction::Shl &&
4890 isa<ConstantInt>(Inst->getOperand(1))) {
4891 unsigned ShAmt =cast<ConstantUInt>(Inst->getOperand(1))->getValue();
4892 if (Inst->getType()->isSigned())
4893 Scale = ConstantSInt::get(Inst->getType(), 1ULL << ShAmt);
4895 Scale = ConstantUInt::get(Inst->getType(), 1ULL << ShAmt);
4896 NewIdx = Inst->getOperand(0);
4897 } else if (Inst->getOpcode() == Instruction::Mul &&
4898 isa<ConstantInt>(Inst->getOperand(1))) {
4899 Scale = cast<ConstantInt>(Inst->getOperand(1));
4900 NewIdx = Inst->getOperand(0);
4904 // If the index will be to exactly the right offset with the scale taken
4905 // out, perform the transformation.
4906 if (Scale && Scale->getRawValue() % ArrayEltSize == 0) {
4907 if (ConstantSInt *C = dyn_cast<ConstantSInt>(Scale))
4908 Scale = ConstantSInt::get(C->getType(),
4909 (int64_t)C->getRawValue() /
4910 (int64_t)ArrayEltSize);
4912 Scale = ConstantUInt::get(Scale->getType(),
4913 Scale->getRawValue() / ArrayEltSize);
4914 if (Scale->getRawValue() != 1) {
4915 Constant *C = ConstantExpr::getCast(Scale, NewIdx->getType());
4916 Instruction *Sc = BinaryOperator::createMul(NewIdx, C, "idxscale");
4917 NewIdx = InsertNewInstBefore(Sc, GEP);
4920 // Insert the new GEP instruction.
4922 new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy),
4923 NewIdx, GEP.getName());
4924 Idx = InsertNewInstBefore(Idx, GEP);
4925 return new CastInst(Idx, GEP.getType());
4934 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
4935 // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
4936 if (AI.isArrayAllocation()) // Check C != 1
4937 if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
4938 const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
4939 AllocationInst *New = 0;
4941 // Create and insert the replacement instruction...
4942 if (isa<MallocInst>(AI))
4943 New = new MallocInst(NewTy, 0, AI.getName());
4945 assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
4946 New = new AllocaInst(NewTy, 0, AI.getName());
4949 InsertNewInstBefore(New, AI);
4951 // Scan to the end of the allocation instructions, to skip over a block of
4952 // allocas if possible...
4954 BasicBlock::iterator It = New;
4955 while (isa<AllocationInst>(*It)) ++It;
4957 // Now that I is pointing to the first non-allocation-inst in the block,
4958 // insert our getelementptr instruction...
4960 Value *NullIdx = Constant::getNullValue(Type::IntTy);
4961 Value *V = new GetElementPtrInst(New, NullIdx, NullIdx,
4962 New->getName()+".sub", It);
4964 // Now make everything use the getelementptr instead of the original
4966 return ReplaceInstUsesWith(AI, V);
4967 } else if (isa<UndefValue>(AI.getArraySize())) {
4968 return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4971 // If alloca'ing a zero byte object, replace the alloca with a null pointer.
4972 // Note that we only do this for alloca's, because malloc should allocate and
4973 // return a unique pointer, even for a zero byte allocation.
4974 if (isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized() &&
4975 TD->getTypeSize(AI.getAllocatedType()) == 0)
4976 return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4981 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) {
4982 Value *Op = FI.getOperand(0);
4984 // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X
4985 if (CastInst *CI = dyn_cast<CastInst>(Op))
4986 if (isa<PointerType>(CI->getOperand(0)->getType())) {
4987 FI.setOperand(0, CI->getOperand(0));
4991 // free undef -> unreachable.
4992 if (isa<UndefValue>(Op)) {
4993 // Insert a new store to null because we cannot modify the CFG here.
4994 new StoreInst(ConstantBool::True,
4995 UndefValue::get(PointerType::get(Type::BoolTy)), &FI);
4996 return EraseInstFromFunction(FI);
4999 // If we have 'free null' delete the instruction. This can happen in stl code
5000 // when lots of inlining happens.
5001 if (isa<ConstantPointerNull>(Op))
5002 return EraseInstFromFunction(FI);
5008 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
5009 /// constantexpr, return the constant value being addressed by the constant
5010 /// expression, or null if something is funny.
5012 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
5013 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
5014 return 0; // Do not allow stepping over the value!
5016 // Loop over all of the operands, tracking down which value we are
5018 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
5019 for (++I; I != E; ++I)
5020 if (const StructType *STy = dyn_cast<StructType>(*I)) {
5021 ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
5022 assert(CU->getValue() < STy->getNumElements() &&
5023 "Struct index out of range!");
5024 unsigned El = (unsigned)CU->getValue();
5025 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
5026 C = CS->getOperand(El);
5027 } else if (isa<ConstantAggregateZero>(C)) {
5028 C = Constant::getNullValue(STy->getElementType(El));
5029 } else if (isa<UndefValue>(C)) {
5030 C = UndefValue::get(STy->getElementType(El));
5034 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
5035 const ArrayType *ATy = cast<ArrayType>(*I);
5036 if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
5037 if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
5038 C = CA->getOperand((unsigned)CI->getRawValue());
5039 else if (isa<ConstantAggregateZero>(C))
5040 C = Constant::getNullValue(ATy->getElementType());
5041 else if (isa<UndefValue>(C))
5042 C = UndefValue::get(ATy->getElementType());
5051 /// InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.
5052 static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
5053 User *CI = cast<User>(LI.getOperand(0));
5054 Value *CastOp = CI->getOperand(0);
5056 const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
5057 if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
5058 const Type *SrcPTy = SrcTy->getElementType();
5060 if (DestPTy->isInteger() || isa<PointerType>(DestPTy)) {
5061 // If the source is an array, the code below will not succeed. Check to
5062 // see if a trivial 'gep P, 0, 0' will help matters. Only do this for
5064 if (const ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
5065 if (Constant *CSrc = dyn_cast<Constant>(CastOp))
5066 if (ASrcTy->getNumElements() != 0) {
5067 std::vector<Value*> Idxs(2, Constant::getNullValue(Type::IntTy));
5068 CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
5069 SrcTy = cast<PointerType>(CastOp->getType());
5070 SrcPTy = SrcTy->getElementType();
5073 if ((SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
5074 // Do not allow turning this into a load of an integer, which is then
5075 // casted to a pointer, this pessimizes pointer analysis a lot.
5076 (isa<PointerType>(SrcPTy) == isa<PointerType>(LI.getType())) &&
5077 IC.getTargetData().getTypeSize(SrcPTy) ==
5078 IC.getTargetData().getTypeSize(DestPTy)) {
5080 // Okay, we are casting from one integer or pointer type to another of
5081 // the same size. Instead of casting the pointer before the load, cast
5082 // the result of the loaded value.
5083 Value *NewLoad = IC.InsertNewInstBefore(new LoadInst(CastOp,
5085 LI.isVolatile()),LI);
5086 // Now cast the result of the load.
5087 return new CastInst(NewLoad, LI.getType());
5094 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
5095 /// from this value cannot trap. If it is not obviously safe to load from the
5096 /// specified pointer, we do a quick local scan of the basic block containing
5097 /// ScanFrom, to determine if the address is already accessed.
5098 static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
5099 // If it is an alloca or global variable, it is always safe to load from.
5100 if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
5102 // Otherwise, be a little bit agressive by scanning the local block where we
5103 // want to check to see if the pointer is already being loaded or stored
5104 // from/to. If so, the previous load or store would have already trapped,
5105 // so there is no harm doing an extra load (also, CSE will later eliminate
5106 // the load entirely).
5107 BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
5112 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
5113 if (LI->getOperand(0) == V) return true;
5114 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
5115 if (SI->getOperand(1) == V) return true;
5121 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
5122 Value *Op = LI.getOperand(0);
5124 // load (cast X) --> cast (load X) iff safe
5125 if (CastInst *CI = dyn_cast<CastInst>(Op))
5126 if (Instruction *Res = InstCombineLoadCast(*this, LI))
5129 // None of the following transforms are legal for volatile loads.
5130 if (LI.isVolatile()) return 0;
5132 if (&LI.getParent()->front() != &LI) {
5133 BasicBlock::iterator BBI = &LI; --BBI;
5134 // If the instruction immediately before this is a store to the same
5135 // address, do a simple form of store->load forwarding.
5136 if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
5137 if (SI->getOperand(1) == LI.getOperand(0))
5138 return ReplaceInstUsesWith(LI, SI->getOperand(0));
5139 if (LoadInst *LIB = dyn_cast<LoadInst>(BBI))
5140 if (LIB->getOperand(0) == LI.getOperand(0))
5141 return ReplaceInstUsesWith(LI, LIB);
5144 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op))
5145 if (isa<ConstantPointerNull>(GEPI->getOperand(0)) ||
5146 isa<UndefValue>(GEPI->getOperand(0))) {
5147 // Insert a new store to null instruction before the load to indicate
5148 // that this code is not reachable. We do this instead of inserting
5149 // an unreachable instruction directly because we cannot modify the
5151 new StoreInst(UndefValue::get(LI.getType()),
5152 Constant::getNullValue(Op->getType()), &LI);
5153 return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
5156 if (Constant *C = dyn_cast<Constant>(Op)) {
5157 // load null/undef -> undef
5158 if ((C->isNullValue() || isa<UndefValue>(C))) {
5159 // Insert a new store to null instruction before the load to indicate that
5160 // this code is not reachable. We do this instead of inserting an
5161 // unreachable instruction directly because we cannot modify the CFG.
5162 new StoreInst(UndefValue::get(LI.getType()),
5163 Constant::getNullValue(Op->getType()), &LI);
5164 return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
5167 // Instcombine load (constant global) into the value loaded.
5168 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
5169 if (GV->isConstant() && !GV->isExternal())
5170 return ReplaceInstUsesWith(LI, GV->getInitializer());
5172 // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded.
5173 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
5174 if (CE->getOpcode() == Instruction::GetElementPtr) {
5175 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
5176 if (GV->isConstant() && !GV->isExternal())
5177 if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
5178 return ReplaceInstUsesWith(LI, V);
5179 if (CE->getOperand(0)->isNullValue()) {
5180 // Insert a new store to null instruction before the load to indicate
5181 // that this code is not reachable. We do this instead of inserting
5182 // an unreachable instruction directly because we cannot modify the
5184 new StoreInst(UndefValue::get(LI.getType()),
5185 Constant::getNullValue(Op->getType()), &LI);
5186 return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
5189 } else if (CE->getOpcode() == Instruction::Cast) {
5190 if (Instruction *Res = InstCombineLoadCast(*this, LI))
5195 if (Op->hasOneUse()) {
5196 // Change select and PHI nodes to select values instead of addresses: this
5197 // helps alias analysis out a lot, allows many others simplifications, and
5198 // exposes redundancy in the code.
5200 // Note that we cannot do the transformation unless we know that the
5201 // introduced loads cannot trap! Something like this is valid as long as
5202 // the condition is always false: load (select bool %C, int* null, int* %G),
5203 // but it would not be valid if we transformed it to load from null
5206 if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
5207 // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2).
5208 if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) &&
5209 isSafeToLoadUnconditionally(SI->getOperand(2), SI)) {
5210 Value *V1 = InsertNewInstBefore(new LoadInst(SI->getOperand(1),
5211 SI->getOperand(1)->getName()+".val"), LI);
5212 Value *V2 = InsertNewInstBefore(new LoadInst(SI->getOperand(2),
5213 SI->getOperand(2)->getName()+".val"), LI);
5214 return new SelectInst(SI->getCondition(), V1, V2);
5217 // load (select (cond, null, P)) -> load P
5218 if (Constant *C = dyn_cast<Constant>(SI->getOperand(1)))
5219 if (C->isNullValue()) {
5220 LI.setOperand(0, SI->getOperand(2));
5224 // load (select (cond, P, null)) -> load P
5225 if (Constant *C = dyn_cast<Constant>(SI->getOperand(2)))
5226 if (C->isNullValue()) {
5227 LI.setOperand(0, SI->getOperand(1));
5231 } else if (PHINode *PN = dyn_cast<PHINode>(Op)) {
5232 // load (phi (&V1, &V2, &V3)) --> phi(load &V1, load &V2, load &V3)
5233 bool Safe = PN->getParent() == LI.getParent();
5235 // Scan all of the instructions between the PHI and the load to make
5236 // sure there are no instructions that might possibly alter the value
5237 // loaded from the PHI.
5239 BasicBlock::iterator I = &LI;
5240 for (--I; !isa<PHINode>(I); --I)
5241 if (isa<StoreInst>(I) || isa<CallInst>(I)) {
5247 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e && Safe; ++i)
5248 if (!isSafeToLoadUnconditionally(PN->getIncomingValue(i),
5249 PN->getIncomingBlock(i)->getTerminator()))
5254 PHINode *NewPN = new PHINode(LI.getType(), PN->getName());
5255 InsertNewInstBefore(NewPN, *PN);
5256 std::map<BasicBlock*,Value*> LoadMap; // Don't insert duplicate loads
5258 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5259 BasicBlock *BB = PN->getIncomingBlock(i);
5260 Value *&TheLoad = LoadMap[BB];
5262 Value *InVal = PN->getIncomingValue(i);
5263 TheLoad = InsertNewInstBefore(new LoadInst(InVal,
5264 InVal->getName()+".val"),
5265 *BB->getTerminator());
5267 NewPN->addIncoming(TheLoad, BB);
5269 return ReplaceInstUsesWith(LI, NewPN);
5276 /// InstCombineStoreToCast - Fold 'store V, (cast P)' -> store (cast V), P'
5278 static Instruction *InstCombineStoreToCast(InstCombiner &IC, StoreInst &SI) {
5279 User *CI = cast<User>(SI.getOperand(1));
5280 Value *CastOp = CI->getOperand(0);
5282 const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
5283 if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
5284 const Type *SrcPTy = SrcTy->getElementType();
5286 if (DestPTy->isInteger() || isa<PointerType>(DestPTy)) {
5287 // If the source is an array, the code below will not succeed. Check to
5288 // see if a trivial 'gep P, 0, 0' will help matters. Only do this for
5290 if (const ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
5291 if (Constant *CSrc = dyn_cast<Constant>(CastOp))
5292 if (ASrcTy->getNumElements() != 0) {
5293 std::vector<Value*> Idxs(2, Constant::getNullValue(Type::IntTy));
5294 CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
5295 SrcTy = cast<PointerType>(CastOp->getType());
5296 SrcPTy = SrcTy->getElementType();
5299 if ((SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
5300 IC.getTargetData().getTypeSize(SrcPTy) ==
5301 IC.getTargetData().getTypeSize(DestPTy)) {
5303 // Okay, we are casting from one integer or pointer type to another of
5304 // the same size. Instead of casting the pointer before the store, cast
5305 // the value to be stored.
5307 if (Constant *C = dyn_cast<Constant>(SI.getOperand(0)))
5308 NewCast = ConstantExpr::getCast(C, SrcPTy);
5310 NewCast = IC.InsertNewInstBefore(new CastInst(SI.getOperand(0),
5312 SI.getOperand(0)->getName()+".c"), SI);
5314 return new StoreInst(NewCast, CastOp);
5321 Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
5322 Value *Val = SI.getOperand(0);
5323 Value *Ptr = SI.getOperand(1);
5325 if (isa<UndefValue>(Ptr)) { // store X, undef -> noop (even if volatile)
5326 removeFromWorkList(&SI);
5327 SI.eraseFromParent();
5332 if (SI.isVolatile()) return 0; // Don't hack volatile loads.
5334 // store X, null -> turns into 'unreachable' in SimplifyCFG
5335 if (isa<ConstantPointerNull>(Ptr)) {
5336 if (!isa<UndefValue>(Val)) {
5337 SI.setOperand(0, UndefValue::get(Val->getType()));
5338 if (Instruction *U = dyn_cast<Instruction>(Val))
5339 WorkList.push_back(U); // Dropped a use.
5342 return 0; // Do not modify these!
5345 // store undef, Ptr -> noop
5346 if (isa<UndefValue>(Val)) {
5347 removeFromWorkList(&SI);
5348 SI.eraseFromParent();
5353 // If the pointer destination is a cast, see if we can fold the cast into the
5355 if (CastInst *CI = dyn_cast<CastInst>(Ptr))
5356 if (Instruction *Res = InstCombineStoreToCast(*this, SI))
5358 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
5359 if (CE->getOpcode() == Instruction::Cast)
5360 if (Instruction *Res = InstCombineStoreToCast(*this, SI))
5364 // If this store is the last instruction in the basic block, and if the block
5365 // ends with an unconditional branch, try to move it to the successor block.
5366 BasicBlock::iterator BBI = &SI; ++BBI;
5367 if (BranchInst *BI = dyn_cast<BranchInst>(BBI))
5368 if (BI->isUnconditional()) {
5369 // Check to see if the successor block has exactly two incoming edges. If
5370 // so, see if the other predecessor contains a store to the same location.
5371 // if so, insert a PHI node (if needed) and move the stores down.
5372 BasicBlock *Dest = BI->getSuccessor(0);
5374 pred_iterator PI = pred_begin(Dest);
5375 BasicBlock *Other = 0;
5376 if (*PI != BI->getParent())
5379 if (PI != pred_end(Dest)) {
5380 if (*PI != BI->getParent())
5385 if (++PI != pred_end(Dest))
5388 if (Other) { // If only one other pred...
5389 BBI = Other->getTerminator();
5390 // Make sure this other block ends in an unconditional branch and that
5391 // there is an instruction before the branch.
5392 if (isa<BranchInst>(BBI) && cast<BranchInst>(BBI)->isUnconditional() &&
5393 BBI != Other->begin()) {
5395 StoreInst *OtherStore = dyn_cast<StoreInst>(BBI);
5397 // If this instruction is a store to the same location.
5398 if (OtherStore && OtherStore->getOperand(1) == SI.getOperand(1)) {
5399 // Okay, we know we can perform this transformation. Insert a PHI
5400 // node now if we need it.
5401 Value *MergedVal = OtherStore->getOperand(0);
5402 if (MergedVal != SI.getOperand(0)) {
5403 PHINode *PN = new PHINode(MergedVal->getType(), "storemerge");
5404 PN->reserveOperandSpace(2);
5405 PN->addIncoming(SI.getOperand(0), SI.getParent());
5406 PN->addIncoming(OtherStore->getOperand(0), Other);
5407 MergedVal = InsertNewInstBefore(PN, Dest->front());
5410 // Advance to a place where it is safe to insert the new store and
5412 BBI = Dest->begin();
5413 while (isa<PHINode>(BBI)) ++BBI;
5414 InsertNewInstBefore(new StoreInst(MergedVal, SI.getOperand(1),
5415 OtherStore->isVolatile()), *BBI);
5417 // Nuke the old stores.
5418 removeFromWorkList(&SI);
5419 removeFromWorkList(OtherStore);
5420 SI.eraseFromParent();
5421 OtherStore->eraseFromParent();
5433 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
5434 // Change br (not X), label True, label False to: br X, label False, True
5436 BasicBlock *TrueDest;
5437 BasicBlock *FalseDest;
5438 if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
5439 !isa<Constant>(X)) {
5440 // Swap Destinations and condition...
5442 BI.setSuccessor(0, FalseDest);
5443 BI.setSuccessor(1, TrueDest);
5447 // Cannonicalize setne -> seteq
5448 Instruction::BinaryOps Op; Value *Y;
5449 if (match(&BI, m_Br(m_SetCond(Op, m_Value(X), m_Value(Y)),
5450 TrueDest, FalseDest)))
5451 if ((Op == Instruction::SetNE || Op == Instruction::SetLE ||
5452 Op == Instruction::SetGE) && BI.getCondition()->hasOneUse()) {
5453 SetCondInst *I = cast<SetCondInst>(BI.getCondition());
5454 std::string Name = I->getName(); I->setName("");
5455 Instruction::BinaryOps NewOpcode = SetCondInst::getInverseCondition(Op);
5456 Value *NewSCC = BinaryOperator::create(NewOpcode, X, Y, Name, I);
5457 // Swap Destinations and condition...
5458 BI.setCondition(NewSCC);
5459 BI.setSuccessor(0, FalseDest);
5460 BI.setSuccessor(1, TrueDest);
5461 removeFromWorkList(I);
5462 I->getParent()->getInstList().erase(I);
5463 WorkList.push_back(cast<Instruction>(NewSCC));
5470 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
5471 Value *Cond = SI.getCondition();
5472 if (Instruction *I = dyn_cast<Instruction>(Cond)) {
5473 if (I->getOpcode() == Instruction::Add)
5474 if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
5475 // change 'switch (X+4) case 1:' into 'switch (X) case -3'
5476 for (unsigned i = 2, e = SI.getNumOperands(); i != e; i += 2)
5477 SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
5479 SI.setOperand(0, I->getOperand(0));
5480 WorkList.push_back(I);
5488 void InstCombiner::removeFromWorkList(Instruction *I) {
5489 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
5494 /// TryToSinkInstruction - Try to move the specified instruction from its
5495 /// current block into the beginning of DestBlock, which can only happen if it's
5496 /// safe to move the instruction past all of the instructions between it and the
5497 /// end of its block.
5498 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
5499 assert(I->hasOneUse() && "Invariants didn't hold!");
5501 // Cannot move control-flow-involving instructions.
5502 if (isa<PHINode>(I) || isa<InvokeInst>(I) || isa<CallInst>(I)) return false;
5504 // Do not sink alloca instructions out of the entry block.
5505 if (isa<AllocaInst>(I) && I->getParent() == &DestBlock->getParent()->front())
5508 // We can only sink load instructions if there is nothing between the load and
5509 // the end of block that could change the value.
5510 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
5511 if (LI->isVolatile()) return false; // Don't sink volatile loads.
5513 for (BasicBlock::iterator Scan = LI, E = LI->getParent()->end();
5515 if (Scan->mayWriteToMemory())
5519 BasicBlock::iterator InsertPos = DestBlock->begin();
5520 while (isa<PHINode>(InsertPos)) ++InsertPos;
5522 I->moveBefore(InsertPos);
5527 bool InstCombiner::runOnFunction(Function &F) {
5528 bool Changed = false;
5529 TD = &getAnalysis<TargetData>();
5532 // Populate the worklist with the reachable instructions.
5533 std::set<BasicBlock*> Visited;
5534 for (df_ext_iterator<BasicBlock*> BB = df_ext_begin(&F.front(), Visited),
5535 E = df_ext_end(&F.front(), Visited); BB != E; ++BB)
5536 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
5537 WorkList.push_back(I);
5539 // Do a quick scan over the function. If we find any blocks that are
5540 // unreachable, remove any instructions inside of them. This prevents
5541 // the instcombine code from having to deal with some bad special cases.
5542 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
5543 if (!Visited.count(BB)) {
5544 Instruction *Term = BB->getTerminator();
5545 while (Term != BB->begin()) { // Remove instrs bottom-up
5546 BasicBlock::iterator I = Term; --I;
5548 DEBUG(std::cerr << "IC: DCE: " << *I);
5551 if (!I->use_empty())
5552 I->replaceAllUsesWith(UndefValue::get(I->getType()));
5553 I->eraseFromParent();
5558 while (!WorkList.empty()) {
5559 Instruction *I = WorkList.back(); // Get an instruction from the worklist
5560 WorkList.pop_back();
5562 // Check to see if we can DCE or ConstantPropagate the instruction...
5563 // Check to see if we can DIE the instruction...
5564 if (isInstructionTriviallyDead(I)) {
5565 // Add operands to the worklist...
5566 if (I->getNumOperands() < 4)
5567 AddUsesToWorkList(*I);
5570 DEBUG(std::cerr << "IC: DCE: " << *I);
5572 I->eraseFromParent();
5573 removeFromWorkList(I);
5577 // Instruction isn't dead, see if we can constant propagate it...
5578 if (Constant *C = ConstantFoldInstruction(I)) {
5579 Value* Ptr = I->getOperand(0);
5580 if (isa<GetElementPtrInst>(I) &&
5581 cast<Constant>(Ptr)->isNullValue() &&
5582 !isa<ConstantPointerNull>(C) &&
5583 cast<PointerType>(Ptr->getType())->getElementType()->isSized()) {
5584 // If this is a constant expr gep that is effectively computing an
5585 // "offsetof", fold it into 'cast int X to T*' instead of 'gep 0, 0, 12'
5586 bool isFoldableGEP = true;
5587 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
5588 if (!isa<ConstantInt>(I->getOperand(i)))
5589 isFoldableGEP = false;
5590 if (isFoldableGEP) {
5591 uint64_t Offset = TD->getIndexedOffset(Ptr->getType(),
5592 std::vector<Value*>(I->op_begin()+1, I->op_end()));
5593 C = ConstantUInt::get(Type::ULongTy, Offset);
5594 C = ConstantExpr::getCast(C, TD->getIntPtrType());
5595 C = ConstantExpr::getCast(C, I->getType());
5599 DEBUG(std::cerr << "IC: ConstFold to: " << *C << " from: " << *I);
5601 // Add operands to the worklist...
5602 AddUsesToWorkList(*I);
5603 ReplaceInstUsesWith(*I, C);
5606 I->getParent()->getInstList().erase(I);
5607 removeFromWorkList(I);
5611 // See if we can trivially sink this instruction to a successor basic block.
5612 if (I->hasOneUse()) {
5613 BasicBlock *BB = I->getParent();
5614 BasicBlock *UserParent = cast<Instruction>(I->use_back())->getParent();
5615 if (UserParent != BB) {
5616 bool UserIsSuccessor = false;
5617 // See if the user is one of our successors.
5618 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
5619 if (*SI == UserParent) {
5620 UserIsSuccessor = true;
5624 // If the user is one of our immediate successors, and if that successor
5625 // only has us as a predecessors (we'd have to split the critical edge
5626 // otherwise), we can keep going.
5627 if (UserIsSuccessor && !isa<PHINode>(I->use_back()) &&
5628 next(pred_begin(UserParent)) == pred_end(UserParent))
5629 // Okay, the CFG is simple enough, try to sink this instruction.
5630 Changed |= TryToSinkInstruction(I, UserParent);
5634 // Now that we have an instruction, try combining it to simplify it...
5635 if (Instruction *Result = visit(*I)) {
5637 // Should we replace the old instruction with a new one?
5639 DEBUG(std::cerr << "IC: Old = " << *I
5640 << " New = " << *Result);
5642 // Everything uses the new instruction now.
5643 I->replaceAllUsesWith(Result);
5645 // Push the new instruction and any users onto the worklist.
5646 WorkList.push_back(Result);
5647 AddUsersToWorkList(*Result);
5649 // Move the name to the new instruction first...
5650 std::string OldName = I->getName(); I->setName("");
5651 Result->setName(OldName);
5653 // Insert the new instruction into the basic block...
5654 BasicBlock *InstParent = I->getParent();
5655 BasicBlock::iterator InsertPos = I;
5657 if (!isa<PHINode>(Result)) // If combining a PHI, don't insert
5658 while (isa<PHINode>(InsertPos)) // middle of a block of PHIs.
5661 InstParent->getInstList().insert(InsertPos, Result);
5663 // Make sure that we reprocess all operands now that we reduced their
5665 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
5666 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
5667 WorkList.push_back(OpI);
5669 // Instructions can end up on the worklist more than once. Make sure
5670 // we do not process an instruction that has been deleted.
5671 removeFromWorkList(I);
5673 // Erase the old instruction.
5674 InstParent->getInstList().erase(I);
5676 DEBUG(std::cerr << "IC: MOD = " << *I);
5678 // If the instruction was modified, it's possible that it is now dead.
5679 // if so, remove it.
5680 if (isInstructionTriviallyDead(I)) {
5681 // Make sure we process all operands now that we are reducing their
5683 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
5684 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
5685 WorkList.push_back(OpI);
5687 // Instructions may end up in the worklist more than once. Erase all
5688 // occurrances of this instruction.
5689 removeFromWorkList(I);
5690 I->eraseFromParent();
5692 WorkList.push_back(Result);
5693 AddUsersToWorkList(*Result);
5703 FunctionPass *llvm::createInstructionCombiningPass() {
5704 return new InstCombiner();