InstructionSimplify.cpp revision 280031
1251881Speter//===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 2251881Speter// 3251881Speter// The LLVM Compiler Infrastructure 4251881Speter// 5251881Speter// This file is distributed under the University of Illinois Open Source 6251881Speter// License. See LICENSE.TXT for details. 7251881Speter// 8251881Speter//===----------------------------------------------------------------------===// 9251881Speter// 10251881Speter// This file implements routines for folding instructions into simpler forms 11251881Speter// that do not require creating new instructions. This does constant folding 12251881Speter// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 13251881Speter// returning a constant ("and i32 %x, 0" -> "0") or an already existing value 14251881Speter// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 15251881Speter// simplified: This is usually true and assuming it simplifies the logic (if 16251881Speter// they have not been simplified then results are correct but maybe suboptimal). 17251881Speter// 18251881Speter//===----------------------------------------------------------------------===// 19251881Speter 20251881Speter#include "llvm/Analysis/InstructionSimplify.h" 21251881Speter#include "llvm/ADT/SetVector.h" 22251881Speter#include "llvm/ADT/Statistic.h" 23251881Speter#include "llvm/Analysis/AliasAnalysis.h" 24251881Speter#include "llvm/Analysis/ConstantFolding.h" 25251881Speter#include "llvm/Analysis/MemoryBuiltins.h" 26251881Speter#include "llvm/Analysis/ValueTracking.h" 27251881Speter#include "llvm/IR/ConstantRange.h" 28251881Speter#include "llvm/IR/DataLayout.h" 29251881Speter#include "llvm/IR/Dominators.h" 30251881Speter#include "llvm/IR/GetElementPtrTypeIterator.h" 31251881Speter#include "llvm/IR/GlobalAlias.h" 32251881Speter#include "llvm/IR/Operator.h" 33251881Speter#include "llvm/IR/PatternMatch.h" 34251881Speter#include "llvm/IR/ValueHandle.h" 35251881Speter#include <algorithm> 36251881Speterusing namespace llvm; 37251881Speterusing namespace llvm::PatternMatch; 38251881Speter 39251881Speter#define DEBUG_TYPE "instsimplify" 40251881Speter 41251881Speterenum { RecursionLimit = 3 }; 42251881Speter 43251881SpeterSTATISTIC(NumExpand, "Number of expansions"); 44251881SpeterSTATISTIC(NumReassoc, "Number of reassociations"); 45251881Speter 46251881Speternamespace { 47251881Speterstruct Query { 48251881Speter const DataLayout *DL; 49251881Speter const TargetLibraryInfo *TLI; 50251881Speter const DominatorTree *DT; 51251881Speter AssumptionCache *AC; 52251881Speter const Instruction *CxtI; 53251881Speter 54251881Speter Query(const DataLayout *DL, const TargetLibraryInfo *tli, 55251881Speter const DominatorTree *dt, AssumptionCache *ac = nullptr, 56251881Speter const Instruction *cxti = nullptr) 57251881Speter : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {} 58251881Speter}; 59251881Speter} // end anonymous namespace 60251881Speter 61251881Speterstatic Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); 62251881Speterstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &, 63251881Speter unsigned); 64251881Speterstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &, 65251881Speter unsigned); 66251881Speterstatic Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned); 67251881Speterstatic Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned); 68251881Speterstatic Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned); 69251881Speter 70251881Speter/// getFalse - For a boolean type, or a vector of boolean type, return false, or 71251881Speter/// a vector with every element false, as appropriate for the type. 72251881Speterstatic Constant *getFalse(Type *Ty) { 73251881Speter assert(Ty->getScalarType()->isIntegerTy(1) && 74251881Speter "Expected i1 type or a vector of i1!"); 75251881Speter return Constant::getNullValue(Ty); 76251881Speter} 77251881Speter 78251881Speter/// getTrue - For a boolean type, or a vector of boolean type, return true, or 79251881Speter/// a vector with every element true, as appropriate for the type. 80251881Speterstatic Constant *getTrue(Type *Ty) { 81251881Speter assert(Ty->getScalarType()->isIntegerTy(1) && 82251881Speter "Expected i1 type or a vector of i1!"); 83251881Speter return Constant::getAllOnesValue(Ty); 84251881Speter} 85251881Speter 86251881Speter/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? 87251881Speterstatic bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, 88251881Speter Value *RHS) { 89251881Speter CmpInst *Cmp = dyn_cast<CmpInst>(V); 90251881Speter if (!Cmp) 91251881Speter return false; 92251881Speter CmpInst::Predicate CPred = Cmp->getPredicate(); 93251881Speter Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); 94251881Speter if (CPred == Pred && CLHS == LHS && CRHS == RHS) 95251881Speter return true; 96251881Speter return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && 97251881Speter CRHS == LHS; 98251881Speter} 99251881Speter 100251881Speter/// ValueDominatesPHI - Does the given value dominate the specified phi node? 101251881Speterstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 102251881Speter Instruction *I = dyn_cast<Instruction>(V); 103251881Speter if (!I) 104251881Speter // Arguments and constants dominate all instructions. 105251881Speter return true; 106251881Speter 107251881Speter // If we are processing instructions (and/or basic blocks) that have not been 108251881Speter // fully added to a function, the parent nodes may still be null. Simply 109251881Speter // return the conservative answer in these cases. 110251881Speter if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) 111251881Speter return false; 112251881Speter 113251881Speter // If we have a DominatorTree then do a precise test. 114251881Speter if (DT) { 115251881Speter if (!DT->isReachableFromEntry(P->getParent())) 116251881Speter return true; 117251881Speter if (!DT->isReachableFromEntry(I->getParent())) 118251881Speter return false; 119251881Speter return DT->dominates(I, P); 120251881Speter } 121251881Speter 122251881Speter // Otherwise, if the instruction is in the entry block, and is not an invoke, 123251881Speter // then it obviously dominates all phi nodes. 124251881Speter if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 125251881Speter !isa<InvokeInst>(I)) 126251881Speter return true; 127251881Speter 128251881Speter return false; 129251881Speter} 130251881Speter 131251881Speter/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 132251881Speter/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 133251881Speter/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 134251881Speter/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 135251881Speter/// Returns the simplified value, or null if no simplification was performed. 136251881Speterstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 137251881Speter unsigned OpcToExpand, const Query &Q, 138251881Speter unsigned MaxRecurse) { 139251881Speter Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 140251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 141251881Speter if (!MaxRecurse--) 142251881Speter return nullptr; 143251881Speter 144251881Speter // Check whether the expression has the form "(A op' B) op C". 145251881Speter if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 146251881Speter if (Op0->getOpcode() == OpcodeToExpand) { 147251881Speter // It does! Try turning it into "(A op C) op' (B op C)". 148251881Speter Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 149251881Speter // Do "A op C" and "B op C" both simplify? 150251881Speter if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) 151251881Speter if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 152251881Speter // They do! Return "L op' R" if it simplifies or is already available. 153251881Speter // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 154251881Speter if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 155251881Speter && L == B && R == A)) { 156251881Speter ++NumExpand; 157251881Speter return LHS; 158251881Speter } 159251881Speter // Otherwise return "L op' R" if it simplifies. 160251881Speter if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 161251881Speter ++NumExpand; 162251881Speter return V; 163251881Speter } 164251881Speter } 165251881Speter } 166251881Speter 167251881Speter // Check whether the expression has the form "A op (B op' C)". 168251881Speter if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 169251881Speter if (Op1->getOpcode() == OpcodeToExpand) { 170251881Speter // It does! Try turning it into "(A op B) op' (A op C)". 171251881Speter Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 172251881Speter // Do "A op B" and "A op C" both simplify? 173251881Speter if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) 174251881Speter if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { 175251881Speter // They do! Return "L op' R" if it simplifies or is already available. 176251881Speter // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 177251881Speter if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 178251881Speter && L == C && R == B)) { 179251881Speter ++NumExpand; 180251881Speter return RHS; 181251881Speter } 182251881Speter // Otherwise return "L op' R" if it simplifies. 183251881Speter if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 184251881Speter ++NumExpand; 185251881Speter return V; 186251881Speter } 187251881Speter } 188251881Speter } 189251881Speter 190251881Speter return nullptr; 191251881Speter} 192251881Speter 193251881Speter/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 194251881Speter/// operations. Returns the simpler value, or null if none was found. 195251881Speterstatic Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 196251881Speter const Query &Q, unsigned MaxRecurse) { 197251881Speter Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 198251881Speter assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 199251881Speter 200251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 201251881Speter if (!MaxRecurse--) 202251881Speter return nullptr; 203251881Speter 204251881Speter BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 205251881Speter BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 206251881Speter 207251881Speter // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 208251881Speter if (Op0 && Op0->getOpcode() == Opcode) { 209251881Speter Value *A = Op0->getOperand(0); 210251881Speter Value *B = Op0->getOperand(1); 211251881Speter Value *C = RHS; 212251881Speter 213251881Speter // Does "B op C" simplify? 214251881Speter if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 215251881Speter // It does! Return "A op V" if it simplifies or is already available. 216251881Speter // If V equals B then "A op V" is just the LHS. 217251881Speter if (V == B) return LHS; 218251881Speter // Otherwise return "A op V" if it simplifies. 219251881Speter if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) { 220251881Speter ++NumReassoc; 221251881Speter return W; 222251881Speter } 223251881Speter } 224251881Speter } 225251881Speter 226251881Speter // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 227251881Speter if (Op1 && Op1->getOpcode() == Opcode) { 228251881Speter Value *A = LHS; 229251881Speter Value *B = Op1->getOperand(0); 230251881Speter Value *C = Op1->getOperand(1); 231251881Speter 232251881Speter // Does "A op B" simplify? 233251881Speter if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) { 234251881Speter // It does! Return "V op C" if it simplifies or is already available. 235251881Speter // If V equals B then "V op C" is just the RHS. 236251881Speter if (V == B) return RHS; 237251881Speter // Otherwise return "V op C" if it simplifies. 238251881Speter if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) { 239251881Speter ++NumReassoc; 240251881Speter return W; 241251881Speter } 242251881Speter } 243251881Speter } 244251881Speter 245251881Speter // The remaining transforms require commutativity as well as associativity. 246251881Speter if (!Instruction::isCommutative(Opcode)) 247251881Speter return nullptr; 248251881Speter 249251881Speter // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 250251881Speter if (Op0 && Op0->getOpcode() == Opcode) { 251251881Speter Value *A = Op0->getOperand(0); 252251881Speter Value *B = Op0->getOperand(1); 253251881Speter Value *C = RHS; 254251881Speter 255251881Speter // Does "C op A" simplify? 256251881Speter if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 257251881Speter // It does! Return "V op B" if it simplifies or is already available. 258251881Speter // If V equals A then "V op B" is just the LHS. 259251881Speter if (V == A) return LHS; 260251881Speter // Otherwise return "V op B" if it simplifies. 261251881Speter if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) { 262251881Speter ++NumReassoc; 263251881Speter return W; 264251881Speter } 265251881Speter } 266251881Speter } 267251881Speter 268251881Speter // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 269251881Speter if (Op1 && Op1->getOpcode() == Opcode) { 270251881Speter Value *A = LHS; 271251881Speter Value *B = Op1->getOperand(0); 272251881Speter Value *C = Op1->getOperand(1); 273251881Speter 274251881Speter // Does "C op A" simplify? 275251881Speter if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 276251881Speter // It does! Return "B op V" if it simplifies or is already available. 277251881Speter // If V equals C then "B op V" is just the RHS. 278251881Speter if (V == C) return RHS; 279251881Speter // Otherwise return "B op V" if it simplifies. 280251881Speter if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) { 281251881Speter ++NumReassoc; 282251881Speter return W; 283251881Speter } 284251881Speter } 285251881Speter } 286251881Speter 287251881Speter return nullptr; 288251881Speter} 289251881Speter 290251881Speter/// ThreadBinOpOverSelect - In the case of a binary operation with a select 291251881Speter/// instruction as an operand, try to simplify the binop by seeing whether 292251881Speter/// evaluating it on both branches of the select results in the same value. 293251881Speter/// Returns the common value if so, otherwise returns null. 294251881Speterstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 295251881Speter const Query &Q, unsigned MaxRecurse) { 296251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 297251881Speter if (!MaxRecurse--) 298251881Speter return nullptr; 299251881Speter 300251881Speter SelectInst *SI; 301251881Speter if (isa<SelectInst>(LHS)) { 302251881Speter SI = cast<SelectInst>(LHS); 303251881Speter } else { 304251881Speter assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 305251881Speter SI = cast<SelectInst>(RHS); 306251881Speter } 307251881Speter 308251881Speter // Evaluate the BinOp on the true and false branches of the select. 309251881Speter Value *TV; 310251881Speter Value *FV; 311251881Speter if (SI == LHS) { 312251881Speter TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse); 313251881Speter FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse); 314251881Speter } else { 315251881Speter TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse); 316251881Speter FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse); 317251881Speter } 318251881Speter 319251881Speter // If they simplified to the same value, then return the common value. 320251881Speter // If they both failed to simplify then return null. 321251881Speter if (TV == FV) 322251881Speter return TV; 323251881Speter 324251881Speter // If one branch simplified to undef, return the other one. 325251881Speter if (TV && isa<UndefValue>(TV)) 326251881Speter return FV; 327251881Speter if (FV && isa<UndefValue>(FV)) 328251881Speter return TV; 329251881Speter 330251881Speter // If applying the operation did not change the true and false select values, 331251881Speter // then the result of the binop is the select itself. 332251881Speter if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 333251881Speter return SI; 334251881Speter 335251881Speter // If one branch simplified and the other did not, and the simplified 336251881Speter // value is equal to the unsimplified one, return the simplified value. 337251881Speter // For example, select (cond, X, X & Z) & Z -> X & Z. 338251881Speter if ((FV && !TV) || (TV && !FV)) { 339251881Speter // Check that the simplified value has the form "X op Y" where "op" is the 340251881Speter // same as the original operation. 341251881Speter Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 342251881Speter if (Simplified && Simplified->getOpcode() == Opcode) { 343251881Speter // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 344251881Speter // We already know that "op" is the same as for the simplified value. See 345251881Speter // if the operands match too. If so, return the simplified value. 346251881Speter Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 347251881Speter Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 348251881Speter Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 349251881Speter if (Simplified->getOperand(0) == UnsimplifiedLHS && 350251881Speter Simplified->getOperand(1) == UnsimplifiedRHS) 351251881Speter return Simplified; 352251881Speter if (Simplified->isCommutative() && 353251881Speter Simplified->getOperand(1) == UnsimplifiedLHS && 354251881Speter Simplified->getOperand(0) == UnsimplifiedRHS) 355251881Speter return Simplified; 356251881Speter } 357251881Speter } 358251881Speter 359251881Speter return nullptr; 360251881Speter} 361251881Speter 362251881Speter/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 363251881Speter/// try to simplify the comparison by seeing whether both branches of the select 364251881Speter/// result in the same value. Returns the common value if so, otherwise returns 365251881Speter/// null. 366251881Speterstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 367251881Speter Value *RHS, const Query &Q, 368251881Speter unsigned MaxRecurse) { 369251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 370251881Speter if (!MaxRecurse--) 371251881Speter return nullptr; 372251881Speter 373251881Speter // Make sure the select is on the LHS. 374251881Speter if (!isa<SelectInst>(LHS)) { 375251881Speter std::swap(LHS, RHS); 376251881Speter Pred = CmpInst::getSwappedPredicate(Pred); 377251881Speter } 378251881Speter assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 379251881Speter SelectInst *SI = cast<SelectInst>(LHS); 380251881Speter Value *Cond = SI->getCondition(); 381251881Speter Value *TV = SI->getTrueValue(); 382251881Speter Value *FV = SI->getFalseValue(); 383251881Speter 384251881Speter // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 385251881Speter // Does "cmp TV, RHS" simplify? 386251881Speter Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); 387251881Speter if (TCmp == Cond) { 388251881Speter // It not only simplified, it simplified to the select condition. Replace 389251881Speter // it with 'true'. 390251881Speter TCmp = getTrue(Cond->getType()); 391251881Speter } else if (!TCmp) { 392251881Speter // It didn't simplify. However if "cmp TV, RHS" is equal to the select 393251881Speter // condition then we can replace it with 'true'. Otherwise give up. 394251881Speter if (!isSameCompare(Cond, Pred, TV, RHS)) 395251881Speter return nullptr; 396251881Speter TCmp = getTrue(Cond->getType()); 397251881Speter } 398251881Speter 399251881Speter // Does "cmp FV, RHS" simplify? 400251881Speter Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); 401251881Speter if (FCmp == Cond) { 402251881Speter // It not only simplified, it simplified to the select condition. Replace 403251881Speter // it with 'false'. 404251881Speter FCmp = getFalse(Cond->getType()); 405251881Speter } else if (!FCmp) { 406251881Speter // It didn't simplify. However if "cmp FV, RHS" is equal to the select 407251881Speter // condition then we can replace it with 'false'. Otherwise give up. 408251881Speter if (!isSameCompare(Cond, Pred, FV, RHS)) 409251881Speter return nullptr; 410251881Speter FCmp = getFalse(Cond->getType()); 411251881Speter } 412251881Speter 413251881Speter // If both sides simplified to the same value, then use it as the result of 414251881Speter // the original comparison. 415251881Speter if (TCmp == FCmp) 416251881Speter return TCmp; 417251881Speter 418251881Speter // The remaining cases only make sense if the select condition has the same 419251881Speter // type as the result of the comparison, so bail out if this is not so. 420251881Speter if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) 421251881Speter return nullptr; 422251881Speter // If the false value simplified to false, then the result of the compare 423251881Speter // is equal to "Cond && TCmp". This also catches the case when the false 424251881Speter // value simplified to false and the true value to true, returning "Cond". 425251881Speter if (match(FCmp, m_Zero())) 426251881Speter if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) 427251881Speter return V; 428251881Speter // If the true value simplified to true, then the result of the compare 429251881Speter // is equal to "Cond || FCmp". 430251881Speter if (match(TCmp, m_One())) 431251881Speter if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) 432251881Speter return V; 433251881Speter // Finally, if the false value simplified to true and the true value to 434251881Speter // false, then the result of the compare is equal to "!Cond". 435251881Speter if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 436251881Speter if (Value *V = 437251881Speter SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 438251881Speter Q, MaxRecurse)) 439251881Speter return V; 440251881Speter 441251881Speter return nullptr; 442251881Speter} 443251881Speter 444251881Speter/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 445251881Speter/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 446251881Speter/// it on the incoming phi values yields the same result for every value. If so 447251881Speter/// returns the common value, otherwise returns null. 448251881Speterstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 449251881Speter const Query &Q, unsigned MaxRecurse) { 450251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 451251881Speter if (!MaxRecurse--) 452251881Speter return nullptr; 453251881Speter 454251881Speter PHINode *PI; 455251881Speter if (isa<PHINode>(LHS)) { 456251881Speter PI = cast<PHINode>(LHS); 457251881Speter // Bail out if RHS and the phi may be mutually interdependent due to a loop. 458251881Speter if (!ValueDominatesPHI(RHS, PI, Q.DT)) 459251881Speter return nullptr; 460251881Speter } else { 461251881Speter assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 462251881Speter PI = cast<PHINode>(RHS); 463251881Speter // Bail out if LHS and the phi may be mutually interdependent due to a loop. 464251881Speter if (!ValueDominatesPHI(LHS, PI, Q.DT)) 465251881Speter return nullptr; 466251881Speter } 467251881Speter 468251881Speter // Evaluate the BinOp on the incoming phi values. 469251881Speter Value *CommonValue = nullptr; 470251881Speter for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 471251881Speter Value *Incoming = PI->getIncomingValue(i); 472251881Speter // If the incoming value is the phi node itself, it can safely be skipped. 473251881Speter if (Incoming == PI) continue; 474251881Speter Value *V = PI == LHS ? 475251881Speter SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) : 476251881Speter SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse); 477251881Speter // If the operation failed to simplify, or simplified to a different value 478251881Speter // to previously, then give up. 479251881Speter if (!V || (CommonValue && V != CommonValue)) 480251881Speter return nullptr; 481251881Speter CommonValue = V; 482251881Speter } 483251881Speter 484251881Speter return CommonValue; 485251881Speter} 486251881Speter 487251881Speter/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 488251881Speter/// try to simplify the comparison by seeing whether comparing with all of the 489251881Speter/// incoming phi values yields the same result every time. If so returns the 490251881Speter/// common result, otherwise returns null. 491251881Speterstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 492251881Speter const Query &Q, unsigned MaxRecurse) { 493251881Speter // Recursion is always used, so bail out at once if we already hit the limit. 494251881Speter if (!MaxRecurse--) 495251881Speter return nullptr; 496251881Speter 497251881Speter // Make sure the phi is on the LHS. 498251881Speter if (!isa<PHINode>(LHS)) { 499251881Speter std::swap(LHS, RHS); 500251881Speter Pred = CmpInst::getSwappedPredicate(Pred); 501251881Speter } 502251881Speter assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 503251881Speter PHINode *PI = cast<PHINode>(LHS); 504251881Speter 505251881Speter // Bail out if RHS and the phi may be mutually interdependent due to a loop. 506251881Speter if (!ValueDominatesPHI(RHS, PI, Q.DT)) 507251881Speter return nullptr; 508251881Speter 509251881Speter // Evaluate the BinOp on the incoming phi values. 510251881Speter Value *CommonValue = nullptr; 511251881Speter for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 512251881Speter Value *Incoming = PI->getIncomingValue(i); 513251881Speter // If the incoming value is the phi node itself, it can safely be skipped. 514251881Speter if (Incoming == PI) continue; 515251881Speter Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); 516251881Speter // If the operation failed to simplify, or simplified to a different value 517251881Speter // to previously, then give up. 518251881Speter if (!V || (CommonValue && V != CommonValue)) 519251881Speter return nullptr; 520251881Speter CommonValue = V; 521251881Speter } 522251881Speter 523251881Speter return CommonValue; 524251881Speter} 525251881Speter 526251881Speter/// SimplifyAddInst - Given operands for an Add, see if we can 527251881Speter/// fold the result. If not, this returns null. 528251881Speterstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 529251881Speter const Query &Q, unsigned MaxRecurse) { 530251881Speter if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 531251881Speter if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 532251881Speter Constant *Ops[] = { CLHS, CRHS }; 533251881Speter return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops, 534251881Speter Q.DL, Q.TLI); 535251881Speter } 536251881Speter 537251881Speter // Canonicalize the constant to the RHS. 538251881Speter std::swap(Op0, Op1); 539251881Speter } 540251881Speter 541251881Speter // X + undef -> undef 542251881Speter if (match(Op1, m_Undef())) 543251881Speter return Op1; 544251881Speter 545251881Speter // X + 0 -> X 546251881Speter if (match(Op1, m_Zero())) 547251881Speter return Op0; 548251881Speter 549251881Speter // X + (Y - X) -> Y 550251881Speter // (Y - X) + X -> Y 551251881Speter // Eg: X + -X -> 0 552251881Speter Value *Y = nullptr; 553251881Speter if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 554251881Speter match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 555251881Speter return Y; 556251881Speter 557251881Speter // X + ~X -> -1 since ~X = -X-1 558251881Speter if (match(Op0, m_Not(m_Specific(Op1))) || 559251881Speter match(Op1, m_Not(m_Specific(Op0)))) 560251881Speter return Constant::getAllOnesValue(Op0->getType()); 561251881Speter 562251881Speter /// i1 add -> xor. 563251881Speter if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 564251881Speter if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 565251881Speter return V; 566251881Speter 567251881Speter // Try some generic simplifications for associative operations. 568251881Speter if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, 569251881Speter MaxRecurse)) 570251881Speter return V; 571251881Speter 572251881Speter // Threading Add over selects and phi nodes is pointless, so don't bother. 573251881Speter // Threading over the select in "A + select(cond, B, C)" means evaluating 574251881Speter // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 575251881Speter // only if B and C are equal. If B and C are equal then (since we assume 576251881Speter // that operands have already been simplified) "select(cond, B, C)" should 577251881Speter // have been simplified to the common value of B and C already. Analysing 578251881Speter // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 579251881Speter // for threading over phi nodes. 580251881Speter 581251881Speter return nullptr; 582251881Speter} 583251881Speter 584251881SpeterValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 585251881Speter const DataLayout *DL, const TargetLibraryInfo *TLI, 586251881Speter const DominatorTree *DT, AssumptionCache *AC, 587251881Speter const Instruction *CxtI) { 588251881Speter return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 589251881Speter RecursionLimit); 590251881Speter} 591251881Speter 592251881Speter/// \brief Compute the base pointer and cumulative constant offsets for V. 593251881Speter/// 594251881Speter/// This strips all constant offsets off of V, leaving it the base pointer, and 595251881Speter/// accumulates the total constant offset applied in the returned constant. It 596251881Speter/// returns 0 if V is not a pointer, and returns the constant '0' if there are 597251881Speter/// no constant offsets applied. 598251881Speter/// 599251881Speter/// This is very similar to GetPointerBaseWithConstantOffset except it doesn't 600251881Speter/// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. 601251881Speter/// folding. 602251881Speterstatic Constant *stripAndComputeConstantOffsets(const DataLayout *DL, 603251881Speter Value *&V, 604251881Speter bool AllowNonInbounds = false) { 605251881Speter assert(V->getType()->getScalarType()->isPointerTy()); 606251881Speter 607251881Speter // Without DataLayout, just be conservative for now. Theoretically, more could 608251881Speter // be done in this case. 609251881Speter if (!DL) 610251881Speter return ConstantInt::get(IntegerType::get(V->getContext(), 64), 0); 611251881Speter 612251881Speter Type *IntPtrTy = DL->getIntPtrType(V->getType())->getScalarType(); 613251881Speter APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); 614251881Speter 615251881Speter // Even though we don't look through PHI nodes, we could be called on an 616251881Speter // instruction in an unreachable block, which may be on a cycle. 617251881Speter SmallPtrSet<Value *, 4> Visited; 618251881Speter Visited.insert(V); 619251881Speter do { 620251881Speter if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 621251881Speter if ((!AllowNonInbounds && !GEP->isInBounds()) || 622251881Speter !GEP->accumulateConstantOffset(*DL, Offset)) 623251881Speter break; 624251881Speter V = GEP->getPointerOperand(); 625251881Speter } else if (Operator::getOpcode(V) == Instruction::BitCast) { 626251881Speter V = cast<Operator>(V)->getOperand(0); 627251881Speter } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 628251881Speter if (GA->mayBeOverridden()) 629251881Speter break; 630251881Speter V = GA->getAliasee(); 631251881Speter } else { 632251881Speter break; 633251881Speter } 634251881Speter assert(V->getType()->getScalarType()->isPointerTy() && 635251881Speter "Unexpected operand type!"); 636251881Speter } while (Visited.insert(V).second); 637251881Speter 638251881Speter Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); 639251881Speter if (V->getType()->isVectorTy()) 640251881Speter return ConstantVector::getSplat(V->getType()->getVectorNumElements(), 641251881Speter OffsetIntPtr); 642251881Speter return OffsetIntPtr; 643251881Speter} 644251881Speter 645251881Speter/// \brief Compute the constant difference between two pointer values. 646251881Speter/// If the difference is not a constant, returns zero. 647251881Speterstatic Constant *computePointerDifference(const DataLayout *DL, 648251881Speter Value *LHS, Value *RHS) { 649251881Speter Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 650251881Speter Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 651251881Speter 652251881Speter // If LHS and RHS are not related via constant offsets to the same base 653251881Speter // value, there is nothing we can do here. 654251881Speter if (LHS != RHS) 655251881Speter return nullptr; 656251881Speter 657251881Speter // Otherwise, the difference of LHS - RHS can be computed as: 658251881Speter // LHS - RHS 659251881Speter // = (LHSOffset + Base) - (RHSOffset + Base) 660251881Speter // = LHSOffset - RHSOffset 661251881Speter return ConstantExpr::getSub(LHSOffset, RHSOffset); 662251881Speter} 663251881Speter 664251881Speter/// SimplifySubInst - Given operands for a Sub, see if we can 665251881Speter/// fold the result. If not, this returns null. 666251881Speterstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 667251881Speter const Query &Q, unsigned MaxRecurse) { 668251881Speter if (Constant *CLHS = dyn_cast<Constant>(Op0)) 669251881Speter if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 670251881Speter Constant *Ops[] = { CLHS, CRHS }; 671251881Speter return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 672251881Speter Ops, Q.DL, Q.TLI); 673251881Speter } 674251881Speter 675251881Speter // X - undef -> undef 676251881Speter // undef - X -> undef 677251881Speter if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 678251881Speter return UndefValue::get(Op0->getType()); 679251881Speter 680251881Speter // X - 0 -> X 681251881Speter if (match(Op1, m_Zero())) 682251881Speter return Op0; 683251881Speter 684251881Speter // X - X -> 0 685251881Speter if (Op0 == Op1) 686251881Speter return Constant::getNullValue(Op0->getType()); 687251881Speter 688251881Speter // 0 - X -> 0 if the sub is NUW. 689251881Speter if (isNUW && match(Op0, m_Zero())) 690251881Speter return Op0; 691251881Speter 692251881Speter // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 693 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 694 Value *X = nullptr, *Y = nullptr, *Z = Op1; 695 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 696 // See if "V === Y - Z" simplifies. 697 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) 698 // It does! Now see if "X + V" simplifies. 699 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { 700 // It does, we successfully reassociated! 701 ++NumReassoc; 702 return W; 703 } 704 // See if "V === X - Z" simplifies. 705 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 706 // It does! Now see if "Y + V" simplifies. 707 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) { 708 // It does, we successfully reassociated! 709 ++NumReassoc; 710 return W; 711 } 712 } 713 714 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 715 // For example, X - (X + 1) -> -1 716 X = Op0; 717 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 718 // See if "V === X - Y" simplifies. 719 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 720 // It does! Now see if "V - Z" simplifies. 721 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) { 722 // It does, we successfully reassociated! 723 ++NumReassoc; 724 return W; 725 } 726 // See if "V === X - Z" simplifies. 727 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 728 // It does! Now see if "V - Y" simplifies. 729 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) { 730 // It does, we successfully reassociated! 731 ++NumReassoc; 732 return W; 733 } 734 } 735 736 // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 737 // For example, X - (X - Y) -> Y. 738 Z = Op0; 739 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 740 // See if "V === Z - X" simplifies. 741 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1)) 742 // It does! Now see if "V + Y" simplifies. 743 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) { 744 // It does, we successfully reassociated! 745 ++NumReassoc; 746 return W; 747 } 748 749 // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies. 750 if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) && 751 match(Op1, m_Trunc(m_Value(Y)))) 752 if (X->getType() == Y->getType()) 753 // See if "V === X - Y" simplifies. 754 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 755 // It does! Now see if "trunc V" simplifies. 756 if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1)) 757 // It does, return the simplified "trunc V". 758 return W; 759 760 // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). 761 if (match(Op0, m_PtrToInt(m_Value(X))) && 762 match(Op1, m_PtrToInt(m_Value(Y)))) 763 if (Constant *Result = computePointerDifference(Q.DL, X, Y)) 764 return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); 765 766 // i1 sub -> xor. 767 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 768 if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 769 return V; 770 771 // Threading Sub over selects and phi nodes is pointless, so don't bother. 772 // Threading over the select in "A - select(cond, B, C)" means evaluating 773 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 774 // only if B and C are equal. If B and C are equal then (since we assume 775 // that operands have already been simplified) "select(cond, B, C)" should 776 // have been simplified to the common value of B and C already. Analysing 777 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 778 // for threading over phi nodes. 779 780 return nullptr; 781} 782 783Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 784 const DataLayout *DL, const TargetLibraryInfo *TLI, 785 const DominatorTree *DT, AssumptionCache *AC, 786 const Instruction *CxtI) { 787 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 788 RecursionLimit); 789} 790 791/// Given operands for an FAdd, see if we can fold the result. If not, this 792/// returns null. 793static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 794 const Query &Q, unsigned MaxRecurse) { 795 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 796 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 797 Constant *Ops[] = { CLHS, CRHS }; 798 return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(), 799 Ops, Q.DL, Q.TLI); 800 } 801 802 // Canonicalize the constant to the RHS. 803 std::swap(Op0, Op1); 804 } 805 806 // fadd X, -0 ==> X 807 if (match(Op1, m_NegZero())) 808 return Op0; 809 810 // fadd X, 0 ==> X, when we know X is not -0 811 if (match(Op1, m_Zero()) && 812 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 813 return Op0; 814 815 // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 816 // where nnan and ninf have to occur at least once somewhere in this 817 // expression 818 Value *SubOp = nullptr; 819 if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) 820 SubOp = Op1; 821 else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) 822 SubOp = Op0; 823 if (SubOp) { 824 Instruction *FSub = cast<Instruction>(SubOp); 825 if ((FMF.noNaNs() || FSub->hasNoNaNs()) && 826 (FMF.noInfs() || FSub->hasNoInfs())) 827 return Constant::getNullValue(Op0->getType()); 828 } 829 830 return nullptr; 831} 832 833/// Given operands for an FSub, see if we can fold the result. If not, this 834/// returns null. 835static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 836 const Query &Q, unsigned MaxRecurse) { 837 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 838 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 839 Constant *Ops[] = { CLHS, CRHS }; 840 return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(), 841 Ops, Q.DL, Q.TLI); 842 } 843 } 844 845 // fsub X, 0 ==> X 846 if (match(Op1, m_Zero())) 847 return Op0; 848 849 // fsub X, -0 ==> X, when we know X is not -0 850 if (match(Op1, m_NegZero()) && 851 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 852 return Op0; 853 854 // fsub 0, (fsub -0.0, X) ==> X 855 Value *X; 856 if (match(Op0, m_AnyZero())) { 857 if (match(Op1, m_FSub(m_NegZero(), m_Value(X)))) 858 return X; 859 if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) 860 return X; 861 } 862 863 // fsub nnan ninf x, x ==> 0.0 864 if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1) 865 return Constant::getNullValue(Op0->getType()); 866 867 return nullptr; 868} 869 870/// Given the operands for an FMul, see if we can fold the result 871static Value *SimplifyFMulInst(Value *Op0, Value *Op1, 872 FastMathFlags FMF, 873 const Query &Q, 874 unsigned MaxRecurse) { 875 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 876 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 877 Constant *Ops[] = { CLHS, CRHS }; 878 return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(), 879 Ops, Q.DL, Q.TLI); 880 } 881 882 // Canonicalize the constant to the RHS. 883 std::swap(Op0, Op1); 884 } 885 886 // fmul X, 1.0 ==> X 887 if (match(Op1, m_FPOne())) 888 return Op0; 889 890 // fmul nnan nsz X, 0 ==> 0 891 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) 892 return Op1; 893 894 return nullptr; 895} 896 897/// SimplifyMulInst - Given operands for a Mul, see if we can 898/// fold the result. If not, this returns null. 899static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, 900 unsigned MaxRecurse) { 901 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 902 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 903 Constant *Ops[] = { CLHS, CRHS }; 904 return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 905 Ops, Q.DL, Q.TLI); 906 } 907 908 // Canonicalize the constant to the RHS. 909 std::swap(Op0, Op1); 910 } 911 912 // X * undef -> 0 913 if (match(Op1, m_Undef())) 914 return Constant::getNullValue(Op0->getType()); 915 916 // X * 0 -> 0 917 if (match(Op1, m_Zero())) 918 return Op1; 919 920 // X * 1 -> X 921 if (match(Op1, m_One())) 922 return Op0; 923 924 // (X / Y) * Y -> X if the division is exact. 925 Value *X = nullptr; 926 if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y 927 match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) 928 return X; 929 930 // i1 mul -> and. 931 if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 932 if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1)) 933 return V; 934 935 // Try some generic simplifications for associative operations. 936 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, 937 MaxRecurse)) 938 return V; 939 940 // Mul distributes over Add. Try some generic simplifications based on this. 941 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 942 Q, MaxRecurse)) 943 return V; 944 945 // If the operation is with the result of a select instruction, check whether 946 // operating on either branch of the select always yields the same value. 947 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 948 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, 949 MaxRecurse)) 950 return V; 951 952 // If the operation is with the result of a phi instruction, check whether 953 // operating on all incoming values of the phi always yields the same value. 954 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 955 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, 956 MaxRecurse)) 957 return V; 958 959 return nullptr; 960} 961 962Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 963 const DataLayout *DL, 964 const TargetLibraryInfo *TLI, 965 const DominatorTree *DT, AssumptionCache *AC, 966 const Instruction *CxtI) { 967 return ::SimplifyFAddInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 968 RecursionLimit); 969} 970 971Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 972 const DataLayout *DL, 973 const TargetLibraryInfo *TLI, 974 const DominatorTree *DT, AssumptionCache *AC, 975 const Instruction *CxtI) { 976 return ::SimplifyFSubInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 977 RecursionLimit); 978} 979 980Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, 981 const DataLayout *DL, 982 const TargetLibraryInfo *TLI, 983 const DominatorTree *DT, AssumptionCache *AC, 984 const Instruction *CxtI) { 985 return ::SimplifyFMulInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 986 RecursionLimit); 987} 988 989Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *DL, 990 const TargetLibraryInfo *TLI, 991 const DominatorTree *DT, AssumptionCache *AC, 992 const Instruction *CxtI) { 993 return ::SimplifyMulInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 994 RecursionLimit); 995} 996 997/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 998/// fold the result. If not, this returns null. 999static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 1000 const Query &Q, unsigned MaxRecurse) { 1001 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1002 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1003 Constant *Ops[] = { C0, C1 }; 1004 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1005 } 1006 } 1007 1008 bool isSigned = Opcode == Instruction::SDiv; 1009 1010 // X / undef -> undef 1011 if (match(Op1, m_Undef())) 1012 return Op1; 1013 1014 // X / 0 -> undef, we don't need to preserve faults! 1015 if (match(Op1, m_Zero())) 1016 return UndefValue::get(Op1->getType()); 1017 1018 // undef / X -> 0 1019 if (match(Op0, m_Undef())) 1020 return Constant::getNullValue(Op0->getType()); 1021 1022 // 0 / X -> 0, we don't need to preserve faults! 1023 if (match(Op0, m_Zero())) 1024 return Op0; 1025 1026 // X / 1 -> X 1027 if (match(Op1, m_One())) 1028 return Op0; 1029 1030 if (Op0->getType()->isIntegerTy(1)) 1031 // It can't be division by zero, hence it must be division by one. 1032 return Op0; 1033 1034 // X / X -> 1 1035 if (Op0 == Op1) 1036 return ConstantInt::get(Op0->getType(), 1); 1037 1038 // (X * Y) / Y -> X if the multiplication does not overflow. 1039 Value *X = nullptr, *Y = nullptr; 1040 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 1041 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 1042 OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 1043 // If the Mul knows it does not overflow, then we are good to go. 1044 if ((isSigned && Mul->hasNoSignedWrap()) || 1045 (!isSigned && Mul->hasNoUnsignedWrap())) 1046 return X; 1047 // If X has the form X = A / Y then X * Y cannot overflow. 1048 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 1049 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 1050 return X; 1051 } 1052 1053 // (X rem Y) / Y -> 0 1054 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1055 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1056 return Constant::getNullValue(Op0->getType()); 1057 1058 // (X /u C1) /u C2 -> 0 if C1 * C2 overflow 1059 ConstantInt *C1, *C2; 1060 if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) && 1061 match(Op1, m_ConstantInt(C2))) { 1062 bool Overflow; 1063 C1->getValue().umul_ov(C2->getValue(), Overflow); 1064 if (Overflow) 1065 return Constant::getNullValue(Op0->getType()); 1066 } 1067 1068 // If the operation is with the result of a select instruction, check whether 1069 // operating on either branch of the select always yields the same value. 1070 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1071 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1072 return V; 1073 1074 // If the operation is with the result of a phi instruction, check whether 1075 // operating on all incoming values of the phi always yields the same value. 1076 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1077 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1078 return V; 1079 1080 return nullptr; 1081} 1082 1083/// SimplifySDivInst - Given operands for an SDiv, see if we can 1084/// fold the result. If not, this returns null. 1085static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, 1086 unsigned MaxRecurse) { 1087 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse)) 1088 return V; 1089 1090 return nullptr; 1091} 1092 1093Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 1094 const TargetLibraryInfo *TLI, 1095 const DominatorTree *DT, AssumptionCache *AC, 1096 const Instruction *CxtI) { 1097 return ::SimplifySDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1098 RecursionLimit); 1099} 1100 1101/// SimplifyUDivInst - Given operands for a UDiv, see if we can 1102/// fold the result. If not, this returns null. 1103static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, 1104 unsigned MaxRecurse) { 1105 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse)) 1106 return V; 1107 1108 return nullptr; 1109} 1110 1111Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 1112 const TargetLibraryInfo *TLI, 1113 const DominatorTree *DT, AssumptionCache *AC, 1114 const Instruction *CxtI) { 1115 return ::SimplifyUDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1116 RecursionLimit); 1117} 1118 1119static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q, 1120 unsigned) { 1121 // undef / X -> undef (the undef could be a snan). 1122 if (match(Op0, m_Undef())) 1123 return Op0; 1124 1125 // X / undef -> undef 1126 if (match(Op1, m_Undef())) 1127 return Op1; 1128 1129 return nullptr; 1130} 1131 1132Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 1133 const TargetLibraryInfo *TLI, 1134 const DominatorTree *DT, AssumptionCache *AC, 1135 const Instruction *CxtI) { 1136 return ::SimplifyFDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1137 RecursionLimit); 1138} 1139 1140/// SimplifyRem - Given operands for an SRem or URem, see if we can 1141/// fold the result. If not, this returns null. 1142static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 1143 const Query &Q, unsigned MaxRecurse) { 1144 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1145 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1146 Constant *Ops[] = { C0, C1 }; 1147 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1148 } 1149 } 1150 1151 // X % undef -> undef 1152 if (match(Op1, m_Undef())) 1153 return Op1; 1154 1155 // undef % X -> 0 1156 if (match(Op0, m_Undef())) 1157 return Constant::getNullValue(Op0->getType()); 1158 1159 // 0 % X -> 0, we don't need to preserve faults! 1160 if (match(Op0, m_Zero())) 1161 return Op0; 1162 1163 // X % 0 -> undef, we don't need to preserve faults! 1164 if (match(Op1, m_Zero())) 1165 return UndefValue::get(Op0->getType()); 1166 1167 // X % 1 -> 0 1168 if (match(Op1, m_One())) 1169 return Constant::getNullValue(Op0->getType()); 1170 1171 if (Op0->getType()->isIntegerTy(1)) 1172 // It can't be remainder by zero, hence it must be remainder by one. 1173 return Constant::getNullValue(Op0->getType()); 1174 1175 // X % X -> 0 1176 if (Op0 == Op1) 1177 return Constant::getNullValue(Op0->getType()); 1178 1179 // (X % Y) % Y -> X % Y 1180 if ((Opcode == Instruction::SRem && 1181 match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1182 (Opcode == Instruction::URem && 1183 match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1184 return Op0; 1185 1186 // If the operation is with the result of a select instruction, check whether 1187 // operating on either branch of the select always yields the same value. 1188 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1189 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1190 return V; 1191 1192 // If the operation is with the result of a phi instruction, check whether 1193 // operating on all incoming values of the phi always yields the same value. 1194 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1195 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1196 return V; 1197 1198 return nullptr; 1199} 1200 1201/// SimplifySRemInst - Given operands for an SRem, see if we can 1202/// fold the result. If not, this returns null. 1203static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, 1204 unsigned MaxRecurse) { 1205 if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse)) 1206 return V; 1207 1208 return nullptr; 1209} 1210 1211Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1212 const TargetLibraryInfo *TLI, 1213 const DominatorTree *DT, AssumptionCache *AC, 1214 const Instruction *CxtI) { 1215 return ::SimplifySRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1216 RecursionLimit); 1217} 1218 1219/// SimplifyURemInst - Given operands for a URem, see if we can 1220/// fold the result. If not, this returns null. 1221static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, 1222 unsigned MaxRecurse) { 1223 if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse)) 1224 return V; 1225 1226 return nullptr; 1227} 1228 1229Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1230 const TargetLibraryInfo *TLI, 1231 const DominatorTree *DT, AssumptionCache *AC, 1232 const Instruction *CxtI) { 1233 return ::SimplifyURemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1234 RecursionLimit); 1235} 1236 1237static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &, 1238 unsigned) { 1239 // undef % X -> undef (the undef could be a snan). 1240 if (match(Op0, m_Undef())) 1241 return Op0; 1242 1243 // X % undef -> undef 1244 if (match(Op1, m_Undef())) 1245 return Op1; 1246 1247 return nullptr; 1248} 1249 1250Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1251 const TargetLibraryInfo *TLI, 1252 const DominatorTree *DT, AssumptionCache *AC, 1253 const Instruction *CxtI) { 1254 return ::SimplifyFRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1255 RecursionLimit); 1256} 1257 1258/// isUndefShift - Returns true if a shift by \c Amount always yields undef. 1259static bool isUndefShift(Value *Amount) { 1260 Constant *C = dyn_cast<Constant>(Amount); 1261 if (!C) 1262 return false; 1263 1264 // X shift by undef -> undef because it may shift by the bitwidth. 1265 if (isa<UndefValue>(C)) 1266 return true; 1267 1268 // Shifting by the bitwidth or more is undefined. 1269 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 1270 if (CI->getValue().getLimitedValue() >= 1271 CI->getType()->getScalarSizeInBits()) 1272 return true; 1273 1274 // If all lanes of a vector shift are undefined the whole shift is. 1275 if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) { 1276 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I) 1277 if (!isUndefShift(C->getAggregateElement(I))) 1278 return false; 1279 return true; 1280 } 1281 1282 return false; 1283} 1284 1285/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 1286/// fold the result. If not, this returns null. 1287static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1288 const Query &Q, unsigned MaxRecurse) { 1289 if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1290 if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1291 Constant *Ops[] = { C0, C1 }; 1292 return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1293 } 1294 } 1295 1296 // 0 shift by X -> 0 1297 if (match(Op0, m_Zero())) 1298 return Op0; 1299 1300 // X shift by 0 -> X 1301 if (match(Op1, m_Zero())) 1302 return Op0; 1303 1304 // Fold undefined shifts. 1305 if (isUndefShift(Op1)) 1306 return UndefValue::get(Op0->getType()); 1307 1308 // If the operation is with the result of a select instruction, check whether 1309 // operating on either branch of the select always yields the same value. 1310 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1311 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1312 return V; 1313 1314 // If the operation is with the result of a phi instruction, check whether 1315 // operating on all incoming values of the phi always yields the same value. 1316 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1317 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1318 return V; 1319 1320 return nullptr; 1321} 1322 1323/// \brief Given operands for an Shl, LShr or AShr, see if we can 1324/// fold the result. If not, this returns null. 1325static Value *SimplifyRightShift(unsigned Opcode, Value *Op0, Value *Op1, 1326 bool isExact, const Query &Q, 1327 unsigned MaxRecurse) { 1328 if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse)) 1329 return V; 1330 1331 // X >> X -> 0 1332 if (Op0 == Op1) 1333 return Constant::getNullValue(Op0->getType()); 1334 1335 // undef >> X -> 0 1336 // undef >> X -> undef (if it's exact) 1337 if (match(Op0, m_Undef())) 1338 return isExact ? Op0 : Constant::getNullValue(Op0->getType()); 1339 1340 // The low bit cannot be shifted out of an exact shift if it is set. 1341 if (isExact) { 1342 unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 1343 APInt Op0KnownZero(BitWidth, 0); 1344 APInt Op0KnownOne(BitWidth, 0); 1345 computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC, 1346 Q.CxtI, Q.DT); 1347 if (Op0KnownOne[0]) 1348 return Op0; 1349 } 1350 1351 return nullptr; 1352} 1353 1354/// SimplifyShlInst - Given operands for an Shl, see if we can 1355/// fold the result. If not, this returns null. 1356static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1357 const Query &Q, unsigned MaxRecurse) { 1358 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse)) 1359 return V; 1360 1361 // undef << X -> 0 1362 // undef << X -> undef if (if it's NSW/NUW) 1363 if (match(Op0, m_Undef())) 1364 return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType()); 1365 1366 // (X >> A) << A -> X 1367 Value *X; 1368 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) 1369 return X; 1370 return nullptr; 1371} 1372 1373Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1374 const DataLayout *DL, const TargetLibraryInfo *TLI, 1375 const DominatorTree *DT, AssumptionCache *AC, 1376 const Instruction *CxtI) { 1377 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 1378 RecursionLimit); 1379} 1380 1381/// SimplifyLShrInst - Given operands for an LShr, see if we can 1382/// fold the result. If not, this returns null. 1383static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1384 const Query &Q, unsigned MaxRecurse) { 1385 if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q, 1386 MaxRecurse)) 1387 return V; 1388 1389 // (X << A) >> A -> X 1390 Value *X; 1391 if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1)))) 1392 return X; 1393 1394 return nullptr; 1395} 1396 1397Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1398 const DataLayout *DL, 1399 const TargetLibraryInfo *TLI, 1400 const DominatorTree *DT, AssumptionCache *AC, 1401 const Instruction *CxtI) { 1402 return ::SimplifyLShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1403 RecursionLimit); 1404} 1405 1406/// SimplifyAShrInst - Given operands for an AShr, see if we can 1407/// fold the result. If not, this returns null. 1408static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1409 const Query &Q, unsigned MaxRecurse) { 1410 if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q, 1411 MaxRecurse)) 1412 return V; 1413 1414 // all ones >>a X -> all ones 1415 if (match(Op0, m_AllOnes())) 1416 return Op0; 1417 1418 // (X << A) >> A -> X 1419 Value *X; 1420 if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1)))) 1421 return X; 1422 1423 // Arithmetic shifting an all-sign-bit value is a no-op. 1424 unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); 1425 if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 1426 return Op0; 1427 1428 return nullptr; 1429} 1430 1431Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1432 const DataLayout *DL, 1433 const TargetLibraryInfo *TLI, 1434 const DominatorTree *DT, AssumptionCache *AC, 1435 const Instruction *CxtI) { 1436 return ::SimplifyAShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1437 RecursionLimit); 1438} 1439 1440static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp, 1441 ICmpInst *UnsignedICmp, bool IsAnd) { 1442 Value *X, *Y; 1443 1444 ICmpInst::Predicate EqPred; 1445 if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) || 1446 !ICmpInst::isEquality(EqPred)) 1447 return nullptr; 1448 1449 ICmpInst::Predicate UnsignedPred; 1450 if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) && 1451 ICmpInst::isUnsigned(UnsignedPred)) 1452 ; 1453 else if (match(UnsignedICmp, 1454 m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) && 1455 ICmpInst::isUnsigned(UnsignedPred)) 1456 UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred); 1457 else 1458 return nullptr; 1459 1460 // X < Y && Y != 0 --> X < Y 1461 // X < Y || Y != 0 --> Y != 0 1462 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE) 1463 return IsAnd ? UnsignedICmp : ZeroICmp; 1464 1465 // X >= Y || Y != 0 --> true 1466 // X >= Y || Y == 0 --> X >= Y 1467 if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) { 1468 if (EqPred == ICmpInst::ICMP_NE) 1469 return getTrue(UnsignedICmp->getType()); 1470 return UnsignedICmp; 1471 } 1472 1473 // X < Y && Y == 0 --> false 1474 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ && 1475 IsAnd) 1476 return getFalse(UnsignedICmp->getType()); 1477 1478 return nullptr; 1479} 1480 1481// Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range 1482// of possible values cannot be satisfied. 1483static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1484 ICmpInst::Predicate Pred0, Pred1; 1485 ConstantInt *CI1, *CI2; 1486 Value *V; 1487 1488 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true)) 1489 return X; 1490 1491 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1492 m_ConstantInt(CI2)))) 1493 return nullptr; 1494 1495 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1496 return nullptr; 1497 1498 Type *ITy = Op0->getType(); 1499 1500 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1501 bool isNSW = AddInst->hasNoSignedWrap(); 1502 bool isNUW = AddInst->hasNoUnsignedWrap(); 1503 1504 const APInt &CI1V = CI1->getValue(); 1505 const APInt &CI2V = CI2->getValue(); 1506 const APInt Delta = CI2V - CI1V; 1507 if (CI1V.isStrictlyPositive()) { 1508 if (Delta == 2) { 1509 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT) 1510 return getFalse(ITy); 1511 if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1512 return getFalse(ITy); 1513 } 1514 if (Delta == 1) { 1515 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT) 1516 return getFalse(ITy); 1517 if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1518 return getFalse(ITy); 1519 } 1520 } 1521 if (CI1V.getBoolValue() && isNUW) { 1522 if (Delta == 2) 1523 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT) 1524 return getFalse(ITy); 1525 if (Delta == 1) 1526 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT) 1527 return getFalse(ITy); 1528 } 1529 1530 return nullptr; 1531} 1532 1533/// SimplifyAndInst - Given operands for an And, see if we can 1534/// fold the result. If not, this returns null. 1535static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, 1536 unsigned MaxRecurse) { 1537 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1538 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1539 Constant *Ops[] = { CLHS, CRHS }; 1540 return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1541 Ops, Q.DL, Q.TLI); 1542 } 1543 1544 // Canonicalize the constant to the RHS. 1545 std::swap(Op0, Op1); 1546 } 1547 1548 // X & undef -> 0 1549 if (match(Op1, m_Undef())) 1550 return Constant::getNullValue(Op0->getType()); 1551 1552 // X & X = X 1553 if (Op0 == Op1) 1554 return Op0; 1555 1556 // X & 0 = 0 1557 if (match(Op1, m_Zero())) 1558 return Op1; 1559 1560 // X & -1 = X 1561 if (match(Op1, m_AllOnes())) 1562 return Op0; 1563 1564 // A & ~A = ~A & A = 0 1565 if (match(Op0, m_Not(m_Specific(Op1))) || 1566 match(Op1, m_Not(m_Specific(Op0)))) 1567 return Constant::getNullValue(Op0->getType()); 1568 1569 // (A | ?) & A = A 1570 Value *A = nullptr, *B = nullptr; 1571 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1572 (A == Op1 || B == Op1)) 1573 return Op1; 1574 1575 // A & (A | ?) = A 1576 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1577 (A == Op0 || B == Op0)) 1578 return Op0; 1579 1580 // A & (-A) = A if A is a power of two or zero. 1581 if (match(Op0, m_Neg(m_Specific(Op1))) || 1582 match(Op1, m_Neg(m_Specific(Op0)))) { 1583 if (isKnownToBeAPowerOfTwo(Op0, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) 1584 return Op0; 1585 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) 1586 return Op1; 1587 } 1588 1589 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1590 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1591 if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS)) 1592 return V; 1593 if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS)) 1594 return V; 1595 } 1596 } 1597 1598 // Try some generic simplifications for associative operations. 1599 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, 1600 MaxRecurse)) 1601 return V; 1602 1603 // And distributes over Or. Try some generic simplifications based on this. 1604 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1605 Q, MaxRecurse)) 1606 return V; 1607 1608 // And distributes over Xor. Try some generic simplifications based on this. 1609 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1610 Q, MaxRecurse)) 1611 return V; 1612 1613 // If the operation is with the result of a select instruction, check whether 1614 // operating on either branch of the select always yields the same value. 1615 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1616 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, 1617 MaxRecurse)) 1618 return V; 1619 1620 // If the operation is with the result of a phi instruction, check whether 1621 // operating on all incoming values of the phi always yields the same value. 1622 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1623 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q, 1624 MaxRecurse)) 1625 return V; 1626 1627 return nullptr; 1628} 1629 1630Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *DL, 1631 const TargetLibraryInfo *TLI, 1632 const DominatorTree *DT, AssumptionCache *AC, 1633 const Instruction *CxtI) { 1634 return ::SimplifyAndInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1635 RecursionLimit); 1636} 1637 1638// Simplify (or (icmp ...) (icmp ...)) to true when we can tell that the union 1639// contains all possible values. 1640static Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1641 ICmpInst::Predicate Pred0, Pred1; 1642 ConstantInt *CI1, *CI2; 1643 Value *V; 1644 1645 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false)) 1646 return X; 1647 1648 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1649 m_ConstantInt(CI2)))) 1650 return nullptr; 1651 1652 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1653 return nullptr; 1654 1655 Type *ITy = Op0->getType(); 1656 1657 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1658 bool isNSW = AddInst->hasNoSignedWrap(); 1659 bool isNUW = AddInst->hasNoUnsignedWrap(); 1660 1661 const APInt &CI1V = CI1->getValue(); 1662 const APInt &CI2V = CI2->getValue(); 1663 const APInt Delta = CI2V - CI1V; 1664 if (CI1V.isStrictlyPositive()) { 1665 if (Delta == 2) { 1666 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE) 1667 return getTrue(ITy); 1668 if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1669 return getTrue(ITy); 1670 } 1671 if (Delta == 1) { 1672 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE) 1673 return getTrue(ITy); 1674 if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1675 return getTrue(ITy); 1676 } 1677 } 1678 if (CI1V.getBoolValue() && isNUW) { 1679 if (Delta == 2) 1680 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE) 1681 return getTrue(ITy); 1682 if (Delta == 1) 1683 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE) 1684 return getTrue(ITy); 1685 } 1686 1687 return nullptr; 1688} 1689 1690/// SimplifyOrInst - Given operands for an Or, see if we can 1691/// fold the result. If not, this returns null. 1692static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, 1693 unsigned MaxRecurse) { 1694 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1695 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1696 Constant *Ops[] = { CLHS, CRHS }; 1697 return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1698 Ops, Q.DL, Q.TLI); 1699 } 1700 1701 // Canonicalize the constant to the RHS. 1702 std::swap(Op0, Op1); 1703 } 1704 1705 // X | undef -> -1 1706 if (match(Op1, m_Undef())) 1707 return Constant::getAllOnesValue(Op0->getType()); 1708 1709 // X | X = X 1710 if (Op0 == Op1) 1711 return Op0; 1712 1713 // X | 0 = X 1714 if (match(Op1, m_Zero())) 1715 return Op0; 1716 1717 // X | -1 = -1 1718 if (match(Op1, m_AllOnes())) 1719 return Op1; 1720 1721 // A | ~A = ~A | A = -1 1722 if (match(Op0, m_Not(m_Specific(Op1))) || 1723 match(Op1, m_Not(m_Specific(Op0)))) 1724 return Constant::getAllOnesValue(Op0->getType()); 1725 1726 // (A & ?) | A = A 1727 Value *A = nullptr, *B = nullptr; 1728 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1729 (A == Op1 || B == Op1)) 1730 return Op1; 1731 1732 // A | (A & ?) = A 1733 if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1734 (A == Op0 || B == Op0)) 1735 return Op0; 1736 1737 // ~(A & ?) | A = -1 1738 if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1739 (A == Op1 || B == Op1)) 1740 return Constant::getAllOnesValue(Op1->getType()); 1741 1742 // A | ~(A & ?) = -1 1743 if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1744 (A == Op0 || B == Op0)) 1745 return Constant::getAllOnesValue(Op0->getType()); 1746 1747 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1748 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1749 if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS)) 1750 return V; 1751 if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS)) 1752 return V; 1753 } 1754 } 1755 1756 // Try some generic simplifications for associative operations. 1757 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, 1758 MaxRecurse)) 1759 return V; 1760 1761 // Or distributes over And. Try some generic simplifications based on this. 1762 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, 1763 MaxRecurse)) 1764 return V; 1765 1766 // If the operation is with the result of a select instruction, check whether 1767 // operating on either branch of the select always yields the same value. 1768 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1769 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, 1770 MaxRecurse)) 1771 return V; 1772 1773 // (A & C)|(B & D) 1774 Value *C = nullptr, *D = nullptr; 1775 if (match(Op0, m_And(m_Value(A), m_Value(C))) && 1776 match(Op1, m_And(m_Value(B), m_Value(D)))) { 1777 ConstantInt *C1 = dyn_cast<ConstantInt>(C); 1778 ConstantInt *C2 = dyn_cast<ConstantInt>(D); 1779 if (C1 && C2 && (C1->getValue() == ~C2->getValue())) { 1780 // (A & C1)|(B & C2) 1781 // If we have: ((V + N) & C1) | (V & C2) 1782 // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 1783 // replace with V+N. 1784 Value *V1, *V2; 1785 if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+ 1786 match(A, m_Add(m_Value(V1), m_Value(V2)))) { 1787 // Add commutes, try both ways. 1788 if (V1 == B && 1789 MaskedValueIsZero(V2, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1790 return A; 1791 if (V2 == B && 1792 MaskedValueIsZero(V1, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1793 return A; 1794 } 1795 // Or commutes, try both ways. 1796 if ((C1->getValue() & (C1->getValue() + 1)) == 0 && 1797 match(B, m_Add(m_Value(V1), m_Value(V2)))) { 1798 // Add commutes, try both ways. 1799 if (V1 == A && 1800 MaskedValueIsZero(V2, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1801 return B; 1802 if (V2 == A && 1803 MaskedValueIsZero(V1, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1804 return B; 1805 } 1806 } 1807 } 1808 1809 // If the operation is with the result of a phi instruction, check whether 1810 // operating on all incoming values of the phi always yields the same value. 1811 if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1812 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse)) 1813 return V; 1814 1815 return nullptr; 1816} 1817 1818Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *DL, 1819 const TargetLibraryInfo *TLI, 1820 const DominatorTree *DT, AssumptionCache *AC, 1821 const Instruction *CxtI) { 1822 return ::SimplifyOrInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1823 RecursionLimit); 1824} 1825 1826/// SimplifyXorInst - Given operands for a Xor, see if we can 1827/// fold the result. If not, this returns null. 1828static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, 1829 unsigned MaxRecurse) { 1830 if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1831 if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1832 Constant *Ops[] = { CLHS, CRHS }; 1833 return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1834 Ops, Q.DL, Q.TLI); 1835 } 1836 1837 // Canonicalize the constant to the RHS. 1838 std::swap(Op0, Op1); 1839 } 1840 1841 // A ^ undef -> undef 1842 if (match(Op1, m_Undef())) 1843 return Op1; 1844 1845 // A ^ 0 = A 1846 if (match(Op1, m_Zero())) 1847 return Op0; 1848 1849 // A ^ A = 0 1850 if (Op0 == Op1) 1851 return Constant::getNullValue(Op0->getType()); 1852 1853 // A ^ ~A = ~A ^ A = -1 1854 if (match(Op0, m_Not(m_Specific(Op1))) || 1855 match(Op1, m_Not(m_Specific(Op0)))) 1856 return Constant::getAllOnesValue(Op0->getType()); 1857 1858 // Try some generic simplifications for associative operations. 1859 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, 1860 MaxRecurse)) 1861 return V; 1862 1863 // Threading Xor over selects and phi nodes is pointless, so don't bother. 1864 // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1865 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1866 // only if B and C are equal. If B and C are equal then (since we assume 1867 // that operands have already been simplified) "select(cond, B, C)" should 1868 // have been simplified to the common value of B and C already. Analysing 1869 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1870 // for threading over phi nodes. 1871 1872 return nullptr; 1873} 1874 1875Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *DL, 1876 const TargetLibraryInfo *TLI, 1877 const DominatorTree *DT, AssumptionCache *AC, 1878 const Instruction *CxtI) { 1879 return ::SimplifyXorInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1880 RecursionLimit); 1881} 1882 1883static Type *GetCompareTy(Value *Op) { 1884 return CmpInst::makeCmpResultType(Op->getType()); 1885} 1886 1887/// ExtractEquivalentCondition - Rummage around inside V looking for something 1888/// equivalent to the comparison "LHS Pred RHS". Return such a value if found, 1889/// otherwise return null. Helper function for analyzing max/min idioms. 1890static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1891 Value *LHS, Value *RHS) { 1892 SelectInst *SI = dyn_cast<SelectInst>(V); 1893 if (!SI) 1894 return nullptr; 1895 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1896 if (!Cmp) 1897 return nullptr; 1898 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1899 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1900 return Cmp; 1901 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1902 LHS == CmpRHS && RHS == CmpLHS) 1903 return Cmp; 1904 return nullptr; 1905} 1906 1907// A significant optimization not implemented here is assuming that alloca 1908// addresses are not equal to incoming argument values. They don't *alias*, 1909// as we say, but that doesn't mean they aren't equal, so we take a 1910// conservative approach. 1911// 1912// This is inspired in part by C++11 5.10p1: 1913// "Two pointers of the same type compare equal if and only if they are both 1914// null, both point to the same function, or both represent the same 1915// address." 1916// 1917// This is pretty permissive. 1918// 1919// It's also partly due to C11 6.5.9p6: 1920// "Two pointers compare equal if and only if both are null pointers, both are 1921// pointers to the same object (including a pointer to an object and a 1922// subobject at its beginning) or function, both are pointers to one past the 1923// last element of the same array object, or one is a pointer to one past the 1924// end of one array object and the other is a pointer to the start of a 1925// different array object that happens to immediately follow the first array 1926// object in the address space.) 1927// 1928// C11's version is more restrictive, however there's no reason why an argument 1929// couldn't be a one-past-the-end value for a stack object in the caller and be 1930// equal to the beginning of a stack object in the callee. 1931// 1932// If the C and C++ standards are ever made sufficiently restrictive in this 1933// area, it may be possible to update LLVM's semantics accordingly and reinstate 1934// this optimization. 1935static Constant *computePointerICmp(const DataLayout *DL, 1936 const TargetLibraryInfo *TLI, 1937 CmpInst::Predicate Pred, 1938 Value *LHS, Value *RHS) { 1939 // First, skip past any trivial no-ops. 1940 LHS = LHS->stripPointerCasts(); 1941 RHS = RHS->stripPointerCasts(); 1942 1943 // A non-null pointer is not equal to a null pointer. 1944 if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) && 1945 (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) 1946 return ConstantInt::get(GetCompareTy(LHS), 1947 !CmpInst::isTrueWhenEqual(Pred)); 1948 1949 // We can only fold certain predicates on pointer comparisons. 1950 switch (Pred) { 1951 default: 1952 return nullptr; 1953 1954 // Equality comaprisons are easy to fold. 1955 case CmpInst::ICMP_EQ: 1956 case CmpInst::ICMP_NE: 1957 break; 1958 1959 // We can only handle unsigned relational comparisons because 'inbounds' on 1960 // a GEP only protects against unsigned wrapping. 1961 case CmpInst::ICMP_UGT: 1962 case CmpInst::ICMP_UGE: 1963 case CmpInst::ICMP_ULT: 1964 case CmpInst::ICMP_ULE: 1965 // However, we have to switch them to their signed variants to handle 1966 // negative indices from the base pointer. 1967 Pred = ICmpInst::getSignedPredicate(Pred); 1968 break; 1969 } 1970 1971 // Strip off any constant offsets so that we can reason about them. 1972 // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets 1973 // here and compare base addresses like AliasAnalysis does, however there are 1974 // numerous hazards. AliasAnalysis and its utilities rely on special rules 1975 // governing loads and stores which don't apply to icmps. Also, AliasAnalysis 1976 // doesn't need to guarantee pointer inequality when it says NoAlias. 1977 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 1978 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 1979 1980 // If LHS and RHS are related via constant offsets to the same base 1981 // value, we can replace it with an icmp which just compares the offsets. 1982 if (LHS == RHS) 1983 return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); 1984 1985 // Various optimizations for (in)equality comparisons. 1986 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { 1987 // Different non-empty allocations that exist at the same time have 1988 // different addresses (if the program can tell). Global variables always 1989 // exist, so they always exist during the lifetime of each other and all 1990 // allocas. Two different allocas usually have different addresses... 1991 // 1992 // However, if there's an @llvm.stackrestore dynamically in between two 1993 // allocas, they may have the same address. It's tempting to reduce the 1994 // scope of the problem by only looking at *static* allocas here. That would 1995 // cover the majority of allocas while significantly reducing the likelihood 1996 // of having an @llvm.stackrestore pop up in the middle. However, it's not 1997 // actually impossible for an @llvm.stackrestore to pop up in the middle of 1998 // an entry block. Also, if we have a block that's not attached to a 1999 // function, we can't tell if it's "static" under the current definition. 2000 // Theoretically, this problem could be fixed by creating a new kind of 2001 // instruction kind specifically for static allocas. Such a new instruction 2002 // could be required to be at the top of the entry block, thus preventing it 2003 // from being subject to a @llvm.stackrestore. Instcombine could even 2004 // convert regular allocas into these special allocas. It'd be nifty. 2005 // However, until then, this problem remains open. 2006 // 2007 // So, we'll assume that two non-empty allocas have different addresses 2008 // for now. 2009 // 2010 // With all that, if the offsets are within the bounds of their allocations 2011 // (and not one-past-the-end! so we can't use inbounds!), and their 2012 // allocations aren't the same, the pointers are not equal. 2013 // 2014 // Note that it's not necessary to check for LHS being a global variable 2015 // address, due to canonicalization and constant folding. 2016 if (isa<AllocaInst>(LHS) && 2017 (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) { 2018 ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset); 2019 ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset); 2020 uint64_t LHSSize, RHSSize; 2021 if (LHSOffsetCI && RHSOffsetCI && 2022 getObjectSize(LHS, LHSSize, DL, TLI) && 2023 getObjectSize(RHS, RHSSize, DL, TLI)) { 2024 const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); 2025 const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); 2026 if (!LHSOffsetValue.isNegative() && 2027 !RHSOffsetValue.isNegative() && 2028 LHSOffsetValue.ult(LHSSize) && 2029 RHSOffsetValue.ult(RHSSize)) { 2030 return ConstantInt::get(GetCompareTy(LHS), 2031 !CmpInst::isTrueWhenEqual(Pred)); 2032 } 2033 } 2034 2035 // Repeat the above check but this time without depending on DataLayout 2036 // or being able to compute a precise size. 2037 if (!cast<PointerType>(LHS->getType())->isEmptyTy() && 2038 !cast<PointerType>(RHS->getType())->isEmptyTy() && 2039 LHSOffset->isNullValue() && 2040 RHSOffset->isNullValue()) 2041 return ConstantInt::get(GetCompareTy(LHS), 2042 !CmpInst::isTrueWhenEqual(Pred)); 2043 } 2044 2045 // Even if an non-inbounds GEP occurs along the path we can still optimize 2046 // equality comparisons concerning the result. We avoid walking the whole 2047 // chain again by starting where the last calls to 2048 // stripAndComputeConstantOffsets left off and accumulate the offsets. 2049 Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true); 2050 Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true); 2051 if (LHS == RHS) 2052 return ConstantExpr::getICmp(Pred, 2053 ConstantExpr::getAdd(LHSOffset, LHSNoBound), 2054 ConstantExpr::getAdd(RHSOffset, RHSNoBound)); 2055 2056 // If one side of the equality comparison must come from a noalias call 2057 // (meaning a system memory allocation function), and the other side must 2058 // come from a pointer that cannot overlap with dynamically-allocated 2059 // memory within the lifetime of the current function (allocas, byval 2060 // arguments, globals), then determine the comparison result here. 2061 SmallVector<Value *, 8> LHSUObjs, RHSUObjs; 2062 GetUnderlyingObjects(LHS, LHSUObjs, DL); 2063 GetUnderlyingObjects(RHS, RHSUObjs, DL); 2064 2065 // Is the set of underlying objects all noalias calls? 2066 auto IsNAC = [](SmallVectorImpl<Value *> &Objects) { 2067 return std::all_of(Objects.begin(), Objects.end(), 2068 [](Value *V){ return isNoAliasCall(V); }); 2069 }; 2070 2071 // Is the set of underlying objects all things which must be disjoint from 2072 // noalias calls. For allocas, we consider only static ones (dynamic 2073 // allocas might be transformed into calls to malloc not simultaneously 2074 // live with the compared-to allocation). For globals, we exclude symbols 2075 // that might be resolve lazily to symbols in another dynamically-loaded 2076 // library (and, thus, could be malloc'ed by the implementation). 2077 auto IsAllocDisjoint = [](SmallVectorImpl<Value *> &Objects) { 2078 return std::all_of(Objects.begin(), Objects.end(), 2079 [](Value *V){ 2080 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) 2081 return AI->getParent() && AI->getParent()->getParent() && 2082 AI->isStaticAlloca(); 2083 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2084 return (GV->hasLocalLinkage() || 2085 GV->hasHiddenVisibility() || 2086 GV->hasProtectedVisibility() || 2087 GV->hasUnnamedAddr()) && 2088 !GV->isThreadLocal(); 2089 if (const Argument *A = dyn_cast<Argument>(V)) 2090 return A->hasByValAttr(); 2091 return false; 2092 }); 2093 }; 2094 2095 if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) || 2096 (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs))) 2097 return ConstantInt::get(GetCompareTy(LHS), 2098 !CmpInst::isTrueWhenEqual(Pred)); 2099 } 2100 2101 // Otherwise, fail. 2102 return nullptr; 2103} 2104 2105/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 2106/// fold the result. If not, this returns null. 2107static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2108 const Query &Q, unsigned MaxRecurse) { 2109 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2110 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 2111 2112 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2113 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2114 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 2115 2116 // If we have a constant, make sure it is on the RHS. 2117 std::swap(LHS, RHS); 2118 Pred = CmpInst::getSwappedPredicate(Pred); 2119 } 2120 2121 Type *ITy = GetCompareTy(LHS); // The return type. 2122 Type *OpTy = LHS->getType(); // The operand type. 2123 2124 // icmp X, X -> true/false 2125 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 2126 // because X could be 0. 2127 if (LHS == RHS || isa<UndefValue>(RHS)) 2128 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 2129 2130 // Special case logic when the operands have i1 type. 2131 if (OpTy->getScalarType()->isIntegerTy(1)) { 2132 switch (Pred) { 2133 default: break; 2134 case ICmpInst::ICMP_EQ: 2135 // X == 1 -> X 2136 if (match(RHS, m_One())) 2137 return LHS; 2138 break; 2139 case ICmpInst::ICMP_NE: 2140 // X != 0 -> X 2141 if (match(RHS, m_Zero())) 2142 return LHS; 2143 break; 2144 case ICmpInst::ICMP_UGT: 2145 // X >u 0 -> X 2146 if (match(RHS, m_Zero())) 2147 return LHS; 2148 break; 2149 case ICmpInst::ICMP_UGE: 2150 // X >=u 1 -> X 2151 if (match(RHS, m_One())) 2152 return LHS; 2153 break; 2154 case ICmpInst::ICMP_SLT: 2155 // X <s 0 -> X 2156 if (match(RHS, m_Zero())) 2157 return LHS; 2158 break; 2159 case ICmpInst::ICMP_SLE: 2160 // X <=s -1 -> X 2161 if (match(RHS, m_One())) 2162 return LHS; 2163 break; 2164 } 2165 } 2166 2167 // If we are comparing with zero then try hard since this is a common case. 2168 if (match(RHS, m_Zero())) { 2169 bool LHSKnownNonNegative, LHSKnownNegative; 2170 switch (Pred) { 2171 default: llvm_unreachable("Unknown ICmp predicate!"); 2172 case ICmpInst::ICMP_ULT: 2173 return getFalse(ITy); 2174 case ICmpInst::ICMP_UGE: 2175 return getTrue(ITy); 2176 case ICmpInst::ICMP_EQ: 2177 case ICmpInst::ICMP_ULE: 2178 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2179 return getFalse(ITy); 2180 break; 2181 case ICmpInst::ICMP_NE: 2182 case ICmpInst::ICMP_UGT: 2183 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2184 return getTrue(ITy); 2185 break; 2186 case ICmpInst::ICMP_SLT: 2187 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2188 Q.CxtI, Q.DT); 2189 if (LHSKnownNegative) 2190 return getTrue(ITy); 2191 if (LHSKnownNonNegative) 2192 return getFalse(ITy); 2193 break; 2194 case ICmpInst::ICMP_SLE: 2195 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2196 Q.CxtI, Q.DT); 2197 if (LHSKnownNegative) 2198 return getTrue(ITy); 2199 if (LHSKnownNonNegative && 2200 isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2201 return getFalse(ITy); 2202 break; 2203 case ICmpInst::ICMP_SGE: 2204 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2205 Q.CxtI, Q.DT); 2206 if (LHSKnownNegative) 2207 return getFalse(ITy); 2208 if (LHSKnownNonNegative) 2209 return getTrue(ITy); 2210 break; 2211 case ICmpInst::ICMP_SGT: 2212 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2213 Q.CxtI, Q.DT); 2214 if (LHSKnownNegative) 2215 return getFalse(ITy); 2216 if (LHSKnownNonNegative && 2217 isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2218 return getTrue(ITy); 2219 break; 2220 } 2221 } 2222 2223 // See if we are doing a comparison with a constant integer. 2224 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2225 // Rule out tautological comparisons (eg., ult 0 or uge 0). 2226 ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 2227 if (RHS_CR.isEmptySet()) 2228 return ConstantInt::getFalse(CI->getContext()); 2229 if (RHS_CR.isFullSet()) 2230 return ConstantInt::getTrue(CI->getContext()); 2231 2232 // Many binary operators with constant RHS have easy to compute constant 2233 // range. Use them to check whether the comparison is a tautology. 2234 unsigned Width = CI->getBitWidth(); 2235 APInt Lower = APInt(Width, 0); 2236 APInt Upper = APInt(Width, 0); 2237 ConstantInt *CI2; 2238 if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 2239 // 'urem x, CI2' produces [0, CI2). 2240 Upper = CI2->getValue(); 2241 } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 2242 // 'srem x, CI2' produces (-|CI2|, |CI2|). 2243 Upper = CI2->getValue().abs(); 2244 Lower = (-Upper) + 1; 2245 } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 2246 // 'udiv CI2, x' produces [0, CI2]. 2247 Upper = CI2->getValue() + 1; 2248 } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 2249 // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 2250 APInt NegOne = APInt::getAllOnesValue(Width); 2251 if (!CI2->isZero()) 2252 Upper = NegOne.udiv(CI2->getValue()) + 1; 2253 } else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) { 2254 if (CI2->isMinSignedValue()) { 2255 // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. 2256 Lower = CI2->getValue(); 2257 Upper = Lower.lshr(1) + 1; 2258 } else { 2259 // 'sdiv CI2, x' produces [-|CI2|, |CI2|]. 2260 Upper = CI2->getValue().abs() + 1; 2261 Lower = (-Upper) + 1; 2262 } 2263 } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 2264 APInt IntMin = APInt::getSignedMinValue(Width); 2265 APInt IntMax = APInt::getSignedMaxValue(Width); 2266 APInt Val = CI2->getValue(); 2267 if (Val.isAllOnesValue()) { 2268 // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] 2269 // where CI2 != -1 and CI2 != 0 and CI2 != 1 2270 Lower = IntMin + 1; 2271 Upper = IntMax + 1; 2272 } else if (Val.countLeadingZeros() < Width - 1) { 2273 // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2] 2274 // where CI2 != -1 and CI2 != 0 and CI2 != 1 2275 Lower = IntMin.sdiv(Val); 2276 Upper = IntMax.sdiv(Val); 2277 if (Lower.sgt(Upper)) 2278 std::swap(Lower, Upper); 2279 Upper = Upper + 1; 2280 assert(Upper != Lower && "Upper part of range has wrapped!"); 2281 } 2282 } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) { 2283 // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)] 2284 Lower = CI2->getValue(); 2285 Upper = Lower.shl(Lower.countLeadingZeros()) + 1; 2286 } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) { 2287 if (CI2->isNegative()) { 2288 // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2] 2289 unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1; 2290 Lower = CI2->getValue().shl(ShiftAmount); 2291 Upper = CI2->getValue() + 1; 2292 } else { 2293 // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1] 2294 unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1; 2295 Lower = CI2->getValue(); 2296 Upper = CI2->getValue().shl(ShiftAmount) + 1; 2297 } 2298 } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 2299 // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 2300 APInt NegOne = APInt::getAllOnesValue(Width); 2301 if (CI2->getValue().ult(Width)) 2302 Upper = NegOne.lshr(CI2->getValue()) + 1; 2303 } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) { 2304 // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2]. 2305 unsigned ShiftAmount = Width - 1; 2306 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2307 ShiftAmount = CI2->getValue().countTrailingZeros(); 2308 Lower = CI2->getValue().lshr(ShiftAmount); 2309 Upper = CI2->getValue() + 1; 2310 } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 2311 // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 2312 APInt IntMin = APInt::getSignedMinValue(Width); 2313 APInt IntMax = APInt::getSignedMaxValue(Width); 2314 if (CI2->getValue().ult(Width)) { 2315 Lower = IntMin.ashr(CI2->getValue()); 2316 Upper = IntMax.ashr(CI2->getValue()) + 1; 2317 } 2318 } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) { 2319 unsigned ShiftAmount = Width - 1; 2320 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2321 ShiftAmount = CI2->getValue().countTrailingZeros(); 2322 if (CI2->isNegative()) { 2323 // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)] 2324 Lower = CI2->getValue(); 2325 Upper = CI2->getValue().ashr(ShiftAmount) + 1; 2326 } else { 2327 // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2] 2328 Lower = CI2->getValue().ashr(ShiftAmount); 2329 Upper = CI2->getValue() + 1; 2330 } 2331 } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 2332 // 'or x, CI2' produces [CI2, UINT_MAX]. 2333 Lower = CI2->getValue(); 2334 } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 2335 // 'and x, CI2' produces [0, CI2]. 2336 Upper = CI2->getValue() + 1; 2337 } 2338 if (Lower != Upper) { 2339 ConstantRange LHS_CR = ConstantRange(Lower, Upper); 2340 if (RHS_CR.contains(LHS_CR)) 2341 return ConstantInt::getTrue(RHS->getContext()); 2342 if (RHS_CR.inverse().contains(LHS_CR)) 2343 return ConstantInt::getFalse(RHS->getContext()); 2344 } 2345 } 2346 2347 // Compare of cast, for example (zext X) != 0 -> X != 0 2348 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 2349 Instruction *LI = cast<CastInst>(LHS); 2350 Value *SrcOp = LI->getOperand(0); 2351 Type *SrcTy = SrcOp->getType(); 2352 Type *DstTy = LI->getType(); 2353 2354 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 2355 // if the integer type is the same size as the pointer type. 2356 if (MaxRecurse && Q.DL && isa<PtrToIntInst>(LI) && 2357 Q.DL->getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { 2358 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2359 // Transfer the cast to the constant. 2360 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 2361 ConstantExpr::getIntToPtr(RHSC, SrcTy), 2362 Q, MaxRecurse-1)) 2363 return V; 2364 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 2365 if (RI->getOperand(0)->getType() == SrcTy) 2366 // Compare without the cast. 2367 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2368 Q, MaxRecurse-1)) 2369 return V; 2370 } 2371 } 2372 2373 if (isa<ZExtInst>(LHS)) { 2374 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 2375 // same type. 2376 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 2377 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2378 // Compare X and Y. Note that signed predicates become unsigned. 2379 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2380 SrcOp, RI->getOperand(0), Q, 2381 MaxRecurse-1)) 2382 return V; 2383 } 2384 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 2385 // too. If not, then try to deduce the result of the comparison. 2386 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2387 // Compute the constant that would happen if we truncated to SrcTy then 2388 // reextended to DstTy. 2389 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2390 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 2391 2392 // If the re-extended constant didn't change then this is effectively 2393 // also a case of comparing two zero-extended values. 2394 if (RExt == CI && MaxRecurse) 2395 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2396 SrcOp, Trunc, Q, MaxRecurse-1)) 2397 return V; 2398 2399 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 2400 // there. Use this to work out the result of the comparison. 2401 if (RExt != CI) { 2402 switch (Pred) { 2403 default: llvm_unreachable("Unknown ICmp predicate!"); 2404 // LHS <u RHS. 2405 case ICmpInst::ICMP_EQ: 2406 case ICmpInst::ICMP_UGT: 2407 case ICmpInst::ICMP_UGE: 2408 return ConstantInt::getFalse(CI->getContext()); 2409 2410 case ICmpInst::ICMP_NE: 2411 case ICmpInst::ICMP_ULT: 2412 case ICmpInst::ICMP_ULE: 2413 return ConstantInt::getTrue(CI->getContext()); 2414 2415 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 2416 // is non-negative then LHS <s RHS. 2417 case ICmpInst::ICMP_SGT: 2418 case ICmpInst::ICMP_SGE: 2419 return CI->getValue().isNegative() ? 2420 ConstantInt::getTrue(CI->getContext()) : 2421 ConstantInt::getFalse(CI->getContext()); 2422 2423 case ICmpInst::ICMP_SLT: 2424 case ICmpInst::ICMP_SLE: 2425 return CI->getValue().isNegative() ? 2426 ConstantInt::getFalse(CI->getContext()) : 2427 ConstantInt::getTrue(CI->getContext()); 2428 } 2429 } 2430 } 2431 } 2432 2433 if (isa<SExtInst>(LHS)) { 2434 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 2435 // same type. 2436 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 2437 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2438 // Compare X and Y. Note that the predicate does not change. 2439 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2440 Q, MaxRecurse-1)) 2441 return V; 2442 } 2443 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 2444 // too. If not, then try to deduce the result of the comparison. 2445 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2446 // Compute the constant that would happen if we truncated to SrcTy then 2447 // reextended to DstTy. 2448 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2449 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 2450 2451 // If the re-extended constant didn't change then this is effectively 2452 // also a case of comparing two sign-extended values. 2453 if (RExt == CI && MaxRecurse) 2454 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1)) 2455 return V; 2456 2457 // Otherwise the upper bits of LHS are all equal, while RHS has varying 2458 // bits there. Use this to work out the result of the comparison. 2459 if (RExt != CI) { 2460 switch (Pred) { 2461 default: llvm_unreachable("Unknown ICmp predicate!"); 2462 case ICmpInst::ICMP_EQ: 2463 return ConstantInt::getFalse(CI->getContext()); 2464 case ICmpInst::ICMP_NE: 2465 return ConstantInt::getTrue(CI->getContext()); 2466 2467 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 2468 // LHS >s RHS. 2469 case ICmpInst::ICMP_SGT: 2470 case ICmpInst::ICMP_SGE: 2471 return CI->getValue().isNegative() ? 2472 ConstantInt::getTrue(CI->getContext()) : 2473 ConstantInt::getFalse(CI->getContext()); 2474 case ICmpInst::ICMP_SLT: 2475 case ICmpInst::ICMP_SLE: 2476 return CI->getValue().isNegative() ? 2477 ConstantInt::getFalse(CI->getContext()) : 2478 ConstantInt::getTrue(CI->getContext()); 2479 2480 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 2481 // LHS >u RHS. 2482 case ICmpInst::ICMP_UGT: 2483 case ICmpInst::ICMP_UGE: 2484 // Comparison is true iff the LHS <s 0. 2485 if (MaxRecurse) 2486 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 2487 Constant::getNullValue(SrcTy), 2488 Q, MaxRecurse-1)) 2489 return V; 2490 break; 2491 case ICmpInst::ICMP_ULT: 2492 case ICmpInst::ICMP_ULE: 2493 // Comparison is true iff the LHS >=s 0. 2494 if (MaxRecurse) 2495 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 2496 Constant::getNullValue(SrcTy), 2497 Q, MaxRecurse-1)) 2498 return V; 2499 break; 2500 } 2501 } 2502 } 2503 } 2504 } 2505 2506 // Special logic for binary operators. 2507 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 2508 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 2509 if (MaxRecurse && (LBO || RBO)) { 2510 // Analyze the case when either LHS or RHS is an add instruction. 2511 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 2512 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 2513 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 2514 if (LBO && LBO->getOpcode() == Instruction::Add) { 2515 A = LBO->getOperand(0); B = LBO->getOperand(1); 2516 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 2517 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 2518 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 2519 } 2520 if (RBO && RBO->getOpcode() == Instruction::Add) { 2521 C = RBO->getOperand(0); D = RBO->getOperand(1); 2522 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 2523 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 2524 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 2525 } 2526 2527 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 2528 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 2529 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 2530 Constant::getNullValue(RHS->getType()), 2531 Q, MaxRecurse-1)) 2532 return V; 2533 2534 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 2535 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 2536 if (Value *V = SimplifyICmpInst(Pred, 2537 Constant::getNullValue(LHS->getType()), 2538 C == LHS ? D : C, Q, MaxRecurse-1)) 2539 return V; 2540 2541 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 2542 if (A && C && (A == C || A == D || B == C || B == D) && 2543 NoLHSWrapProblem && NoRHSWrapProblem) { 2544 // Determine Y and Z in the form icmp (X+Y), (X+Z). 2545 Value *Y, *Z; 2546 if (A == C) { 2547 // C + B == C + D -> B == D 2548 Y = B; 2549 Z = D; 2550 } else if (A == D) { 2551 // D + B == C + D -> B == C 2552 Y = B; 2553 Z = C; 2554 } else if (B == C) { 2555 // A + C == C + D -> A == D 2556 Y = A; 2557 Z = D; 2558 } else { 2559 assert(B == D); 2560 // A + D == C + D -> A == C 2561 Y = A; 2562 Z = C; 2563 } 2564 if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1)) 2565 return V; 2566 } 2567 } 2568 2569 // icmp pred (or X, Y), X 2570 if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)), 2571 m_Or(m_Specific(RHS), m_Value())))) { 2572 if (Pred == ICmpInst::ICMP_ULT) 2573 return getFalse(ITy); 2574 if (Pred == ICmpInst::ICMP_UGE) 2575 return getTrue(ITy); 2576 } 2577 // icmp pred X, (or X, Y) 2578 if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)), 2579 m_Or(m_Specific(LHS), m_Value())))) { 2580 if (Pred == ICmpInst::ICMP_ULE) 2581 return getTrue(ITy); 2582 if (Pred == ICmpInst::ICMP_UGT) 2583 return getFalse(ITy); 2584 } 2585 2586 // icmp pred (and X, Y), X 2587 if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)), 2588 m_And(m_Specific(RHS), m_Value())))) { 2589 if (Pred == ICmpInst::ICMP_UGT) 2590 return getFalse(ITy); 2591 if (Pred == ICmpInst::ICMP_ULE) 2592 return getTrue(ITy); 2593 } 2594 // icmp pred X, (and X, Y) 2595 if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)), 2596 m_And(m_Specific(LHS), m_Value())))) { 2597 if (Pred == ICmpInst::ICMP_UGE) 2598 return getTrue(ITy); 2599 if (Pred == ICmpInst::ICMP_ULT) 2600 return getFalse(ITy); 2601 } 2602 2603 // 0 - (zext X) pred C 2604 if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) { 2605 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 2606 if (RHSC->getValue().isStrictlyPositive()) { 2607 if (Pred == ICmpInst::ICMP_SLT) 2608 return ConstantInt::getTrue(RHSC->getContext()); 2609 if (Pred == ICmpInst::ICMP_SGE) 2610 return ConstantInt::getFalse(RHSC->getContext()); 2611 if (Pred == ICmpInst::ICMP_EQ) 2612 return ConstantInt::getFalse(RHSC->getContext()); 2613 if (Pred == ICmpInst::ICMP_NE) 2614 return ConstantInt::getTrue(RHSC->getContext()); 2615 } 2616 if (RHSC->getValue().isNonNegative()) { 2617 if (Pred == ICmpInst::ICMP_SLE) 2618 return ConstantInt::getTrue(RHSC->getContext()); 2619 if (Pred == ICmpInst::ICMP_SGT) 2620 return ConstantInt::getFalse(RHSC->getContext()); 2621 } 2622 } 2623 } 2624 2625 // icmp pred (urem X, Y), Y 2626 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 2627 bool KnownNonNegative, KnownNegative; 2628 switch (Pred) { 2629 default: 2630 break; 2631 case ICmpInst::ICMP_SGT: 2632 case ICmpInst::ICMP_SGE: 2633 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2634 Q.CxtI, Q.DT); 2635 if (!KnownNonNegative) 2636 break; 2637 // fall-through 2638 case ICmpInst::ICMP_EQ: 2639 case ICmpInst::ICMP_UGT: 2640 case ICmpInst::ICMP_UGE: 2641 return getFalse(ITy); 2642 case ICmpInst::ICMP_SLT: 2643 case ICmpInst::ICMP_SLE: 2644 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2645 Q.CxtI, Q.DT); 2646 if (!KnownNonNegative) 2647 break; 2648 // fall-through 2649 case ICmpInst::ICMP_NE: 2650 case ICmpInst::ICMP_ULT: 2651 case ICmpInst::ICMP_ULE: 2652 return getTrue(ITy); 2653 } 2654 } 2655 2656 // icmp pred X, (urem Y, X) 2657 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 2658 bool KnownNonNegative, KnownNegative; 2659 switch (Pred) { 2660 default: 2661 break; 2662 case ICmpInst::ICMP_SGT: 2663 case ICmpInst::ICMP_SGE: 2664 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2665 Q.CxtI, Q.DT); 2666 if (!KnownNonNegative) 2667 break; 2668 // fall-through 2669 case ICmpInst::ICMP_NE: 2670 case ICmpInst::ICMP_UGT: 2671 case ICmpInst::ICMP_UGE: 2672 return getTrue(ITy); 2673 case ICmpInst::ICMP_SLT: 2674 case ICmpInst::ICMP_SLE: 2675 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2676 Q.CxtI, Q.DT); 2677 if (!KnownNonNegative) 2678 break; 2679 // fall-through 2680 case ICmpInst::ICMP_EQ: 2681 case ICmpInst::ICMP_ULT: 2682 case ICmpInst::ICMP_ULE: 2683 return getFalse(ITy); 2684 } 2685 } 2686 2687 // x udiv y <=u x. 2688 if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 2689 // icmp pred (X /u Y), X 2690 if (Pred == ICmpInst::ICMP_UGT) 2691 return getFalse(ITy); 2692 if (Pred == ICmpInst::ICMP_ULE) 2693 return getTrue(ITy); 2694 } 2695 2696 // handle: 2697 // CI2 << X == CI 2698 // CI2 << X != CI 2699 // 2700 // where CI2 is a power of 2 and CI isn't 2701 if (auto *CI = dyn_cast<ConstantInt>(RHS)) { 2702 const APInt *CI2Val, *CIVal = &CI->getValue(); 2703 if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) && 2704 CI2Val->isPowerOf2()) { 2705 if (!CIVal->isPowerOf2()) { 2706 // CI2 << X can equal zero in some circumstances, 2707 // this simplification is unsafe if CI is zero. 2708 // 2709 // We know it is safe if: 2710 // - The shift is nsw, we can't shift out the one bit. 2711 // - The shift is nuw, we can't shift out the one bit. 2712 // - CI2 is one 2713 // - CI isn't zero 2714 if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() || 2715 *CI2Val == 1 || !CI->isZero()) { 2716 if (Pred == ICmpInst::ICMP_EQ) 2717 return ConstantInt::getFalse(RHS->getContext()); 2718 if (Pred == ICmpInst::ICMP_NE) 2719 return ConstantInt::getTrue(RHS->getContext()); 2720 } 2721 } 2722 if (CIVal->isSignBit() && *CI2Val == 1) { 2723 if (Pred == ICmpInst::ICMP_UGT) 2724 return ConstantInt::getFalse(RHS->getContext()); 2725 if (Pred == ICmpInst::ICMP_ULE) 2726 return ConstantInt::getTrue(RHS->getContext()); 2727 } 2728 } 2729 } 2730 2731 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 2732 LBO->getOperand(1) == RBO->getOperand(1)) { 2733 switch (LBO->getOpcode()) { 2734 default: break; 2735 case Instruction::UDiv: 2736 case Instruction::LShr: 2737 if (ICmpInst::isSigned(Pred)) 2738 break; 2739 // fall-through 2740 case Instruction::SDiv: 2741 case Instruction::AShr: 2742 if (!LBO->isExact() || !RBO->isExact()) 2743 break; 2744 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2745 RBO->getOperand(0), Q, MaxRecurse-1)) 2746 return V; 2747 break; 2748 case Instruction::Shl: { 2749 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2750 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2751 if (!NUW && !NSW) 2752 break; 2753 if (!NSW && ICmpInst::isSigned(Pred)) 2754 break; 2755 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2756 RBO->getOperand(0), Q, MaxRecurse-1)) 2757 return V; 2758 break; 2759 } 2760 } 2761 } 2762 2763 // Simplify comparisons involving max/min. 2764 Value *A, *B; 2765 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2766 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2767 2768 // Signed variants on "max(a,b)>=a -> true". 2769 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2770 if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2771 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2772 // We analyze this as smax(A, B) pred A. 2773 P = Pred; 2774 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2775 (A == LHS || B == LHS)) { 2776 if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2777 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2778 // We analyze this as smax(A, B) swapped-pred A. 2779 P = CmpInst::getSwappedPredicate(Pred); 2780 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2781 (A == RHS || B == RHS)) { 2782 if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2783 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2784 // We analyze this as smax(-A, -B) swapped-pred -A. 2785 // Note that we do not need to actually form -A or -B thanks to EqP. 2786 P = CmpInst::getSwappedPredicate(Pred); 2787 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2788 (A == LHS || B == LHS)) { 2789 if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2790 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2791 // We analyze this as smax(-A, -B) pred -A. 2792 // Note that we do not need to actually form -A or -B thanks to EqP. 2793 P = Pred; 2794 } 2795 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2796 // Cases correspond to "max(A, B) p A". 2797 switch (P) { 2798 default: 2799 break; 2800 case CmpInst::ICMP_EQ: 2801 case CmpInst::ICMP_SLE: 2802 // Equivalent to "A EqP B". This may be the same as the condition tested 2803 // in the max/min; if so, we can just return that. 2804 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2805 return V; 2806 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2807 return V; 2808 // Otherwise, see if "A EqP B" simplifies. 2809 if (MaxRecurse) 2810 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2811 return V; 2812 break; 2813 case CmpInst::ICMP_NE: 2814 case CmpInst::ICMP_SGT: { 2815 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2816 // Equivalent to "A InvEqP B". This may be the same as the condition 2817 // tested in the max/min; if so, we can just return that. 2818 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2819 return V; 2820 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2821 return V; 2822 // Otherwise, see if "A InvEqP B" simplifies. 2823 if (MaxRecurse) 2824 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2825 return V; 2826 break; 2827 } 2828 case CmpInst::ICMP_SGE: 2829 // Always true. 2830 return getTrue(ITy); 2831 case CmpInst::ICMP_SLT: 2832 // Always false. 2833 return getFalse(ITy); 2834 } 2835 } 2836 2837 // Unsigned variants on "max(a,b)>=a -> true". 2838 P = CmpInst::BAD_ICMP_PREDICATE; 2839 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2840 if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2841 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2842 // We analyze this as umax(A, B) pred A. 2843 P = Pred; 2844 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2845 (A == LHS || B == LHS)) { 2846 if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2847 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2848 // We analyze this as umax(A, B) swapped-pred A. 2849 P = CmpInst::getSwappedPredicate(Pred); 2850 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2851 (A == RHS || B == RHS)) { 2852 if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2853 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2854 // We analyze this as umax(-A, -B) swapped-pred -A. 2855 // Note that we do not need to actually form -A or -B thanks to EqP. 2856 P = CmpInst::getSwappedPredicate(Pred); 2857 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2858 (A == LHS || B == LHS)) { 2859 if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2860 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2861 // We analyze this as umax(-A, -B) pred -A. 2862 // Note that we do not need to actually form -A or -B thanks to EqP. 2863 P = Pred; 2864 } 2865 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2866 // Cases correspond to "max(A, B) p A". 2867 switch (P) { 2868 default: 2869 break; 2870 case CmpInst::ICMP_EQ: 2871 case CmpInst::ICMP_ULE: 2872 // Equivalent to "A EqP B". This may be the same as the condition tested 2873 // in the max/min; if so, we can just return that. 2874 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2875 return V; 2876 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2877 return V; 2878 // Otherwise, see if "A EqP B" simplifies. 2879 if (MaxRecurse) 2880 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2881 return V; 2882 break; 2883 case CmpInst::ICMP_NE: 2884 case CmpInst::ICMP_UGT: { 2885 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2886 // Equivalent to "A InvEqP B". This may be the same as the condition 2887 // tested in the max/min; if so, we can just return that. 2888 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2889 return V; 2890 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2891 return V; 2892 // Otherwise, see if "A InvEqP B" simplifies. 2893 if (MaxRecurse) 2894 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2895 return V; 2896 break; 2897 } 2898 case CmpInst::ICMP_UGE: 2899 // Always true. 2900 return getTrue(ITy); 2901 case CmpInst::ICMP_ULT: 2902 // Always false. 2903 return getFalse(ITy); 2904 } 2905 } 2906 2907 // Variants on "max(x,y) >= min(x,z)". 2908 Value *C, *D; 2909 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2910 match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2911 (A == C || A == D || B == C || B == D)) { 2912 // max(x, ?) pred min(x, ?). 2913 if (Pred == CmpInst::ICMP_SGE) 2914 // Always true. 2915 return getTrue(ITy); 2916 if (Pred == CmpInst::ICMP_SLT) 2917 // Always false. 2918 return getFalse(ITy); 2919 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2920 match(RHS, m_SMax(m_Value(C), m_Value(D))) && 2921 (A == C || A == D || B == C || B == D)) { 2922 // min(x, ?) pred max(x, ?). 2923 if (Pred == CmpInst::ICMP_SLE) 2924 // Always true. 2925 return getTrue(ITy); 2926 if (Pred == CmpInst::ICMP_SGT) 2927 // Always false. 2928 return getFalse(ITy); 2929 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 2930 match(RHS, m_UMin(m_Value(C), m_Value(D))) && 2931 (A == C || A == D || B == C || B == D)) { 2932 // max(x, ?) pred min(x, ?). 2933 if (Pred == CmpInst::ICMP_UGE) 2934 // Always true. 2935 return getTrue(ITy); 2936 if (Pred == CmpInst::ICMP_ULT) 2937 // Always false. 2938 return getFalse(ITy); 2939 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2940 match(RHS, m_UMax(m_Value(C), m_Value(D))) && 2941 (A == C || A == D || B == C || B == D)) { 2942 // min(x, ?) pred max(x, ?). 2943 if (Pred == CmpInst::ICMP_ULE) 2944 // Always true. 2945 return getTrue(ITy); 2946 if (Pred == CmpInst::ICMP_UGT) 2947 // Always false. 2948 return getFalse(ITy); 2949 } 2950 2951 // Simplify comparisons of related pointers using a powerful, recursive 2952 // GEP-walk when we have target data available.. 2953 if (LHS->getType()->isPointerTy()) 2954 if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS)) 2955 return C; 2956 2957 if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) { 2958 if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) { 2959 if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && 2960 GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() && 2961 (ICmpInst::isEquality(Pred) || 2962 (GLHS->isInBounds() && GRHS->isInBounds() && 2963 Pred == ICmpInst::getSignedPredicate(Pred)))) { 2964 // The bases are equal and the indices are constant. Build a constant 2965 // expression GEP with the same indices and a null base pointer to see 2966 // what constant folding can make out of it. 2967 Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); 2968 SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); 2969 Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS); 2970 2971 SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); 2972 Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS); 2973 return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); 2974 } 2975 } 2976 } 2977 2978 // If a bit is known to be zero for A and known to be one for B, 2979 // then A and B cannot be equal. 2980 if (ICmpInst::isEquality(Pred)) { 2981 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2982 uint32_t BitWidth = CI->getBitWidth(); 2983 APInt LHSKnownZero(BitWidth, 0); 2984 APInt LHSKnownOne(BitWidth, 0); 2985 computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC, 2986 Q.CxtI, Q.DT); 2987 const APInt &RHSVal = CI->getValue(); 2988 if (((LHSKnownZero & RHSVal) != 0) || ((LHSKnownOne & ~RHSVal) != 0)) 2989 return Pred == ICmpInst::ICMP_EQ 2990 ? ConstantInt::getFalse(CI->getContext()) 2991 : ConstantInt::getTrue(CI->getContext()); 2992 } 2993 } 2994 2995 // If the comparison is with the result of a select instruction, check whether 2996 // comparing with either branch of the select always yields the same value. 2997 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2998 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 2999 return V; 3000 3001 // If the comparison is with the result of a phi instruction, check whether 3002 // doing the compare with each incoming phi value yields a common result. 3003 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3004 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3005 return V; 3006 3007 return nullptr; 3008} 3009 3010Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3011 const DataLayout *DL, 3012 const TargetLibraryInfo *TLI, 3013 const DominatorTree *DT, AssumptionCache *AC, 3014 Instruction *CxtI) { 3015 return ::SimplifyICmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3016 RecursionLimit); 3017} 3018 3019/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 3020/// fold the result. If not, this returns null. 3021static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3022 const Query &Q, unsigned MaxRecurse) { 3023 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 3024 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 3025 3026 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 3027 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 3028 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 3029 3030 // If we have a constant, make sure it is on the RHS. 3031 std::swap(LHS, RHS); 3032 Pred = CmpInst::getSwappedPredicate(Pred); 3033 } 3034 3035 // Fold trivial predicates. 3036 if (Pred == FCmpInst::FCMP_FALSE) 3037 return ConstantInt::get(GetCompareTy(LHS), 0); 3038 if (Pred == FCmpInst::FCMP_TRUE) 3039 return ConstantInt::get(GetCompareTy(LHS), 1); 3040 3041 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 3042 return UndefValue::get(GetCompareTy(LHS)); 3043 3044 // fcmp x,x -> true/false. Not all compares are foldable. 3045 if (LHS == RHS) { 3046 if (CmpInst::isTrueWhenEqual(Pred)) 3047 return ConstantInt::get(GetCompareTy(LHS), 1); 3048 if (CmpInst::isFalseWhenEqual(Pred)) 3049 return ConstantInt::get(GetCompareTy(LHS), 0); 3050 } 3051 3052 // Handle fcmp with constant RHS 3053 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 3054 // If the constant is a nan, see if we can fold the comparison based on it. 3055 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 3056 if (CFP->getValueAPF().isNaN()) { 3057 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 3058 return ConstantInt::getFalse(CFP->getContext()); 3059 assert(FCmpInst::isUnordered(Pred) && 3060 "Comparison must be either ordered or unordered!"); 3061 // True if unordered. 3062 return ConstantInt::getTrue(CFP->getContext()); 3063 } 3064 // Check whether the constant is an infinity. 3065 if (CFP->getValueAPF().isInfinity()) { 3066 if (CFP->getValueAPF().isNegative()) { 3067 switch (Pred) { 3068 case FCmpInst::FCMP_OLT: 3069 // No value is ordered and less than negative infinity. 3070 return ConstantInt::getFalse(CFP->getContext()); 3071 case FCmpInst::FCMP_UGE: 3072 // All values are unordered with or at least negative infinity. 3073 return ConstantInt::getTrue(CFP->getContext()); 3074 default: 3075 break; 3076 } 3077 } else { 3078 switch (Pred) { 3079 case FCmpInst::FCMP_OGT: 3080 // No value is ordered and greater than infinity. 3081 return ConstantInt::getFalse(CFP->getContext()); 3082 case FCmpInst::FCMP_ULE: 3083 // All values are unordered with and at most infinity. 3084 return ConstantInt::getTrue(CFP->getContext()); 3085 default: 3086 break; 3087 } 3088 } 3089 } 3090 } 3091 } 3092 3093 // If the comparison is with the result of a select instruction, check whether 3094 // comparing with either branch of the select always yields the same value. 3095 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3096 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 3097 return V; 3098 3099 // If the comparison is with the result of a phi instruction, check whether 3100 // doing the compare with each incoming phi value yields a common result. 3101 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3102 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3103 return V; 3104 3105 return nullptr; 3106} 3107 3108Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3109 const DataLayout *DL, 3110 const TargetLibraryInfo *TLI, 3111 const DominatorTree *DT, AssumptionCache *AC, 3112 const Instruction *CxtI) { 3113 return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3114 RecursionLimit); 3115} 3116 3117/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 3118/// the result. If not, this returns null. 3119static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, 3120 Value *FalseVal, const Query &Q, 3121 unsigned MaxRecurse) { 3122 // select true, X, Y -> X 3123 // select false, X, Y -> Y 3124 if (Constant *CB = dyn_cast<Constant>(CondVal)) { 3125 if (CB->isAllOnesValue()) 3126 return TrueVal; 3127 if (CB->isNullValue()) 3128 return FalseVal; 3129 } 3130 3131 // select C, X, X -> X 3132 if (TrueVal == FalseVal) 3133 return TrueVal; 3134 3135 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 3136 if (isa<Constant>(TrueVal)) 3137 return TrueVal; 3138 return FalseVal; 3139 } 3140 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 3141 return FalseVal; 3142 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 3143 return TrueVal; 3144 3145 const auto *ICI = dyn_cast<ICmpInst>(CondVal); 3146 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits(); 3147 if (ICI && BitWidth) { 3148 ICmpInst::Predicate Pred = ICI->getPredicate(); 3149 APInt MinSignedValue = APInt::getSignBit(BitWidth); 3150 Value *X; 3151 const APInt *Y; 3152 bool TrueWhenUnset; 3153 bool IsBitTest = false; 3154 if (ICmpInst::isEquality(Pred) && 3155 match(ICI->getOperand(0), m_And(m_Value(X), m_APInt(Y))) && 3156 match(ICI->getOperand(1), m_Zero())) { 3157 IsBitTest = true; 3158 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ; 3159 } else if (Pred == ICmpInst::ICMP_SLT && 3160 match(ICI->getOperand(1), m_Zero())) { 3161 X = ICI->getOperand(0); 3162 Y = &MinSignedValue; 3163 IsBitTest = true; 3164 TrueWhenUnset = false; 3165 } else if (Pred == ICmpInst::ICMP_SGT && 3166 match(ICI->getOperand(1), m_AllOnes())) { 3167 X = ICI->getOperand(0); 3168 Y = &MinSignedValue; 3169 IsBitTest = true; 3170 TrueWhenUnset = true; 3171 } 3172 if (IsBitTest) { 3173 const APInt *C; 3174 // (X & Y) == 0 ? X & ~Y : X --> X 3175 // (X & Y) != 0 ? X & ~Y : X --> X & ~Y 3176 if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) && 3177 *Y == ~*C) 3178 return TrueWhenUnset ? FalseVal : TrueVal; 3179 // (X & Y) == 0 ? X : X & ~Y --> X & ~Y 3180 // (X & Y) != 0 ? X : X & ~Y --> X 3181 if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) && 3182 *Y == ~*C) 3183 return TrueWhenUnset ? FalseVal : TrueVal; 3184 3185 if (Y->isPowerOf2()) { 3186 // (X & Y) == 0 ? X | Y : X --> X | Y 3187 // (X & Y) != 0 ? X | Y : X --> X 3188 if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) && 3189 *Y == *C) 3190 return TrueWhenUnset ? TrueVal : FalseVal; 3191 // (X & Y) == 0 ? X : X | Y --> X 3192 // (X & Y) != 0 ? X : X | Y --> X | Y 3193 if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) && 3194 *Y == *C) 3195 return TrueWhenUnset ? TrueVal : FalseVal; 3196 } 3197 } 3198 } 3199 3200 return nullptr; 3201} 3202 3203Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 3204 const DataLayout *DL, 3205 const TargetLibraryInfo *TLI, 3206 const DominatorTree *DT, AssumptionCache *AC, 3207 const Instruction *CxtI) { 3208 return ::SimplifySelectInst(Cond, TrueVal, FalseVal, 3209 Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3210} 3211 3212/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 3213/// fold the result. If not, this returns null. 3214static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { 3215 // The type of the GEP pointer operand. 3216 PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()->getScalarType()); 3217 unsigned AS = PtrTy->getAddressSpace(); 3218 3219 // getelementptr P -> P. 3220 if (Ops.size() == 1) 3221 return Ops[0]; 3222 3223 // Compute the (pointer) type returned by the GEP instruction. 3224 Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1)); 3225 Type *GEPTy = PointerType::get(LastType, AS); 3226 if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType())) 3227 GEPTy = VectorType::get(GEPTy, VT->getNumElements()); 3228 3229 if (isa<UndefValue>(Ops[0])) 3230 return UndefValue::get(GEPTy); 3231 3232 if (Ops.size() == 2) { 3233 // getelementptr P, 0 -> P. 3234 if (match(Ops[1], m_Zero())) 3235 return Ops[0]; 3236 3237 Type *Ty = PtrTy->getElementType(); 3238 if (Q.DL && Ty->isSized()) { 3239 Value *P; 3240 uint64_t C; 3241 uint64_t TyAllocSize = Q.DL->getTypeAllocSize(Ty); 3242 // getelementptr P, N -> P if P points to a type of zero size. 3243 if (TyAllocSize == 0) 3244 return Ops[0]; 3245 3246 // The following transforms are only safe if the ptrtoint cast 3247 // doesn't truncate the pointers. 3248 if (Ops[1]->getType()->getScalarSizeInBits() == 3249 Q.DL->getPointerSizeInBits(AS)) { 3250 auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { 3251 if (match(P, m_Zero())) 3252 return Constant::getNullValue(GEPTy); 3253 Value *Temp; 3254 if (match(P, m_PtrToInt(m_Value(Temp)))) 3255 if (Temp->getType() == GEPTy) 3256 return Temp; 3257 return nullptr; 3258 }; 3259 3260 // getelementptr V, (sub P, V) -> P if P points to a type of size 1. 3261 if (TyAllocSize == 1 && 3262 match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))))) 3263 if (Value *R = PtrToIntOrZero(P)) 3264 return R; 3265 3266 // getelementptr V, (ashr (sub P, V), C) -> Q 3267 // if P points to a type of size 1 << C. 3268 if (match(Ops[1], 3269 m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3270 m_ConstantInt(C))) && 3271 TyAllocSize == 1ULL << C) 3272 if (Value *R = PtrToIntOrZero(P)) 3273 return R; 3274 3275 // getelementptr V, (sdiv (sub P, V), C) -> Q 3276 // if P points to a type of size C. 3277 if (match(Ops[1], 3278 m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3279 m_SpecificInt(TyAllocSize)))) 3280 if (Value *R = PtrToIntOrZero(P)) 3281 return R; 3282 } 3283 } 3284 } 3285 3286 // Check to see if this is constant foldable. 3287 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 3288 if (!isa<Constant>(Ops[i])) 3289 return nullptr; 3290 3291 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1)); 3292} 3293 3294Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *DL, 3295 const TargetLibraryInfo *TLI, 3296 const DominatorTree *DT, AssumptionCache *AC, 3297 const Instruction *CxtI) { 3298 return ::SimplifyGEPInst(Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3299} 3300 3301/// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we 3302/// can fold the result. If not, this returns null. 3303static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, 3304 ArrayRef<unsigned> Idxs, const Query &Q, 3305 unsigned) { 3306 if (Constant *CAgg = dyn_cast<Constant>(Agg)) 3307 if (Constant *CVal = dyn_cast<Constant>(Val)) 3308 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 3309 3310 // insertvalue x, undef, n -> x 3311 if (match(Val, m_Undef())) 3312 return Agg; 3313 3314 // insertvalue x, (extractvalue y, n), n 3315 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 3316 if (EV->getAggregateOperand()->getType() == Agg->getType() && 3317 EV->getIndices() == Idxs) { 3318 // insertvalue undef, (extractvalue y, n), n -> y 3319 if (match(Agg, m_Undef())) 3320 return EV->getAggregateOperand(); 3321 3322 // insertvalue y, (extractvalue y, n), n -> y 3323 if (Agg == EV->getAggregateOperand()) 3324 return Agg; 3325 } 3326 3327 return nullptr; 3328} 3329 3330Value *llvm::SimplifyInsertValueInst( 3331 Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout *DL, 3332 const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, 3333 const Instruction *CxtI) { 3334 return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI), 3335 RecursionLimit); 3336} 3337 3338/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 3339static Value *SimplifyPHINode(PHINode *PN, const Query &Q) { 3340 // If all of the PHI's incoming values are the same then replace the PHI node 3341 // with the common value. 3342 Value *CommonValue = nullptr; 3343 bool HasUndefInput = false; 3344 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 3345 Value *Incoming = PN->getIncomingValue(i); 3346 // If the incoming value is the phi node itself, it can safely be skipped. 3347 if (Incoming == PN) continue; 3348 if (isa<UndefValue>(Incoming)) { 3349 // Remember that we saw an undef value, but otherwise ignore them. 3350 HasUndefInput = true; 3351 continue; 3352 } 3353 if (CommonValue && Incoming != CommonValue) 3354 return nullptr; // Not the same, bail out. 3355 CommonValue = Incoming; 3356 } 3357 3358 // If CommonValue is null then all of the incoming values were either undef or 3359 // equal to the phi node itself. 3360 if (!CommonValue) 3361 return UndefValue::get(PN->getType()); 3362 3363 // If we have a PHI node like phi(X, undef, X), where X is defined by some 3364 // instruction, we cannot return X as the result of the PHI node unless it 3365 // dominates the PHI block. 3366 if (HasUndefInput) 3367 return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr; 3368 3369 return CommonValue; 3370} 3371 3372static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { 3373 if (Constant *C = dyn_cast<Constant>(Op)) 3374 return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI); 3375 3376 return nullptr; 3377} 3378 3379Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *DL, 3380 const TargetLibraryInfo *TLI, 3381 const DominatorTree *DT, AssumptionCache *AC, 3382 const Instruction *CxtI) { 3383 return ::SimplifyTruncInst(Op, Ty, Query(DL, TLI, DT, AC, CxtI), 3384 RecursionLimit); 3385} 3386 3387//=== Helper functions for higher up the class hierarchy. 3388 3389/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 3390/// fold the result. If not, this returns null. 3391static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3392 const Query &Q, unsigned MaxRecurse) { 3393 switch (Opcode) { 3394 case Instruction::Add: 3395 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3396 Q, MaxRecurse); 3397 case Instruction::FAdd: 3398 return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3399 3400 case Instruction::Sub: 3401 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3402 Q, MaxRecurse); 3403 case Instruction::FSub: 3404 return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3405 3406 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, Q, MaxRecurse); 3407 case Instruction::FMul: 3408 return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3409 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); 3410 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); 3411 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse); 3412 case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); 3413 case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); 3414 case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, Q, MaxRecurse); 3415 case Instruction::Shl: 3416 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3417 Q, MaxRecurse); 3418 case Instruction::LShr: 3419 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3420 case Instruction::AShr: 3421 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3422 case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse); 3423 case Instruction::Or: return SimplifyOrInst (LHS, RHS, Q, MaxRecurse); 3424 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse); 3425 default: 3426 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 3427 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 3428 Constant *COps[] = {CLHS, CRHS}; 3429 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL, 3430 Q.TLI); 3431 } 3432 3433 // If the operation is associative, try some generic simplifications. 3434 if (Instruction::isAssociative(Opcode)) 3435 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse)) 3436 return V; 3437 3438 // If the operation is with the result of a select instruction check whether 3439 // operating on either branch of the select always yields the same value. 3440 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3441 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse)) 3442 return V; 3443 3444 // If the operation is with the result of a phi instruction, check whether 3445 // operating on all incoming values of the phi always yields the same value. 3446 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3447 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse)) 3448 return V; 3449 3450 return nullptr; 3451 } 3452} 3453 3454Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3455 const DataLayout *DL, const TargetLibraryInfo *TLI, 3456 const DominatorTree *DT, AssumptionCache *AC, 3457 const Instruction *CxtI) { 3458 return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3459 RecursionLimit); 3460} 3461 3462/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 3463/// fold the result. 3464static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3465 const Query &Q, unsigned MaxRecurse) { 3466 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 3467 return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 3468 return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 3469} 3470 3471Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3472 const DataLayout *DL, const TargetLibraryInfo *TLI, 3473 const DominatorTree *DT, AssumptionCache *AC, 3474 const Instruction *CxtI) { 3475 return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3476 RecursionLimit); 3477} 3478 3479static bool IsIdempotent(Intrinsic::ID ID) { 3480 switch (ID) { 3481 default: return false; 3482 3483 // Unary idempotent: f(f(x)) = f(x) 3484 case Intrinsic::fabs: 3485 case Intrinsic::floor: 3486 case Intrinsic::ceil: 3487 case Intrinsic::trunc: 3488 case Intrinsic::rint: 3489 case Intrinsic::nearbyint: 3490 case Intrinsic::round: 3491 return true; 3492 } 3493} 3494 3495template <typename IterTy> 3496static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd, 3497 const Query &Q, unsigned MaxRecurse) { 3498 // Perform idempotent optimizations 3499 if (!IsIdempotent(IID)) 3500 return nullptr; 3501 3502 // Unary Ops 3503 if (std::distance(ArgBegin, ArgEnd) == 1) 3504 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) 3505 if (II->getIntrinsicID() == IID) 3506 return II; 3507 3508 return nullptr; 3509} 3510 3511template <typename IterTy> 3512static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, 3513 const Query &Q, unsigned MaxRecurse) { 3514 Type *Ty = V->getType(); 3515 if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 3516 Ty = PTy->getElementType(); 3517 FunctionType *FTy = cast<FunctionType>(Ty); 3518 3519 // call undef -> undef 3520 if (isa<UndefValue>(V)) 3521 return UndefValue::get(FTy->getReturnType()); 3522 3523 Function *F = dyn_cast<Function>(V); 3524 if (!F) 3525 return nullptr; 3526 3527 if (unsigned IID = F->getIntrinsicID()) 3528 if (Value *Ret = 3529 SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse)) 3530 return Ret; 3531 3532 if (!canConstantFoldCallTo(F)) 3533 return nullptr; 3534 3535 SmallVector<Constant *, 4> ConstantArgs; 3536 ConstantArgs.reserve(ArgEnd - ArgBegin); 3537 for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { 3538 Constant *C = dyn_cast<Constant>(*I); 3539 if (!C) 3540 return nullptr; 3541 ConstantArgs.push_back(C); 3542 } 3543 3544 return ConstantFoldCall(F, ConstantArgs, Q.TLI); 3545} 3546 3547Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, 3548 User::op_iterator ArgEnd, const DataLayout *DL, 3549 const TargetLibraryInfo *TLI, const DominatorTree *DT, 3550 AssumptionCache *AC, const Instruction *CxtI) { 3551 return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI), 3552 RecursionLimit); 3553} 3554 3555Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, 3556 const DataLayout *DL, const TargetLibraryInfo *TLI, 3557 const DominatorTree *DT, AssumptionCache *AC, 3558 const Instruction *CxtI) { 3559 return ::SimplifyCall(V, Args.begin(), Args.end(), 3560 Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3561} 3562 3563/// SimplifyInstruction - See if we can compute a simplified version of this 3564/// instruction. If not, this returns null. 3565Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, 3566 const TargetLibraryInfo *TLI, 3567 const DominatorTree *DT, AssumptionCache *AC) { 3568 Value *Result; 3569 3570 switch (I->getOpcode()) { 3571 default: 3572 Result = ConstantFoldInstruction(I, DL, TLI); 3573 break; 3574 case Instruction::FAdd: 3575 Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), 3576 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3577 break; 3578 case Instruction::Add: 3579 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 3580 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3581 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3582 TLI, DT, AC, I); 3583 break; 3584 case Instruction::FSub: 3585 Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), 3586 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3587 break; 3588 case Instruction::Sub: 3589 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 3590 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3591 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3592 TLI, DT, AC, I); 3593 break; 3594 case Instruction::FMul: 3595 Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), 3596 I->getFastMathFlags(), DL, TLI, DT, AC, I); 3597 break; 3598 case Instruction::Mul: 3599 Result = 3600 SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3601 break; 3602 case Instruction::SDiv: 3603 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3604 AC, I); 3605 break; 3606 case Instruction::UDiv: 3607 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3608 AC, I); 3609 break; 3610 case Instruction::FDiv: 3611 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3612 AC, I); 3613 break; 3614 case Instruction::SRem: 3615 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3616 AC, I); 3617 break; 3618 case Instruction::URem: 3619 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3620 AC, I); 3621 break; 3622 case Instruction::FRem: 3623 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3624 AC, I); 3625 break; 3626 case Instruction::Shl: 3627 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 3628 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3629 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3630 TLI, DT, AC, I); 3631 break; 3632 case Instruction::LShr: 3633 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 3634 cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 3635 AC, I); 3636 break; 3637 case Instruction::AShr: 3638 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 3639 cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 3640 AC, I); 3641 break; 3642 case Instruction::And: 3643 Result = 3644 SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3645 break; 3646 case Instruction::Or: 3647 Result = 3648 SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3649 break; 3650 case Instruction::Xor: 3651 Result = 3652 SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3653 break; 3654 case Instruction::ICmp: 3655 Result = 3656 SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), I->getOperand(0), 3657 I->getOperand(1), DL, TLI, DT, AC, I); 3658 break; 3659 case Instruction::FCmp: 3660 Result = 3661 SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0), 3662 I->getOperand(1), DL, TLI, DT, AC, I); 3663 break; 3664 case Instruction::Select: 3665 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 3666 I->getOperand(2), DL, TLI, DT, AC, I); 3667 break; 3668 case Instruction::GetElementPtr: { 3669 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 3670 Result = SimplifyGEPInst(Ops, DL, TLI, DT, AC, I); 3671 break; 3672 } 3673 case Instruction::InsertValue: { 3674 InsertValueInst *IV = cast<InsertValueInst>(I); 3675 Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 3676 IV->getInsertedValueOperand(), 3677 IV->getIndices(), DL, TLI, DT, AC, I); 3678 break; 3679 } 3680 case Instruction::PHI: 3681 Result = SimplifyPHINode(cast<PHINode>(I), Query(DL, TLI, DT, AC, I)); 3682 break; 3683 case Instruction::Call: { 3684 CallSite CS(cast<CallInst>(I)); 3685 Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), DL, 3686 TLI, DT, AC, I); 3687 break; 3688 } 3689 case Instruction::Trunc: 3690 Result = 3691 SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT, AC, I); 3692 break; 3693 } 3694 3695 /// If called on unreachable code, the above logic may report that the 3696 /// instruction simplified to itself. Make life easier for users by 3697 /// detecting that case here, returning a safe value instead. 3698 return Result == I ? UndefValue::get(I->getType()) : Result; 3699} 3700 3701/// \brief Implementation of recursive simplification through an instructions 3702/// uses. 3703/// 3704/// This is the common implementation of the recursive simplification routines. 3705/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to 3706/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of 3707/// instructions to process and attempt to simplify it using 3708/// InstructionSimplify. 3709/// 3710/// This routine returns 'true' only when *it* simplifies something. The passed 3711/// in simplified value does not count toward this. 3712static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, 3713 const DataLayout *DL, 3714 const TargetLibraryInfo *TLI, 3715 const DominatorTree *DT, 3716 AssumptionCache *AC) { 3717 bool Simplified = false; 3718 SmallSetVector<Instruction *, 8> Worklist; 3719 3720 // If we have an explicit value to collapse to, do that round of the 3721 // simplification loop by hand initially. 3722 if (SimpleV) { 3723 for (User *U : I->users()) 3724 if (U != I) 3725 Worklist.insert(cast<Instruction>(U)); 3726 3727 // Replace the instruction with its simplified value. 3728 I->replaceAllUsesWith(SimpleV); 3729 3730 // Gracefully handle edge cases where the instruction is not wired into any 3731 // parent block. 3732 if (I->getParent()) 3733 I->eraseFromParent(); 3734 } else { 3735 Worklist.insert(I); 3736 } 3737 3738 // Note that we must test the size on each iteration, the worklist can grow. 3739 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { 3740 I = Worklist[Idx]; 3741 3742 // See if this instruction simplifies. 3743 SimpleV = SimplifyInstruction(I, DL, TLI, DT, AC); 3744 if (!SimpleV) 3745 continue; 3746 3747 Simplified = true; 3748 3749 // Stash away all the uses of the old instruction so we can check them for 3750 // recursive simplifications after a RAUW. This is cheaper than checking all 3751 // uses of To on the recursive step in most cases. 3752 for (User *U : I->users()) 3753 Worklist.insert(cast<Instruction>(U)); 3754 3755 // Replace the instruction with its simplified value. 3756 I->replaceAllUsesWith(SimpleV); 3757 3758 // Gracefully handle edge cases where the instruction is not wired into any 3759 // parent block. 3760 if (I->getParent()) 3761 I->eraseFromParent(); 3762 } 3763 return Simplified; 3764} 3765 3766bool llvm::recursivelySimplifyInstruction(Instruction *I, const DataLayout *DL, 3767 const TargetLibraryInfo *TLI, 3768 const DominatorTree *DT, 3769 AssumptionCache *AC) { 3770 return replaceAndRecursivelySimplifyImpl(I, nullptr, DL, TLI, DT, AC); 3771} 3772 3773bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, 3774 const DataLayout *DL, 3775 const TargetLibraryInfo *TLI, 3776 const DominatorTree *DT, 3777 AssumptionCache *AC) { 3778 assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); 3779 assert(SimpleV && "Must provide a simplified value."); 3780 return replaceAndRecursivelySimplifyImpl(I, SimpleV, DL, TLI, DT, AC); 3781} 3782