LLVM API Documentation
00001 //===- InstructionCombining.cpp - Combine multiple instructions -----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // InstructionCombining - Combine instructions to form fewer, simple 00011 // instructions. This pass does not modify the CFG This pass is where algebraic 00012 // simplification happens. 00013 // 00014 // This pass combines things like: 00015 // %Y = add int %X, 1 00016 // %Z = add int %Y, 1 00017 // into: 00018 // %Z = add int %X, 2 00019 // 00020 // This is a simple worklist driven algorithm. 00021 // 00022 // This pass guarantees that the following canonicalizations are performed on 00023 // the program: 00024 // 1. If a binary operator has a constant operand, it is moved to the RHS 00025 // 2. Bitwise operators with constant operands are always grouped so that 00026 // shifts are performed first, then or's, then and's, then xor's. 00027 // 3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible 00028 // 4. All SetCC instructions on boolean values are replaced with logical ops 00029 // 5. add X, X is represented as (X*2) => (X << 1) 00030 // 6. Multiplies with a power-of-two constant argument are transformed into 00031 // shifts. 00032 // ... etc. 00033 // 00034 //===----------------------------------------------------------------------===// 00035 00036 #define DEBUG_TYPE "instcombine" 00037 #include "llvm/Transforms/Scalar.h" 00038 #include "llvm/IntrinsicInst.h" 00039 #include "llvm/Pass.h" 00040 #include "llvm/DerivedTypes.h" 00041 #include "llvm/GlobalVariable.h" 00042 #include "llvm/Target/TargetData.h" 00043 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00044 #include "llvm/Transforms/Utils/Local.h" 00045 #include "llvm/Support/CallSite.h" 00046 #include "llvm/Support/GetElementPtrTypeIterator.h" 00047 #include "llvm/Support/InstIterator.h" 00048 #include "llvm/Support/InstVisitor.h" 00049 #include "llvm/Support/PatternMatch.h" 00050 #include "llvm/Support/Debug.h" 00051 #include "llvm/ADT/Statistic.h" 00052 #include <algorithm> 00053 using namespace llvm; 00054 using namespace llvm::PatternMatch; 00055 00056 namespace { 00057 Statistic<> NumCombined ("instcombine", "Number of insts combined"); 00058 Statistic<> NumConstProp("instcombine", "Number of constant folds"); 00059 Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated"); 00060 00061 class InstCombiner : public FunctionPass, 00062 public InstVisitor<InstCombiner, Instruction*> { 00063 // Worklist of all of the instructions that need to be simplified. 00064 std::vector<Instruction*> WorkList; 00065 TargetData *TD; 00066 00067 /// AddUsersToWorkList - When an instruction is simplified, add all users of 00068 /// the instruction to the work lists because they might get more simplified 00069 /// now. 00070 /// 00071 void AddUsersToWorkList(Instruction &I) { 00072 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); 00073 UI != UE; ++UI) 00074 WorkList.push_back(cast<Instruction>(*UI)); 00075 } 00076 00077 /// AddUsesToWorkList - When an instruction is simplified, add operands to 00078 /// the work lists because they might get more simplified now. 00079 /// 00080 void AddUsesToWorkList(Instruction &I) { 00081 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 00082 if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i))) 00083 WorkList.push_back(Op); 00084 } 00085 00086 // removeFromWorkList - remove all instances of I from the worklist. 00087 void removeFromWorkList(Instruction *I); 00088 public: 00089 virtual bool runOnFunction(Function &F); 00090 00091 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00092 AU.addRequired<TargetData>(); 00093 AU.setPreservesCFG(); 00094 } 00095 00096 TargetData &getTargetData() const { return *TD; } 00097 00098 // Visitation implementation - Implement instruction combining for different 00099 // instruction types. The semantics are as follows: 00100 // Return Value: 00101 // null - No change was made 00102 // I - Change was made, I is still valid, I may be dead though 00103 // otherwise - Change was made, replace I with returned instruction 00104 // 00105 Instruction *visitAdd(BinaryOperator &I); 00106 Instruction *visitSub(BinaryOperator &I); 00107 Instruction *visitMul(BinaryOperator &I); 00108 Instruction *visitDiv(BinaryOperator &I); 00109 Instruction *visitRem(BinaryOperator &I); 00110 Instruction *visitAnd(BinaryOperator &I); 00111 Instruction *visitOr (BinaryOperator &I); 00112 Instruction *visitXor(BinaryOperator &I); 00113 Instruction *visitSetCondInst(BinaryOperator &I); 00114 Instruction *visitSetCondInstWithCastAndConstant(BinaryOperator&I, 00115 CastInst*LHSI, 00116 ConstantInt* CI); 00117 Instruction *visitShiftInst(ShiftInst &I); 00118 Instruction *visitCastInst(CastInst &CI); 00119 Instruction *visitSelectInst(SelectInst &CI); 00120 Instruction *visitCallInst(CallInst &CI); 00121 Instruction *visitInvokeInst(InvokeInst &II); 00122 Instruction *visitPHINode(PHINode &PN); 00123 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP); 00124 Instruction *visitAllocationInst(AllocationInst &AI); 00125 Instruction *visitFreeInst(FreeInst &FI); 00126 Instruction *visitLoadInst(LoadInst &LI); 00127 Instruction *visitBranchInst(BranchInst &BI); 00128 Instruction *visitSwitchInst(SwitchInst &SI); 00129 00130 // visitInstruction - Specify what to return for unhandled instructions... 00131 Instruction *visitInstruction(Instruction &I) { return 0; } 00132 00133 private: 00134 Instruction *visitCallSite(CallSite CS); 00135 bool transformConstExprCastCall(CallSite CS); 00136 00137 public: 00138 // InsertNewInstBefore - insert an instruction New before instruction Old 00139 // in the program. Add the new instruction to the worklist. 00140 // 00141 Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) { 00142 assert(New && New->getParent() == 0 && 00143 "New instruction already inserted into a basic block!"); 00144 BasicBlock *BB = Old.getParent(); 00145 BB->getInstList().insert(&Old, New); // Insert inst 00146 WorkList.push_back(New); // Add to worklist 00147 return New; 00148 } 00149 00150 /// InsertCastBefore - Insert a cast of V to TY before the instruction POS. 00151 /// This also adds the cast to the worklist. Finally, this returns the 00152 /// cast. 00153 Value *InsertCastBefore(Value *V, const Type *Ty, Instruction &Pos) { 00154 if (V->getType() == Ty) return V; 00155 00156 Instruction *C = new CastInst(V, Ty, V->getName(), &Pos); 00157 WorkList.push_back(C); 00158 return C; 00159 } 00160 00161 // ReplaceInstUsesWith - This method is to be used when an instruction is 00162 // found to be dead, replacable with another preexisting expression. Here 00163 // we add all uses of I to the worklist, replace all uses of I with the new 00164 // value, then return I, so that the inst combiner will know that I was 00165 // modified. 00166 // 00167 Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) { 00168 AddUsersToWorkList(I); // Add all modified instrs to worklist 00169 if (&I != V) { 00170 I.replaceAllUsesWith(V); 00171 return &I; 00172 } else { 00173 // If we are replacing the instruction with itself, this must be in a 00174 // segment of unreachable code, so just clobber the instruction. 00175 I.replaceAllUsesWith(UndefValue::get(I.getType())); 00176 return &I; 00177 } 00178 } 00179 00180 // EraseInstFromFunction - When dealing with an instruction that has side 00181 // effects or produces a void value, we can't rely on DCE to delete the 00182 // instruction. Instead, visit methods should return the value returned by 00183 // this function. 00184 Instruction *EraseInstFromFunction(Instruction &I) { 00185 assert(I.use_empty() && "Cannot erase instruction that is used!"); 00186 AddUsesToWorkList(I); 00187 removeFromWorkList(&I); 00188 I.eraseFromParent(); 00189 return 0; // Don't do anything with FI 00190 } 00191 00192 00193 private: 00194 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the 00195 /// InsertBefore instruction. This is specialized a bit to avoid inserting 00196 /// casts that are known to not do anything... 00197 /// 00198 Value *InsertOperandCastBefore(Value *V, const Type *DestTy, 00199 Instruction *InsertBefore); 00200 00201 // SimplifyCommutative - This performs a few simplifications for commutative 00202 // operators. 00203 bool SimplifyCommutative(BinaryOperator &I); 00204 00205 00206 // FoldOpIntoPhi - Given a binary operator or cast instruction which has a 00207 // PHI node as operand #0, see if we can fold the instruction into the PHI 00208 // (which is only possible if all operands to the PHI are constants). 00209 Instruction *FoldOpIntoPhi(Instruction &I); 00210 00211 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary" 00212 // operator and they all are only used by the PHI, PHI together their 00213 // inputs, and do the operation once, to the result of the PHI. 00214 Instruction *FoldPHIArgOpIntoPHI(PHINode &PN); 00215 00216 Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS, 00217 ConstantIntegral *AndRHS, BinaryOperator &TheAnd); 00218 00219 Instruction *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, 00220 bool Inside, Instruction &IB); 00221 }; 00222 00223 RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions"); 00224 } 00225 00226 // getComplexity: Assign a complexity or rank value to LLVM Values... 00227 // 0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst 00228 static unsigned getComplexity(Value *V) { 00229 if (isa<Instruction>(V)) { 00230 if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V)) 00231 return 3; 00232 return 4; 00233 } 00234 if (isa<Argument>(V)) return 3; 00235 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2; 00236 } 00237 00238 // isOnlyUse - Return true if this instruction will be deleted if we stop using 00239 // it. 00240 static bool isOnlyUse(Value *V) { 00241 return V->hasOneUse() || isa<Constant>(V); 00242 } 00243 00244 // getPromotedType - Return the specified type promoted as it would be to pass 00245 // though a va_arg area... 00246 static const Type *getPromotedType(const Type *Ty) { 00247 switch (Ty->getTypeID()) { 00248 case Type::SByteTyID: 00249 case Type::ShortTyID: return Type::IntTy; 00250 case Type::UByteTyID: 00251 case Type::UShortTyID: return Type::UIntTy; 00252 case Type::FloatTyID: return Type::DoubleTy; 00253 default: return Ty; 00254 } 00255 } 00256 00257 // SimplifyCommutative - This performs a few simplifications for commutative 00258 // operators: 00259 // 00260 // 1. Order operands such that they are listed from right (least complex) to 00261 // left (most complex). This puts constants before unary operators before 00262 // binary operators. 00263 // 00264 // 2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2)) 00265 // 3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2)) 00266 // 00267 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) { 00268 bool Changed = false; 00269 if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) 00270 Changed = !I.swapOperands(); 00271 00272 if (!I.isAssociative()) return Changed; 00273 Instruction::BinaryOps Opcode = I.getOpcode(); 00274 if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0))) 00275 if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) { 00276 if (isa<Constant>(I.getOperand(1))) { 00277 Constant *Folded = ConstantExpr::get(I.getOpcode(), 00278 cast<Constant>(I.getOperand(1)), 00279 cast<Constant>(Op->getOperand(1))); 00280 I.setOperand(0, Op->getOperand(0)); 00281 I.setOperand(1, Folded); 00282 return true; 00283 } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1))) 00284 if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) && 00285 isOnlyUse(Op) && isOnlyUse(Op1)) { 00286 Constant *C1 = cast<Constant>(Op->getOperand(1)); 00287 Constant *C2 = cast<Constant>(Op1->getOperand(1)); 00288 00289 // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2)) 00290 Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2); 00291 Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0), 00292 Op1->getOperand(0), 00293 Op1->getName(), &I); 00294 WorkList.push_back(New); 00295 I.setOperand(0, New); 00296 I.setOperand(1, Folded); 00297 return true; 00298 } 00299 } 00300 return Changed; 00301 } 00302 00303 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction 00304 // if the LHS is a constant zero (which is the 'negate' form). 00305 // 00306 static inline Value *dyn_castNegVal(Value *V) { 00307 if (BinaryOperator::isNeg(V)) 00308 return BinaryOperator::getNegArgument(cast<BinaryOperator>(V)); 00309 00310 // Constants can be considered to be negated values if they can be folded... 00311 if (Constant *C = dyn_cast<Constant>(V)) 00312 return ConstantExpr::getNeg(C); 00313 return 0; 00314 } 00315 00316 static inline Value *dyn_castNotVal(Value *V) { 00317 if (BinaryOperator::isNot(V)) 00318 return BinaryOperator::getNotArgument(cast<BinaryOperator>(V)); 00319 00320 // Constants can be considered to be not'ed values... 00321 if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V)) 00322 return ConstantExpr::getNot(C); 00323 return 0; 00324 } 00325 00326 // dyn_castFoldableMul - If this value is a multiply that can be folded into 00327 // other computations (because it has a constant operand), return the 00328 // non-constant operand of the multiply, and set CST to point to the multiplier. 00329 // Otherwise, return null. 00330 // 00331 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 00332 if (V->hasOneUse() && V->getType()->isInteger()) 00333 if (Instruction *I = dyn_cast<Instruction>(V)) { 00334 if (I->getOpcode() == Instruction::Mul) 00335 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 00336 return I->getOperand(0); 00337 if (I->getOpcode() == Instruction::Shl) 00338 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 00339 // The multiplier is really 1 << CST. 00340 Constant *One = ConstantInt::get(V->getType(), 1); 00341 CST = cast<ConstantInt>(ConstantExpr::getShl(One, CST)); 00342 return I->getOperand(0); 00343 } 00344 } 00345 return 0; 00346 } 00347 00348 // Log2 - Calculate the log base 2 for the specified value if it is exactly a 00349 // power of 2. 00350 static unsigned Log2(uint64_t Val) { 00351 assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!"); 00352 unsigned Count = 0; 00353 while (Val != 1) { 00354 if (Val & 1) return 0; // Multiple bits set? 00355 Val >>= 1; 00356 ++Count; 00357 } 00358 return Count; 00359 } 00360 00361 // AddOne, SubOne - Add or subtract a constant one from an integer constant... 00362 static ConstantInt *AddOne(ConstantInt *C) { 00363 return cast<ConstantInt>(ConstantExpr::getAdd(C, 00364 ConstantInt::get(C->getType(), 1))); 00365 } 00366 static ConstantInt *SubOne(ConstantInt *C) { 00367 return cast<ConstantInt>(ConstantExpr::getSub(C, 00368 ConstantInt::get(C->getType(), 1))); 00369 } 00370 00371 // isTrueWhenEqual - Return true if the specified setcondinst instruction is 00372 // true when both operands are equal... 00373 // 00374 static bool isTrueWhenEqual(Instruction &I) { 00375 return I.getOpcode() == Instruction::SetEQ || 00376 I.getOpcode() == Instruction::SetGE || 00377 I.getOpcode() == Instruction::SetLE; 00378 } 00379 00380 /// AssociativeOpt - Perform an optimization on an associative operator. This 00381 /// function is designed to check a chain of associative operators for a 00382 /// potential to apply a certain optimization. Since the optimization may be 00383 /// applicable if the expression was reassociated, this checks the chain, then 00384 /// reassociates the expression as necessary to expose the optimization 00385 /// opportunity. This makes use of a special Functor, which must define 00386 /// 'shouldApply' and 'apply' methods. 00387 /// 00388 template<typename Functor> 00389 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) { 00390 unsigned Opcode = Root.getOpcode(); 00391 Value *LHS = Root.getOperand(0); 00392 00393 // Quick check, see if the immediate LHS matches... 00394 if (F.shouldApply(LHS)) 00395 return F.apply(Root); 00396 00397 // Otherwise, if the LHS is not of the same opcode as the root, return. 00398 Instruction *LHSI = dyn_cast<Instruction>(LHS); 00399 while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) { 00400 // Should we apply this transform to the RHS? 00401 bool ShouldApply = F.shouldApply(LHSI->getOperand(1)); 00402 00403 // If not to the RHS, check to see if we should apply to the LHS... 00404 if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) { 00405 cast<BinaryOperator>(LHSI)->swapOperands(); // Make the LHS the RHS 00406 ShouldApply = true; 00407 } 00408 00409 // If the functor wants to apply the optimization to the RHS of LHSI, 00410 // reassociate the expression from ((? op A) op B) to (? op (A op B)) 00411 if (ShouldApply) { 00412 BasicBlock *BB = Root.getParent(); 00413 00414 // Now all of the instructions are in the current basic block, go ahead 00415 // and perform the reassociation. 00416 Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0)); 00417 00418 // First move the selected RHS to the LHS of the root... 00419 Root.setOperand(0, LHSI->getOperand(1)); 00420 00421 // Make what used to be the LHS of the root be the user of the root... 00422 Value *ExtraOperand = TmpLHSI->getOperand(1); 00423 if (&Root == TmpLHSI) { 00424 Root.replaceAllUsesWith(Constant::getNullValue(TmpLHSI->getType())); 00425 return 0; 00426 } 00427 Root.replaceAllUsesWith(TmpLHSI); // Users now use TmpLHSI 00428 TmpLHSI->setOperand(1, &Root); // TmpLHSI now uses the root 00429 TmpLHSI->getParent()->getInstList().remove(TmpLHSI); 00430 BasicBlock::iterator ARI = &Root; ++ARI; 00431 BB->getInstList().insert(ARI, TmpLHSI); // Move TmpLHSI to after Root 00432 ARI = Root; 00433 00434 // Now propagate the ExtraOperand down the chain of instructions until we 00435 // get to LHSI. 00436 while (TmpLHSI != LHSI) { 00437 Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0)); 00438 // Move the instruction to immediately before the chain we are 00439 // constructing to avoid breaking dominance properties. 00440 NextLHSI->getParent()->getInstList().remove(NextLHSI); 00441 BB->getInstList().insert(ARI, NextLHSI); 00442 ARI = NextLHSI; 00443 00444 Value *NextOp = NextLHSI->getOperand(1); 00445 NextLHSI->setOperand(1, ExtraOperand); 00446 TmpLHSI = NextLHSI; 00447 ExtraOperand = NextOp; 00448 } 00449 00450 // Now that the instructions are reassociated, have the functor perform 00451 // the transformation... 00452 return F.apply(Root); 00453 } 00454 00455 LHSI = dyn_cast<Instruction>(LHSI->getOperand(0)); 00456 } 00457 return 0; 00458 } 00459 00460 00461 // AddRHS - Implements: X + X --> X << 1 00462 struct AddRHS { 00463 Value *RHS; 00464 AddRHS(Value *rhs) : RHS(rhs) {} 00465 bool shouldApply(Value *LHS) const { return LHS == RHS; } 00466 Instruction *apply(BinaryOperator &Add) const { 00467 return new ShiftInst(Instruction::Shl, Add.getOperand(0), 00468 ConstantInt::get(Type::UByteTy, 1)); 00469 } 00470 }; 00471 00472 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2) 00473 // iff C1&C2 == 0 00474 struct AddMaskingAnd { 00475 Constant *C2; 00476 AddMaskingAnd(Constant *c) : C2(c) {} 00477 bool shouldApply(Value *LHS) const { 00478 ConstantInt *C1; 00479 return match(LHS, m_And(m_Value(), m_ConstantInt(C1))) && 00480 ConstantExpr::getAnd(C1, C2)->isNullValue(); 00481 } 00482 Instruction *apply(BinaryOperator &Add) const { 00483 return BinaryOperator::createOr(Add.getOperand(0), Add.getOperand(1)); 00484 } 00485 }; 00486 00487 static Value *FoldOperationIntoSelectOperand(Instruction &BI, Value *SO, 00488 InstCombiner *IC) { 00489 // Figure out if the constant is the left or the right argument. 00490 bool ConstIsRHS = isa<Constant>(BI.getOperand(1)); 00491 Constant *ConstOperand = cast<Constant>(BI.getOperand(ConstIsRHS)); 00492 00493 if (Constant *SOC = dyn_cast<Constant>(SO)) { 00494 if (ConstIsRHS) 00495 return ConstantExpr::get(BI.getOpcode(), SOC, ConstOperand); 00496 return ConstantExpr::get(BI.getOpcode(), ConstOperand, SOC); 00497 } 00498 00499 Value *Op0 = SO, *Op1 = ConstOperand; 00500 if (!ConstIsRHS) 00501 std::swap(Op0, Op1); 00502 Instruction *New; 00503 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&BI)) 00504 New = BinaryOperator::create(BO->getOpcode(), Op0, Op1); 00505 else if (ShiftInst *SI = dyn_cast<ShiftInst>(&BI)) 00506 New = new ShiftInst(SI->getOpcode(), Op0, Op1); 00507 else { 00508 assert(0 && "Unknown binary instruction type!"); 00509 abort(); 00510 } 00511 return IC->InsertNewInstBefore(New, BI); 00512 } 00513 00514 00515 /// FoldOpIntoPhi - Given a binary operator or cast instruction which has a PHI 00516 /// node as operand #0, see if we can fold the instruction into the PHI (which 00517 /// is only possible if all operands to the PHI are constants). 00518 Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) { 00519 PHINode *PN = cast<PHINode>(I.getOperand(0)); 00520 unsigned NumPHIValues = PN->getNumIncomingValues(); 00521 if (!PN->hasOneUse() || NumPHIValues == 0 || 00522 !isa<Constant>(PN->getIncomingValue(0))) return 0; 00523 00524 // Check to see if all of the operands of the PHI are constants. If not, we 00525 // cannot do the transformation. 00526 for (unsigned i = 1; i != NumPHIValues; ++i) 00527 if (!isa<Constant>(PN->getIncomingValue(i))) 00528 return 0; 00529 00530 // Okay, we can do the transformation: create the new PHI node. 00531 PHINode *NewPN = new PHINode(I.getType(), I.getName()); 00532 I.setName(""); 00533 NewPN->op_reserve(PN->getNumOperands()); 00534 InsertNewInstBefore(NewPN, *PN); 00535 00536 // Next, add all of the operands to the PHI. 00537 if (I.getNumOperands() == 2) { 00538 Constant *C = cast<Constant>(I.getOperand(1)); 00539 for (unsigned i = 0; i != NumPHIValues; ++i) { 00540 Constant *InV = cast<Constant>(PN->getIncomingValue(i)); 00541 NewPN->addIncoming(ConstantExpr::get(I.getOpcode(), InV, C), 00542 PN->getIncomingBlock(i)); 00543 } 00544 } else { 00545 assert(isa<CastInst>(I) && "Unary op should be a cast!"); 00546 const Type *RetTy = I.getType(); 00547 for (unsigned i = 0; i != NumPHIValues; ++i) { 00548 Constant *InV = cast<Constant>(PN->getIncomingValue(i)); 00549 NewPN->addIncoming(ConstantExpr::getCast(InV, RetTy), 00550 PN->getIncomingBlock(i)); 00551 } 00552 } 00553 return ReplaceInstUsesWith(I, NewPN); 00554 } 00555 00556 // FoldBinOpIntoSelect - Given an instruction with a select as one operand and a 00557 // constant as the other operand, try to fold the binary operator into the 00558 // select arguments. 00559 static Instruction *FoldBinOpIntoSelect(Instruction &BI, SelectInst *SI, 00560 InstCombiner *IC) { 00561 // Don't modify shared select instructions 00562 if (!SI->hasOneUse()) return 0; 00563 Value *TV = SI->getOperand(1); 00564 Value *FV = SI->getOperand(2); 00565 00566 if (isa<Constant>(TV) || isa<Constant>(FV)) { 00567 Value *SelectTrueVal = FoldOperationIntoSelectOperand(BI, TV, IC); 00568 Value *SelectFalseVal = FoldOperationIntoSelectOperand(BI, FV, IC); 00569 00570 return new SelectInst(SI->getCondition(), SelectTrueVal, 00571 SelectFalseVal); 00572 } 00573 return 0; 00574 } 00575 00576 Instruction *InstCombiner::visitAdd(BinaryOperator &I) { 00577 bool Changed = SimplifyCommutative(I); 00578 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 00579 00580 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 00581 // X + undef -> undef 00582 if (isa<UndefValue>(RHS)) 00583 return ReplaceInstUsesWith(I, RHS); 00584 00585 // X + 0 --> X 00586 if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop 00587 RHSC->isNullValue()) 00588 return ReplaceInstUsesWith(I, LHS); 00589 00590 // X + (signbit) --> X ^ signbit 00591 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) { 00592 unsigned NumBits = CI->getType()->getPrimitiveSize()*8; 00593 uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1; 00594 if (Val == (1ULL << (NumBits-1))) 00595 return BinaryOperator::createXor(LHS, RHS); 00596 } 00597 00598 if (isa<PHINode>(LHS)) 00599 if (Instruction *NV = FoldOpIntoPhi(I)) 00600 return NV; 00601 } 00602 00603 // X + X --> X << 1 00604 if (I.getType()->isInteger()) { 00605 if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result; 00606 } 00607 00608 // -A + B --> B - A 00609 if (Value *V = dyn_castNegVal(LHS)) 00610 return BinaryOperator::createSub(RHS, V); 00611 00612 // A + -B --> A - B 00613 if (!isa<Constant>(RHS)) 00614 if (Value *V = dyn_castNegVal(RHS)) 00615 return BinaryOperator::createSub(LHS, V); 00616 00617 ConstantInt *C2; 00618 if (Value *X = dyn_castFoldableMul(LHS, C2)) { 00619 if (X == RHS) // X*C + X --> X * (C+1) 00620 return BinaryOperator::createMul(RHS, AddOne(C2)); 00621 00622 // X*C1 + X*C2 --> X * (C1+C2) 00623 ConstantInt *C1; 00624 if (X == dyn_castFoldableMul(RHS, C1)) 00625 return BinaryOperator::createMul(X, ConstantExpr::getAdd(C1, C2)); 00626 } 00627 00628 // X + X*C --> X * (C+1) 00629 if (dyn_castFoldableMul(RHS, C2) == LHS) 00630 return BinaryOperator::createMul(LHS, AddOne(C2)); 00631 00632 00633 // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0 00634 if (match(RHS, m_And(m_Value(), m_ConstantInt(C2)))) 00635 if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R; 00636 00637 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 00638 Value *X; 00639 if (match(LHS, m_Not(m_Value(X)))) { // ~X + C --> (C-1) - X 00640 Constant *C= ConstantExpr::getSub(CRHS, ConstantInt::get(I.getType(), 1)); 00641 return BinaryOperator::createSub(C, X); 00642 } 00643 00644 // (X & FF00) + xx00 -> (X+xx00) & FF00 00645 if (LHS->hasOneUse() && match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) { 00646 Constant *Anded = ConstantExpr::getAnd(CRHS, C2); 00647 if (Anded == CRHS) { 00648 // See if all bits from the first bit set in the Add RHS up are included 00649 // in the mask. First, get the rightmost bit. 00650 uint64_t AddRHSV = CRHS->getRawValue(); 00651 00652 // Form a mask of all bits from the lowest bit added through the top. 00653 uint64_t AddRHSHighBits = ~((AddRHSV & -AddRHSV)-1); 00654 AddRHSHighBits &= (1ULL << C2->getType()->getPrimitiveSize()*8)-1; 00655 00656 // See if the and mask includes all of these bits. 00657 uint64_t AddRHSHighBitsAnd = AddRHSHighBits & C2->getRawValue(); 00658 00659 if (AddRHSHighBits == AddRHSHighBitsAnd) { 00660 // Okay, the xform is safe. Insert the new add pronto. 00661 Value *NewAdd = InsertNewInstBefore(BinaryOperator::createAdd(X, CRHS, 00662 LHS->getName()), I); 00663 return BinaryOperator::createAnd(NewAdd, C2); 00664 } 00665 } 00666 } 00667 00668 00669 // Try to fold constant add into select arguments. 00670 if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 00671 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 00672 return R; 00673 } 00674 00675 return Changed ? &I : 0; 00676 } 00677 00678 // isSignBit - Return true if the value represented by the constant only has the 00679 // highest order bit set. 00680 static bool isSignBit(ConstantInt *CI) { 00681 unsigned NumBits = CI->getType()->getPrimitiveSize()*8; 00682 return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1)); 00683 } 00684 00685 static unsigned getTypeSizeInBits(const Type *Ty) { 00686 return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8; 00687 } 00688 00689 /// RemoveNoopCast - Strip off nonconverting casts from the value. 00690 /// 00691 static Value *RemoveNoopCast(Value *V) { 00692 if (CastInst *CI = dyn_cast<CastInst>(V)) { 00693 const Type *CTy = CI->getType(); 00694 const Type *OpTy = CI->getOperand(0)->getType(); 00695 if (CTy->isInteger() && OpTy->isInteger()) { 00696 if (CTy->getPrimitiveSize() == OpTy->getPrimitiveSize()) 00697 return RemoveNoopCast(CI->getOperand(0)); 00698 } else if (isa<PointerType>(CTy) && isa<PointerType>(OpTy)) 00699 return RemoveNoopCast(CI->getOperand(0)); 00700 } 00701 return V; 00702 } 00703 00704 Instruction *InstCombiner::visitSub(BinaryOperator &I) { 00705 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 00706 00707 if (Op0 == Op1) // sub X, X -> 0 00708 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 00709 00710 // If this is a 'B = x-(-A)', change to B = x+A... 00711 if (Value *V = dyn_castNegVal(Op1)) 00712 return BinaryOperator::createAdd(Op0, V); 00713 00714 if (isa<UndefValue>(Op0)) 00715 return ReplaceInstUsesWith(I, Op0); // undef - X -> undef 00716 if (isa<UndefValue>(Op1)) 00717 return ReplaceInstUsesWith(I, Op1); // X - undef -> undef 00718 00719 if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 00720 // Replace (-1 - A) with (~A)... 00721 if (C->isAllOnesValue()) 00722 return BinaryOperator::createNot(Op1); 00723 00724 // C - ~X == X + (1+C) 00725 Value *X; 00726 if (match(Op1, m_Not(m_Value(X)))) 00727 return BinaryOperator::createAdd(X, 00728 ConstantExpr::getAdd(C, ConstantInt::get(I.getType(), 1))); 00729 // -((uint)X >> 31) -> ((int)X >> 31) 00730 // -((int)X >> 31) -> ((uint)X >> 31) 00731 if (C->isNullValue()) { 00732 Value *NoopCastedRHS = RemoveNoopCast(Op1); 00733 if (ShiftInst *SI = dyn_cast<ShiftInst>(NoopCastedRHS)) 00734 if (SI->getOpcode() == Instruction::Shr) 00735 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(SI->getOperand(1))) { 00736 const Type *NewTy; 00737 if (SI->getType()->isSigned()) 00738 NewTy = SI->getType()->getUnsignedVersion(); 00739 else 00740 NewTy = SI->getType()->getSignedVersion(); 00741 // Check to see if we are shifting out everything but the sign bit. 00742 if (CU->getValue() == SI->getType()->getPrimitiveSize()*8-1) { 00743 // Ok, the transformation is safe. Insert a cast of the incoming 00744 // value, then the new shift, then the new cast. 00745 Instruction *FirstCast = new CastInst(SI->getOperand(0), NewTy, 00746 SI->getOperand(0)->getName()); 00747 Value *InV = InsertNewInstBefore(FirstCast, I); 00748 Instruction *NewShift = new ShiftInst(Instruction::Shr, FirstCast, 00749 CU, SI->getName()); 00750 if (NewShift->getType() == I.getType()) 00751 return NewShift; 00752 else { 00753 InV = InsertNewInstBefore(NewShift, I); 00754 return new CastInst(NewShift, I.getType()); 00755 } 00756 } 00757 } 00758 } 00759 00760 // Try to fold constant sub into select arguments. 00761 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 00762 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 00763 return R; 00764 00765 if (isa<PHINode>(Op0)) 00766 if (Instruction *NV = FoldOpIntoPhi(I)) 00767 return NV; 00768 } 00769 00770 if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) 00771 if (Op1I->hasOneUse()) { 00772 // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression 00773 // is not used by anyone else... 00774 // 00775 if (Op1I->getOpcode() == Instruction::Sub && 00776 !Op1I->getType()->isFloatingPoint()) { 00777 // Swap the two operands of the subexpr... 00778 Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1); 00779 Op1I->setOperand(0, IIOp1); 00780 Op1I->setOperand(1, IIOp0); 00781 00782 // Create the new top level add instruction... 00783 return BinaryOperator::createAdd(Op0, Op1); 00784 } 00785 00786 // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)... 00787 // 00788 if (Op1I->getOpcode() == Instruction::And && 00789 (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) { 00790 Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0); 00791 00792 Value *NewNot = 00793 InsertNewInstBefore(BinaryOperator::createNot(OtherOp, "B.not"), I); 00794 return BinaryOperator::createAnd(Op0, NewNot); 00795 } 00796 00797 // -(X sdiv C) -> (X sdiv -C) 00798 if (Op1I->getOpcode() == Instruction::Div) 00799 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0)) 00800 if (CSI->getValue() == 0) 00801 if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1))) 00802 return BinaryOperator::createDiv(Op1I->getOperand(0), 00803 ConstantExpr::getNeg(DivRHS)); 00804 00805 // X - X*C --> X * (1-C) 00806 ConstantInt *C2; 00807 if (dyn_castFoldableMul(Op1I, C2) == Op0) { 00808 Constant *CP1 = 00809 ConstantExpr::getSub(ConstantInt::get(I.getType(), 1), C2); 00810 return BinaryOperator::createMul(Op0, CP1); 00811 } 00812 } 00813 00814 00815 ConstantInt *C1; 00816 if (Value *X = dyn_castFoldableMul(Op0, C1)) { 00817 if (X == Op1) { // X*C - X --> X * (C-1) 00818 Constant *CP1 = ConstantExpr::getSub(C1, ConstantInt::get(I.getType(),1)); 00819 return BinaryOperator::createMul(Op1, CP1); 00820 } 00821 00822 ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 00823 if (X == dyn_castFoldableMul(Op1, C2)) 00824 return BinaryOperator::createMul(Op1, ConstantExpr::getSub(C1, C2)); 00825 } 00826 return 0; 00827 } 00828 00829 /// isSignBitCheck - Given an exploded setcc instruction, return true if it is 00830 /// really just returns true if the most significant (sign) bit is set. 00831 static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) { 00832 if (RHS->getType()->isSigned()) { 00833 // True if source is LHS < 0 or LHS <= -1 00834 return Opcode == Instruction::SetLT && RHS->isNullValue() || 00835 Opcode == Instruction::SetLE && RHS->isAllOnesValue(); 00836 } else { 00837 ConstantUInt *RHSC = cast<ConstantUInt>(RHS); 00838 // True if source is LHS > 127 or LHS >= 128, where the constants depend on 00839 // the size of the integer type. 00840 if (Opcode == Instruction::SetGE) 00841 return RHSC->getValue() == 1ULL<<(RHS->getType()->getPrimitiveSize()*8-1); 00842 if (Opcode == Instruction::SetGT) 00843 return RHSC->getValue() == 00844 (1ULL << (RHS->getType()->getPrimitiveSize()*8-1))-1; 00845 } 00846 return false; 00847 } 00848 00849 Instruction *InstCombiner::visitMul(BinaryOperator &I) { 00850 bool Changed = SimplifyCommutative(I); 00851 Value *Op0 = I.getOperand(0); 00852 00853 if (isa<UndefValue>(I.getOperand(1))) // undef * X -> 0 00854 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 00855 00856 // Simplify mul instructions with a constant RHS... 00857 if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) { 00858 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 00859 00860 // ((X << C1)*C2) == (X * (C2 << C1)) 00861 if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0)) 00862 if (SI->getOpcode() == Instruction::Shl) 00863 if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1))) 00864 return BinaryOperator::createMul(SI->getOperand(0), 00865 ConstantExpr::getShl(CI, ShOp)); 00866 00867 if (CI->isNullValue()) 00868 return ReplaceInstUsesWith(I, Op1); // X * 0 == 0 00869 if (CI->equalsInt(1)) // X * 1 == X 00870 return ReplaceInstUsesWith(I, Op0); 00871 if (CI->isAllOnesValue()) // X * -1 == 0 - X 00872 return BinaryOperator::createNeg(Op0, I.getName()); 00873 00874 int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue(); 00875 if (uint64_t C = Log2(Val)) // Replace X*(2^C) with X << C 00876 return new ShiftInst(Instruction::Shl, Op0, 00877 ConstantUInt::get(Type::UByteTy, C)); 00878 } else if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1)) { 00879 if (Op1F->isNullValue()) 00880 return ReplaceInstUsesWith(I, Op1); 00881 00882 // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 00883 // ANSI says we can drop signals, so we can do this anyway." (from GCC) 00884 if (Op1F->getValue() == 1.0) 00885 return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0' 00886 } 00887 00888 // Try to fold constant mul into select arguments. 00889 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 00890 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 00891 return R; 00892 00893 if (isa<PHINode>(Op0)) 00894 if (Instruction *NV = FoldOpIntoPhi(I)) 00895 return NV; 00896 } 00897 00898 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 00899 if (Value *Op1v = dyn_castNegVal(I.getOperand(1))) 00900 return BinaryOperator::createMul(Op0v, Op1v); 00901 00902 // If one of the operands of the multiply is a cast from a boolean value, then 00903 // we know the bool is either zero or one, so this is a 'masking' multiply. 00904 // See if we can simplify things based on how the boolean was originally 00905 // formed. 00906 CastInst *BoolCast = 0; 00907 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(0))) 00908 if (CI->getOperand(0)->getType() == Type::BoolTy) 00909 BoolCast = CI; 00910 if (!BoolCast) 00911 if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(1))) 00912 if (CI->getOperand(0)->getType() == Type::BoolTy) 00913 BoolCast = CI; 00914 if (BoolCast) { 00915 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BoolCast->getOperand(0))) { 00916 Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1); 00917 const Type *SCOpTy = SCIOp0->getType(); 00918 00919 // If the setcc is true iff the sign bit of X is set, then convert this 00920 // multiply into a shift/and combination. 00921 if (isa<ConstantInt>(SCIOp1) && 00922 isSignBitCheck(SCI->getOpcode(), SCIOp0, cast<ConstantInt>(SCIOp1))) { 00923 // Shift the X value right to turn it into "all signbits". 00924 Constant *Amt = ConstantUInt::get(Type::UByteTy, 00925 SCOpTy->getPrimitiveSize()*8-1); 00926 if (SCIOp0->getType()->isUnsigned()) { 00927 const Type *NewTy = SCIOp0->getType()->getSignedVersion(); 00928 SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy, 00929 SCIOp0->getName()), I); 00930 } 00931 00932 Value *V = 00933 InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt, 00934 BoolCast->getOperand(0)->getName()+ 00935 ".mask"), I); 00936 00937 // If the multiply type is not the same as the source type, sign extend 00938 // or truncate to the multiply type. 00939 if (I.getType() != V->getType()) 00940 V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I); 00941 00942 Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0; 00943 return BinaryOperator::createAnd(V, OtherOp); 00944 } 00945 } 00946 } 00947 00948 return Changed ? &I : 0; 00949 } 00950 00951 Instruction *InstCombiner::visitDiv(BinaryOperator &I) { 00952 if (isa<UndefValue>(I.getOperand(0))) // undef / X -> 0 00953 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 00954 if (isa<UndefValue>(I.getOperand(1))) 00955 return ReplaceInstUsesWith(I, I.getOperand(1)); // X / undef -> undef 00956 00957 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) { 00958 // div X, 1 == X 00959 if (RHS->equalsInt(1)) 00960 return ReplaceInstUsesWith(I, I.getOperand(0)); 00961 00962 // div X, -1 == -X 00963 if (RHS->isAllOnesValue()) 00964 return BinaryOperator::createNeg(I.getOperand(0)); 00965 00966 if (Instruction *LHS = dyn_cast<Instruction>(I.getOperand(0))) 00967 if (LHS->getOpcode() == Instruction::Div) 00968 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 00969 // (X / C1) / C2 -> X / (C1*C2) 00970 return BinaryOperator::createDiv(LHS->getOperand(0), 00971 ConstantExpr::getMul(RHS, LHSRHS)); 00972 } 00973 00974 // Check to see if this is an unsigned division with an exact power of 2, 00975 // if so, convert to a right shift. 00976 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS)) 00977 if (uint64_t Val = C->getValue()) // Don't break X / 0 00978 if (uint64_t C = Log2(Val)) 00979 return new ShiftInst(Instruction::Shr, I.getOperand(0), 00980 ConstantUInt::get(Type::UByteTy, C)); 00981 00982 // -X/C -> X/-C 00983 if (RHS->getType()->isSigned()) 00984 if (Value *LHSNeg = dyn_castNegVal(I.getOperand(0))) 00985 return BinaryOperator::createDiv(LHSNeg, ConstantExpr::getNeg(RHS)); 00986 00987 if (isa<PHINode>(I.getOperand(0)) && !RHS->isNullValue()) 00988 if (Instruction *NV = FoldOpIntoPhi(I)) 00989 return NV; 00990 } 00991 00992 // 0 / X == 0, we don't need to preserve faults! 00993 if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0))) 00994 if (LHS->equalsInt(0)) 00995 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 00996 00997 return 0; 00998 } 00999 01000 01001 Instruction *InstCombiner::visitRem(BinaryOperator &I) { 01002 if (I.getType()->isSigned()) 01003 if (Value *RHSNeg = dyn_castNegVal(I.getOperand(1))) 01004 if (!isa<ConstantSInt>(RHSNeg) || 01005 cast<ConstantSInt>(RHSNeg)->getValue() > 0) { 01006 // X % -Y -> X % Y 01007 AddUsesToWorkList(I); 01008 I.setOperand(1, RHSNeg); 01009 return &I; 01010 } 01011 01012 if (isa<UndefValue>(I.getOperand(0))) // undef % X -> 0 01013 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01014 if (isa<UndefValue>(I.getOperand(1))) 01015 return ReplaceInstUsesWith(I, I.getOperand(1)); // X % undef -> undef 01016 01017 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) { 01018 if (RHS->equalsInt(1)) // X % 1 == 0 01019 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01020 01021 // Check to see if this is an unsigned remainder with an exact power of 2, 01022 // if so, convert to a bitwise and. 01023 if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS)) 01024 if (uint64_t Val = C->getValue()) // Don't break X % 0 (divide by zero) 01025 if (!(Val & (Val-1))) // Power of 2 01026 return BinaryOperator::createAnd(I.getOperand(0), 01027 ConstantUInt::get(I.getType(), Val-1)); 01028 if (isa<PHINode>(I.getOperand(0)) && !RHS->isNullValue()) 01029 if (Instruction *NV = FoldOpIntoPhi(I)) 01030 return NV; 01031 } 01032 01033 // 0 % X == 0, we don't need to preserve faults! 01034 if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0))) 01035 if (LHS->equalsInt(0)) 01036 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01037 01038 return 0; 01039 } 01040 01041 // isMaxValueMinusOne - return true if this is Max-1 01042 static bool isMaxValueMinusOne(const ConstantInt *C) { 01043 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) { 01044 // Calculate -1 casted to the right type... 01045 unsigned TypeBits = C->getType()->getPrimitiveSize()*8; 01046 uint64_t Val = ~0ULL; // All ones 01047 Val >>= 64-TypeBits; // Shift out unwanted 1 bits... 01048 return CU->getValue() == Val-1; 01049 } 01050 01051 const ConstantSInt *CS = cast<ConstantSInt>(C); 01052 01053 // Calculate 0111111111..11111 01054 unsigned TypeBits = C->getType()->getPrimitiveSize()*8; 01055 int64_t Val = INT64_MAX; // All ones 01056 Val >>= 64-TypeBits; // Shift out unwanted 1 bits... 01057 return CS->getValue() == Val-1; 01058 } 01059 01060 // isMinValuePlusOne - return true if this is Min+1 01061 static bool isMinValuePlusOne(const ConstantInt *C) { 01062 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) 01063 return CU->getValue() == 1; 01064 01065 const ConstantSInt *CS = cast<ConstantSInt>(C); 01066 01067 // Calculate 1111111111000000000000 01068 unsigned TypeBits = C->getType()->getPrimitiveSize()*8; 01069 int64_t Val = -1; // All ones 01070 Val <<= TypeBits-1; // Shift over to the right spot 01071 return CS->getValue() == Val+1; 01072 } 01073 01074 // isOneBitSet - Return true if there is exactly one bit set in the specified 01075 // constant. 01076 static bool isOneBitSet(const ConstantInt *CI) { 01077 uint64_t V = CI->getRawValue(); 01078 return V && (V & (V-1)) == 0; 01079 } 01080 01081 #if 0 // Currently unused 01082 // isLowOnes - Return true if the constant is of the form 0+1+. 01083 static bool isLowOnes(const ConstantInt *CI) { 01084 uint64_t V = CI->getRawValue(); 01085 01086 // There won't be bits set in parts that the type doesn't contain. 01087 V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue(); 01088 01089 uint64_t U = V+1; // If it is low ones, this should be a power of two. 01090 return U && V && (U & V) == 0; 01091 } 01092 #endif 01093 01094 // isHighOnes - Return true if the constant is of the form 1+0+. 01095 // This is the same as lowones(~X). 01096 static bool isHighOnes(const ConstantInt *CI) { 01097 uint64_t V = ~CI->getRawValue(); 01098 01099 // There won't be bits set in parts that the type doesn't contain. 01100 V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue(); 01101 01102 uint64_t U = V+1; // If it is low ones, this should be a power of two. 01103 return U && V && (U & V) == 0; 01104 } 01105 01106 01107 /// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits 01108 /// are carefully arranged to allow folding of expressions such as: 01109 /// 01110 /// (A < B) | (A > B) --> (A != B) 01111 /// 01112 /// Bit value '4' represents that the comparison is true if A > B, bit value '2' 01113 /// represents that the comparison is true if A == B, and bit value '1' is true 01114 /// if A < B. 01115 /// 01116 static unsigned getSetCondCode(const SetCondInst *SCI) { 01117 switch (SCI->getOpcode()) { 01118 // False -> 0 01119 case Instruction::SetGT: return 1; 01120 case Instruction::SetEQ: return 2; 01121 case Instruction::SetGE: return 3; 01122 case Instruction::SetLT: return 4; 01123 case Instruction::SetNE: return 5; 01124 case Instruction::SetLE: return 6; 01125 // True -> 7 01126 default: 01127 assert(0 && "Invalid SetCC opcode!"); 01128 return 0; 01129 } 01130 } 01131 01132 /// getSetCCValue - This is the complement of getSetCondCode, which turns an 01133 /// opcode and two operands into either a constant true or false, or a brand new 01134 /// SetCC instruction. 01135 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) { 01136 switch (Opcode) { 01137 case 0: return ConstantBool::False; 01138 case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS); 01139 case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS); 01140 case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS); 01141 case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS); 01142 case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS); 01143 case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS); 01144 case 7: return ConstantBool::True; 01145 default: assert(0 && "Illegal SetCCCode!"); return 0; 01146 } 01147 } 01148 01149 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) 01150 struct FoldSetCCLogical { 01151 InstCombiner &IC; 01152 Value *LHS, *RHS; 01153 FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI) 01154 : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {} 01155 bool shouldApply(Value *V) const { 01156 if (SetCondInst *SCI = dyn_cast<SetCondInst>(V)) 01157 return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS || 01158 SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS); 01159 return false; 01160 } 01161 Instruction *apply(BinaryOperator &Log) const { 01162 SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0)); 01163 if (SCI->getOperand(0) != LHS) { 01164 assert(SCI->getOperand(1) == LHS); 01165 SCI->swapOperands(); // Swap the LHS and RHS of the SetCC 01166 } 01167 01168 unsigned LHSCode = getSetCondCode(SCI); 01169 unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1))); 01170 unsigned Code; 01171 switch (Log.getOpcode()) { 01172 case Instruction::And: Code = LHSCode & RHSCode; break; 01173 case Instruction::Or: Code = LHSCode | RHSCode; break; 01174 case Instruction::Xor: Code = LHSCode ^ RHSCode; break; 01175 default: assert(0 && "Illegal logical opcode!"); return 0; 01176 } 01177 01178 Value *RV = getSetCCValue(Code, LHS, RHS); 01179 if (Instruction *I = dyn_cast<Instruction>(RV)) 01180 return I; 01181 // Otherwise, it's a constant boolean value... 01182 return IC.ReplaceInstUsesWith(Log, RV); 01183 } 01184 }; 01185 01186 01187 // OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where 01188 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is 01189 // guaranteed to be either a shift instruction or a binary operator. 01190 Instruction *InstCombiner::OptAndOp(Instruction *Op, 01191 ConstantIntegral *OpRHS, 01192 ConstantIntegral *AndRHS, 01193 BinaryOperator &TheAnd) { 01194 Value *X = Op->getOperand(0); 01195 Constant *Together = 0; 01196 if (!isa<ShiftInst>(Op)) 01197 Together = ConstantExpr::getAnd(AndRHS, OpRHS); 01198 01199 switch (Op->getOpcode()) { 01200 case Instruction::Xor: 01201 if (Together->isNullValue()) { 01202 // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0 01203 return BinaryOperator::createAnd(X, AndRHS); 01204 } else if (Op->hasOneUse()) { 01205 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) 01206 std::string OpName = Op->getName(); Op->setName(""); 01207 Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName); 01208 InsertNewInstBefore(And, TheAnd); 01209 return BinaryOperator::createXor(And, Together); 01210 } 01211 break; 01212 case Instruction::Or: 01213 // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0 01214 if (Together->isNullValue()) 01215 return BinaryOperator::createAnd(X, AndRHS); 01216 else { 01217 if (Together == AndRHS) // (X | C) & C --> C 01218 return ReplaceInstUsesWith(TheAnd, AndRHS); 01219 01220 if (Op->hasOneUse() && Together != OpRHS) { 01221 // (X | C1) & C2 --> (X | (C1&C2)) & C2 01222 std::string Op0Name = Op->getName(); Op->setName(""); 01223 Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name); 01224 InsertNewInstBefore(Or, TheAnd); 01225 return BinaryOperator::createAnd(Or, AndRHS); 01226 } 01227 } 01228 break; 01229 case Instruction::Add: 01230 if (Op->hasOneUse()) { 01231 // Adding a one to a single bit bit-field should be turned into an XOR 01232 // of the bit. First thing to check is to see if this AND is with a 01233 // single bit constant. 01234 uint64_t AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue(); 01235 01236 // Clear bits that are not part of the constant. 01237 AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1; 01238 01239 // If there is only one bit set... 01240 if (isOneBitSet(cast<ConstantInt>(AndRHS))) { 01241 // Ok, at this point, we know that we are masking the result of the 01242 // ADD down to exactly one bit. If the constant we are adding has 01243 // no bits set below this bit, then we can eliminate the ADD. 01244 uint64_t AddRHS = cast<ConstantInt>(OpRHS)->getRawValue(); 01245 01246 // Check to see if any bits below the one bit set in AndRHSV are set. 01247 if ((AddRHS & (AndRHSV-1)) == 0) { 01248 // If not, the only thing that can effect the output of the AND is 01249 // the bit specified by AndRHSV. If that bit is set, the effect of 01250 // the XOR is to toggle the bit. If it is clear, then the ADD has 01251 // no effect. 01252 if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop 01253 TheAnd.setOperand(0, X); 01254 return &TheAnd; 01255 } else { 01256 std::string Name = Op->getName(); Op->setName(""); 01257 // Pull the XOR out of the AND. 01258 Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS, Name); 01259 InsertNewInstBefore(NewAnd, TheAnd); 01260 return BinaryOperator::createXor(NewAnd, AndRHS); 01261 } 01262 } 01263 } 01264 } 01265 break; 01266 01267 case Instruction::Shl: { 01268 // We know that the AND will not produce any of the bits shifted in, so if 01269 // the anded constant includes them, clear them now! 01270 // 01271 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); 01272 Constant *ShlMask = ConstantExpr::getShl(AllOne, OpRHS); 01273 Constant *CI = ConstantExpr::getAnd(AndRHS, ShlMask); 01274 01275 if (CI == ShlMask) { // Masking out bits that the shift already masks 01276 return ReplaceInstUsesWith(TheAnd, Op); // No need for the and. 01277 } else if (CI != AndRHS) { // Reducing bits set in and. 01278 TheAnd.setOperand(1, CI); 01279 return &TheAnd; 01280 } 01281 break; 01282 } 01283 case Instruction::Shr: 01284 // We know that the AND will not produce any of the bits shifted in, so if 01285 // the anded constant includes them, clear them now! This only applies to 01286 // unsigned shifts, because a signed shr may bring in set bits! 01287 // 01288 if (AndRHS->getType()->isUnsigned()) { 01289 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); 01290 Constant *ShrMask = ConstantExpr::getShr(AllOne, OpRHS); 01291 Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask); 01292 01293 if (CI == ShrMask) { // Masking out bits that the shift already masks. 01294 return ReplaceInstUsesWith(TheAnd, Op); 01295 } else if (CI != AndRHS) { 01296 TheAnd.setOperand(1, CI); // Reduce bits set in and cst. 01297 return &TheAnd; 01298 } 01299 } else { // Signed shr. 01300 // See if this is shifting in some sign extension, then masking it out 01301 // with an and. 01302 if (Op->hasOneUse()) { 01303 Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType()); 01304 Constant *ShrMask = ConstantExpr::getUShr(AllOne, OpRHS); 01305 Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask); 01306 if (CI == AndRHS) { // Masking out bits shifted in. 01307 // Make the argument unsigned. 01308 Value *ShVal = Op->getOperand(0); 01309 ShVal = InsertCastBefore(ShVal, 01310 ShVal->getType()->getUnsignedVersion(), 01311 TheAnd); 01312 ShVal = InsertNewInstBefore(new ShiftInst(Instruction::Shr, ShVal, 01313 OpRHS, Op->getName()), 01314 TheAnd); 01315 Value *AndRHS2 = ConstantExpr::getCast(AndRHS, ShVal->getType()); 01316 ShVal = InsertNewInstBefore(BinaryOperator::createAnd(ShVal, AndRHS2, 01317 TheAnd.getName()), 01318 TheAnd); 01319 return new CastInst(ShVal, Op->getType()); 01320 } 01321 } 01322 } 01323 break; 01324 } 01325 return 0; 01326 } 01327 01328 01329 /// InsertRangeTest - Emit a computation of: (V >= Lo && V < Hi) if Inside is 01330 /// true, otherwise (V < Lo || V >= Hi). In pratice, we emit the more efficient 01331 /// (V-Lo) <u Hi-Lo. This method expects that Lo <= Hi. IB is the location to 01332 /// insert new instructions. 01333 Instruction *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, 01334 bool Inside, Instruction &IB) { 01335 assert(cast<ConstantBool>(ConstantExpr::getSetLE(Lo, Hi))->getValue() && 01336 "Lo is not <= Hi in range emission code!"); 01337 if (Inside) { 01338 if (Lo == Hi) // Trivially false. 01339 return new SetCondInst(Instruction::SetNE, V, V); 01340 if (cast<ConstantIntegral>(Lo)->isMinValue()) 01341 return new SetCondInst(Instruction::SetLT, V, Hi); 01342 01343 Constant *AddCST = ConstantExpr::getNeg(Lo); 01344 Instruction *Add = BinaryOperator::createAdd(V, AddCST,V->getName()+".off"); 01345 InsertNewInstBefore(Add, IB); 01346 // Convert to unsigned for the comparison. 01347 const Type *UnsType = Add->getType()->getUnsignedVersion(); 01348 Value *OffsetVal = InsertCastBefore(Add, UnsType, IB); 01349 AddCST = ConstantExpr::getAdd(AddCST, Hi); 01350 AddCST = ConstantExpr::getCast(AddCST, UnsType); 01351 return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST); 01352 } 01353 01354 if (Lo == Hi) // Trivially true. 01355 return new SetCondInst(Instruction::SetEQ, V, V); 01356 01357 Hi = SubOne(cast<ConstantInt>(Hi)); 01358 if (cast<ConstantIntegral>(Lo)->isMinValue()) // V < 0 || V >= Hi ->'V > Hi-1' 01359 return new SetCondInst(Instruction::SetGT, V, Hi); 01360 01361 // Emit X-Lo > Hi-Lo-1 01362 Constant *AddCST = ConstantExpr::getNeg(Lo); 01363 Instruction *Add = BinaryOperator::createAdd(V, AddCST, V->getName()+".off"); 01364 InsertNewInstBefore(Add, IB); 01365 // Convert to unsigned for the comparison. 01366 const Type *UnsType = Add->getType()->getUnsignedVersion(); 01367 Value *OffsetVal = InsertCastBefore(Add, UnsType, IB); 01368 AddCST = ConstantExpr::getAdd(AddCST, Hi); 01369 AddCST = ConstantExpr::getCast(AddCST, UnsType); 01370 return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST); 01371 } 01372 01373 01374 Instruction *InstCombiner::visitAnd(BinaryOperator &I) { 01375 bool Changed = SimplifyCommutative(I); 01376 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 01377 01378 if (isa<UndefValue>(Op1)) // X & undef -> 0 01379 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01380 01381 // and X, X = X and X, 0 == 0 01382 if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType())) 01383 return ReplaceInstUsesWith(I, Op1); 01384 01385 // and X, -1 == X 01386 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) { 01387 if (RHS->isAllOnesValue()) 01388 return ReplaceInstUsesWith(I, Op0); 01389 01390 // Optimize a variety of ((val OP C1) & C2) combinations... 01391 if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) { 01392 Instruction *Op0I = cast<Instruction>(Op0); 01393 Value *X = Op0I->getOperand(0); 01394 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) 01395 if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I)) 01396 return Res; 01397 } 01398 01399 // Try to fold constant and into select arguments. 01400 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 01401 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 01402 return R; 01403 if (isa<PHINode>(Op0)) 01404 if (Instruction *NV = FoldOpIntoPhi(I)) 01405 return NV; 01406 } 01407 01408 Value *Op0NotVal = dyn_castNotVal(Op0); 01409 Value *Op1NotVal = dyn_castNotVal(Op1); 01410 01411 if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0 01412 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01413 01414 // (~A & ~B) == (~(A | B)) - De Morgan's Law 01415 if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) { 01416 Instruction *Or = BinaryOperator::createOr(Op0NotVal, Op1NotVal, 01417 I.getName()+".demorgan"); 01418 InsertNewInstBefore(Or, I); 01419 return BinaryOperator::createNot(Or); 01420 } 01421 01422 if (SetCondInst *RHS = dyn_cast<SetCondInst>(Op1)) { 01423 // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B) 01424 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) 01425 return R; 01426 01427 Value *LHSVal, *RHSVal; 01428 ConstantInt *LHSCst, *RHSCst; 01429 Instruction::BinaryOps LHSCC, RHSCC; 01430 if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst)))) 01431 if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst)))) 01432 if (LHSVal == RHSVal && // Found (X setcc C1) & (X setcc C2) 01433 // Set[GL]E X, CST is folded to Set[GL]T elsewhere. 01434 LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE && 01435 RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) { 01436 // Ensure that the larger constant is on the RHS. 01437 Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst); 01438 SetCondInst *LHS = cast<SetCondInst>(Op0); 01439 if (cast<ConstantBool>(Cmp)->getValue()) { 01440 std::swap(LHS, RHS); 01441 std::swap(LHSCst, RHSCst); 01442 std::swap(LHSCC, RHSCC); 01443 } 01444 01445 // At this point, we know we have have two setcc instructions 01446 // comparing a value against two constants and and'ing the result 01447 // together. Because of the above check, we know that we only have 01448 // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the 01449 // FoldSetCCLogical check above), that the two constants are not 01450 // equal. 01451 assert(LHSCst != RHSCst && "Compares not folded above?"); 01452 01453 switch (LHSCC) { 01454 default: assert(0 && "Unknown integer condition code!"); 01455 case Instruction::SetEQ: 01456 switch (RHSCC) { 01457 default: assert(0 && "Unknown integer condition code!"); 01458 case Instruction::SetEQ: // (X == 13 & X == 15) -> false 01459 case Instruction::SetGT: // (X == 13 & X > 15) -> false 01460 return ReplaceInstUsesWith(I, ConstantBool::False); 01461 case Instruction::SetNE: // (X == 13 & X != 15) -> X == 13 01462 case Instruction::SetLT: // (X == 13 & X < 15) -> X == 13 01463 return ReplaceInstUsesWith(I, LHS); 01464 } 01465 case Instruction::SetNE: 01466 switch (RHSCC) { 01467 default: assert(0 && "Unknown integer condition code!"); 01468 case Instruction::SetLT: 01469 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X < 14) -> X < 13 01470 return new SetCondInst(Instruction::SetLT, LHSVal, LHSCst); 01471 break; // (X != 13 & X < 15) -> no change 01472 case Instruction::SetEQ: // (X != 13 & X == 15) -> X == 15 01473 case Instruction::SetGT: // (X != 13 & X > 15) -> X > 15 01474 return ReplaceInstUsesWith(I, RHS); 01475 case Instruction::SetNE: 01476 if (LHSCst == SubOne(RHSCst)) {// (X != 13 & X != 14) -> X-13 >u 1 01477 Constant *AddCST = ConstantExpr::getNeg(LHSCst); 01478 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST, 01479 LHSVal->getName()+".off"); 01480 InsertNewInstBefore(Add, I); 01481 const Type *UnsType = Add->getType()->getUnsignedVersion(); 01482 Value *OffsetVal = InsertCastBefore(Add, UnsType, I); 01483 AddCST = ConstantExpr::getSub(RHSCst, LHSCst); 01484 AddCST = ConstantExpr::getCast(AddCST, UnsType); 01485 return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST); 01486 } 01487 break; // (X != 13 & X != 15) -> no change 01488 } 01489 break; 01490 case Instruction::SetLT: 01491 switch (RHSCC) { 01492 default: assert(0 && "Unknown integer condition code!"); 01493 case Instruction::SetEQ: // (X < 13 & X == 15) -> false 01494 case Instruction::SetGT: // (X < 13 & X > 15) -> false 01495 return ReplaceInstUsesWith(I, ConstantBool::False); 01496 case Instruction::SetNE: // (X < 13 & X != 15) -> X < 13 01497 case Instruction::SetLT: // (X < 13 & X < 15) -> X < 13 01498 return ReplaceInstUsesWith(I, LHS); 01499 } 01500 case Instruction::SetGT: 01501 switch (RHSCC) { 01502 default: assert(0 && "Unknown integer condition code!"); 01503 case Instruction::SetEQ: // (X > 13 & X == 15) -> X > 13 01504 return ReplaceInstUsesWith(I, LHS); 01505 case Instruction::SetGT: // (X > 13 & X > 15) -> X > 15 01506 return ReplaceInstUsesWith(I, RHS); 01507 case Instruction::SetNE: 01508 if (RHSCst == AddOne(LHSCst)) // (X > 13 & X != 14) -> X > 14 01509 return new SetCondInst(Instruction::SetGT, LHSVal, RHSCst); 01510 break; // (X > 13 & X != 15) -> no change 01511 case Instruction::SetLT: // (X > 13 & X < 15) -> (X-14) <u 1 01512 return InsertRangeTest(LHSVal, AddOne(LHSCst), RHSCst, true, I); 01513 } 01514 } 01515 } 01516 } 01517 01518 return Changed ? &I : 0; 01519 } 01520 01521 Instruction *InstCombiner::visitOr(BinaryOperator &I) { 01522 bool Changed = SimplifyCommutative(I); 01523 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 01524 01525 if (isa<UndefValue>(Op1)) 01526 return ReplaceInstUsesWith(I, // X | undef -> -1 01527 ConstantIntegral::getAllOnesValue(I.getType())); 01528 01529 // or X, X = X or X, 0 == X 01530 if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType())) 01531 return ReplaceInstUsesWith(I, Op0); 01532 01533 // or X, -1 == -1 01534 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) { 01535 if (RHS->isAllOnesValue()) 01536 return ReplaceInstUsesWith(I, Op1); 01537 01538 ConstantInt *C1; Value *X; 01539 // (X & C1) | C2 --> (X | C2) & (C1|C2) 01540 if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) { 01541 std::string Op0Name = Op0->getName(); Op0->setName(""); 01542 Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name); 01543 InsertNewInstBefore(Or, I); 01544 return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, C1)); 01545 } 01546 01547 // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) 01548 if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) { 01549 std::string Op0Name = Op0->getName(); Op0->setName(""); 01550 Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name); 01551 InsertNewInstBefore(Or, I); 01552 return BinaryOperator::createXor(Or, 01553 ConstantExpr::getAnd(C1, ConstantExpr::getNot(RHS))); 01554 } 01555 01556 // Try to fold constant and into select arguments. 01557 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 01558 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 01559 return R; 01560 if (isa<PHINode>(Op0)) 01561 if (Instruction *NV = FoldOpIntoPhi(I)) 01562 return NV; 01563 } 01564 01565 // (A & C1)|(A & C2) == A & (C1|C2) 01566 Value *A, *B; ConstantInt *C1, *C2; 01567 if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) && 01568 match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) && A == B) 01569 return BinaryOperator::createAnd(A, ConstantExpr::getOr(C1, C2)); 01570 01571 if (match(Op0, m_Not(m_Value(A)))) { // ~A | Op1 01572 if (A == Op1) // ~A | A == -1 01573 return ReplaceInstUsesWith(I, 01574 ConstantIntegral::getAllOnesValue(I.getType())); 01575 } else { 01576 A = 0; 01577 } 01578 01579 if (match(Op1, m_Not(m_Value(B)))) { // Op0 | ~B 01580 if (Op0 == B) 01581 return ReplaceInstUsesWith(I, 01582 ConstantIntegral::getAllOnesValue(I.getType())); 01583 01584 // (~A | ~B) == (~(A & B)) - De Morgan's Law 01585 if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) { 01586 Value *And = InsertNewInstBefore(BinaryOperator::createAnd(A, B, 01587 I.getName()+".demorgan"), I); 01588 return BinaryOperator::createNot(And); 01589 } 01590 } 01591 01592 // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B) 01593 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1))) { 01594 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) 01595 return R; 01596 01597 Value *LHSVal, *RHSVal; 01598 ConstantInt *LHSCst, *RHSCst; 01599 Instruction::BinaryOps LHSCC, RHSCC; 01600 if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst)))) 01601 if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst)))) 01602 if (LHSVal == RHSVal && // Found (X setcc C1) | (X setcc C2) 01603 // Set[GL]E X, CST is folded to Set[GL]T elsewhere. 01604 LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE && 01605 RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) { 01606 // Ensure that the larger constant is on the RHS. 01607 Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst); 01608 SetCondInst *LHS = cast<SetCondInst>(Op0); 01609 if (cast<ConstantBool>(Cmp)->getValue()) { 01610 std::swap(LHS, RHS); 01611 std::swap(LHSCst, RHSCst); 01612 std::swap(LHSCC, RHSCC); 01613 } 01614 01615 // At this point, we know we have have two setcc instructions 01616 // comparing a value against two constants and or'ing the result 01617 // together. Because of the above check, we know that we only have 01618 // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the 01619 // FoldSetCCLogical check above), that the two constants are not 01620 // equal. 01621 assert(LHSCst != RHSCst && "Compares not folded above?"); 01622 01623 switch (LHSCC) { 01624 default: assert(0 && "Unknown integer condition code!"); 01625 case Instruction::SetEQ: 01626 switch (RHSCC) { 01627 default: assert(0 && "Unknown integer condition code!"); 01628 case Instruction::SetEQ: 01629 if (LHSCst == SubOne(RHSCst)) {// (X == 13 | X == 14) -> X-13 <u 2 01630 Constant *AddCST = ConstantExpr::getNeg(LHSCst); 01631 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST, 01632 LHSVal->getName()+".off"); 01633 InsertNewInstBefore(Add, I); 01634 const Type *UnsType = Add->getType()->getUnsignedVersion(); 01635 Value *OffsetVal = InsertCastBefore(Add, UnsType, I); 01636 AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst); 01637 AddCST = ConstantExpr::getCast(AddCST, UnsType); 01638 return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST); 01639 } 01640 break; // (X == 13 | X == 15) -> no change 01641 01642 case Instruction::SetGT: 01643 if (LHSCst == SubOne(RHSCst)) // (X == 13 | X > 14) -> X > 13 01644 return new SetCondInst(Instruction::SetGT, LHSVal, LHSCst); 01645 break; // (X == 13 | X > 15) -> no change 01646 case Instruction::SetNE: // (X == 13 | X != 15) -> X != 15 01647 case Instruction::SetLT: // (X == 13 | X < 15) -> X < 15 01648 return ReplaceInstUsesWith(I, RHS); 01649 } 01650 break; 01651 case Instruction::SetNE: 01652 switch (RHSCC) { 01653 default: assert(0 && "Unknown integer condition code!"); 01654 case Instruction::SetLT: // (X != 13 | X < 15) -> X < 15 01655 return ReplaceInstUsesWith(I, RHS); 01656 case Instruction::SetEQ: // (X != 13 | X == 15) -> X != 13 01657 case Instruction::SetGT: // (X != 13 | X > 15) -> X != 13 01658 return ReplaceInstUsesWith(I, LHS); 01659 case Instruction::SetNE: // (X != 13 | X != 15) -> true 01660 return ReplaceInstUsesWith(I, ConstantBool::True); 01661 } 01662 break; 01663 case Instruction::SetLT: 01664 switch (RHSCC) { 01665 default: assert(0 && "Unknown integer condition code!"); 01666 case Instruction::SetEQ: // (X < 13 | X == 14) -> no change 01667 break; 01668 case Instruction::SetGT: // (X < 13 | X > 15) -> (X-13) > 2 01669 return InsertRangeTest(LHSVal, LHSCst, AddOne(RHSCst), false, I); 01670 case Instruction::SetNE: // (X < 13 | X != 15) -> X != 15 01671 case Instruction::SetLT: // (X < 13 | X < 15) -> X < 15 01672 return ReplaceInstUsesWith(I, RHS); 01673 } 01674 break; 01675 case Instruction::SetGT: 01676 switch (RHSCC) { 01677 default: assert(0 && "Unknown integer condition code!"); 01678 case Instruction::SetEQ: // (X > 13 | X == 15) -> X > 13 01679 case Instruction::SetGT: // (X > 13 | X > 15) -> X > 13 01680 return ReplaceInstUsesWith(I, LHS); 01681 case Instruction::SetNE: // (X > 13 | X != 15) -> true 01682 case Instruction::SetLT: // (X > 13 | X < 15) -> true 01683 return ReplaceInstUsesWith(I, ConstantBool::True); 01684 } 01685 } 01686 } 01687 } 01688 return Changed ? &I : 0; 01689 } 01690 01691 // XorSelf - Implements: X ^ X --> 0 01692 struct XorSelf { 01693 Value *RHS; 01694 XorSelf(Value *rhs) : RHS(rhs) {} 01695 bool shouldApply(Value *LHS) const { return LHS == RHS; } 01696 Instruction *apply(BinaryOperator &Xor) const { 01697 return &Xor; 01698 } 01699 }; 01700 01701 01702 Instruction *InstCombiner::visitXor(BinaryOperator &I) { 01703 bool Changed = SimplifyCommutative(I); 01704 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 01705 01706 if (isa<UndefValue>(Op1)) 01707 return ReplaceInstUsesWith(I, Op1); // X ^ undef -> undef 01708 01709 // xor X, X = 0, even if X is nested in a sequence of Xor's. 01710 if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) { 01711 assert(Result == &I && "AssociativeOpt didn't work?"); 01712 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 01713 } 01714 01715 if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) { 01716 // xor X, 0 == X 01717 if (RHS->isNullValue()) 01718 return ReplaceInstUsesWith(I, Op0); 01719 01720 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 01721 // xor (setcc A, B), true = not (setcc A, B) = setncc A, B 01722 if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I)) 01723 if (RHS == ConstantBool::True && SCI->hasOneUse()) 01724 return new SetCondInst(SCI->getInverseCondition(), 01725 SCI->getOperand(0), SCI->getOperand(1)); 01726 01727 // ~(c-X) == X-c-1 == X+(-c-1) 01728 if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue()) 01729 if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) { 01730 Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C); 01731 Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C, 01732 ConstantInt::get(I.getType(), 1)); 01733 return BinaryOperator::createAdd(Op0I->getOperand(1), ConstantRHS); 01734 } 01735 01736 // ~(~X & Y) --> (X | ~Y) 01737 if (Op0I->getOpcode() == Instruction::And && RHS->isAllOnesValue()) { 01738 if (dyn_castNotVal(Op0I->getOperand(1))) Op0I->swapOperands(); 01739 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) { 01740 Instruction *NotY = 01741 BinaryOperator::createNot(Op0I->getOperand(1), 01742 Op0I->getOperand(1)->getName()+".not"); 01743 InsertNewInstBefore(NotY, I); 01744 return BinaryOperator::createOr(Op0NotVal, NotY); 01745 } 01746 } 01747 01748 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) 01749 switch (Op0I->getOpcode()) { 01750 case Instruction::Add: 01751 // ~(X-c) --> (-c-1)-X 01752 if (RHS->isAllOnesValue()) { 01753 Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI); 01754 return BinaryOperator::createSub( 01755 ConstantExpr::getSub(NegOp0CI, 01756 ConstantInt::get(I.getType(), 1)), 01757 Op0I->getOperand(0)); 01758 } 01759 break; 01760 case Instruction::And: 01761 // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0 01762 if (ConstantExpr::getAnd(RHS, Op0CI)->isNullValue()) 01763 return BinaryOperator::createOr(Op0, RHS); 01764 break; 01765 case Instruction::Or: 01766 // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 01767 if (ConstantExpr::getAnd(RHS, Op0CI) == RHS) 01768 return BinaryOperator::createAnd(Op0, ConstantExpr::getNot(RHS)); 01769 break; 01770 default: break; 01771 } 01772 } 01773 01774 // Try to fold constant and into select arguments. 01775 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 01776 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 01777 return R; 01778 if (isa<PHINode>(Op0)) 01779 if (Instruction *NV = FoldOpIntoPhi(I)) 01780 return NV; 01781 } 01782 01783 if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1 01784 if (X == Op1) 01785 return ReplaceInstUsesWith(I, 01786 ConstantIntegral::getAllOnesValue(I.getType())); 01787 01788 if (Value *X = dyn_castNotVal(Op1)) // A ^ ~A == -1 01789 if (X == Op0) 01790 return ReplaceInstUsesWith(I, 01791 ConstantIntegral::getAllOnesValue(I.getType())); 01792 01793 if (Instruction *Op1I = dyn_cast<Instruction>(Op1)) 01794 if (Op1I->getOpcode() == Instruction::Or) { 01795 if (Op1I->getOperand(0) == Op0) { // B^(B|A) == (A|B)^B 01796 cast<BinaryOperator>(Op1I)->swapOperands(); 01797 I.swapOperands(); 01798 std::swap(Op0, Op1); 01799 } else if (Op1I->getOperand(1) == Op0) { // B^(A|B) == (A|B)^B 01800 I.swapOperands(); 01801 std::swap(Op0, Op1); 01802 } 01803 } else if (Op1I->getOpcode() == Instruction::Xor) { 01804 if (Op0 == Op1I->getOperand(0)) // A^(A^B) == B 01805 return ReplaceInstUsesWith(I, Op1I->getOperand(1)); 01806 else if (Op0 == Op1I->getOperand(1)) // A^(B^A) == B 01807 return ReplaceInstUsesWith(I, Op1I->getOperand(0)); 01808 } 01809 01810 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) 01811 if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) { 01812 if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B 01813 cast<BinaryOperator>(Op0I)->swapOperands(); 01814 if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B 01815 Value *NotB = InsertNewInstBefore(BinaryOperator::createNot(Op1, 01816 Op1->getName()+".not"), I); 01817 return BinaryOperator::createAnd(Op0I->getOperand(0), NotB); 01818 } 01819 } else if (Op0I->getOpcode() == Instruction::Xor) { 01820 if (Op1 == Op0I->getOperand(0)) // (A^B)^A == B 01821 return ReplaceInstUsesWith(I, Op0I->getOperand(1)); 01822 else if (Op1 == Op0I->getOperand(1)) // (B^A)^A == B 01823 return ReplaceInstUsesWith(I, Op0I->getOperand(0)); 01824 } 01825 01826 // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 01827 Value *A, *B; ConstantInt *C1, *C2; 01828 if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) && 01829 match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) && 01830 ConstantExpr::getAnd(C1, C2)->isNullValue()) 01831 return BinaryOperator::createOr(Op0, Op1); 01832 01833 // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B) 01834 if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1))) 01835 if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS))) 01836 return R; 01837 01838 return Changed ? &I : 0; 01839 } 01840 01841 /// MulWithOverflow - Compute Result = In1*In2, returning true if the result 01842 /// overflowed for this type. 01843 static bool MulWithOverflow(ConstantInt *&Result, ConstantInt *In1, 01844 ConstantInt *In2) { 01845 Result = cast<ConstantInt>(ConstantExpr::getMul(In1, In2)); 01846 return !In2->isNullValue() && ConstantExpr::getDiv(Result, In2) != In1; 01847 } 01848 01849 static bool isPositive(ConstantInt *C) { 01850 return cast<ConstantSInt>(C)->getValue() >= 0; 01851 } 01852 01853 /// AddWithOverflow - Compute Result = In1+In2, returning true if the result 01854 /// overflowed for this type. 01855 static bool AddWithOverflow(ConstantInt *&Result, ConstantInt *In1, 01856 ConstantInt *In2) { 01857 Result = cast<ConstantInt>(ConstantExpr::getAdd(In1, In2)); 01858 01859 if (In1->getType()->isUnsigned()) 01860 return cast<ConstantUInt>(Result)->getValue() < 01861 cast<ConstantUInt>(In1)->getValue(); 01862 if (isPositive(In1) != isPositive(In2)) 01863 return false; 01864 if (isPositive(In1)) 01865 return cast<ConstantSInt>(Result)->getValue() < 01866 cast<ConstantSInt>(In1)->getValue(); 01867 return cast<ConstantSInt>(Result)->getValue() > 01868 cast<ConstantSInt>(In1)->getValue(); 01869 } 01870 01871 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) { 01872 bool Changed = SimplifyCommutative(I); 01873 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 01874 const Type *Ty = Op0->getType(); 01875 01876 // setcc X, X 01877 if (Op0 == Op1) 01878 return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I))); 01879 01880 if (isa<UndefValue>(Op1)) // X setcc undef -> undef 01881 return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy)); 01882 01883 // setcc <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 01884 // addresses never equal each other! We already know that Op0 != Op1. 01885 if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) || 01886 isa<ConstantPointerNull>(Op0)) && 01887 (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) || 01888 isa<ConstantPointerNull>(Op1))) 01889 return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I))); 01890 01891 // setcc's with boolean values can always be turned into bitwise operations 01892 if (Ty == Type::BoolTy) { 01893 switch (I.getOpcode()) { 01894 default: assert(0 && "Invalid setcc instruction!"); 01895 case Instruction::SetEQ: { // seteq bool %A, %B -> ~(A^B) 01896 Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp"); 01897 InsertNewInstBefore(Xor, I); 01898 return BinaryOperator::createNot(Xor); 01899 } 01900 case Instruction::SetNE: 01901 return BinaryOperator::createXor(Op0, Op1); 01902 01903 case Instruction::SetGT: 01904 std::swap(Op0, Op1); // Change setgt -> setlt 01905 // FALL THROUGH 01906 case Instruction::SetLT: { // setlt bool A, B -> ~X & Y 01907 Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp"); 01908 InsertNewInstBefore(Not, I); 01909 return BinaryOperator::createAnd(Not, Op1); 01910 } 01911 case Instruction::SetGE: 01912 std::swap(Op0, Op1); // Change setge -> setle 01913 // FALL THROUGH 01914 case Instruction::SetLE: { // setle bool %A, %B -> ~A | B 01915 Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp"); 01916 InsertNewInstBefore(Not, I); 01917 return BinaryOperator::createOr(Not, Op1); 01918 } 01919 } 01920 } 01921 01922 // See if we are doing a comparison between a constant and an instruction that 01923 // can be folded into the comparison. 01924 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 01925 // Check to see if we are comparing against the minimum or maximum value... 01926 if (CI->isMinValue()) { 01927 if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE 01928 return ReplaceInstUsesWith(I, ConstantBool::False); 01929 if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE 01930 return ReplaceInstUsesWith(I, ConstantBool::True); 01931 if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN 01932 return BinaryOperator::createSetEQ(Op0, Op1); 01933 if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN 01934 return BinaryOperator::createSetNE(Op0, Op1); 01935 01936 } else if (CI->isMaxValue()) { 01937 if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE 01938 return ReplaceInstUsesWith(I, ConstantBool::False); 01939 if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE 01940 return ReplaceInstUsesWith(I, ConstantBool::True); 01941 if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX 01942 return BinaryOperator::createSetEQ(Op0, Op1); 01943 if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX 01944 return BinaryOperator::createSetNE(Op0, Op1); 01945 01946 // Comparing against a value really close to min or max? 01947 } else if (isMinValuePlusOne(CI)) { 01948 if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN 01949 return BinaryOperator::createSetEQ(Op0, SubOne(CI)); 01950 if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN 01951 return BinaryOperator::createSetNE(Op0, SubOne(CI)); 01952 01953 } else if (isMaxValueMinusOne(CI)) { 01954 if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX 01955 return BinaryOperator::createSetEQ(Op0, AddOne(CI)); 01956 if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX 01957 return BinaryOperator::createSetNE(Op0, AddOne(CI)); 01958 } 01959 01960 // If we still have a setle or setge instruction, turn it into the 01961 // appropriate setlt or setgt instruction. Since the border cases have 01962 // already been handled above, this requires little checking. 01963 // 01964 if (I.getOpcode() == Instruction::SetLE) 01965 return BinaryOperator::createSetLT(Op0, AddOne(CI)); 01966 if (I.getOpcode() == Instruction::SetGE) 01967 return BinaryOperator::createSetGT(Op0, SubOne(CI)); 01968 01969 if (Instruction *LHSI = dyn_cast<Instruction>(Op0)) 01970 switch (LHSI->getOpcode()) { 01971 case Instruction::PHI: 01972 if (Instruction *NV = FoldOpIntoPhi(I)) 01973 return NV; 01974 break; 01975 case Instruction::And: 01976 if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) && 01977 LHSI->getOperand(0)->hasOneUse()) { 01978 // If this is: (X >> C1) & C2 != C3 (where any shift and any compare 01979 // could exist), turn it into (X & (C2 << C1)) != (C3 << C1). This 01980 // happens a LOT in code produced by the C front-end, for bitfield 01981 // access. 01982 ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0)); 01983 ConstantUInt *ShAmt; 01984 ShAmt = Shift ? dyn_cast<ConstantUInt>(Shift->getOperand(1)) : 0; 01985 ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1)); 01986 const Type *Ty = LHSI->getType(); 01987 01988 // We can fold this as long as we can't shift unknown bits 01989 // into the mask. This can only happen with signed shift 01990 // rights, as they sign-extend. 01991 if (ShAmt) { 01992 bool CanFold = Shift->getOpcode() != Instruction::Shr || 01993 Shift->getType()->isUnsigned(); 01994 if (!CanFold) { 01995 // To test for the bad case of the signed shr, see if any 01996 // of the bits shifted in could be tested after the mask. 01997 Constant *OShAmt = ConstantUInt::get(Type::UByteTy, 01998 Ty->getPrimitiveSize()*8-ShAmt->getValue()); 01999 Constant *ShVal = 02000 ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), OShAmt); 02001 if (ConstantExpr::getAnd(ShVal, AndCST)->isNullValue()) 02002 CanFold = true; 02003 } 02004 02005 if (CanFold) { 02006 Constant *NewCst; 02007 if (Shift->getOpcode() == Instruction::Shl) 02008 NewCst = ConstantExpr::getUShr(CI, ShAmt); 02009 else 02010 NewCst = ConstantExpr::getShl(CI, ShAmt); 02011 02012 // Check to see if we are shifting out any of the bits being 02013 // compared. 02014 if (ConstantExpr::get(Shift->getOpcode(), NewCst, ShAmt) != CI){ 02015 // If we shifted bits out, the fold is not going to work out. 02016 // As a special case, check to see if this means that the 02017 // result is always true or false now. 02018 if (I.getOpcode() == Instruction::SetEQ) 02019 return ReplaceInstUsesWith(I, ConstantBool::False); 02020 if (I.getOpcode() == Instruction::SetNE) 02021 return ReplaceInstUsesWith(I, ConstantBool::True); 02022 } else { 02023 I.setOperand(1, NewCst); 02024 Constant *NewAndCST; 02025 if (Shift->getOpcode() == Instruction::Shl) 02026 NewAndCST = ConstantExpr::getUShr(AndCST, ShAmt); 02027 else 02028 NewAndCST = ConstantExpr::getShl(AndCST, ShAmt); 02029 LHSI->setOperand(1, NewAndCST); 02030 LHSI->setOperand(0, Shift->getOperand(0)); 02031 WorkList.push_back(Shift); // Shift is dead. 02032 AddUsesToWorkList(I); 02033 return &I; 02034 } 02035 } 02036 } 02037 } 02038 break; 02039 02040 // (setcc (cast X to larger), CI) 02041 case Instruction::Cast: { 02042 Instruction* replacement = 02043 visitSetCondInstWithCastAndConstant(I,cast<CastInst>(LHSI),CI); 02044 if (replacement) 02045 return replacement; 02046 break; 02047 } 02048 02049 case Instruction::Shl: // (setcc (shl X, ShAmt), CI) 02050 if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) { 02051 switch (I.getOpcode()) { 02052 default: break; 02053 case Instruction::SetEQ: 02054 case Instruction::SetNE: { 02055 // If we are comparing against bits always shifted out, the 02056 // comparison cannot succeed. 02057 Constant *Comp = 02058 ConstantExpr::getShl(ConstantExpr::getShr(CI, ShAmt), ShAmt); 02059 if (Comp != CI) {// Comparing against a bit that we know is zero. 02060 bool IsSetNE = I.getOpcode() == Instruction::SetNE; 02061 Constant *Cst = ConstantBool::get(IsSetNE); 02062 return ReplaceInstUsesWith(I, Cst); 02063 } 02064 02065 if (LHSI->hasOneUse()) { 02066 // Otherwise strength reduce the shift into an and. 02067 unsigned ShAmtVal = ShAmt->getValue(); 02068 unsigned TypeBits = CI->getType()->getPrimitiveSize()*8; 02069 uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1; 02070 02071 Constant *Mask; 02072 if (CI->getType()->isUnsigned()) { 02073 Mask = ConstantUInt::get(CI->getType(), Val); 02074 } else if (ShAmtVal != 0) { 02075 Mask = ConstantSInt::get(CI->getType(), Val); 02076 } else { 02077 Mask = ConstantInt::getAllOnesValue(CI->getType()); 02078 } 02079 02080 Instruction *AndI = 02081 BinaryOperator::createAnd(LHSI->getOperand(0), 02082 Mask, LHSI->getName()+".mask"); 02083 Value *And = InsertNewInstBefore(AndI, I); 02084 return new SetCondInst(I.getOpcode(), And, 02085 ConstantExpr::getUShr(CI, ShAmt)); 02086 } 02087 } 02088 } 02089 } 02090 break; 02091 02092 case Instruction::Shr: // (setcc (shr X, ShAmt), CI) 02093 if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) { 02094 switch (I.getOpcode()) { 02095 default: break; 02096 case Instruction::SetEQ: 02097 case Instruction::SetNE: { 02098 // If we are comparing against bits always shifted out, the 02099 // comparison cannot succeed. 02100 Constant *Comp = 02101 ConstantExpr::getShr(ConstantExpr::getShl(CI, ShAmt), ShAmt); 02102 02103 if (Comp != CI) {// Comparing against a bit that we know is zero. 02104 bool IsSetNE = I.getOpcode() == Instruction::SetNE; 02105 Constant *Cst = ConstantBool::get(IsSetNE); 02106 return ReplaceInstUsesWith(I, Cst); 02107 } 02108 02109 if (LHSI->hasOneUse() || CI->isNullValue()) { 02110 unsigned ShAmtVal = ShAmt->getValue(); 02111 02112 // Otherwise strength reduce the shift into an and. 02113 uint64_t Val = ~0ULL; // All ones. 02114 Val <<= ShAmtVal; // Shift over to the right spot. 02115 02116 Constant *Mask; 02117 if (CI->getType()->isUnsigned()) { 02118 unsigned TypeBits = CI->getType()->getPrimitiveSize()*8; 02119 Val &= (1ULL << TypeBits)-1; 02120 Mask = ConstantUInt::get(CI->getType(), Val); 02121 } else { 02122 Mask = ConstantSInt::get(CI->getType(), Val); 02123 } 02124 02125 Instruction *AndI = 02126 BinaryOperator::createAnd(LHSI->getOperand(0), 02127 Mask, LHSI->getName()+".mask"); 02128 Value *And = InsertNewInstBefore(AndI, I); 02129 return new SetCondInst(I.getOpcode(), And, 02130 ConstantExpr::getShl(CI, ShAmt)); 02131 } 02132 break; 02133 } 02134 } 02135 } 02136 break; 02137 02138 case Instruction::Div: 02139 // Fold: (div X, C1) op C2 -> range check 02140 if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) { 02141 // Fold this div into the comparison, producing a range check. 02142 // Determine, based on the divide type, what the range is being 02143 // checked. If there is an overflow on the low or high side, remember 02144 // it, otherwise compute the range [low, hi) bounding the new value. 02145 bool LoOverflow = false, HiOverflow = 0; 02146 ConstantInt *LoBound = 0, *HiBound = 0; 02147 02148 ConstantInt *Prod; 02149 bool ProdOV = MulWithOverflow(Prod, CI, DivRHS); 02150 02151 Instruction::BinaryOps Opcode = I.getOpcode(); 02152 02153 if (DivRHS->isNullValue()) { // Don't hack on divide by zeros. 02154 } else if (LHSI->getType()->isUnsigned()) { // udiv 02155 LoBound = Prod; 02156 LoOverflow = ProdOV; 02157 HiOverflow = ProdOV || AddWithOverflow(HiBound, LoBound, DivRHS); 02158 } else if (isPositive(DivRHS)) { // Divisor is > 0. 02159 if (CI->isNullValue()) { // (X / pos) op 0 02160 // Can't overflow. 02161 LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS))); 02162 HiBound = DivRHS; 02163 } else if (isPositive(CI)) { // (X / pos) op pos 02164 LoBound = Prod; 02165 LoOverflow = ProdOV; 02166 HiOverflow = ProdOV || AddWithOverflow(HiBound, Prod, DivRHS); 02167 } else { // (X / pos) op neg 02168 Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS)); 02169 LoOverflow = AddWithOverflow(LoBound, Prod, 02170 cast<ConstantInt>(DivRHSH)); 02171 HiBound = Prod; 02172 HiOverflow = ProdOV; 02173 } 02174 } else { // Divisor is < 0. 02175 if (CI->isNullValue()) { // (X / neg) op 0 02176 LoBound = AddOne(DivRHS); 02177 HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS)); 02178 } else if (isPositive(CI)) { // (X / neg) op pos 02179 HiOverflow = LoOverflow = ProdOV; 02180 if (!LoOverflow) 02181 LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS)); 02182 HiBound = AddOne(Prod); 02183 } else { // (X / neg) op neg 02184 LoBound = Prod; 02185 LoOverflow = HiOverflow = ProdOV; 02186 HiBound = cast<ConstantInt>(ConstantExpr::getSub(Prod, DivRHS)); 02187 } 02188 02189 // Dividing by a negate swaps the condition. 02190 Opcode = SetCondInst::getSwappedCondition(Opcode); 02191 } 02192 02193 if (LoBound) { 02194 Value *X = LHSI->getOperand(0); 02195 switch (Opcode) { 02196 default: assert(0 && "Unhandled setcc opcode!"); 02197 case Instruction::SetEQ: 02198 if (LoOverflow && HiOverflow) 02199 return ReplaceInstUsesWith(I, ConstantBool::False); 02200 else if (HiOverflow) 02201 return new SetCondInst(Instruction::SetGE, X, LoBound); 02202 else if (LoOverflow) 02203 return new SetCondInst(Instruction::SetLT, X, HiBound); 02204 else 02205 return InsertRangeTest(X, LoBound, HiBound, true, I); 02206 case Instruction::SetNE: 02207 if (LoOverflow && HiOverflow) 02208 return ReplaceInstUsesWith(I, ConstantBool::True); 02209 else if (HiOverflow) 02210 return new SetCondInst(Instruction::SetLT, X, LoBound); 02211 else if (LoOverflow) 02212 return new SetCondInst(Instruction::SetGE, X, HiBound); 02213 else 02214 return InsertRangeTest(X, LoBound, HiBound, false, I); 02215 case Instruction::SetLT: 02216 if (LoOverflow) 02217 return ReplaceInstUsesWith(I, ConstantBool::False); 02218 return new SetCondInst(Instruction::SetLT, X, LoBound); 02219 case Instruction::SetGT: 02220 if (HiOverflow) 02221 return ReplaceInstUsesWith(I, ConstantBool::False); 02222 return new SetCondInst(Instruction::SetGE, X, HiBound); 02223 } 02224 } 02225 } 02226 break; 02227 case Instruction::Select: 02228 // If either operand of the select is a constant, we can fold the 02229 // comparison into the select arms, which will cause one to be 02230 // constant folded and the select turned into a bitwise or. 02231 Value *Op1 = 0, *Op2 = 0; 02232 if (LHSI->hasOneUse()) { 02233 if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) { 02234 // Fold the known value into the constant operand. 02235 Op1 = ConstantExpr::get(I.getOpcode(), C, CI); 02236 // Insert a new SetCC of the other select operand. 02237 Op2 = InsertNewInstBefore(new SetCondInst(I.getOpcode(), 02238 LHSI->getOperand(2), CI, 02239 I.getName()), I); 02240 } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) { 02241 // Fold the known value into the constant operand. 02242 Op2 = ConstantExpr::get(I.getOpcode(), C, CI); 02243 // Insert a new SetCC of the other select operand. 02244 Op1 = InsertNewInstBefore(new SetCondInst(I.getOpcode(), 02245 LHSI->getOperand(1), CI, 02246 I.getName()), I); 02247 } 02248 } 02249 02250 if (Op1) 02251 return new SelectInst(LHSI->getOperand(0), Op1, Op2); 02252 break; 02253 } 02254 02255 // Simplify seteq and setne instructions... 02256 if (I.getOpcode() == Instruction::SetEQ || 02257 I.getOpcode() == Instruction::SetNE) { 02258 bool isSetNE = I.getOpcode() == Instruction::SetNE; 02259 02260 // If the first operand is (and|or|xor) with a constant, and the second 02261 // operand is a constant, simplify a bit. 02262 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) { 02263 switch (BO->getOpcode()) { 02264 case Instruction::Rem: 02265 // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one. 02266 if (CI->isNullValue() && isa<ConstantSInt>(BO->getOperand(1)) && 02267 BO->hasOneUse() && 02268 cast<ConstantSInt>(BO->getOperand(1))->getValue() > 1) 02269 if (unsigned L2 = 02270 Log2(cast<ConstantSInt>(BO->getOperand(1))->getValue())) { 02271 const Type *UTy = BO->getType()->getUnsignedVersion(); 02272 Value *NewX = InsertNewInstBefore(new CastInst(BO->getOperand(0), 02273 UTy, "tmp"), I); 02274 Constant *RHSCst = ConstantUInt::get(UTy, 1ULL << L2); 02275 Value *NewRem =InsertNewInstBefore(BinaryOperator::createRem(NewX, 02276 RHSCst, BO->getName()), I); 02277 return BinaryOperator::create(I.getOpcode(), NewRem, 02278 Constant::getNullValue(UTy)); 02279 } 02280 break; 02281 02282 case Instruction::Add: 02283 // Replace ((add A, B) != C) with (A != C-B) if B & C are constants. 02284 if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) { 02285 if (BO->hasOneUse()) 02286 return new SetCondInst(I.getOpcode(), BO->getOperand(0), 02287 ConstantExpr::getSub(CI, BOp1C)); 02288 } else if (CI->isNullValue()) { 02289 // Replace ((add A, B) != 0) with (A != -B) if A or B is 02290 // efficiently invertible, or if the add has just this one use. 02291 Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1); 02292 02293 if (Value *NegVal = dyn_castNegVal(BOp1)) 02294 return new SetCondInst(I.getOpcode(), BOp0, NegVal); 02295 else if (Value *NegVal = dyn_castNegVal(BOp0)) 02296 return new SetCondInst(I.getOpcode(), NegVal, BOp1); 02297 else if (BO->hasOneUse()) { 02298 Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName()); 02299 BO->setName(""); 02300 InsertNewInstBefore(Neg, I); 02301 return new SetCondInst(I.getOpcode(), BOp0, Neg); 02302 } 02303 } 02304 break; 02305 case Instruction::Xor: 02306 // For the xor case, we can xor two constants together, eliminating 02307 // the explicit xor. 02308 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) 02309 return BinaryOperator::create(I.getOpcode(), BO->getOperand(0), 02310 ConstantExpr::getXor(CI, BOC)); 02311 02312 // FALLTHROUGH 02313 case Instruction::Sub: 02314 // Replace (([sub|xor] A, B) != 0) with (A != B) 02315 if (CI->isNullValue()) 02316 return new SetCondInst(I.getOpcode(), BO->getOperand(0), 02317 BO->getOperand(1)); 02318 break; 02319 02320 case Instruction::Or: 02321 // If bits are being or'd in that are not present in the constant we 02322 // are comparing against, then the comparison could never succeed! 02323 if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) { 02324 Constant *NotCI = ConstantExpr::getNot(CI); 02325 if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue()) 02326 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE)); 02327 } 02328 break; 02329 02330 case Instruction::And: 02331 if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) { 02332 // If bits are being compared against that are and'd out, then the 02333 // comparison can never succeed! 02334 if (!ConstantExpr::getAnd(CI, 02335 ConstantExpr::getNot(BOC))->isNullValue()) 02336 return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE)); 02337 02338 // If we have ((X & C) == C), turn it into ((X & C) != 0). 02339 if (CI == BOC && isOneBitSet(CI)) 02340 return new SetCondInst(isSetNE ? Instruction::SetEQ : 02341 Instruction::SetNE, Op0, 02342 Constant::getNullValue(CI->getType())); 02343 02344 // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X 02345 // to be a signed value as appropriate. 02346 if (isSignBit(BOC)) { 02347 Value *X = BO->getOperand(0); 02348 // If 'X' is not signed, insert a cast now... 02349 if (!BOC->getType()->isSigned()) { 02350 const Type *DestTy = BOC->getType()->getSignedVersion(); 02351 X = InsertCastBefore(X, DestTy, I); 02352 } 02353 return new SetCondInst(isSetNE ? Instruction::SetLT : 02354 Instruction::SetGE, X, 02355 Constant::getNullValue(X->getType())); 02356 } 02357 02358 // ((X & ~7) == 0) --> X < 8 02359 if (CI->isNullValue() && isHighOnes(BOC)) { 02360 Value *X = BO->getOperand(0); 02361 Constant *NegX = ConstantExpr::getNeg(BOC); 02362 02363 // If 'X' is signed, insert a cast now. 02364 if (NegX->getType()->isSigned()) { 02365 const Type *DestTy = NegX->getType()->getUnsignedVersion(); 02366 X = InsertCastBefore(X, DestTy, I); 02367 NegX = ConstantExpr::getCast(NegX, DestTy); 02368 } 02369 02370 return new SetCondInst(isSetNE ? Instruction::SetGE : 02371 Instruction::SetLT, X, NegX); 02372 } 02373 02374 } 02375 default: break; 02376 } 02377 } 02378 } else { // Not a SetEQ/SetNE 02379 // If the LHS is a cast from an integral value of the same size, 02380 if (CastInst *Cast = dyn_cast<CastInst>(Op0)) { 02381 Value *CastOp = Cast->getOperand(0); 02382 const Type *SrcTy = CastOp->getType(); 02383 unsigned SrcTySize = SrcTy->getPrimitiveSize(); 02384 if (SrcTy != Cast->getType() && SrcTy->isInteger() && 02385 SrcTySize == Cast->getType()->getPrimitiveSize()) { 02386 assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) && 02387 "Source and destination signednesses should differ!"); 02388 if (Cast->getType()->isSigned()) { 02389 // If this is a signed comparison, check for comparisons in the 02390 // vicinity of zero. 02391 if (I.getOpcode() == Instruction::SetLT && CI->isNullValue()) 02392 // X < 0 => x > 127 02393 return BinaryOperator::createSetGT(CastOp, 02394 ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1)); 02395 else if (I.getOpcode() == Instruction::SetGT && 02396 cast<ConstantSInt>(CI)->getValue() == -1) 02397 // X > -1 => x < 128 02398 return BinaryOperator::createSetLT(CastOp, 02399 ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1))); 02400 } else { 02401 ConstantUInt *CUI = cast<ConstantUInt>(CI); 02402 if (I.getOpcode() == Instruction::SetLT && 02403 CUI->getValue() == 1ULL << (SrcTySize*8-1)) 02404 // X < 128 => X > -1 02405 return BinaryOperator::createSetGT(CastOp, 02406 ConstantSInt::get(SrcTy, -1)); 02407 else if (I.getOpcode() == Instruction::SetGT && 02408 CUI->getValue() == (1ULL << (SrcTySize*8-1))-1) 02409 // X > 127 => X < 0 02410 return BinaryOperator::createSetLT(CastOp, 02411 Constant::getNullValue(SrcTy)); 02412 } 02413 } 02414 } 02415 } 02416 } 02417 02418 // Test to see if the operands of the setcc are casted versions of other 02419 // values. If the cast can be stripped off both arguments, we do so now. 02420 if (CastInst *CI = dyn_cast<CastInst>(Op0)) { 02421 Value *CastOp0 = CI->getOperand(0); 02422 if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) && 02423 (isa<Constant>(Op1) || isa<CastInst>(Op1)) && 02424 (I.getOpcode() == Instruction::SetEQ || 02425 I.getOpcode() == Instruction::SetNE)) { 02426 // We keep moving the cast from the left operand over to the right 02427 // operand, where it can often be eliminated completely. 02428 Op0 = CastOp0; 02429 02430 // If operand #1 is a cast instruction, see if we can eliminate it as 02431 // well. 02432 if (CastInst *CI2 = dyn_cast<CastInst>(Op1)) 02433 if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo( 02434 Op0->getType())) 02435 Op1 = CI2->getOperand(0); 02436 02437 // If Op1 is a constant, we can fold the cast into the constant. 02438 if (Op1->getType() != Op0->getType()) 02439 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 02440 Op1 = ConstantExpr::getCast(Op1C, Op0->getType()); 02441 } else { 02442 // Otherwise, cast the RHS right before the setcc 02443 Op1 = new CastInst(Op1, Op0->getType(), Op1->getName()); 02444 InsertNewInstBefore(cast<Instruction>(Op1), I); 02445 } 02446 return BinaryOperator::create(I.getOpcode(), Op0, Op1); 02447 } 02448 02449 // Handle the special case of: setcc (cast bool to X), <cst> 02450 // This comes up when you have code like 02451 // int X = A < B; 02452 // if (X) ... 02453 // For generality, we handle any zero-extension of any operand comparison 02454 // with a constant. 02455 if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) { 02456 const Type *SrcTy = CastOp0->getType(); 02457 const Type *DestTy = Op0->getType(); 02458 if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() && 02459 (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) { 02460 // Ok, we have an expansion of operand 0 into a new type. Get the 02461 // constant value, masink off bits which are not set in the RHS. These 02462 // could be set if the destination value is signed. 02463 uint64_t ConstVal = ConstantRHS->getRawValue(); 02464 ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1; 02465 02466 // If the constant we are comparing it with has high bits set, which 02467 // don't exist in the original value, the values could never be equal, 02468 // because the source would be zero extended. 02469 unsigned SrcBits = 02470 SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8; 02471 bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1)); 02472 if (ConstVal & ~((1ULL << SrcBits)-1)) { 02473 switch (I.getOpcode()) { 02474 default: assert(0 && "Unknown comparison type!"); 02475 case Instruction::SetEQ: 02476 return ReplaceInstUsesWith(I, ConstantBool::False); 02477 case Instruction::SetNE: 02478 return ReplaceInstUsesWith(I, ConstantBool::True); 02479 case Instruction::SetLT: 02480 case Instruction::SetLE: 02481 if (DestTy->isSigned() && HasSignBit) 02482 return ReplaceInstUsesWith(I, ConstantBool::False); 02483 return ReplaceInstUsesWith(I, ConstantBool::True); 02484 case Instruction::SetGT: 02485 case Instruction::SetGE: 02486 if (DestTy->isSigned() && HasSignBit) 02487 return ReplaceInstUsesWith(I, ConstantBool::True); 02488 return ReplaceInstUsesWith(I, ConstantBool::False); 02489 } 02490 } 02491 02492 // Otherwise, we can replace the setcc with a setcc of the smaller 02493 // operand value. 02494 Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy); 02495 return BinaryOperator::create(I.getOpcode(), CastOp0, Op1); 02496 } 02497 } 02498 } 02499 return Changed ? &I : 0; 02500 } 02501 02502 // visitSetCondInstWithCastAndConstant - this method is part of the 02503 // visitSetCondInst method. It handles the situation where we have: 02504 // (setcc (cast X to larger), CI) 02505 // It tries to remove the cast and even the setcc if the CI value 02506 // and range of the cast allow it. 02507 Instruction * 02508 InstCombiner::visitSetCondInstWithCastAndConstant(BinaryOperator&I, 02509 CastInst* LHSI, 02510 ConstantInt* CI) { 02511 const Type *SrcTy = LHSI->getOperand(0)->getType(); 02512 const Type *DestTy = LHSI->getType(); 02513 if (SrcTy->isIntegral() && DestTy->isIntegral()) { 02514 unsigned SrcBits = SrcTy->getPrimitiveSize()*8; 02515 unsigned DestBits = DestTy->getPrimitiveSize()*8; 02516 if (SrcTy == Type::BoolTy) 02517 SrcBits = 1; 02518 if (DestTy == Type::BoolTy) 02519 DestBits = 1; 02520 if (SrcBits < DestBits) { 02521 // There are fewer bits in the source of the cast than in the result 02522 // of the cast. Any other case doesn't matter because the constant 02523 // value won't have changed due to sign extension. 02524 Constant *NewCst = ConstantExpr::getCast(CI, SrcTy); 02525 if (ConstantExpr::getCast(NewCst, DestTy) == CI) { 02526 // The constant value operand of the setCC before and after a 02527 // cast to the source type of the cast instruction is the same 02528 // value, so we just replace with the same setcc opcode, but 02529 // using the source value compared to the constant casted to the 02530 // source type. 02531 if (SrcTy->isSigned() && DestTy->isUnsigned()) { 02532 CastInst* Cst = new CastInst(LHSI->getOperand(0), 02533 SrcTy->getUnsignedVersion(), LHSI->getName()); 02534 InsertNewInstBefore(Cst,I); 02535 return new SetCondInst(I.getOpcode(), Cst, 02536 ConstantExpr::getCast(CI, SrcTy->getUnsignedVersion())); 02537 } 02538 return new SetCondInst(I.getOpcode(), LHSI->getOperand(0),NewCst); 02539 } 02540 // The constant value before and after a cast to the source type 02541 // is different, so various cases are possible depending on the 02542 // opcode and the signs of the types involved in the cast. 02543 switch (I.getOpcode()) { 02544 case Instruction::SetLT: { 02545 Constant* Max = ConstantIntegral::getMaxValue(SrcTy); 02546 Max = ConstantExpr::getCast(Max, DestTy); 02547 return ReplaceInstUsesWith(I, ConstantExpr::getSetLT(Max, CI)); 02548 } 02549 case Instruction::SetGT: { 02550 Constant* Min = ConstantIntegral::getMinValue(SrcTy); 02551 Min = ConstantExpr::getCast(Min, DestTy); 02552 return ReplaceInstUsesWith(I, ConstantExpr::getSetGT(Min, CI)); 02553 } 02554 case Instruction::SetEQ: 02555 // We're looking for equality, and we know the values are not 02556 // equal so replace with constant False. 02557 return ReplaceInstUsesWith(I, ConstantBool::False); 02558 case Instruction::SetNE: 02559 // We're testing for inequality, and we know the values are not 02560 // equal so replace with constant True. 02561 return ReplaceInstUsesWith(I, ConstantBool::True); 02562 case Instruction::SetLE: 02563 case Instruction::SetGE: 02564 assert(!"SetLE and SetGE should be handled elsewhere"); 02565 default: 02566 assert(!"unknown integer comparison"); 02567 } 02568 } 02569 } 02570 return 0; 02571 } 02572 02573 02574 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) { 02575 assert(I.getOperand(1)->getType() == Type::UByteTy); 02576 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 02577 bool isLeftShift = I.getOpcode() == Instruction::Shl; 02578 02579 // shl X, 0 == X and shr X, 0 == X 02580 // shl 0, X == 0 and shr 0, X == 0 02581 if (Op1 == Constant::getNullValue(Type::UByteTy) || 02582 Op0 == Constant::getNullValue(Op0->getType())) 02583 return ReplaceInstUsesWith(I, Op0); 02584 02585 if (isa<UndefValue>(Op0)) { // undef >>s X -> undef 02586 if (!isLeftShift && I.getType()->isSigned()) 02587 return ReplaceInstUsesWith(I, Op0); 02588 else // undef << X -> 0 AND undef >>u X -> 0 02589 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 02590 } 02591 if (isa<UndefValue>(Op1)) { 02592 if (isLeftShift || I.getType()->isUnsigned()) 02593 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 02594 else 02595 return ReplaceInstUsesWith(I, Op0); // X >>s undef -> X 02596 } 02597 02598 // shr int -1, X = -1 (for any arithmetic shift rights of ~0) 02599 if (!isLeftShift) 02600 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0)) 02601 if (CSI->isAllOnesValue()) 02602 return ReplaceInstUsesWith(I, CSI); 02603 02604 // Try to fold constant and into select arguments. 02605 if (isa<Constant>(Op0)) 02606 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 02607 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 02608 return R; 02609 02610 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) { 02611 // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr 02612 // of a signed value. 02613 // 02614 unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8; 02615 if (CUI->getValue() >= TypeBits) { 02616 if (!Op0->getType()->isSigned() || isLeftShift) 02617 return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); 02618 else { 02619 I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1)); 02620 return &I; 02621 } 02622 } 02623 02624 // ((X*C1) << C2) == (X * (C1 << C2)) 02625 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 02626 if (BO->getOpcode() == Instruction::Mul && isLeftShift) 02627 if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 02628 return BinaryOperator::createMul(BO->getOperand(0), 02629 ConstantExpr::getShl(BOOp, CUI)); 02630 02631 // Try to fold constant and into select arguments. 02632 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 02633 if (Instruction *R = FoldBinOpIntoSelect(I, SI, this)) 02634 return R; 02635 if (isa<PHINode>(Op0)) 02636 if (Instruction *NV = FoldOpIntoPhi(I)) 02637 return NV; 02638 02639 // If the operand is an bitwise operator with a constant RHS, and the 02640 // shift is the only use, we can pull it out of the shift. 02641 if (Op0->hasOneUse()) 02642 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) 02643 if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 02644 bool isValid = true; // Valid only for And, Or, Xor 02645 bool highBitSet = false; // Transform if high bit of constant set? 02646 02647 switch (Op0BO->getOpcode()) { 02648 default: isValid = false; break; // Do not perform transform! 02649 case Instruction::Add: 02650 isValid = isLeftShift; 02651 break; 02652 case Instruction::Or: 02653 case Instruction::Xor: 02654 highBitSet = false; 02655 break; 02656 case Instruction::And: 02657 highBitSet = true; 02658 break; 02659 } 02660 02661 // If this is a signed shift right, and the high bit is modified 02662 // by the logical operation, do not perform the transformation. 02663 // The highBitSet boolean indicates the value of the high bit of 02664 // the constant which would cause it to be modified for this 02665 // operation. 02666 // 02667 if (isValid && !isLeftShift && !I.getType()->isUnsigned()) { 02668 uint64_t Val = Op0C->getRawValue(); 02669 isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet; 02670 } 02671 02672 if (isValid) { 02673 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI); 02674 02675 Instruction *NewShift = 02676 new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI, 02677 Op0BO->getName()); 02678 Op0BO->setName(""); 02679 InsertNewInstBefore(NewShift, I); 02680 02681 return BinaryOperator::create(Op0BO->getOpcode(), NewShift, 02682 NewRHS); 02683 } 02684 } 02685 02686 // If this is a shift of a shift, see if we can fold the two together... 02687 if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0)) 02688 if (ConstantUInt *ShiftAmt1C = 02689 dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) { 02690 unsigned ShiftAmt1 = ShiftAmt1C->getValue(); 02691 unsigned ShiftAmt2 = CUI->getValue(); 02692 02693 // Check for (A << c1) << c2 and (A >> c1) >> c2 02694 if (I.getOpcode() == Op0SI->getOpcode()) { 02695 unsigned Amt = ShiftAmt1+ShiftAmt2; // Fold into one big shift... 02696 if (Op0->getType()->getPrimitiveSize()*8 < Amt) 02697 Amt = Op0->getType()->getPrimitiveSize()*8; 02698 return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0), 02699 ConstantUInt::get(Type::UByteTy, Amt)); 02700 } 02701 02702 // Check for (A << c1) >> c2 or visaversa. If we are dealing with 02703 // signed types, we can only support the (A >> c1) << c2 configuration, 02704 // because it can not turn an arbitrary bit of A into a sign bit. 02705 if (I.getType()->isUnsigned() || isLeftShift) { 02706 // Calculate bitmask for what gets shifted off the edge... 02707 Constant *C = ConstantIntegral::getAllOnesValue(I.getType()); 02708 if (isLeftShift) 02709 C = ConstantExpr::getShl(C, ShiftAmt1C); 02710 else 02711 C = ConstantExpr::getShr(C, ShiftAmt1C); 02712 02713 Instruction *Mask = 02714 BinaryOperator::createAnd(Op0SI->getOperand(0), C, 02715 Op0SI->getOperand(0)->getName()+".mask"); 02716 InsertNewInstBefore(Mask, I); 02717 02718 // Figure out what flavor of shift we should use... 02719 if (ShiftAmt1 == ShiftAmt2) 02720 return ReplaceInstUsesWith(I, Mask); // (A << c) >> c === A & c2 02721 else if (ShiftAmt1 < ShiftAmt2) { 02722 return new ShiftInst(I.getOpcode(), Mask, 02723 ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1)); 02724 } else { 02725 return new ShiftInst(Op0SI->getOpcode(), Mask, 02726 ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2)); 02727 } 02728 } 02729 } 02730 } 02731 02732 return 0; 02733 } 02734 02735 enum CastType { 02736 Noop = 0, 02737 Truncate = 1, 02738 Signext = 2, 02739 Zeroext = 3 02740 }; 02741 02742 /// getCastType - In the future, we will split the cast instruction into these 02743 /// various types. Until then, we have to do the analysis here. 02744 static CastType getCastType(const Type *Src, const Type *Dest) { 02745 assert(Src->isIntegral() && Dest->isIntegral() && 02746 "Only works on integral types!"); 02747 unsigned SrcSize = Src->getPrimitiveSize()*8; 02748 if (Src == Type::BoolTy) SrcSize = 1; 02749 unsigned DestSize = Dest->getPrimitiveSize()*8; 02750 if (Dest == Type::BoolTy) DestSize = 1; 02751 02752 if (SrcSize == DestSize) return Noop; 02753 if (SrcSize > DestSize) return Truncate; 02754 if (Src->isSigned()) return Signext; 02755 return Zeroext; 02756 } 02757 02758 02759 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI 02760 // instruction. 02761 // 02762 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy, 02763 const Type *DstTy, TargetData *TD) { 02764 02765 // It is legal to eliminate the instruction if casting A->B->A if the sizes 02766 // are identical and the bits don't get reinterpreted (for example 02767 // int->float->int would not be allowed). 02768 if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy)) 02769 return true; 02770 02771 // If we are casting between pointer and integer types, treat pointers as 02772 // integers of the appropriate size for the code below. 02773 if (isa<PointerType>(SrcTy)) SrcTy = TD->getIntPtrType(); 02774 if (isa<PointerType>(MidTy)) MidTy = TD->getIntPtrType(); 02775 if (isa<PointerType>(DstTy)) DstTy = TD->getIntPtrType(); 02776 02777 // Allow free casting and conversion of sizes as long as the sign doesn't 02778 // change... 02779 if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) { 02780 CastType FirstCast = getCastType(SrcTy, MidTy); 02781 CastType SecondCast = getCastType(MidTy, DstTy); 02782 02783 // Capture the effect of these two casts. If the result is a legal cast, 02784 // the CastType is stored here, otherwise a special code is used. 02785 static const unsigned CastResult[] = { 02786 // First cast is noop 02787 0, 1, 2, 3, 02788 // First cast is a truncate 02789 1, 1, 4, 4, // trunc->extend is not safe to eliminate 02790 // First cast is a sign ext 02791 2, 5, 2, 4, // signext->zeroext never ok 02792 // First cast is a zero ext 02793 3, 5, 3, 3, 02794 }; 02795 02796 unsigned Result = CastResult[FirstCast*4+SecondCast]; 02797 switch (Result) { 02798 default: assert(0 && "Illegal table value!"); 02799 case 0: 02800 case 1: 02801 case 2: 02802 case 3: 02803 // FIXME: in the future, when LLVM has explicit sign/zeroextends and 02804 // truncates, we could eliminate more casts. 02805 return (unsigned)getCastType(SrcTy, DstTy) == Result; 02806 case 4: 02807 return false; // Not possible to eliminate this here. 02808 case 5: 02809 // Sign or zero extend followed by truncate is always ok if the result 02810 // is a truncate or noop. 02811 CastType ResultCast = getCastType(SrcTy, DstTy); 02812 if (ResultCast == Noop || ResultCast == Truncate) 02813 return true; 02814 // Otherwise we are still growing the value, we are only safe if the 02815 // result will match the sign/zeroextendness of the result. 02816 return ResultCast == FirstCast; 02817 } 02818 } 02819 return false; 02820 } 02821 02822 static bool ValueRequiresCast(const Value *V, const Type *Ty, TargetData *TD) { 02823 if (V->getType() == Ty || isa<Constant>(V)) return false; 02824 if (const CastInst *CI = dyn_cast<CastInst>(V)) 02825 if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty, 02826 TD)) 02827 return false; 02828 return true; 02829 } 02830 02831 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the 02832 /// InsertBefore instruction. This is specialized a bit to avoid inserting 02833 /// casts that are known to not do anything... 02834 /// 02835 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy, 02836 Instruction *InsertBefore) { 02837 if (V->getType() == DestTy) return V; 02838 if (Constant *C = dyn_cast<Constant>(V)) 02839 return ConstantExpr::getCast(C, DestTy); 02840 02841 CastInst *CI = new CastInst(V, DestTy, V->getName()); 02842 InsertNewInstBefore(CI, *InsertBefore); 02843 return CI; 02844 } 02845 02846 // CastInst simplification 02847 // 02848 Instruction *InstCombiner::visitCastInst(CastInst &CI) { 02849 Value *Src = CI.getOperand(0); 02850 02851 // If the user is casting a value to the same type, eliminate this cast 02852 // instruction... 02853 if (CI.getType() == Src->getType()) 02854 return ReplaceInstUsesWith(CI, Src); 02855 02856 if (isa<UndefValue>(Src)) // cast undef -> undef 02857 return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType())); 02858 02859 // If casting the result of another cast instruction, try to eliminate this 02860 // one! 02861 // 02862 if (CastInst *CSrc = dyn_cast<CastInst>(Src)) { 02863 if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(), 02864 CSrc->getType(), CI.getType(), TD)) { 02865 // This instruction now refers directly to the cast's src operand. This 02866 // has a good chance of making CSrc dead. 02867 CI.setOperand(0, CSrc->getOperand(0)); 02868 return &CI; 02869 } 02870 02871 // If this is an A->B->A cast, and we are dealing with integral types, try 02872 // to convert this into a logical 'and' instruction. 02873 // 02874 if (CSrc->getOperand(0)->getType() == CI.getType() && 02875 CI.getType()->isInteger() && CSrc->getType()->isInteger() && 02876 CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() && 02877 CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){ 02878 assert(CSrc->getType() != Type::ULongTy && 02879 "Cannot have type bigger than ulong!"); 02880 uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1; 02881 Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue); 02882 return BinaryOperator::createAnd(CSrc->getOperand(0), AndOp); 02883 } 02884 } 02885 02886 // If this is a cast to bool, turn it into the appropriate setne instruction. 02887 if (CI.getType() == Type::BoolTy) 02888 return BinaryOperator::createSetNE(CI.getOperand(0), 02889 Constant::getNullValue(CI.getOperand(0)->getType())); 02890 02891 // If casting the result of a getelementptr instruction with no offset, turn 02892 // this into a cast of the original pointer! 02893 // 02894 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) { 02895 bool AllZeroOperands = true; 02896 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) 02897 if (!isa<Constant>(GEP->getOperand(i)) || 02898 !cast<Constant>(GEP->getOperand(i))->isNullValue()) { 02899 AllZeroOperands = false; 02900 break; 02901 } 02902 if (AllZeroOperands) { 02903 CI.setOperand(0, GEP->getOperand(0)); 02904 return &CI; 02905 } 02906 } 02907 02908 // If we are casting a malloc or alloca to a pointer to a type of the same 02909 // size, rewrite the allocation instruction to allocate the "right" type. 02910 // 02911 if (AllocationInst *AI = dyn_cast<AllocationInst>(Src)) 02912 if (AI->hasOneUse() && !AI->isArrayAllocation()) 02913 if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) { 02914 // Get the type really allocated and the type casted to... 02915 const Type *AllocElTy = AI->getAllocatedType(); 02916 const Type *CastElTy = PTy->getElementType(); 02917 if (AllocElTy->isSized() && CastElTy->isSized()) { 02918 unsigned AllocElTySize = TD->getTypeSize(AllocElTy); 02919 unsigned CastElTySize = TD->getTypeSize(CastElTy); 02920 02921 // If the allocation is for an even multiple of the cast type size 02922 if (CastElTySize && (AllocElTySize % CastElTySize == 0)) { 02923 Value *Amt = ConstantUInt::get(Type::UIntTy, 02924 AllocElTySize/CastElTySize); 02925 std::string Name = AI->getName(); AI->setName(""); 02926 AllocationInst *New; 02927 if (isa<MallocInst>(AI)) 02928 New = new MallocInst(CastElTy, Amt, Name); 02929 else 02930 New = new AllocaInst(CastElTy, Amt, Name); 02931 InsertNewInstBefore(New, *AI); 02932 return ReplaceInstUsesWith(CI, New); 02933 } 02934 } 02935 } 02936 02937 if (isa<PHINode>(Src)) 02938 if (Instruction *NV = FoldOpIntoPhi(CI)) 02939 return NV; 02940 02941 // If the source value is an instruction with only this use, we can attempt to 02942 // propagate the cast into the instruction. Also, only handle integral types 02943 // for now. 02944 if (Instruction *SrcI = dyn_cast<Instruction>(Src)) 02945 if (SrcI->hasOneUse() && Src->getType()->isIntegral() && 02946 CI.getType()->isInteger()) { // Don't mess with casts to bool here 02947 const Type *DestTy = CI.getType(); 02948 unsigned SrcBitSize = getTypeSizeInBits(Src->getType()); 02949 unsigned DestBitSize = getTypeSizeInBits(DestTy); 02950 02951 Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0; 02952 Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0; 02953 02954 switch (SrcI->getOpcode()) { 02955 case Instruction::Add: 02956 case Instruction::Mul: 02957 case Instruction::And: 02958 case Instruction::Or: 02959 case Instruction::Xor: 02960 // If we are discarding information, or just changing the sign, rewrite. 02961 if (DestBitSize <= SrcBitSize && DestBitSize != 1) { 02962 // Don't insert two casts if they cannot be eliminated. We allow two 02963 // casts to be inserted if the sizes are the same. This could only be 02964 // converting signedness, which is a noop. 02965 if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy,TD) || 02966 !ValueRequiresCast(Op0, DestTy, TD)) { 02967 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); 02968 Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI); 02969 return BinaryOperator::create(cast<BinaryOperator>(SrcI) 02970 ->getOpcode(), Op0c, Op1c); 02971 } 02972 } 02973 break; 02974 case Instruction::Shl: 02975 // Allow changing the sign of the source operand. Do not allow changing 02976 // the size of the shift, UNLESS the shift amount is a constant. We 02977 // mush not change variable sized shifts to a smaller size, because it 02978 // is undefined to shift more bits out than exist in the value. 02979 if (DestBitSize == SrcBitSize || 02980 (DestBitSize < SrcBitSize && isa<Constant>(Op1))) { 02981 Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI); 02982 return new ShiftInst(Instruction::Shl, Op0c, Op1); 02983 } 02984 break; 02985 } 02986 } 02987 02988 return 0; 02989 } 02990 02991 /// GetSelectFoldableOperands - We want to turn code that looks like this: 02992 /// %C = or %A, %B 02993 /// %D = select %cond, %C, %A 02994 /// into: 02995 /// %C = select %cond, %B, 0 02996 /// %D = or %A, %C 02997 /// 02998 /// Assuming that the specified instruction is an operand to the select, return 02999 /// a bitmask indicating which operands of this instruction are foldable if they 03000 /// equal the other incoming value of the select. 03001 /// 03002 static unsigned GetSelectFoldableOperands(Instruction *I) { 03003 switch (I->getOpcode()) { 03004 case Instruction::Add: 03005 case Instruction::Mul: 03006 case Instruction::And: 03007 case Instruction::Or: 03008 case Instruction::Xor: 03009 return 3; // Can fold through either operand. 03010 case Instruction::Sub: // Can only fold on the amount subtracted. 03011 case Instruction::Shl: // Can only fold on the shift amount. 03012 case Instruction::Shr: 03013 return 1; 03014 default: 03015 return 0; // Cannot fold 03016 } 03017 } 03018 03019 /// GetSelectFoldableConstant - For the same transformation as the previous 03020 /// function, return the identity constant that goes into the select. 03021 static Constant *GetSelectFoldableConstant(Instruction *I) { 03022 switch (I->getOpcode()) { 03023 default: assert(0 && "This cannot happen!"); abort(); 03024 case Instruction::Add: 03025 case Instruction::Sub: 03026 case Instruction::Or: 03027 case Instruction::Xor: 03028 return Constant::getNullValue(I->getType()); 03029 case Instruction::Shl: 03030 case Instruction::Shr: 03031 return Constant::getNullValue(Type::UByteTy); 03032 case Instruction::And: 03033 return ConstantInt::getAllOnesValue(I->getType()); 03034 case Instruction::Mul: 03035 return ConstantInt::get(I->getType(), 1); 03036 } 03037 } 03038 03039 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { 03040 Value *CondVal = SI.getCondition(); 03041 Value *TrueVal = SI.getTrueValue(); 03042 Value *FalseVal = SI.getFalseValue(); 03043 03044 // select true, X, Y -> X 03045 // select false, X, Y -> Y 03046 if (ConstantBool *C = dyn_cast<ConstantBool>(CondVal)) 03047 if (C == ConstantBool::True) 03048 return ReplaceInstUsesWith(SI, TrueVal); 03049 else { 03050 assert(C == ConstantBool::False); 03051 return ReplaceInstUsesWith(SI, FalseVal); 03052 } 03053 03054 // select C, X, X -> X 03055 if (TrueVal == FalseVal) 03056 return ReplaceInstUsesWith(SI, TrueVal); 03057 03058 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 03059 return ReplaceInstUsesWith(SI, FalseVal); 03060 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 03061 return ReplaceInstUsesWith(SI, TrueVal); 03062 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 03063 if (isa<Constant>(TrueVal)) 03064 return ReplaceInstUsesWith(SI, TrueVal); 03065 else 03066 return ReplaceInstUsesWith(SI, FalseVal); 03067 } 03068 03069 if (SI.getType() == Type::BoolTy) 03070 if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) { 03071 if (C == ConstantBool::True) { 03072 // Change: A = select B, true, C --> A = or B, C 03073 return BinaryOperator::createOr(CondVal, FalseVal); 03074 } else { 03075 // Change: A = select B, false, C --> A = and !B, C 03076 Value *NotCond = 03077 InsertNewInstBefore(BinaryOperator::createNot(CondVal, 03078 "not."+CondVal->getName()), SI); 03079 return BinaryOperator::createAnd(NotCond, FalseVal); 03080 } 03081 } else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) { 03082 if (C == ConstantBool::False) { 03083 // Change: A = select B, C, false --> A = and B, C 03084 return BinaryOperator::createAnd(CondVal, TrueVal); 03085 } else { 03086 // Change: A = select B, C, true --> A = or !B, C 03087 Value *NotCond = 03088 InsertNewInstBefore(BinaryOperator::createNot(CondVal, 03089 "not."+CondVal->getName()), SI); 03090 return BinaryOperator::createOr(NotCond, TrueVal); 03091 } 03092 } 03093 03094 // Selecting between two integer constants? 03095 if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal)) 03096 if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) { 03097 // select C, 1, 0 -> cast C to int 03098 if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) { 03099 return new CastInst(CondVal, SI.getType()); 03100 } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) { 03101 // select C, 0, 1 -> cast !C to int 03102 Value *NotCond = 03103 InsertNewInstBefore(BinaryOperator::createNot(CondVal, 03104 "not."+CondVal->getName()), SI); 03105 return new CastInst(NotCond, SI.getType()); 03106 } 03107 03108 // If one of the constants is zero (we know they can't both be) and we 03109 // have a setcc instruction with zero, and we have an 'and' with the 03110 // non-constant value, eliminate this whole mess. This corresponds to 03111 // cases like this: ((X & 27) ? 27 : 0) 03112 if (TrueValC->isNullValue() || FalseValC->isNullValue()) 03113 if (Instruction *IC = dyn_cast<Instruction>(SI.getCondition())) 03114 if ((IC->getOpcode() == Instruction::SetEQ || 03115 IC->getOpcode() == Instruction::SetNE) && 03116 isa<ConstantInt>(IC->getOperand(1)) && 03117 cast<Constant>(IC->getOperand(1))->isNullValue()) 03118 if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0))) 03119 if (ICA->getOpcode() == Instruction::And && 03120 isa<ConstantInt>(ICA->getOperand(1)) && 03121 (ICA->getOperand(1) == TrueValC || 03122 ICA->getOperand(1) == FalseValC) && 03123 isOneBitSet(cast<ConstantInt>(ICA->getOperand(1)))) { 03124 // Okay, now we know that everything is set up, we just don't 03125 // know whether we have a setne or seteq and whether the true or 03126 // false val is the zero. 03127 bool ShouldNotVal = !TrueValC->isNullValue(); 03128 ShouldNotVal ^= IC->getOpcode() == Instruction::SetNE; 03129 Value *V = ICA; 03130 if (ShouldNotVal) 03131 V = InsertNewInstBefore(BinaryOperator::create( 03132 Instruction::Xor, V, ICA->getOperand(1)), SI); 03133 return ReplaceInstUsesWith(SI, V); 03134 } 03135 } 03136 03137 // See if we are selecting two values based on a comparison of the two values. 03138 if (SetCondInst *SCI = dyn_cast<SetCondInst>(CondVal)) { 03139 if (SCI->getOperand(0) == TrueVal && SCI->getOperand(1) == FalseVal) { 03140 // Transform (X == Y) ? X : Y -> Y 03141 if (SCI->getOpcode() == Instruction::SetEQ) 03142 return ReplaceInstUsesWith(SI, FalseVal); 03143 // Transform (X != Y) ? X : Y -> X 03144 if (SCI->getOpcode() == Instruction::SetNE) 03145 return ReplaceInstUsesWith(SI, TrueVal); 03146 // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc. 03147 03148 } else if (SCI->getOperand(0) == FalseVal && SCI->getOperand(1) == TrueVal){ 03149 // Transform (X == Y) ? Y : X -> X 03150 if (SCI->getOpcode() == Instruction::SetEQ) 03151 return ReplaceInstUsesWith(SI, FalseVal); 03152 // Transform (X != Y) ? Y : X -> Y 03153 if (SCI->getOpcode() == Instruction::SetNE) 03154 return ReplaceInstUsesWith(SI, TrueVal); 03155 // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc. 03156 } 03157 } 03158 03159 // See if we can fold the select into one of our operands. 03160 if (SI.getType()->isInteger()) { 03161 // See the comment above GetSelectFoldableOperands for a description of the 03162 // transformation we are doing here. 03163 if (Instruction *TVI = dyn_cast<Instruction>(TrueVal)) 03164 if (TVI->hasOneUse() && TVI->getNumOperands() == 2 && 03165 !isa<Constant>(FalseVal)) 03166 if (unsigned SFO = GetSelectFoldableOperands(TVI)) { 03167 unsigned OpToFold = 0; 03168 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) { 03169 OpToFold = 1; 03170 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) { 03171 OpToFold = 2; 03172 } 03173 03174 if (OpToFold) { 03175 Constant *C = GetSelectFoldableConstant(TVI); 03176 std::string Name = TVI->getName(); TVI->setName(""); 03177 Instruction *NewSel = 03178 new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C, 03179 Name); 03180 InsertNewInstBefore(NewSel, SI); 03181 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI)) 03182 return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel); 03183 else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI)) 03184 return new ShiftInst(SI->getOpcode(), FalseVal, NewSel); 03185 else { 03186 assert(0 && "Unknown instruction!!"); 03187 } 03188 } 03189 } 03190 03191 if (Instruction *FVI = dyn_cast<Instruction>(FalseVal)) 03192 if (FVI->hasOneUse() && FVI->getNumOperands() == 2 && 03193 !isa<Constant>(TrueVal)) 03194 if (unsigned SFO = GetSelectFoldableOperands(FVI)) { 03195 unsigned OpToFold = 0; 03196 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) { 03197 OpToFold = 1; 03198 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) { 03199 OpToFold = 2; 03200 } 03201 03202 if (OpToFold) { 03203 Constant *C = GetSelectFoldableConstant(FVI); 03204 std::string Name = FVI->getName(); FVI->setName(""); 03205 Instruction *NewSel = 03206 new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold), 03207 Name); 03208 InsertNewInstBefore(NewSel, SI); 03209 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI)) 03210 return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel); 03211 else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI)) 03212 return new ShiftInst(SI->getOpcode(), TrueVal, NewSel); 03213 else { 03214 assert(0 && "Unknown instruction!!"); 03215 } 03216 } 03217 } 03218 } 03219 return 0; 03220 } 03221 03222 03223 // CallInst simplification 03224 // 03225 Instruction *InstCombiner::visitCallInst(CallInst &CI) { 03226 // Intrinsics cannot occur in an invoke, so handle them here instead of in 03227 // visitCallSite. 03228 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&CI)) { 03229 bool Changed = false; 03230 03231 // memmove/cpy/set of zero bytes is a noop. 03232 if (Constant *NumBytes = dyn_cast<Constant>(MI->getLength())) { 03233 if (NumBytes->isNullValue()) return EraseInstFromFunction(CI); 03234 03235 // FIXME: Increase alignment here. 03236 03237 if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes)) 03238 if (CI->getRawValue() == 1) { 03239 // Replace the instruction with just byte operations. We would 03240 // transform other cases to loads/stores, but we don't know if 03241 // alignment is sufficient. 03242 } 03243 } 03244 03245 // If we have a memmove and the source operation is a constant global, 03246 // then the source and dest pointers can't alias, so we can change this 03247 // into a call to memcpy. 03248 if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI)) 03249 if (GlobalVariable *GVSrc = dyn_cast<GlobalVariable>(MMI->getSource())) 03250 if (GVSrc->isConstant()) { 03251 Module *M = CI.getParent()->getParent()->getParent(); 03252 Function *MemCpy = M->getOrInsertFunction("llvm.memcpy", 03253 CI.getCalledFunction()->getFunctionType()); 03254 CI.setOperand(0, MemCpy); 03255 Changed = true; 03256 } 03257 03258 if (Changed) return &CI; 03259 } else if (DbgStopPointInst *SPI = dyn_cast<DbgStopPointInst>(&CI)) { 03260 // If this stoppoint is at the same source location as the previous 03261 // stoppoint in the chain, it is not needed. 03262 if (DbgStopPointInst *PrevSPI = 03263 dyn_cast<DbgStopPointInst>(SPI->getChain())) 03264 if (SPI->getLineNo() == PrevSPI->getLineNo() && 03265 SPI->getColNo() == PrevSPI->getColNo()) { 03266 SPI->replaceAllUsesWith(PrevSPI); 03267 return EraseInstFromFunction(CI); 03268 } 03269 } 03270 03271 return visitCallSite(&CI); 03272 } 03273 03274 // InvokeInst simplification 03275 // 03276 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) { 03277 return visitCallSite(&II); 03278 } 03279 03280 // visitCallSite - Improvements for call and invoke instructions. 03281 // 03282 Instruction *InstCombiner::visitCallSite(CallSite CS) { 03283 bool Changed = false; 03284 03285 // If the callee is a constexpr cast of a function, attempt to move the cast 03286 // to the arguments of the call/invoke. 03287 if (transformConstExprCastCall(CS)) return 0; 03288 03289 Value *Callee = CS.getCalledValue(); 03290 03291 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 03292 // This instruction is not reachable, just remove it. We insert a store to 03293 // undef so that we know that this code is not reachable, despite the fact 03294 // that we can't modify the CFG here. 03295 new StoreInst(ConstantBool::True, 03296 UndefValue::get(PointerType::get(Type::BoolTy)), 03297 CS.getInstruction()); 03298 03299 if (!CS.getInstruction()->use_empty()) 03300 CS.getInstruction()-> 03301 replaceAllUsesWith(UndefValue::get(CS.getInstruction()->getType())); 03302 03303 if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { 03304 // Don't break the CFG, insert a dummy cond branch. 03305 new BranchInst(II->getNormalDest(), II->getUnwindDest(), 03306 ConstantBool::True, II); 03307 } 03308 return EraseInstFromFunction(*CS.getInstruction()); 03309 } 03310 03311 const PointerType *PTy = cast<PointerType>(Callee->getType()); 03312 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); 03313 if (FTy->isVarArg()) { 03314 // See if we can optimize any arguments passed through the varargs area of 03315 // the call. 03316 for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(), 03317 E = CS.arg_end(); I != E; ++I) 03318 if (CastInst *CI = dyn_cast<CastInst>(*I)) { 03319 // If this cast does not effect the value passed through the varargs 03320 // area, we can eliminate the use of the cast. 03321 Value *Op = CI->getOperand(0); 03322 if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) { 03323 *I = Op; 03324 Changed = true; 03325 } 03326 } 03327 } 03328 03329 return Changed ? CS.getInstruction() : 0; 03330 } 03331 03332 // transformConstExprCastCall - If the callee is a constexpr cast of a function, 03333 // attempt to move the cast to the arguments of the call/invoke. 03334 // 03335 bool InstCombiner::transformConstExprCastCall(CallSite CS) { 03336 if (!isa<ConstantExpr>(CS.getCalledValue())) return false; 03337 ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue()); 03338 if (CE->getOpcode() != Instruction::Cast || !isa<Function>(CE->getOperand(0))) 03339 return false; 03340 Function *Callee = cast<Function>(CE->getOperand(0)); 03341 Instruction *Caller = CS.getInstruction(); 03342 03343 // Okay, this is a cast from a function to a different type. Unless doing so 03344 // would cause a type conversion of one of our arguments, change this call to 03345 // be a direct call with arguments casted to the appropriate types. 03346 // 03347 const FunctionType *FT = Callee->getFunctionType(); 03348 const Type *OldRetTy = Caller->getType(); 03349 03350 // Check to see if we are changing the return type... 03351 if (OldRetTy != FT->getReturnType()) { 03352 if (Callee->isExternal() && 03353 !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) && 03354 !Caller->use_empty()) 03355 return false; // Cannot transform this return value... 03356 03357 // If the callsite is an invoke instruction, and the return value is used by 03358 // a PHI node in a successor, we cannot change the return type of the call 03359 // because there is no place to put the cast instruction (without breaking 03360 // the critical edge). Bail out in this case. 03361 if (!Caller->use_empty()) 03362 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) 03363 for (Value::use_iterator UI = II->use_begin(), E = II->use_end(); 03364 UI != E; ++UI) 03365 if (PHINode *PN = dyn_cast<PHINode>(*UI)) 03366 if (PN->getParent() == II->getNormalDest() || 03367 PN->getParent() == II->getUnwindDest()) 03368 return false; 03369 } 03370 03371 unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); 03372 unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs); 03373 03374 CallSite::arg_iterator AI = CS.arg_begin(); 03375 for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) { 03376 const Type *ParamTy = FT->getParamType(i); 03377 bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy); 03378 if (Callee->isExternal() && !isConvertible) return false; 03379 } 03380 03381 if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() && 03382 Callee->isExternal()) 03383 return false; // Do not delete arguments unless we have a function body... 03384 03385 // Okay, we decided that this is a safe thing to do: go ahead and start 03386 // inserting cast instructions as necessary... 03387 std::vector<Value*> Args; 03388 Args.reserve(NumActualArgs); 03389 03390 AI = CS.arg_begin(); 03391 for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) { 03392 const Type *ParamTy = FT->getParamType(i); 03393 if ((*AI)->getType() == ParamTy) { 03394 Args.push_back(*AI); 03395 } else { 03396 Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"), 03397 *Caller)); 03398 } 03399 } 03400 03401 // If the function takes more arguments than the call was taking, add them 03402 // now... 03403 for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i) 03404 Args.push_back(Constant::getNullValue(FT->getParamType(i))); 03405 03406 // If we are removing arguments to the function, emit an obnoxious warning... 03407 if (FT->getNumParams() < NumActualArgs) 03408 if (!FT->isVarArg()) { 03409 std::cerr << "WARNING: While resolving call to function '" 03410 << Callee->getName() << "' arguments were dropped!\n"; 03411 } else { 03412 // Add all of the arguments in their promoted form to the arg list... 03413 for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) { 03414 const Type *PTy = getPromotedType((*AI)->getType()); 03415 if (PTy != (*AI)->getType()) { 03416 // Must promote to pass through va_arg area! 03417 Instruction *Cast = new CastInst(*AI, PTy, "tmp"); 03418 InsertNewInstBefore(Cast, *Caller); 03419 Args.push_back(Cast); 03420 } else { 03421 Args.push_back(*AI); 03422 } 03423 } 03424 } 03425 03426 if (FT->getReturnType() == Type::VoidTy) 03427 Caller->setName(""); // Void type should not have a name... 03428 03429 Instruction *NC; 03430 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) { 03431 NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(), 03432 Args, Caller->getName(), Caller); 03433 } else { 03434 NC = new CallInst(Callee, Args, Caller->getName(), Caller); 03435 } 03436 03437 // Insert a cast of the return type as necessary... 03438 Value *NV = NC; 03439 if (Caller->getType() != NV->getType() && !Caller->use_empty()) { 03440 if (NV->getType() != Type::VoidTy) { 03441 NV = NC = new CastInst(NC, Caller->getType(), "tmp"); 03442 03443 // If this is an invoke instruction, we should insert it after the first 03444 // non-phi, instruction in the normal successor block. 03445 if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) { 03446 BasicBlock::iterator I = II->getNormalDest()->begin(); 03447 while (isa<PHINode>(I)) ++I; 03448 InsertNewInstBefore(NC, *I); 03449 } else { 03450 // Otherwise, it's a call, just insert cast right after the call instr 03451 InsertNewInstBefore(NC, *Caller); 03452 } 03453 AddUsersToWorkList(*Caller); 03454 } else { 03455 NV = UndefValue::get(Caller->getType()); 03456 } 03457 } 03458 03459 if (Caller->getType() != Type::VoidTy && !Caller->use_empty()) 03460 Caller->replaceAllUsesWith(NV); 03461 Caller->getParent()->getInstList().erase(Caller); 03462 removeFromWorkList(Caller); 03463 return true; 03464 } 03465 03466 03467 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary" 03468 // operator and they all are only used by the PHI, PHI together their 03469 // inputs, and do the operation once, to the result of the PHI. 03470 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) { 03471 Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0)); 03472 03473 // Scan the instruction, looking for input operations that can be folded away. 03474 // If all input operands to the phi are the same instruction (e.g. a cast from 03475 // the same type or "+42") we can pull the operation through the PHI, reducing 03476 // code size and simplifying code. 03477 Constant *ConstantOp = 0; 03478 const Type *CastSrcTy = 0; 03479 if (isa<CastInst>(FirstInst)) { 03480 CastSrcTy = FirstInst->getOperand(0)->getType(); 03481 } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst)) { 03482 // Can fold binop or shift if the RHS is a constant. 03483 ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1)); 03484 if (ConstantOp == 0) return 0; 03485 } else { 03486 return 0; // Cannot fold this operation. 03487 } 03488 03489 // Check to see if all arguments are the same operation. 03490 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { 03491 if (!isa<Instruction>(PN.getIncomingValue(i))) return 0; 03492 Instruction *I = cast<Instruction>(PN.getIncomingValue(i)); 03493 if (!I->hasOneUse() || I->getOpcode() != FirstInst->getOpcode()) 03494 return 0; 03495 if (CastSrcTy) { 03496 if (I->getOperand(0)->getType() != CastSrcTy) 03497 return 0; // Cast operation must match. 03498 } else if (I->getOperand(1) != ConstantOp) { 03499 return 0; 03500 } 03501 } 03502 03503 // Okay, they are all the same operation. Create a new PHI node of the 03504 // correct type, and PHI together all of the LHS's of the instructions. 03505 PHINode *NewPN = new PHINode(FirstInst->getOperand(0)->getType(), 03506 PN.getName()+".in"); 03507 NewPN->op_reserve(PN.getNumOperands()); 03508 03509 Value *InVal = FirstInst->getOperand(0); 03510 NewPN->addIncoming(InVal, PN.getIncomingBlock(0)); 03511 03512 // Add all operands to the new PHI. 03513 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { 03514 Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0); 03515 if (NewInVal != InVal) 03516 InVal = 0; 03517 NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i)); 03518 } 03519 03520 Value *PhiVal; 03521 if (InVal) { 03522 // The new PHI unions all of the same values together. This is really 03523 // common, so we handle it intelligently here for compile-time speed. 03524 PhiVal = InVal; 03525 delete NewPN; 03526 } else { 03527 InsertNewInstBefore(NewPN, PN); 03528 PhiVal = NewPN; 03529 } 03530 03531 // Insert and return the new operation. 03532 if (isa<CastInst>(FirstInst)) 03533 return new CastInst(PhiVal, PN.getType()); 03534 else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) 03535 return BinaryOperator::create(BinOp->getOpcode(), PhiVal, ConstantOp); 03536 else 03537 return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(), 03538 PhiVal, ConstantOp); 03539 } 03540 03541 // PHINode simplification 03542 // 03543 Instruction *InstCombiner::visitPHINode(PHINode &PN) { 03544 if (Value *V = hasConstantValue(&PN)) { 03545 // If V is an instruction, we have to be certain that it dominates PN. 03546 // However, because we don't have dom info, we can't do a perfect job. 03547 if (Instruction *I = dyn_cast<Instruction>(V)) { 03548 // We know that the instruction dominates the PHI if there are no undef 03549 // values coming in. 03550 if (I->getParent() != &I->getParent()->getParent()->front() || 03551 isa<InvokeInst>(I)) 03552 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 03553 if (isa<UndefValue>(PN.getIncomingValue(i))) { 03554 V = 0; 03555 break; 03556 } 03557 } 03558 03559 if (V) 03560 return ReplaceInstUsesWith(PN, V); 03561 } 03562 03563 // If the only user of this instruction is a cast instruction, and all of the 03564 // incoming values are constants, change this PHI to merge together the casted 03565 // constants. 03566 if (PN.hasOneUse()) 03567 if (CastInst *CI = dyn_cast<CastInst>(PN.use_back())) 03568 if (CI->getType() != PN.getType()) { // noop casts will be folded 03569 bool AllConstant = true; 03570 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 03571 if (!isa<Constant>(PN.getIncomingValue(i))) { 03572 AllConstant = false; 03573 break; 03574 } 03575 if (AllConstant) { 03576 // Make a new PHI with all casted values. 03577 PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN); 03578 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 03579 Constant *OldArg = cast<Constant>(PN.getIncomingValue(i)); 03580 New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()), 03581 PN.getIncomingBlock(i)); 03582 } 03583 03584 // Update the cast instruction. 03585 CI->setOperand(0, New); 03586 WorkList.push_back(CI); // revisit the cast instruction to fold. 03587 WorkList.push_back(New); // Make sure to revisit the new Phi 03588 return &PN; // PN is now dead! 03589 } 03590 } 03591 03592 // If all PHI operands are the same operation, pull them through the PHI, 03593 // reducing code size. 03594 if (isa<Instruction>(PN.getIncomingValue(0)) && 03595 PN.getIncomingValue(0)->hasOneUse()) 03596 if (Instruction *Result = FoldPHIArgOpIntoPHI(PN)) 03597 return Result; 03598 03599 03600 return 0; 03601 } 03602 03603 static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy, 03604 Instruction *InsertPoint, 03605 InstCombiner *IC) { 03606 unsigned PS = IC->getTargetData().getPointerSize(); 03607 const Type *VTy = V->getType(); 03608 if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS) 03609 // We must insert a cast to ensure we sign-extend. 03610 V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(), 03611 V->getName()), *InsertPoint); 03612 return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()), 03613 *InsertPoint); 03614 } 03615 03616 03617 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { 03618 Value *PtrOp = GEP.getOperand(0); 03619 // Is it 'getelementptr %P, long 0' or 'getelementptr %P' 03620 // If so, eliminate the noop. 03621 if (GEP.getNumOperands() == 1) 03622 return ReplaceInstUsesWith(GEP, PtrOp); 03623 03624 if (isa<UndefValue>(GEP.getOperand(0))) 03625 return ReplaceInstUsesWith(GEP, UndefValue::get(GEP.getType())); 03626 03627 bool HasZeroPointerIndex = false; 03628 if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1))) 03629 HasZeroPointerIndex = C->isNullValue(); 03630 03631 if (GEP.getNumOperands() == 2 && HasZeroPointerIndex) 03632 return ReplaceInstUsesWith(GEP, PtrOp); 03633 03634 // Eliminate unneeded casts for indices. 03635 bool MadeChange = false; 03636 gep_type_iterator GTI = gep_type_begin(GEP); 03637 for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI) 03638 if (isa<SequentialType>(*GTI)) { 03639 if (CastInst *CI = dyn_cast<CastInst>(GEP.getOperand(i))) { 03640 Value *Src = CI->getOperand(0); 03641 const Type *SrcTy = Src->getType(); 03642 const Type *DestTy = CI->getType(); 03643 if (Src->getType()->isInteger()) { 03644 if (SrcTy->getPrimitiveSize() == DestTy->getPrimitiveSize()) { 03645 // We can always eliminate a cast from ulong or long to the other. 03646 // We can always eliminate a cast from uint to int or the other on 03647 // 32-bit pointer platforms. 03648 if (DestTy->getPrimitiveSize() >= TD->getPointerSize()) { 03649 MadeChange = true; 03650 GEP.setOperand(i, Src); 03651 } 03652 } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() && 03653 SrcTy->getPrimitiveSize() == 4) { 03654 // We can always eliminate a cast from int to [u]long. We can 03655 // eliminate a cast from uint to [u]long iff the target is a 32-bit 03656 // pointer target. 03657 if (SrcTy->isSigned() || 03658 SrcTy->getPrimitiveSize() >= TD->getPointerSize()) { 03659 MadeChange = true; 03660 GEP.setOperand(i, Src); 03661 } 03662 } 03663 } 03664 } 03665 // If we are using a wider index than needed for this platform, shrink it 03666 // to what we need. If the incoming value needs a cast instruction, 03667 // insert it. This explicit cast can make subsequent optimizations more 03668 // obvious. 03669 Value *Op = GEP.getOperand(i); 03670 if (Op->getType()->getPrimitiveSize() > TD->getPointerSize()) 03671 if (Constant *C = dyn_cast<Constant>(Op)) { 03672 GEP.setOperand(i, ConstantExpr::getCast(C, 03673 TD->getIntPtrType()->getSignedVersion())); 03674 MadeChange = true; 03675 } else { 03676 Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(), 03677 Op->getName()), GEP); 03678 GEP.setOperand(i, Op); 03679 MadeChange = true; 03680 } 03681 03682 // If this is a constant idx, make sure to canonicalize it to be a signed 03683 // operand, otherwise CSE and other optimizations are pessimized. 03684 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op)) { 03685 GEP.setOperand(i, ConstantExpr::getCast(CUI, 03686 CUI->getType()->getSignedVersion())); 03687 MadeChange = true; 03688 } 03689 } 03690 if (MadeChange) return &GEP; 03691 03692 // Combine Indices - If the source pointer to this getelementptr instruction 03693 // is a getelementptr instruction, combine the indices of the two 03694 // getelementptr instructions into a single instruction. 03695 // 03696 std::vector<Value*> SrcGEPOperands; 03697 if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(PtrOp)) { 03698 SrcGEPOperands.assign(Src->op_begin(), Src->op_end()); 03699 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) { 03700 if (CE->getOpcode() == Instruction::GetElementPtr) 03701 SrcGEPOperands.assign(CE->op_begin(), CE->op_end()); 03702 } 03703 03704 if (!SrcGEPOperands.empty()) { 03705 // Note that if our source is a gep chain itself that we wait for that 03706 // chain to be resolved before we perform this transformation. This 03707 // avoids us creating a TON of code in some cases. 03708 // 03709 if (isa<GetElementPtrInst>(SrcGEPOperands[0]) && 03710 cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2) 03711 return 0; // Wait until our source is folded to completion. 03712 03713 std::vector<Value *> Indices; 03714 03715 // Find out whether the last index in the source GEP is a sequential idx. 03716 bool EndsWithSequential = false; 03717 for (gep_type_iterator I = gep_type_begin(*cast<User>(PtrOp)), 03718 E = gep_type_end(*cast<User>(PtrOp)); I != E; ++I) 03719 EndsWithSequential = !isa<StructType>(*I); 03720 03721 // Can we combine the two pointer arithmetics offsets? 03722 if (EndsWithSequential) { 03723 // Replace: gep (gep %P, long B), long A, ... 03724 // With: T = long A+B; gep %P, T, ... 03725 // 03726 Value *Sum, *SO1 = SrcGEPOperands.back(), *GO1 = GEP.getOperand(1); 03727 if (SO1 == Constant::getNullValue(SO1->getType())) { 03728 Sum = GO1; 03729 } else if (GO1 == Constant::getNullValue(GO1->getType())) { 03730 Sum = SO1; 03731 } else { 03732 // If they aren't the same type, convert both to an integer of the 03733 // target's pointer size. 03734 if (SO1->getType() != GO1->getType()) { 03735 if (Constant *SO1C = dyn_cast<Constant>(SO1)) { 03736 SO1 = ConstantExpr::getCast(SO1C, GO1->getType()); 03737 } else if (Constant *GO1C = dyn_cast<Constant>(GO1)) { 03738 GO1 = ConstantExpr::getCast(GO1C, SO1->getType()); 03739 } else { 03740 unsigned PS = TD->getPointerSize(); 03741 if (SO1->getType()->getPrimitiveSize() == PS) { 03742 // Convert GO1 to SO1's type. 03743 GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this); 03744 03745 } else if (GO1->getType()->getPrimitiveSize() == PS) { 03746 // Convert SO1 to GO1's type. 03747 SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this); 03748 } else { 03749 const Type *PT = TD->getIntPtrType(); 03750 SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this); 03751 GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this); 03752 } 03753 } 03754 } 03755 if (isa<Constant>(SO1) && isa<Constant>(GO1)) 03756 Sum = ConstantExpr::getAdd(cast<Constant>(SO1), cast<Constant>(GO1)); 03757 else { 03758 Sum = BinaryOperator::createAdd(SO1, GO1, PtrOp->getName()+".sum"); 03759 InsertNewInstBefore(cast<Instruction>(Sum), GEP); 03760 } 03761 } 03762 03763 // Recycle the GEP we already have if possible. 03764 if (SrcGEPOperands.size() == 2) { 03765 GEP.setOperand(0, SrcGEPOperands[0]); 03766 GEP.setOperand(1, Sum); 03767 return &GEP; 03768 } else { 03769 Indices.insert(Indices.end(), SrcGEPOperands.begin()+1, 03770 SrcGEPOperands.end()-1); 03771 Indices.push_back(Sum); 03772 Indices.insert(Indices.end(), GEP.op_begin()+2, GEP.op_end()); 03773 } 03774 } else if (isa<Constant>(*GEP.idx_begin()) && 03775 cast<Constant>(*GEP.idx_begin())->isNullValue() && 03776 SrcGEPOperands.size() != 1) { 03777 // Otherwise we can do the fold if the first index of the GEP is a zero 03778 Indices.insert(Indices.end(), SrcGEPOperands.begin()+1, 03779 SrcGEPOperands.end()); 03780 Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end()); 03781 } 03782 03783 if (!Indices.empty()) 03784 return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName()); 03785 03786 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) { 03787 // GEP of global variable. If all of the indices for this GEP are 03788 // constants, we can promote this to a constexpr instead of an instruction. 03789 03790 // Scan for nonconstants... 03791 std::vector<Constant*> Indices; 03792 User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); 03793 for (; I != E && isa<Constant>(*I); ++I) 03794 Indices.push_back(cast<Constant>(*I)); 03795 03796 if (I == E) { // If they are all constants... 03797 Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices); 03798 03799 // Replace all uses of the GEP with the new constexpr... 03800 return ReplaceInstUsesWith(GEP, CE); 03801 } 03802 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) { 03803 if (CE->getOpcode() == Instruction::Cast) { 03804 if (HasZeroPointerIndex) { 03805 // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ... 03806 // into : GEP [10 x ubyte]* X, long 0, ... 03807 // 03808 // This occurs when the program declares an array extern like "int X[];" 03809 // 03810 Constant *X = CE->getOperand(0); 03811 const PointerType *CPTy = cast<PointerType>(CE->getType()); 03812 if (const PointerType *XTy = dyn_cast<PointerType>(X->getType())) 03813 if (const ArrayType *XATy = 03814 dyn_cast<ArrayType>(XTy->getElementType())) 03815 if (const ArrayType *CATy = 03816 dyn_cast<ArrayType>(CPTy->getElementType())) 03817 if (CATy->getElementType() == XATy->getElementType()) { 03818 // At this point, we know that the cast source type is a pointer 03819 // to an array of the same type as the destination pointer 03820 // array. Because the array type is never stepped over (there 03821 // is a leading zero) we can fold the cast into this GEP. 03822 GEP.setOperand(0, X); 03823 return &GEP; 03824 } 03825 } else if (GEP.getNumOperands() == 2) { 03826 // Transform things like: 03827 // %t = getelementptr ubyte* cast ([2 x sbyte]* %str to ubyte*), uint %V 03828 // into: %t1 = getelementptr [2 x sbyte*]* %str, int 0, uint %V; cast 03829 Constant *X = CE->getOperand(0); 03830 const Type *SrcElTy = cast<PointerType>(X->getType())->getElementType(); 03831 const Type *ResElTy =cast<PointerType>(CE->getType())->getElementType(); 03832 if (isa<ArrayType>(SrcElTy) && 03833 TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) == 03834 TD->getTypeSize(ResElTy)) { 03835 Value *V = InsertNewInstBefore( 03836 new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy), 03837 GEP.getOperand(1), GEP.getName()), GEP); 03838 return new CastInst(V, GEP.getType()); 03839 } 03840 } 03841 } 03842 } 03843 03844 return 0; 03845 } 03846 03847 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) { 03848 // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1 03849 if (AI.isArrayAllocation()) // Check C != 1 03850 if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) { 03851 const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue()); 03852 AllocationInst *New = 0; 03853 03854 // Create and insert the replacement instruction... 03855 if (isa<MallocInst>(AI)) 03856 New = new MallocInst(NewTy, 0, AI.getName()); 03857 else { 03858 assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!"); 03859 New = new AllocaInst(NewTy, 0, AI.getName()); 03860 } 03861 03862 InsertNewInstBefore(New, AI); 03863 03864 // Scan to the end of the allocation instructions, to skip over a block of 03865 // allocas if possible... 03866 // 03867 BasicBlock::iterator It = New; 03868 while (isa<AllocationInst>(*It)) ++It; 03869 03870 // Now that I is pointing to the first non-allocation-inst in the block, 03871 // insert our getelementptr instruction... 03872 // 03873 std::vector<Value*> Idx(2, Constant::getNullValue(Type::IntTy)); 03874 Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It); 03875 03876 // Now make everything use the getelementptr instead of the original 03877 // allocation. 03878 return ReplaceInstUsesWith(AI, V); 03879 } else if (isa<UndefValue>(AI.getArraySize())) { 03880 return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType())); 03881 } 03882 03883 // If alloca'ing a zero byte object, replace the alloca with a null pointer. 03884 // Note that we only do this for alloca's, because malloc should allocate and 03885 // return a unique pointer, even for a zero byte allocation. 03886 if (isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized() && 03887 TD->getTypeSize(AI.getAllocatedType()) == 0) 03888 return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType())); 03889 03890 return 0; 03891 } 03892 03893 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) { 03894 Value *Op = FI.getOperand(0); 03895 03896 // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X 03897 if (CastInst *CI = dyn_cast<CastInst>(Op)) 03898 if (isa<PointerType>(CI->getOperand(0)->getType())) { 03899 FI.setOperand(0, CI->getOperand(0)); 03900 return &FI; 03901 } 03902 03903 // free undef -> unreachable. 03904 if (isa<UndefValue>(Op)) { 03905 // Insert a new store to null because we cannot modify the CFG here. 03906 new StoreInst(ConstantBool::True, 03907 UndefValue::get(PointerType::get(Type::BoolTy)), &FI); 03908 return EraseInstFromFunction(FI); 03909 } 03910 03911 // If we have 'free null' delete the instruction. This can happen in stl code 03912 // when lots of inlining happens. 03913 if (isa<ConstantPointerNull>(Op)) 03914 return EraseInstFromFunction(FI); 03915 03916 return 0; 03917 } 03918 03919 03920 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr 03921 /// constantexpr, return the constant value being addressed by the constant 03922 /// expression, or null if something is funny. 03923 /// 03924 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) { 03925 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 03926 return 0; // Do not allow stepping over the value! 03927 03928 // Loop over all of the operands, tracking down which value we are 03929 // addressing... 03930 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 03931 for (++I; I != E; ++I) 03932 if (const StructType *STy = dyn_cast<StructType>(*I)) { 03933 ConstantUInt *CU = cast<ConstantUInt>(I.getOperand()); 03934 assert(CU->getValue() < STy->getNumElements() && 03935 "Struct index out of range!"); 03936 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 03937 C = CS->getOperand(CU->getValue()); 03938 } else if (isa<ConstantAggregateZero>(C)) { 03939 C = Constant::getNullValue(STy->getElementType(CU->getValue())); 03940 } else if (isa<UndefValue>(C)) { 03941 C = UndefValue::get(STy->getElementType(CU->getValue())); 03942 } else { 03943 return 0; 03944 } 03945 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 03946 const ArrayType *ATy = cast<ArrayType>(*I); 03947 if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0; 03948 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 03949 C = CA->getOperand(CI->getRawValue()); 03950 else if (isa<ConstantAggregateZero>(C)) 03951 C = Constant::getNullValue(ATy->getElementType()); 03952 else if (isa<UndefValue>(C)) 03953 C = UndefValue::get(ATy->getElementType()); 03954 else 03955 return 0; 03956 } else { 03957 return 0; 03958 } 03959 return C; 03960 } 03961 03962 static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) { 03963 User *CI = cast<User>(LI.getOperand(0)); 03964 03965 const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType(); 03966 if (const PointerType *SrcTy = 03967 dyn_cast<PointerType>(CI->getOperand(0)->getType())) { 03968 const Type *SrcPTy = SrcTy->getElementType(); 03969 if (SrcPTy->isSized() && DestPTy->isSized() && 03970 IC.getTargetData().getTypeSize(SrcPTy) == 03971 IC.getTargetData().getTypeSize(DestPTy) && 03972 (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) && 03973 (DestPTy->isInteger() || isa<PointerType>(DestPTy))) { 03974 // Okay, we are casting from one integer or pointer type to another of 03975 // the same size. Instead of casting the pointer before the load, cast 03976 // the result of the loaded value. 03977 Value *NewLoad = IC.InsertNewInstBefore(new LoadInst(CI->getOperand(0), 03978 CI->getName(), 03979 LI.isVolatile()),LI); 03980 // Now cast the result of the load. 03981 return new CastInst(NewLoad, LI.getType()); 03982 } 03983 } 03984 return 0; 03985 } 03986 03987 /// isSafeToLoadUnconditionally - Return true if we know that executing a load 03988 /// from this value cannot trap. If it is not obviously safe to load from the 03989 /// specified pointer, we do a quick local scan of the basic block containing 03990 /// ScanFrom, to determine if the address is already accessed. 03991 static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) { 03992 // If it is an alloca or global variable, it is always safe to load from. 03993 if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true; 03994 03995 // Otherwise, be a little bit agressive by scanning the local block where we 03996 // want to check to see if the pointer is already being loaded or stored 03997 // from/to. If so, the previous load or store would have already trapped, 03998 // so there is no harm doing an extra load (also, CSE will later eliminate 03999 // the load entirely). 04000 BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); 04001 04002 while (BBI != E) { 04003 --BBI; 04004 04005 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 04006 if (LI->getOperand(0) == V) return true; 04007 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 04008 if (SI->getOperand(1) == V) return true; 04009 04010 } 04011 return false; 04012 } 04013 04014 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { 04015 Value *Op = LI.getOperand(0); 04016 04017 if (Constant *C = dyn_cast<Constant>(Op)) { 04018 if ((C->isNullValue() || isa<UndefValue>(C)) && 04019 !LI.isVolatile()) { // load null/undef -> undef 04020 // Insert a new store to null instruction before the load to indicate that 04021 // this code is not reachable. We do this instead of inserting an 04022 // unreachable instruction directly because we cannot modify the CFG. 04023 new StoreInst(UndefValue::get(LI.getType()), C, &LI); 04024 return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType())); 04025 } 04026 04027 // Instcombine load (constant global) into the value loaded. 04028 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op)) 04029 if (GV->isConstant() && !GV->isExternal()) 04030 return ReplaceInstUsesWith(LI, GV->getInitializer()); 04031 04032 // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded. 04033 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op)) 04034 if (CE->getOpcode() == Instruction::GetElementPtr) { 04035 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 04036 if (GV->isConstant() && !GV->isExternal()) 04037 if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE)) 04038 return ReplaceInstUsesWith(LI, V); 04039 } else if (CE->getOpcode() == Instruction::Cast) { 04040 if (Instruction *Res = InstCombineLoadCast(*this, LI)) 04041 return Res; 04042 } 04043 } 04044 04045 // load (cast X) --> cast (load X) iff safe 04046 if (CastInst *CI = dyn_cast<CastInst>(Op)) 04047 if (Instruction *Res = InstCombineLoadCast(*this, LI)) 04048 return Res; 04049 04050 if (!LI.isVolatile() && Op->hasOneUse()) { 04051 // Change select and PHI nodes to select values instead of addresses: this 04052 // helps alias analysis out a lot, allows many others simplifications, and 04053 // exposes redundancy in the code. 04054 // 04055 // Note that we cannot do the transformation unless we know that the 04056 // introduced loads cannot trap! Something like this is valid as long as 04057 // the condition is always false: load (select bool %C, int* null, int* %G), 04058 // but it would not be valid if we transformed it to load from null 04059 // unconditionally. 04060 // 04061 if (SelectInst *SI = dyn_cast<SelectInst>(Op)) { 04062 // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2). 04063 if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) && 04064 isSafeToLoadUnconditionally(SI->getOperand(2), SI)) { 04065 Value *V1 = InsertNewInstBefore(new LoadInst(SI->getOperand(1), 04066 SI->getOperand(1)->getName()+".val"), LI); 04067 Value *V2 = InsertNewInstBefore(new LoadInst(SI->getOperand(2), 04068 SI->getOperand(2)->getName()+".val"), LI); 04069 return new SelectInst(SI->getCondition(), V1, V2); 04070 } 04071 04072 // load (select (cond, null, P)) -> load P 04073 if (Constant *C = dyn_cast<Constant>(SI->getOperand(1))) 04074 if (C->isNullValue()) { 04075 LI.setOperand(0, SI->getOperand(2)); 04076 return &LI; 04077 } 04078 04079 // load (select (cond, P, null)) -> load P 04080 if (Constant *C = dyn_cast<Constant>(SI->getOperand(2))) 04081 if (C->isNullValue()) { 04082 LI.setOperand(0, SI->getOperand(1)); 04083 return &LI; 04084 } 04085 04086 } else if (PHINode *PN = dyn_cast<PHINode>(Op)) { 04087 // load (phi (&V1, &V2, &V3)) --> phi(load &V1, load &V2, load &V3) 04088 bool Safe = PN->getParent() == LI.getParent(); 04089 04090 // Scan all of the instructions between the PHI and the load to make 04091 // sure there are no instructions that might possibly alter the value 04092 // loaded from the PHI. 04093 if (Safe) { 04094 BasicBlock::iterator I = &LI; 04095 for (--I; !isa<PHINode>(I); --I) 04096 if (isa<StoreInst>(I) || isa<CallInst>(I)) { 04097 Safe = false; 04098 break; 04099 } 04100 } 04101 04102 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e && Safe; ++i) 04103 if (!isSafeToLoadUnconditionally(PN->getIncomingValue(i), 04104 PN->getIncomingBlock(i)->getTerminator())) 04105 Safe = false; 04106 04107 if (Safe) { 04108 // Create the PHI. 04109 PHINode *NewPN = new PHINode(LI.getType(), PN->getName()); 04110 InsertNewInstBefore(NewPN, *PN); 04111 std::map<BasicBlock*,Value*> LoadMap; // Don't insert duplicate loads 04112 04113 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 04114 BasicBlock *BB = PN->getIncomingBlock(i); 04115 Value *&TheLoad = LoadMap[BB]; 04116 if (TheLoad == 0) { 04117 Value *InVal = PN->getIncomingValue(i); 04118 TheLoad = InsertNewInstBefore(new LoadInst(InVal, 04119 InVal->getName()+".val"), 04120 *BB->getTerminator()); 04121 } 04122 NewPN->addIncoming(TheLoad, BB); 04123 } 04124 return ReplaceInstUsesWith(LI, NewPN); 04125 } 04126 } 04127 } 04128 return 0; 04129 } 04130 04131 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) { 04132 // Change br (not X), label True, label False to: br X, label False, True 04133 Value *X; 04134 BasicBlock *TrueDest; 04135 BasicBlock *FalseDest; 04136 if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) && 04137 !isa<Constant>(X)) { 04138 // Swap Destinations and condition... 04139 BI.setCondition(X); 04140 BI.setSuccessor(0, FalseDest); 04141 BI.setSuccessor(1, TrueDest); 04142 return &BI; 04143 } 04144 04145 // Cannonicalize setne -> seteq 04146 Instruction::BinaryOps Op; Value *Y; 04147 if (match(&BI, m_Br(m_SetCond(Op, m_Value(X), m_Value(Y)), 04148 TrueDest, FalseDest))) 04149 if ((Op == Instruction::SetNE || Op == Instruction::SetLE || 04150 Op == Instruction::SetGE) && BI.getCondition()->hasOneUse()) { 04151 SetCondInst *I = cast<SetCondInst>(BI.getCondition()); 04152 std::string Name = I->getName(); I->setName(""); 04153 Instruction::BinaryOps NewOpcode = SetCondInst::getInverseCondition(Op); 04154 Value *NewSCC = BinaryOperator::create(NewOpcode, X, Y, Name, I); 04155 // Swap Destinations and condition... 04156 BI.setCondition(NewSCC); 04157 BI.setSuccessor(0, FalseDest); 04158 BI.setSuccessor(1, TrueDest); 04159 removeFromWorkList(I); 04160 I->getParent()->getInstList().erase(I); 04161 WorkList.push_back(cast<Instruction>(NewSCC)); 04162 return &BI; 04163 } 04164 04165 return 0; 04166 } 04167 04168 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { 04169 Value *Cond = SI.getCondition(); 04170 if (Instruction *I = dyn_cast<Instruction>(Cond)) { 04171 if (I->getOpcode() == Instruction::Add) 04172 if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) { 04173 // change 'switch (X+4) case 1:' into 'switch (X) case -3' 04174 for (unsigned i = 2, e = SI.getNumOperands(); i != e; i += 2) 04175 SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)), 04176 AddRHS)); 04177 SI.setOperand(0, I->getOperand(0)); 04178 WorkList.push_back(I); 04179 return &SI; 04180 } 04181 } 04182 return 0; 04183 } 04184 04185 04186 void InstCombiner::removeFromWorkList(Instruction *I) { 04187 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I), 04188 WorkList.end()); 04189 } 04190 04191 bool InstCombiner::runOnFunction(Function &F) { 04192 bool Changed = false; 04193 TD = &getAnalysis<TargetData>(); 04194 04195 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 04196 WorkList.push_back(&*i); 04197 04198 04199 while (!WorkList.empty()) { 04200 Instruction *I = WorkList.back(); // Get an instruction from the worklist 04201 WorkList.pop_back(); 04202 04203 // Check to see if we can DCE or ConstantPropagate the instruction... 04204 // Check to see if we can DIE the instruction... 04205 if (isInstructionTriviallyDead(I)) { 04206 // Add operands to the worklist... 04207 if (I->getNumOperands() < 4) 04208 AddUsesToWorkList(*I); 04209 ++NumDeadInst; 04210 04211 I->getParent()->getInstList().erase(I); 04212 removeFromWorkList(I); 04213 continue; 04214 } 04215 04216 // Instruction isn't dead, see if we can constant propagate it... 04217 if (Constant *C = ConstantFoldInstruction(I)) { 04218 if (isa<GetElementPtrInst>(I) && 04219 cast<Constant>(I->getOperand(0))->isNullValue() && 04220 !isa<ConstantPointerNull>(C)) { 04221 // If this is a constant expr gep that is effectively computing an 04222 // "offsetof", fold it into 'cast int X to T*' instead of 'gep 0, 0, 12' 04223 bool isFoldableGEP = true; 04224 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) 04225 if (!isa<ConstantInt>(I->getOperand(i))) 04226 isFoldableGEP = false; 04227 if (isFoldableGEP) { 04228 uint64_t Offset = TD->getIndexedOffset(I->getOperand(0)->getType(), 04229 std::vector<Value*>(I->op_begin()+1, I->op_end())); 04230 C = ConstantUInt::get(Type::ULongTy, Offset); 04231 C = ConstantExpr::getCast(C, TD->getIntPtrType()); 04232 C = ConstantExpr::getCast(C, I->getType()); 04233 } 04234 } 04235 04236 // Add operands to the worklist... 04237 AddUsesToWorkList(*I); 04238 ReplaceInstUsesWith(*I, C); 04239 04240 ++NumConstProp; 04241 I->getParent()->getInstList().erase(I); 04242 removeFromWorkList(I); 04243 continue; 04244 } 04245 04246 // Now that we have an instruction, try combining it to simplify it... 04247 if (Instruction *Result = visit(*I)) { 04248 ++NumCombined; 04249 // Should we replace the old instruction with a new one? 04250 if (Result != I) { 04251 DEBUG(std::cerr << "IC: Old = " << *I 04252 << " New = " << *Result); 04253 04254 // Everything uses the new instruction now. 04255 I->replaceAllUsesWith(Result); 04256 04257 // Push the new instruction and any users onto the worklist. 04258 WorkList.push_back(Result); 04259 AddUsersToWorkList(*Result); 04260 04261 // Move the name to the new instruction first... 04262 std::string OldName = I->getName(); I->setName(""); 04263 Result->setName(OldName); 04264 04265 // Insert the new instruction into the basic block... 04266 BasicBlock *InstParent = I->getParent(); 04267 BasicBlock::iterator InsertPos = I; 04268 04269 if (!isa<PHINode>(Result)) // If combining a PHI, don't insert 04270 while (isa<PHINode>(InsertPos)) // middle of a block of PHIs. 04271 ++InsertPos; 04272 04273 InstParent->getInstList().insert(InsertPos, Result); 04274 04275 // Make sure that we reprocess all operands now that we reduced their 04276 // use counts. 04277 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 04278 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i))) 04279 WorkList.push_back(OpI); 04280 04281 // Instructions can end up on the worklist more than once. Make sure 04282 // we do not process an instruction that has been deleted. 04283 removeFromWorkList(I); 04284 04285 // Erase the old instruction. 04286 InstParent->getInstList().erase(I); 04287 } else { 04288 DEBUG(std::cerr << "IC: MOD = " << *I); 04289 04290 // If the instruction was modified, it's possible that it is now dead. 04291 // if so, remove it. 04292 if (isInstructionTriviallyDead(I)) { 04293 // Make sure we process all operands now that we are reducing their 04294 // use counts. 04295 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 04296 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i))) 04297 WorkList.push_back(OpI); 04298 04299 // Instructions may end up in the worklist more than once. Erase all 04300 // occurrances of this instruction. 04301 removeFromWorkList(I); 04302 I->getParent()->getInstList().erase(I); 04303 } else { 04304 WorkList.push_back(Result); 04305 AddUsersToWorkList(*Result); 04306 } 04307 } 04308 Changed = true; 04309 } 04310 } 04311 04312 return Changed; 04313 } 04314 04315 FunctionPass *llvm::createInstructionCombiningPass() { 04316 return new InstCombiner(); 04317 } 04318