1199481Srdivacky//===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 2199481Srdivacky// 3199481Srdivacky// The LLVM Compiler Infrastructure 4199481Srdivacky// 5199481Srdivacky// This file is distributed under the University of Illinois Open Source 6199481Srdivacky// License. See LICENSE.TXT for details. 7199481Srdivacky// 8199481Srdivacky//===----------------------------------------------------------------------===// 9199481Srdivacky// 10199481Srdivacky// This file implements routines for folding instructions into simpler forms 11218893Sdim// that do not require creating new instructions. This does constant folding 12218893Sdim// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 13218893Sdim// returning a constant ("and i32 %x, 0" -> "0") or an already existing value 14218893Sdim// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 15218893Sdim// simplified: This is usually true and assuming it simplifies the logic (if 16218893Sdim// they have not been simplified then results are correct but maybe suboptimal). 17199481Srdivacky// 18199481Srdivacky//===----------------------------------------------------------------------===// 19199481Srdivacky 20249423Sdim#include "llvm/Analysis/InstructionSimplify.h" 21249423Sdim#include "llvm/ADT/SetVector.h" 22218893Sdim#include "llvm/ADT/Statistic.h" 23280031Sdim#include "llvm/Analysis/AliasAnalysis.h" 24199481Srdivacky#include "llvm/Analysis/ConstantFolding.h" 25276479Sdim#include "llvm/Analysis/MemoryBuiltins.h" 26218893Sdim#include "llvm/Analysis/ValueTracking.h" 27288943Sdim#include "llvm/Analysis/VectorUtils.h" 28276479Sdim#include "llvm/IR/ConstantRange.h" 29249423Sdim#include "llvm/IR/DataLayout.h" 30276479Sdim#include "llvm/IR/Dominators.h" 31276479Sdim#include "llvm/IR/GetElementPtrTypeIterator.h" 32249423Sdim#include "llvm/IR/GlobalAlias.h" 33249423Sdim#include "llvm/IR/Operator.h" 34276479Sdim#include "llvm/IR/PatternMatch.h" 35276479Sdim#include "llvm/IR/ValueHandle.h" 36280031Sdim#include <algorithm> 37199481Srdivackyusing namespace llvm; 38199481Srdivackyusing namespace llvm::PatternMatch; 39199481Srdivacky 40276479Sdim#define DEBUG_TYPE "instsimplify" 41276479Sdim 42218893Sdimenum { RecursionLimit = 3 }; 43218893Sdim 44218893SdimSTATISTIC(NumExpand, "Number of expansions"); 45218893SdimSTATISTIC(NumReassoc, "Number of reassociations"); 46218893Sdim 47280031Sdimnamespace { 48234353Sdimstruct Query { 49288943Sdim const DataLayout &DL; 50234353Sdim const TargetLibraryInfo *TLI; 51234353Sdim const DominatorTree *DT; 52280031Sdim AssumptionCache *AC; 53280031Sdim const Instruction *CxtI; 54218893Sdim 55288943Sdim Query(const DataLayout &DL, const TargetLibraryInfo *tli, 56280031Sdim const DominatorTree *dt, AssumptionCache *ac = nullptr, 57280031Sdim const Instruction *cxti = nullptr) 58280031Sdim : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {} 59234353Sdim}; 60280031Sdim} // end anonymous namespace 61234353Sdim 62234353Sdimstatic Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); 63234353Sdimstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &, 64234353Sdim unsigned); 65288943Sdimstatic Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &, 66288943Sdim const Query &, unsigned); 67234353Sdimstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &, 68234353Sdim unsigned); 69234353Sdimstatic Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned); 70234353Sdimstatic Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned); 71234353Sdimstatic Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned); 72234353Sdim 73296417Sdim/// For a boolean type, or a vector of boolean type, return false, or 74226633Sdim/// a vector with every element false, as appropriate for the type. 75226633Sdimstatic Constant *getFalse(Type *Ty) { 76234353Sdim assert(Ty->getScalarType()->isIntegerTy(1) && 77226633Sdim "Expected i1 type or a vector of i1!"); 78226633Sdim return Constant::getNullValue(Ty); 79226633Sdim} 80226633Sdim 81296417Sdim/// For a boolean type, or a vector of boolean type, return true, or 82226633Sdim/// a vector with every element true, as appropriate for the type. 83226633Sdimstatic Constant *getTrue(Type *Ty) { 84234353Sdim assert(Ty->getScalarType()->isIntegerTy(1) && 85226633Sdim "Expected i1 type or a vector of i1!"); 86226633Sdim return Constant::getAllOnesValue(Ty); 87226633Sdim} 88226633Sdim 89234353Sdim/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? 90234353Sdimstatic bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, 91234353Sdim Value *RHS) { 92234353Sdim CmpInst *Cmp = dyn_cast<CmpInst>(V); 93234353Sdim if (!Cmp) 94234353Sdim return false; 95234353Sdim CmpInst::Predicate CPred = Cmp->getPredicate(); 96234353Sdim Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); 97234353Sdim if (CPred == Pred && CLHS == LHS && CRHS == RHS) 98234353Sdim return true; 99234353Sdim return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && 100234353Sdim CRHS == LHS; 101234353Sdim} 102234353Sdim 103296417Sdim/// Does the given value dominate the specified phi node? 104218893Sdimstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 105218893Sdim Instruction *I = dyn_cast<Instruction>(V); 106218893Sdim if (!I) 107218893Sdim // Arguments and constants dominate all instructions. 108218893Sdim return true; 109218893Sdim 110234353Sdim // If we are processing instructions (and/or basic blocks) that have not been 111234353Sdim // fully added to a function, the parent nodes may still be null. Simply 112234353Sdim // return the conservative answer in these cases. 113234353Sdim if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) 114234353Sdim return false; 115234353Sdim 116218893Sdim // If we have a DominatorTree then do a precise test. 117234353Sdim if (DT) { 118234353Sdim if (!DT->isReachableFromEntry(P->getParent())) 119234353Sdim return true; 120234353Sdim if (!DT->isReachableFromEntry(I->getParent())) 121234353Sdim return false; 122218893Sdim return DT->dominates(I, P); 123234353Sdim } 124218893Sdim 125296417Sdim // Otherwise, if the instruction is in the entry block and is not an invoke, 126218893Sdim // then it obviously dominates all phi nodes. 127218893Sdim if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 128218893Sdim !isa<InvokeInst>(I)) 129218893Sdim return true; 130218893Sdim 131218893Sdim return false; 132218893Sdim} 133218893Sdim 134296417Sdim/// Simplify "A op (B op' C)" by distributing op over op', turning it into 135296417Sdim/// "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 136218893Sdim/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 137218893Sdim/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 138218893Sdim/// Returns the simplified value, or null if no simplification was performed. 139218893Sdimstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 140234353Sdim unsigned OpcToExpand, const Query &Q, 141234353Sdim unsigned MaxRecurse) { 142218893Sdim Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 143218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 144218893Sdim if (!MaxRecurse--) 145276479Sdim return nullptr; 146218893Sdim 147218893Sdim // Check whether the expression has the form "(A op' B) op C". 148218893Sdim if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 149218893Sdim if (Op0->getOpcode() == OpcodeToExpand) { 150218893Sdim // It does! Try turning it into "(A op C) op' (B op C)". 151218893Sdim Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 152218893Sdim // Do "A op C" and "B op C" both simplify? 153234353Sdim if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) 154234353Sdim if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 155218893Sdim // They do! Return "L op' R" if it simplifies or is already available. 156218893Sdim // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 157218893Sdim if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 158218893Sdim && L == B && R == A)) { 159218893Sdim ++NumExpand; 160218893Sdim return LHS; 161218893Sdim } 162218893Sdim // Otherwise return "L op' R" if it simplifies. 163234353Sdim if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 164218893Sdim ++NumExpand; 165218893Sdim return V; 166218893Sdim } 167218893Sdim } 168218893Sdim } 169218893Sdim 170218893Sdim // Check whether the expression has the form "A op (B op' C)". 171218893Sdim if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 172218893Sdim if (Op1->getOpcode() == OpcodeToExpand) { 173218893Sdim // It does! Try turning it into "(A op B) op' (A op C)". 174218893Sdim Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 175218893Sdim // Do "A op B" and "A op C" both simplify? 176234353Sdim if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) 177234353Sdim if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { 178218893Sdim // They do! Return "L op' R" if it simplifies or is already available. 179218893Sdim // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 180218893Sdim if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 181218893Sdim && L == C && R == B)) { 182218893Sdim ++NumExpand; 183218893Sdim return RHS; 184218893Sdim } 185218893Sdim // Otherwise return "L op' R" if it simplifies. 186234353Sdim if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 187218893Sdim ++NumExpand; 188218893Sdim return V; 189218893Sdim } 190218893Sdim } 191218893Sdim } 192218893Sdim 193276479Sdim return nullptr; 194218893Sdim} 195218893Sdim 196296417Sdim/// Generic simplifications for associative binary operations. 197296417Sdim/// Returns the simpler value, or null if none was found. 198218893Sdimstatic Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 199234353Sdim const Query &Q, unsigned MaxRecurse) { 200218893Sdim Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 201218893Sdim assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 202218893Sdim 203218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 204218893Sdim if (!MaxRecurse--) 205276479Sdim return nullptr; 206218893Sdim 207218893Sdim BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 208218893Sdim BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 209218893Sdim 210218893Sdim // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 211218893Sdim if (Op0 && Op0->getOpcode() == Opcode) { 212218893Sdim Value *A = Op0->getOperand(0); 213218893Sdim Value *B = Op0->getOperand(1); 214218893Sdim Value *C = RHS; 215218893Sdim 216218893Sdim // Does "B op C" simplify? 217234353Sdim if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 218218893Sdim // It does! Return "A op V" if it simplifies or is already available. 219218893Sdim // If V equals B then "A op V" is just the LHS. 220218893Sdim if (V == B) return LHS; 221218893Sdim // Otherwise return "A op V" if it simplifies. 222234353Sdim if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) { 223218893Sdim ++NumReassoc; 224218893Sdim return W; 225218893Sdim } 226218893Sdim } 227218893Sdim } 228218893Sdim 229218893Sdim // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 230218893Sdim if (Op1 && Op1->getOpcode() == Opcode) { 231218893Sdim Value *A = LHS; 232218893Sdim Value *B = Op1->getOperand(0); 233218893Sdim Value *C = Op1->getOperand(1); 234218893Sdim 235218893Sdim // Does "A op B" simplify? 236234353Sdim if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) { 237218893Sdim // It does! Return "V op C" if it simplifies or is already available. 238218893Sdim // If V equals B then "V op C" is just the RHS. 239218893Sdim if (V == B) return RHS; 240218893Sdim // Otherwise return "V op C" if it simplifies. 241234353Sdim if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) { 242218893Sdim ++NumReassoc; 243218893Sdim return W; 244218893Sdim } 245218893Sdim } 246218893Sdim } 247218893Sdim 248218893Sdim // The remaining transforms require commutativity as well as associativity. 249218893Sdim if (!Instruction::isCommutative(Opcode)) 250276479Sdim return nullptr; 251218893Sdim 252218893Sdim // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 253218893Sdim if (Op0 && Op0->getOpcode() == Opcode) { 254218893Sdim Value *A = Op0->getOperand(0); 255218893Sdim Value *B = Op0->getOperand(1); 256218893Sdim Value *C = RHS; 257218893Sdim 258218893Sdim // Does "C op A" simplify? 259234353Sdim if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 260218893Sdim // It does! Return "V op B" if it simplifies or is already available. 261218893Sdim // If V equals A then "V op B" is just the LHS. 262218893Sdim if (V == A) return LHS; 263218893Sdim // Otherwise return "V op B" if it simplifies. 264234353Sdim if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) { 265218893Sdim ++NumReassoc; 266218893Sdim return W; 267218893Sdim } 268218893Sdim } 269218893Sdim } 270218893Sdim 271218893Sdim // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 272218893Sdim if (Op1 && Op1->getOpcode() == Opcode) { 273218893Sdim Value *A = LHS; 274218893Sdim Value *B = Op1->getOperand(0); 275218893Sdim Value *C = Op1->getOperand(1); 276218893Sdim 277218893Sdim // Does "C op A" simplify? 278234353Sdim if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 279218893Sdim // It does! Return "B op V" if it simplifies or is already available. 280218893Sdim // If V equals C then "B op V" is just the RHS. 281218893Sdim if (V == C) return RHS; 282218893Sdim // Otherwise return "B op V" if it simplifies. 283234353Sdim if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) { 284218893Sdim ++NumReassoc; 285218893Sdim return W; 286218893Sdim } 287218893Sdim } 288218893Sdim } 289218893Sdim 290276479Sdim return nullptr; 291218893Sdim} 292218893Sdim 293296417Sdim/// In the case of a binary operation with a select instruction as an operand, 294296417Sdim/// try to simplify the binop by seeing whether evaluating it on both branches 295296417Sdim/// of the select results in the same value. Returns the common value if so, 296296417Sdim/// otherwise returns null. 297218893Sdimstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 298234353Sdim const Query &Q, unsigned MaxRecurse) { 299218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 300218893Sdim if (!MaxRecurse--) 301276479Sdim return nullptr; 302218893Sdim 303218893Sdim SelectInst *SI; 304218893Sdim if (isa<SelectInst>(LHS)) { 305218893Sdim SI = cast<SelectInst>(LHS); 306218893Sdim } else { 307218893Sdim assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 308218893Sdim SI = cast<SelectInst>(RHS); 309218893Sdim } 310218893Sdim 311218893Sdim // Evaluate the BinOp on the true and false branches of the select. 312218893Sdim Value *TV; 313218893Sdim Value *FV; 314218893Sdim if (SI == LHS) { 315234353Sdim TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse); 316234353Sdim FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse); 317218893Sdim } else { 318234353Sdim TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse); 319234353Sdim FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse); 320218893Sdim } 321218893Sdim 322218893Sdim // If they simplified to the same value, then return the common value. 323218893Sdim // If they both failed to simplify then return null. 324218893Sdim if (TV == FV) 325218893Sdim return TV; 326218893Sdim 327218893Sdim // If one branch simplified to undef, return the other one. 328218893Sdim if (TV && isa<UndefValue>(TV)) 329218893Sdim return FV; 330218893Sdim if (FV && isa<UndefValue>(FV)) 331218893Sdim return TV; 332218893Sdim 333218893Sdim // If applying the operation did not change the true and false select values, 334218893Sdim // then the result of the binop is the select itself. 335218893Sdim if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 336218893Sdim return SI; 337218893Sdim 338218893Sdim // If one branch simplified and the other did not, and the simplified 339218893Sdim // value is equal to the unsimplified one, return the simplified value. 340218893Sdim // For example, select (cond, X, X & Z) & Z -> X & Z. 341218893Sdim if ((FV && !TV) || (TV && !FV)) { 342218893Sdim // Check that the simplified value has the form "X op Y" where "op" is the 343218893Sdim // same as the original operation. 344218893Sdim Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 345218893Sdim if (Simplified && Simplified->getOpcode() == Opcode) { 346218893Sdim // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 347218893Sdim // We already know that "op" is the same as for the simplified value. See 348218893Sdim // if the operands match too. If so, return the simplified value. 349218893Sdim Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 350218893Sdim Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 351218893Sdim Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 352218893Sdim if (Simplified->getOperand(0) == UnsimplifiedLHS && 353218893Sdim Simplified->getOperand(1) == UnsimplifiedRHS) 354218893Sdim return Simplified; 355218893Sdim if (Simplified->isCommutative() && 356218893Sdim Simplified->getOperand(1) == UnsimplifiedLHS && 357218893Sdim Simplified->getOperand(0) == UnsimplifiedRHS) 358218893Sdim return Simplified; 359218893Sdim } 360218893Sdim } 361218893Sdim 362276479Sdim return nullptr; 363218893Sdim} 364218893Sdim 365296417Sdim/// In the case of a comparison with a select instruction, try to simplify the 366296417Sdim/// comparison by seeing whether both branches of the select result in the same 367296417Sdim/// value. Returns the common value if so, otherwise returns null. 368218893Sdimstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 369234353Sdim Value *RHS, const Query &Q, 370218893Sdim unsigned MaxRecurse) { 371218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 372218893Sdim if (!MaxRecurse--) 373276479Sdim return nullptr; 374218893Sdim 375218893Sdim // Make sure the select is on the LHS. 376218893Sdim if (!isa<SelectInst>(LHS)) { 377218893Sdim std::swap(LHS, RHS); 378218893Sdim Pred = CmpInst::getSwappedPredicate(Pred); 379218893Sdim } 380218893Sdim assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 381218893Sdim SelectInst *SI = cast<SelectInst>(LHS); 382234353Sdim Value *Cond = SI->getCondition(); 383234353Sdim Value *TV = SI->getTrueValue(); 384234353Sdim Value *FV = SI->getFalseValue(); 385218893Sdim 386218893Sdim // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 387218893Sdim // Does "cmp TV, RHS" simplify? 388234353Sdim Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); 389234353Sdim if (TCmp == Cond) { 390234353Sdim // It not only simplified, it simplified to the select condition. Replace 391234353Sdim // it with 'true'. 392234353Sdim TCmp = getTrue(Cond->getType()); 393234353Sdim } else if (!TCmp) { 394234353Sdim // It didn't simplify. However if "cmp TV, RHS" is equal to the select 395234353Sdim // condition then we can replace it with 'true'. Otherwise give up. 396234353Sdim if (!isSameCompare(Cond, Pred, TV, RHS)) 397276479Sdim return nullptr; 398234353Sdim TCmp = getTrue(Cond->getType()); 399218893Sdim } 400218893Sdim 401234353Sdim // Does "cmp FV, RHS" simplify? 402234353Sdim Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); 403234353Sdim if (FCmp == Cond) { 404234353Sdim // It not only simplified, it simplified to the select condition. Replace 405234353Sdim // it with 'false'. 406234353Sdim FCmp = getFalse(Cond->getType()); 407234353Sdim } else if (!FCmp) { 408234353Sdim // It didn't simplify. However if "cmp FV, RHS" is equal to the select 409234353Sdim // condition then we can replace it with 'false'. Otherwise give up. 410234353Sdim if (!isSameCompare(Cond, Pred, FV, RHS)) 411276479Sdim return nullptr; 412234353Sdim FCmp = getFalse(Cond->getType()); 413234353Sdim } 414234353Sdim 415234353Sdim // If both sides simplified to the same value, then use it as the result of 416234353Sdim // the original comparison. 417234353Sdim if (TCmp == FCmp) 418234353Sdim return TCmp; 419234353Sdim 420234353Sdim // The remaining cases only make sense if the select condition has the same 421234353Sdim // type as the result of the comparison, so bail out if this is not so. 422234353Sdim if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) 423276479Sdim return nullptr; 424234353Sdim // If the false value simplified to false, then the result of the compare 425234353Sdim // is equal to "Cond && TCmp". This also catches the case when the false 426234353Sdim // value simplified to false and the true value to true, returning "Cond". 427234353Sdim if (match(FCmp, m_Zero())) 428234353Sdim if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) 429234353Sdim return V; 430234353Sdim // If the true value simplified to true, then the result of the compare 431234353Sdim // is equal to "Cond || FCmp". 432234353Sdim if (match(TCmp, m_One())) 433234353Sdim if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) 434234353Sdim return V; 435234353Sdim // Finally, if the false value simplified to true and the true value to 436234353Sdim // false, then the result of the compare is equal to "!Cond". 437234353Sdim if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 438234353Sdim if (Value *V = 439234353Sdim SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 440234353Sdim Q, MaxRecurse)) 441234353Sdim return V; 442234353Sdim 443276479Sdim return nullptr; 444218893Sdim} 445218893Sdim 446296417Sdim/// In the case of a binary operation with an operand that is a PHI instruction, 447296417Sdim/// try to simplify the binop by seeing whether evaluating it on the incoming 448296417Sdim/// phi values yields the same result for every value. If so returns the common 449296417Sdim/// value, otherwise returns null. 450218893Sdimstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 451234353Sdim const Query &Q, unsigned MaxRecurse) { 452218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 453218893Sdim if (!MaxRecurse--) 454276479Sdim return nullptr; 455218893Sdim 456218893Sdim PHINode *PI; 457218893Sdim if (isa<PHINode>(LHS)) { 458218893Sdim PI = cast<PHINode>(LHS); 459218893Sdim // Bail out if RHS and the phi may be mutually interdependent due to a loop. 460234353Sdim if (!ValueDominatesPHI(RHS, PI, Q.DT)) 461276479Sdim return nullptr; 462218893Sdim } else { 463218893Sdim assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 464218893Sdim PI = cast<PHINode>(RHS); 465218893Sdim // Bail out if LHS and the phi may be mutually interdependent due to a loop. 466234353Sdim if (!ValueDominatesPHI(LHS, PI, Q.DT)) 467276479Sdim return nullptr; 468218893Sdim } 469218893Sdim 470218893Sdim // Evaluate the BinOp on the incoming phi values. 471276479Sdim Value *CommonValue = nullptr; 472288943Sdim for (Value *Incoming : PI->incoming_values()) { 473218893Sdim // If the incoming value is the phi node itself, it can safely be skipped. 474218893Sdim if (Incoming == PI) continue; 475218893Sdim Value *V = PI == LHS ? 476234353Sdim SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) : 477234353Sdim SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse); 478218893Sdim // If the operation failed to simplify, or simplified to a different value 479218893Sdim // to previously, then give up. 480218893Sdim if (!V || (CommonValue && V != CommonValue)) 481276479Sdim return nullptr; 482218893Sdim CommonValue = V; 483218893Sdim } 484218893Sdim 485218893Sdim return CommonValue; 486218893Sdim} 487218893Sdim 488296417Sdim/// In the case of a comparison with a PHI instruction, try to simplify the 489296417Sdim/// comparison by seeing whether comparing with all of the incoming phi values 490296417Sdim/// yields the same result every time. If so returns the common result, 491296417Sdim/// otherwise returns null. 492218893Sdimstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 493234353Sdim const Query &Q, unsigned MaxRecurse) { 494218893Sdim // Recursion is always used, so bail out at once if we already hit the limit. 495218893Sdim if (!MaxRecurse--) 496276479Sdim return nullptr; 497218893Sdim 498218893Sdim // Make sure the phi is on the LHS. 499218893Sdim if (!isa<PHINode>(LHS)) { 500218893Sdim std::swap(LHS, RHS); 501218893Sdim Pred = CmpInst::getSwappedPredicate(Pred); 502218893Sdim } 503218893Sdim assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 504218893Sdim PHINode *PI = cast<PHINode>(LHS); 505218893Sdim 506218893Sdim // Bail out if RHS and the phi may be mutually interdependent due to a loop. 507234353Sdim if (!ValueDominatesPHI(RHS, PI, Q.DT)) 508276479Sdim return nullptr; 509218893Sdim 510218893Sdim // Evaluate the BinOp on the incoming phi values. 511276479Sdim Value *CommonValue = nullptr; 512288943Sdim for (Value *Incoming : PI->incoming_values()) { 513218893Sdim // If the incoming value is the phi node itself, it can safely be skipped. 514218893Sdim if (Incoming == PI) continue; 515234353Sdim Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); 516218893Sdim // If the operation failed to simplify, or simplified to a different value 517218893Sdim // to previously, then give up. 518218893Sdim if (!V || (CommonValue && V != CommonValue)) 519276479Sdim return nullptr; 520218893Sdim CommonValue = V; 521218893Sdim } 522218893Sdim 523218893Sdim return CommonValue; 524218893Sdim} 525218893Sdim 526296417Sdim/// Given operands for an Add, see if we can fold the result. 527296417Sdim/// If not, this returns null. 528218893Sdimstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 529234353Sdim const Query &Q, unsigned MaxRecurse) { 530199481Srdivacky if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 531199481Srdivacky if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 532199481Srdivacky Constant *Ops[] = { CLHS, CRHS }; 533234353Sdim return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops, 534276479Sdim Q.DL, Q.TLI); 535199989Srdivacky } 536218893Sdim 537199989Srdivacky // Canonicalize the constant to the RHS. 538199989Srdivacky std::swap(Op0, Op1); 539199989Srdivacky } 540218893Sdim 541218893Sdim // X + undef -> undef 542218893Sdim if (match(Op1, m_Undef())) 543218893Sdim return Op1; 544218893Sdim 545218893Sdim // X + 0 -> X 546218893Sdim if (match(Op1, m_Zero())) 547218893Sdim return Op0; 548218893Sdim 549218893Sdim // X + (Y - X) -> Y 550218893Sdim // (Y - X) + X -> Y 551218893Sdim // Eg: X + -X -> 0 552276479Sdim Value *Y = nullptr; 553218893Sdim if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 554218893Sdim match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 555218893Sdim return Y; 556218893Sdim 557218893Sdim // X + ~X -> -1 since ~X = -X-1 558218893Sdim if (match(Op0, m_Not(m_Specific(Op1))) || 559218893Sdim match(Op1, m_Not(m_Specific(Op0)))) 560218893Sdim return Constant::getAllOnesValue(Op0->getType()); 561218893Sdim 562218893Sdim /// i1 add -> xor. 563218893Sdim if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 564234353Sdim if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 565218893Sdim return V; 566218893Sdim 567218893Sdim // Try some generic simplifications for associative operations. 568234353Sdim if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, 569218893Sdim MaxRecurse)) 570218893Sdim return V; 571218893Sdim 572218893Sdim // Threading Add over selects and phi nodes is pointless, so don't bother. 573218893Sdim // Threading over the select in "A + select(cond, B, C)" means evaluating 574218893Sdim // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 575218893Sdim // only if B and C are equal. If B and C are equal then (since we assume 576218893Sdim // that operands have already been simplified) "select(cond, B, C)" should 577218893Sdim // have been simplified to the common value of B and C already. Analysing 578218893Sdim // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 579218893Sdim // for threading over phi nodes. 580218893Sdim 581276479Sdim return nullptr; 582218893Sdim} 583218893Sdim 584218893SdimValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 585288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 586280031Sdim const DominatorTree *DT, AssumptionCache *AC, 587280031Sdim const Instruction *CxtI) { 588280031Sdim return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 589234353Sdim RecursionLimit); 590218893Sdim} 591218893Sdim 592234353Sdim/// \brief Compute the base pointer and cumulative constant offsets for V. 593234353Sdim/// 594234353Sdim/// This strips all constant offsets off of V, leaving it the base pointer, and 595234353Sdim/// accumulates the total constant offset applied in the returned constant. It 596234353Sdim/// returns 0 if V is not a pointer, and returns the constant '0' if there are 597234353Sdim/// no constant offsets applied. 598249423Sdim/// 599249423Sdim/// This is very similar to GetPointerBaseWithConstantOffset except it doesn't 600249423Sdim/// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. 601249423Sdim/// folding. 602288943Sdimstatic Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V, 603261991Sdim bool AllowNonInbounds = false) { 604249423Sdim assert(V->getType()->getScalarType()->isPointerTy()); 605234353Sdim 606288943Sdim Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); 607261991Sdim APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); 608234353Sdim 609234353Sdim // Even though we don't look through PHI nodes, we could be called on an 610234353Sdim // instruction in an unreachable block, which may be on a cycle. 611234353Sdim SmallPtrSet<Value *, 4> Visited; 612234353Sdim Visited.insert(V); 613234353Sdim do { 614234353Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 615261991Sdim if ((!AllowNonInbounds && !GEP->isInBounds()) || 616288943Sdim !GEP->accumulateConstantOffset(DL, Offset)) 617234353Sdim break; 618234353Sdim V = GEP->getPointerOperand(); 619234353Sdim } else if (Operator::getOpcode(V) == Instruction::BitCast) { 620234353Sdim V = cast<Operator>(V)->getOperand(0); 621234353Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 622234353Sdim if (GA->mayBeOverridden()) 623234353Sdim break; 624234353Sdim V = GA->getAliasee(); 625234353Sdim } else { 626234353Sdim break; 627234353Sdim } 628249423Sdim assert(V->getType()->getScalarType()->isPointerTy() && 629249423Sdim "Unexpected operand type!"); 630280031Sdim } while (Visited.insert(V).second); 631234353Sdim 632249423Sdim Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); 633249423Sdim if (V->getType()->isVectorTy()) 634249423Sdim return ConstantVector::getSplat(V->getType()->getVectorNumElements(), 635249423Sdim OffsetIntPtr); 636249423Sdim return OffsetIntPtr; 637234353Sdim} 638234353Sdim 639234353Sdim/// \brief Compute the constant difference between two pointer values. 640234353Sdim/// If the difference is not a constant, returns zero. 641288943Sdimstatic Constant *computePointerDifference(const DataLayout &DL, Value *LHS, 642288943Sdim Value *RHS) { 643276479Sdim Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 644276479Sdim Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 645234353Sdim 646234353Sdim // If LHS and RHS are not related via constant offsets to the same base 647234353Sdim // value, there is nothing we can do here. 648234353Sdim if (LHS != RHS) 649276479Sdim return nullptr; 650234353Sdim 651234353Sdim // Otherwise, the difference of LHS - RHS can be computed as: 652234353Sdim // LHS - RHS 653234353Sdim // = (LHSOffset + Base) - (RHSOffset + Base) 654234353Sdim // = LHSOffset - RHSOffset 655234353Sdim return ConstantExpr::getSub(LHSOffset, RHSOffset); 656234353Sdim} 657234353Sdim 658296417Sdim/// Given operands for a Sub, see if we can fold the result. 659296417Sdim/// If not, this returns null. 660218893Sdimstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 661234353Sdim const Query &Q, unsigned MaxRecurse) { 662218893Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) 663218893Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 664218893Sdim Constant *Ops[] = { CLHS, CRHS }; 665218893Sdim return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 666276479Sdim Ops, Q.DL, Q.TLI); 667218893Sdim } 668218893Sdim 669218893Sdim // X - undef -> undef 670218893Sdim // undef - X -> undef 671218893Sdim if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 672218893Sdim return UndefValue::get(Op0->getType()); 673218893Sdim 674218893Sdim // X - 0 -> X 675218893Sdim if (match(Op1, m_Zero())) 676218893Sdim return Op0; 677218893Sdim 678218893Sdim // X - X -> 0 679218893Sdim if (Op0 == Op1) 680218893Sdim return Constant::getNullValue(Op0->getType()); 681218893Sdim 682280031Sdim // 0 - X -> 0 if the sub is NUW. 683280031Sdim if (isNUW && match(Op0, m_Zero())) 684280031Sdim return Op0; 685280031Sdim 686218893Sdim // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 687218893Sdim // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 688276479Sdim Value *X = nullptr, *Y = nullptr, *Z = Op1; 689218893Sdim if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 690218893Sdim // See if "V === Y - Z" simplifies. 691234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) 692218893Sdim // It does! Now see if "X + V" simplifies. 693234353Sdim if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { 694218893Sdim // It does, we successfully reassociated! 695218893Sdim ++NumReassoc; 696218893Sdim return W; 697218893Sdim } 698218893Sdim // See if "V === X - Z" simplifies. 699234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 700218893Sdim // It does! Now see if "Y + V" simplifies. 701234353Sdim if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) { 702218893Sdim // It does, we successfully reassociated! 703218893Sdim ++NumReassoc; 704218893Sdim return W; 705218893Sdim } 706199989Srdivacky } 707218893Sdim 708218893Sdim // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 709218893Sdim // For example, X - (X + 1) -> -1 710218893Sdim X = Op0; 711218893Sdim if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 712218893Sdim // See if "V === X - Y" simplifies. 713234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 714218893Sdim // It does! Now see if "V - Z" simplifies. 715234353Sdim if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) { 716218893Sdim // It does, we successfully reassociated! 717218893Sdim ++NumReassoc; 718218893Sdim return W; 719218893Sdim } 720218893Sdim // See if "V === X - Z" simplifies. 721234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 722218893Sdim // It does! Now see if "V - Y" simplifies. 723234353Sdim if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) { 724218893Sdim // It does, we successfully reassociated! 725218893Sdim ++NumReassoc; 726218893Sdim return W; 727218893Sdim } 728218893Sdim } 729218893Sdim 730218893Sdim // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 731218893Sdim // For example, X - (X - Y) -> Y. 732218893Sdim Z = Op0; 733218893Sdim if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 734218893Sdim // See if "V === Z - X" simplifies. 735234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1)) 736218893Sdim // It does! Now see if "V + Y" simplifies. 737234353Sdim if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) { 738218893Sdim // It does, we successfully reassociated! 739218893Sdim ++NumReassoc; 740218893Sdim return W; 741218893Sdim } 742218893Sdim 743234353Sdim // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies. 744234353Sdim if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) && 745234353Sdim match(Op1, m_Trunc(m_Value(Y)))) 746234353Sdim if (X->getType() == Y->getType()) 747234353Sdim // See if "V === X - Y" simplifies. 748234353Sdim if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 749234353Sdim // It does! Now see if "trunc V" simplifies. 750234353Sdim if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1)) 751234353Sdim // It does, return the simplified "trunc V". 752234353Sdim return W; 753234353Sdim 754234353Sdim // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). 755249423Sdim if (match(Op0, m_PtrToInt(m_Value(X))) && 756234353Sdim match(Op1, m_PtrToInt(m_Value(Y)))) 757276479Sdim if (Constant *Result = computePointerDifference(Q.DL, X, Y)) 758234353Sdim return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); 759234353Sdim 760218893Sdim // i1 sub -> xor. 761218893Sdim if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 762234353Sdim if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 763218893Sdim return V; 764218893Sdim 765218893Sdim // Threading Sub over selects and phi nodes is pointless, so don't bother. 766218893Sdim // Threading over the select in "A - select(cond, B, C)" means evaluating 767218893Sdim // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 768218893Sdim // only if B and C are equal. If B and C are equal then (since we assume 769218893Sdim // that operands have already been simplified) "select(cond, B, C)" should 770218893Sdim // have been simplified to the common value of B and C already. Analysing 771218893Sdim // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 772218893Sdim // for threading over phi nodes. 773218893Sdim 774276479Sdim return nullptr; 775199989Srdivacky} 776199989Srdivacky 777218893SdimValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 778288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 779280031Sdim const DominatorTree *DT, AssumptionCache *AC, 780280031Sdim const Instruction *CxtI) { 781280031Sdim return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 782234353Sdim RecursionLimit); 783218893Sdim} 784218893Sdim 785249423Sdim/// Given operands for an FAdd, see if we can fold the result. If not, this 786249423Sdim/// returns null. 787249423Sdimstatic Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 788249423Sdim const Query &Q, unsigned MaxRecurse) { 789249423Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 790249423Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 791249423Sdim Constant *Ops[] = { CLHS, CRHS }; 792249423Sdim return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(), 793276479Sdim Ops, Q.DL, Q.TLI); 794249423Sdim } 795249423Sdim 796249423Sdim // Canonicalize the constant to the RHS. 797249423Sdim std::swap(Op0, Op1); 798249423Sdim } 799249423Sdim 800249423Sdim // fadd X, -0 ==> X 801249423Sdim if (match(Op1, m_NegZero())) 802249423Sdim return Op0; 803249423Sdim 804249423Sdim // fadd X, 0 ==> X, when we know X is not -0 805249423Sdim if (match(Op1, m_Zero()) && 806249423Sdim (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 807249423Sdim return Op0; 808249423Sdim 809249423Sdim // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 810249423Sdim // where nnan and ninf have to occur at least once somewhere in this 811249423Sdim // expression 812276479Sdim Value *SubOp = nullptr; 813249423Sdim if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) 814249423Sdim SubOp = Op1; 815249423Sdim else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) 816249423Sdim SubOp = Op0; 817249423Sdim if (SubOp) { 818249423Sdim Instruction *FSub = cast<Instruction>(SubOp); 819249423Sdim if ((FMF.noNaNs() || FSub->hasNoNaNs()) && 820249423Sdim (FMF.noInfs() || FSub->hasNoInfs())) 821249423Sdim return Constant::getNullValue(Op0->getType()); 822249423Sdim } 823249423Sdim 824276479Sdim return nullptr; 825249423Sdim} 826249423Sdim 827249423Sdim/// Given operands for an FSub, see if we can fold the result. If not, this 828249423Sdim/// returns null. 829249423Sdimstatic Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 830249423Sdim const Query &Q, unsigned MaxRecurse) { 831249423Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 832249423Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 833249423Sdim Constant *Ops[] = { CLHS, CRHS }; 834249423Sdim return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(), 835276479Sdim Ops, Q.DL, Q.TLI); 836249423Sdim } 837249423Sdim } 838249423Sdim 839249423Sdim // fsub X, 0 ==> X 840249423Sdim if (match(Op1, m_Zero())) 841249423Sdim return Op0; 842249423Sdim 843249423Sdim // fsub X, -0 ==> X, when we know X is not -0 844249423Sdim if (match(Op1, m_NegZero()) && 845249423Sdim (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 846249423Sdim return Op0; 847249423Sdim 848249423Sdim // fsub 0, (fsub -0.0, X) ==> X 849249423Sdim Value *X; 850249423Sdim if (match(Op0, m_AnyZero())) { 851249423Sdim if (match(Op1, m_FSub(m_NegZero(), m_Value(X)))) 852249423Sdim return X; 853249423Sdim if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) 854249423Sdim return X; 855249423Sdim } 856249423Sdim 857288943Sdim // fsub nnan x, x ==> 0.0 858288943Sdim if (FMF.noNaNs() && Op0 == Op1) 859249423Sdim return Constant::getNullValue(Op0->getType()); 860249423Sdim 861276479Sdim return nullptr; 862249423Sdim} 863249423Sdim 864249423Sdim/// Given the operands for an FMul, see if we can fold the result 865249423Sdimstatic Value *SimplifyFMulInst(Value *Op0, Value *Op1, 866249423Sdim FastMathFlags FMF, 867249423Sdim const Query &Q, 868249423Sdim unsigned MaxRecurse) { 869249423Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 870249423Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 871249423Sdim Constant *Ops[] = { CLHS, CRHS }; 872249423Sdim return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(), 873276479Sdim Ops, Q.DL, Q.TLI); 874249423Sdim } 875249423Sdim 876249423Sdim // Canonicalize the constant to the RHS. 877249423Sdim std::swap(Op0, Op1); 878249423Sdim } 879249423Sdim 880249423Sdim // fmul X, 1.0 ==> X 881249423Sdim if (match(Op1, m_FPOne())) 882249423Sdim return Op0; 883249423Sdim 884249423Sdim // fmul nnan nsz X, 0 ==> 0 885249423Sdim if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) 886249423Sdim return Op1; 887249423Sdim 888276479Sdim return nullptr; 889249423Sdim} 890249423Sdim 891296417Sdim/// Given operands for a Mul, see if we can fold the result. 892296417Sdim/// If not, this returns null. 893234353Sdimstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, 894234353Sdim unsigned MaxRecurse) { 895218893Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 896218893Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 897218893Sdim Constant *Ops[] = { CLHS, CRHS }; 898218893Sdim return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 899276479Sdim Ops, Q.DL, Q.TLI); 900218893Sdim } 901218893Sdim 902218893Sdim // Canonicalize the constant to the RHS. 903218893Sdim std::swap(Op0, Op1); 904218893Sdim } 905218893Sdim 906218893Sdim // X * undef -> 0 907218893Sdim if (match(Op1, m_Undef())) 908218893Sdim return Constant::getNullValue(Op0->getType()); 909218893Sdim 910218893Sdim // X * 0 -> 0 911218893Sdim if (match(Op1, m_Zero())) 912218893Sdim return Op1; 913218893Sdim 914218893Sdim // X * 1 -> X 915218893Sdim if (match(Op1, m_One())) 916218893Sdim return Op0; 917218893Sdim 918218893Sdim // (X / Y) * Y -> X if the division is exact. 919276479Sdim Value *X = nullptr; 920234353Sdim if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y 921234353Sdim match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) 922234353Sdim return X; 923218893Sdim 924218893Sdim // i1 mul -> and. 925218893Sdim if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 926234353Sdim if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1)) 927218893Sdim return V; 928218893Sdim 929218893Sdim // Try some generic simplifications for associative operations. 930234353Sdim if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, 931218893Sdim MaxRecurse)) 932218893Sdim return V; 933218893Sdim 934218893Sdim // Mul distributes over Add. Try some generic simplifications based on this. 935218893Sdim if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 936234353Sdim Q, MaxRecurse)) 937218893Sdim return V; 938218893Sdim 939218893Sdim // If the operation is with the result of a select instruction, check whether 940218893Sdim // operating on either branch of the select always yields the same value. 941218893Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 942234353Sdim if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, 943218893Sdim MaxRecurse)) 944218893Sdim return V; 945218893Sdim 946218893Sdim // If the operation is with the result of a phi instruction, check whether 947218893Sdim // operating on all incoming values of the phi always yields the same value. 948218893Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 949234353Sdim if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, 950218893Sdim MaxRecurse)) 951218893Sdim return V; 952218893Sdim 953276479Sdim return nullptr; 954218893Sdim} 955218893Sdim 956249423SdimValue *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 957288943Sdim const DataLayout &DL, 958280031Sdim const TargetLibraryInfo *TLI, 959280031Sdim const DominatorTree *DT, AssumptionCache *AC, 960280031Sdim const Instruction *CxtI) { 961280031Sdim return ::SimplifyFAddInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 962280031Sdim RecursionLimit); 963249423Sdim} 964249423Sdim 965249423SdimValue *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 966288943Sdim const DataLayout &DL, 967280031Sdim const TargetLibraryInfo *TLI, 968280031Sdim const DominatorTree *DT, AssumptionCache *AC, 969280031Sdim const Instruction *CxtI) { 970280031Sdim return ::SimplifyFSubInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 971280031Sdim RecursionLimit); 972249423Sdim} 973249423Sdim 974280031SdimValue *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, 975288943Sdim const DataLayout &DL, 976249423Sdim const TargetLibraryInfo *TLI, 977280031Sdim const DominatorTree *DT, AssumptionCache *AC, 978280031Sdim const Instruction *CxtI) { 979280031Sdim return ::SimplifyFMulInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 980280031Sdim RecursionLimit); 981249423Sdim} 982249423Sdim 983288943SdimValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL, 984234353Sdim const TargetLibraryInfo *TLI, 985280031Sdim const DominatorTree *DT, AssumptionCache *AC, 986280031Sdim const Instruction *CxtI) { 987280031Sdim return ::SimplifyMulInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 988280031Sdim RecursionLimit); 989218893Sdim} 990218893Sdim 991296417Sdim/// Given operands for an SDiv or UDiv, see if we can fold the result. 992296417Sdim/// If not, this returns null. 993218893Sdimstatic Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 994234353Sdim const Query &Q, unsigned MaxRecurse) { 995218893Sdim if (Constant *C0 = dyn_cast<Constant>(Op0)) { 996218893Sdim if (Constant *C1 = dyn_cast<Constant>(Op1)) { 997218893Sdim Constant *Ops[] = { C0, C1 }; 998276479Sdim return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 999218893Sdim } 1000218893Sdim } 1001218893Sdim 1002218893Sdim bool isSigned = Opcode == Instruction::SDiv; 1003218893Sdim 1004218893Sdim // X / undef -> undef 1005218893Sdim if (match(Op1, m_Undef())) 1006218893Sdim return Op1; 1007218893Sdim 1008280031Sdim // X / 0 -> undef, we don't need to preserve faults! 1009280031Sdim if (match(Op1, m_Zero())) 1010280031Sdim return UndefValue::get(Op1->getType()); 1011280031Sdim 1012218893Sdim // undef / X -> 0 1013218893Sdim if (match(Op0, m_Undef())) 1014218893Sdim return Constant::getNullValue(Op0->getType()); 1015218893Sdim 1016218893Sdim // 0 / X -> 0, we don't need to preserve faults! 1017218893Sdim if (match(Op0, m_Zero())) 1018218893Sdim return Op0; 1019218893Sdim 1020218893Sdim // X / 1 -> X 1021218893Sdim if (match(Op1, m_One())) 1022218893Sdim return Op0; 1023218893Sdim 1024218893Sdim if (Op0->getType()->isIntegerTy(1)) 1025218893Sdim // It can't be division by zero, hence it must be division by one. 1026218893Sdim return Op0; 1027218893Sdim 1028218893Sdim // X / X -> 1 1029218893Sdim if (Op0 == Op1) 1030218893Sdim return ConstantInt::get(Op0->getType(), 1); 1031218893Sdim 1032218893Sdim // (X * Y) / Y -> X if the multiplication does not overflow. 1033276479Sdim Value *X = nullptr, *Y = nullptr; 1034218893Sdim if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 1035218893Sdim if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 1036234353Sdim OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 1037218893Sdim // If the Mul knows it does not overflow, then we are good to go. 1038218893Sdim if ((isSigned && Mul->hasNoSignedWrap()) || 1039218893Sdim (!isSigned && Mul->hasNoUnsignedWrap())) 1040218893Sdim return X; 1041218893Sdim // If X has the form X = A / Y then X * Y cannot overflow. 1042218893Sdim if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 1043218893Sdim if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 1044218893Sdim return X; 1045218893Sdim } 1046218893Sdim 1047218893Sdim // (X rem Y) / Y -> 0 1048218893Sdim if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1049218893Sdim (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1050218893Sdim return Constant::getNullValue(Op0->getType()); 1051218893Sdim 1052280031Sdim // (X /u C1) /u C2 -> 0 if C1 * C2 overflow 1053280031Sdim ConstantInt *C1, *C2; 1054280031Sdim if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) && 1055280031Sdim match(Op1, m_ConstantInt(C2))) { 1056280031Sdim bool Overflow; 1057280031Sdim C1->getValue().umul_ov(C2->getValue(), Overflow); 1058280031Sdim if (Overflow) 1059280031Sdim return Constant::getNullValue(Op0->getType()); 1060280031Sdim } 1061280031Sdim 1062218893Sdim // If the operation is with the result of a select instruction, check whether 1063218893Sdim // operating on either branch of the select always yields the same value. 1064218893Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1065234353Sdim if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1066218893Sdim return V; 1067218893Sdim 1068218893Sdim // If the operation is with the result of a phi instruction, check whether 1069218893Sdim // operating on all incoming values of the phi always yields the same value. 1070218893Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1071234353Sdim if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1072218893Sdim return V; 1073218893Sdim 1074276479Sdim return nullptr; 1075218893Sdim} 1076218893Sdim 1077296417Sdim/// Given operands for an SDiv, see if we can fold the result. 1078296417Sdim/// If not, this returns null. 1079234353Sdimstatic Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, 1080234353Sdim unsigned MaxRecurse) { 1081234353Sdim if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse)) 1082218893Sdim return V; 1083218893Sdim 1084276479Sdim return nullptr; 1085218893Sdim} 1086218893Sdim 1087288943SdimValue *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL, 1088234353Sdim const TargetLibraryInfo *TLI, 1089280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1090280031Sdim const Instruction *CxtI) { 1091280031Sdim return ::SimplifySDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1092280031Sdim RecursionLimit); 1093218893Sdim} 1094218893Sdim 1095296417Sdim/// Given operands for a UDiv, see if we can fold the result. 1096296417Sdim/// If not, this returns null. 1097234353Sdimstatic Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, 1098234353Sdim unsigned MaxRecurse) { 1099234353Sdim if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse)) 1100218893Sdim return V; 1101218893Sdim 1102276479Sdim return nullptr; 1103218893Sdim} 1104218893Sdim 1105288943SdimValue *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL, 1106234353Sdim const TargetLibraryInfo *TLI, 1107280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1108280031Sdim const Instruction *CxtI) { 1109280031Sdim return ::SimplifyUDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1110280031Sdim RecursionLimit); 1111218893Sdim} 1112218893Sdim 1113288943Sdimstatic Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1114288943Sdim const Query &Q, unsigned) { 1115218893Sdim // undef / X -> undef (the undef could be a snan). 1116218893Sdim if (match(Op0, m_Undef())) 1117218893Sdim return Op0; 1118218893Sdim 1119218893Sdim // X / undef -> undef 1120218893Sdim if (match(Op1, m_Undef())) 1121218893Sdim return Op1; 1122218893Sdim 1123288943Sdim // 0 / X -> 0 1124288943Sdim // Requires that NaNs are off (X could be zero) and signed zeroes are 1125288943Sdim // ignored (X could be positive or negative, so the output sign is unknown). 1126288943Sdim if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) 1127288943Sdim return Op0; 1128288943Sdim 1129288943Sdim if (FMF.noNaNs()) { 1130288943Sdim // X / X -> 1.0 is legal when NaNs are ignored. 1131288943Sdim if (Op0 == Op1) 1132288943Sdim return ConstantFP::get(Op0->getType(), 1.0); 1133288943Sdim 1134288943Sdim // -X / X -> -1.0 and 1135288943Sdim // X / -X -> -1.0 are legal when NaNs are ignored. 1136288943Sdim // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored. 1137288943Sdim if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) && 1138288943Sdim BinaryOperator::getFNegArgument(Op0) == Op1) || 1139288943Sdim (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) && 1140288943Sdim BinaryOperator::getFNegArgument(Op1) == Op0)) 1141288943Sdim return ConstantFP::get(Op0->getType(), -1.0); 1142288943Sdim } 1143288943Sdim 1144276479Sdim return nullptr; 1145218893Sdim} 1146218893Sdim 1147288943SdimValue *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1148288943Sdim const DataLayout &DL, 1149234353Sdim const TargetLibraryInfo *TLI, 1150280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1151280031Sdim const Instruction *CxtI) { 1152288943Sdim return ::SimplifyFDivInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 1153280031Sdim RecursionLimit); 1154218893Sdim} 1155218893Sdim 1156296417Sdim/// Given operands for an SRem or URem, see if we can fold the result. 1157296417Sdim/// If not, this returns null. 1158221345Sdimstatic Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 1159234353Sdim const Query &Q, unsigned MaxRecurse) { 1160221345Sdim if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1161221345Sdim if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1162221345Sdim Constant *Ops[] = { C0, C1 }; 1163276479Sdim return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1164221345Sdim } 1165221345Sdim } 1166221345Sdim 1167221345Sdim // X % undef -> undef 1168221345Sdim if (match(Op1, m_Undef())) 1169221345Sdim return Op1; 1170221345Sdim 1171221345Sdim // undef % X -> 0 1172221345Sdim if (match(Op0, m_Undef())) 1173221345Sdim return Constant::getNullValue(Op0->getType()); 1174221345Sdim 1175221345Sdim // 0 % X -> 0, we don't need to preserve faults! 1176221345Sdim if (match(Op0, m_Zero())) 1177221345Sdim return Op0; 1178221345Sdim 1179221345Sdim // X % 0 -> undef, we don't need to preserve faults! 1180221345Sdim if (match(Op1, m_Zero())) 1181221345Sdim return UndefValue::get(Op0->getType()); 1182221345Sdim 1183221345Sdim // X % 1 -> 0 1184221345Sdim if (match(Op1, m_One())) 1185221345Sdim return Constant::getNullValue(Op0->getType()); 1186221345Sdim 1187221345Sdim if (Op0->getType()->isIntegerTy(1)) 1188221345Sdim // It can't be remainder by zero, hence it must be remainder by one. 1189221345Sdim return Constant::getNullValue(Op0->getType()); 1190221345Sdim 1191221345Sdim // X % X -> 0 1192221345Sdim if (Op0 == Op1) 1193221345Sdim return Constant::getNullValue(Op0->getType()); 1194221345Sdim 1195280031Sdim // (X % Y) % Y -> X % Y 1196280031Sdim if ((Opcode == Instruction::SRem && 1197280031Sdim match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 1198280031Sdim (Opcode == Instruction::URem && 1199280031Sdim match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1200280031Sdim return Op0; 1201280031Sdim 1202221345Sdim // If the operation is with the result of a select instruction, check whether 1203221345Sdim // operating on either branch of the select always yields the same value. 1204221345Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1205234353Sdim if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1206221345Sdim return V; 1207221345Sdim 1208221345Sdim // If the operation is with the result of a phi instruction, check whether 1209221345Sdim // operating on all incoming values of the phi always yields the same value. 1210221345Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1211234353Sdim if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1212221345Sdim return V; 1213221345Sdim 1214276479Sdim return nullptr; 1215221345Sdim} 1216221345Sdim 1217296417Sdim/// Given operands for an SRem, see if we can fold the result. 1218296417Sdim/// If not, this returns null. 1219234353Sdimstatic Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, 1220234353Sdim unsigned MaxRecurse) { 1221234353Sdim if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse)) 1222221345Sdim return V; 1223221345Sdim 1224276479Sdim return nullptr; 1225221345Sdim} 1226221345Sdim 1227288943SdimValue *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL, 1228234353Sdim const TargetLibraryInfo *TLI, 1229280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1230280031Sdim const Instruction *CxtI) { 1231280031Sdim return ::SimplifySRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1232280031Sdim RecursionLimit); 1233221345Sdim} 1234221345Sdim 1235296417Sdim/// Given operands for a URem, see if we can fold the result. 1236296417Sdim/// If not, this returns null. 1237234353Sdimstatic Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, 1238234353Sdim unsigned MaxRecurse) { 1239234353Sdim if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse)) 1240221345Sdim return V; 1241221345Sdim 1242276479Sdim return nullptr; 1243221345Sdim} 1244221345Sdim 1245288943SdimValue *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL, 1246234353Sdim const TargetLibraryInfo *TLI, 1247280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1248280031Sdim const Instruction *CxtI) { 1249280031Sdim return ::SimplifyURemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1250280031Sdim RecursionLimit); 1251221345Sdim} 1252221345Sdim 1253288943Sdimstatic Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1254288943Sdim const Query &, unsigned) { 1255221345Sdim // undef % X -> undef (the undef could be a snan). 1256221345Sdim if (match(Op0, m_Undef())) 1257221345Sdim return Op0; 1258221345Sdim 1259221345Sdim // X % undef -> undef 1260221345Sdim if (match(Op1, m_Undef())) 1261221345Sdim return Op1; 1262221345Sdim 1263288943Sdim // 0 % X -> 0 1264288943Sdim // Requires that NaNs are off (X could be zero) and signed zeroes are 1265288943Sdim // ignored (X could be positive or negative, so the output sign is unknown). 1266288943Sdim if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) 1267288943Sdim return Op0; 1268288943Sdim 1269276479Sdim return nullptr; 1270221345Sdim} 1271221345Sdim 1272288943SdimValue *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, 1273288943Sdim const DataLayout &DL, 1274234353Sdim const TargetLibraryInfo *TLI, 1275280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1276280031Sdim const Instruction *CxtI) { 1277288943Sdim return ::SimplifyFRemInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), 1278280031Sdim RecursionLimit); 1279221345Sdim} 1280221345Sdim 1281296417Sdim/// Returns true if a shift by \c Amount always yields undef. 1282276479Sdimstatic bool isUndefShift(Value *Amount) { 1283276479Sdim Constant *C = dyn_cast<Constant>(Amount); 1284276479Sdim if (!C) 1285276479Sdim return false; 1286276479Sdim 1287276479Sdim // X shift by undef -> undef because it may shift by the bitwidth. 1288276479Sdim if (isa<UndefValue>(C)) 1289276479Sdim return true; 1290276479Sdim 1291276479Sdim // Shifting by the bitwidth or more is undefined. 1292276479Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 1293276479Sdim if (CI->getValue().getLimitedValue() >= 1294276479Sdim CI->getType()->getScalarSizeInBits()) 1295276479Sdim return true; 1296276479Sdim 1297276479Sdim // If all lanes of a vector shift are undefined the whole shift is. 1298276479Sdim if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) { 1299276479Sdim for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I) 1300276479Sdim if (!isUndefShift(C->getAggregateElement(I))) 1301276479Sdim return false; 1302276479Sdim return true; 1303276479Sdim } 1304276479Sdim 1305276479Sdim return false; 1306276479Sdim} 1307276479Sdim 1308296417Sdim/// Given operands for an Shl, LShr or AShr, see if we can fold the result. 1309296417Sdim/// If not, this returns null. 1310218893Sdimstatic Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1311234353Sdim const Query &Q, unsigned MaxRecurse) { 1312218893Sdim if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1313218893Sdim if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1314218893Sdim Constant *Ops[] = { C0, C1 }; 1315276479Sdim return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1316218893Sdim } 1317218893Sdim } 1318218893Sdim 1319218893Sdim // 0 shift by X -> 0 1320218893Sdim if (match(Op0, m_Zero())) 1321218893Sdim return Op0; 1322218893Sdim 1323218893Sdim // X shift by 0 -> X 1324218893Sdim if (match(Op1, m_Zero())) 1325218893Sdim return Op0; 1326218893Sdim 1327276479Sdim // Fold undefined shifts. 1328276479Sdim if (isUndefShift(Op1)) 1329276479Sdim return UndefValue::get(Op0->getType()); 1330218893Sdim 1331218893Sdim // If the operation is with the result of a select instruction, check whether 1332218893Sdim // operating on either branch of the select always yields the same value. 1333218893Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1334234353Sdim if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1335218893Sdim return V; 1336218893Sdim 1337218893Sdim // If the operation is with the result of a phi instruction, check whether 1338218893Sdim // operating on all incoming values of the phi always yields the same value. 1339218893Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1340234353Sdim if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1341218893Sdim return V; 1342218893Sdim 1343276479Sdim return nullptr; 1344218893Sdim} 1345218893Sdim 1346280031Sdim/// \brief Given operands for an Shl, LShr or AShr, see if we can 1347280031Sdim/// fold the result. If not, this returns null. 1348280031Sdimstatic Value *SimplifyRightShift(unsigned Opcode, Value *Op0, Value *Op1, 1349280031Sdim bool isExact, const Query &Q, 1350280031Sdim unsigned MaxRecurse) { 1351280031Sdim if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse)) 1352280031Sdim return V; 1353280031Sdim 1354280031Sdim // X >> X -> 0 1355280031Sdim if (Op0 == Op1) 1356280031Sdim return Constant::getNullValue(Op0->getType()); 1357280031Sdim 1358280031Sdim // undef >> X -> 0 1359280031Sdim // undef >> X -> undef (if it's exact) 1360280031Sdim if (match(Op0, m_Undef())) 1361280031Sdim return isExact ? Op0 : Constant::getNullValue(Op0->getType()); 1362280031Sdim 1363280031Sdim // The low bit cannot be shifted out of an exact shift if it is set. 1364280031Sdim if (isExact) { 1365280031Sdim unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 1366280031Sdim APInt Op0KnownZero(BitWidth, 0); 1367280031Sdim APInt Op0KnownOne(BitWidth, 0); 1368280031Sdim computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC, 1369280031Sdim Q.CxtI, Q.DT); 1370280031Sdim if (Op0KnownOne[0]) 1371280031Sdim return Op0; 1372280031Sdim } 1373280031Sdim 1374280031Sdim return nullptr; 1375280031Sdim} 1376280031Sdim 1377296417Sdim/// Given operands for an Shl, see if we can fold the result. 1378296417Sdim/// If not, this returns null. 1379218893Sdimstatic Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1380234353Sdim const Query &Q, unsigned MaxRecurse) { 1381234353Sdim if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse)) 1382218893Sdim return V; 1383218893Sdim 1384218893Sdim // undef << X -> 0 1385280031Sdim // undef << X -> undef if (if it's NSW/NUW) 1386218893Sdim if (match(Op0, m_Undef())) 1387280031Sdim return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType()); 1388218893Sdim 1389218893Sdim // (X >> A) << A -> X 1390218893Sdim Value *X; 1391234353Sdim if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) 1392218893Sdim return X; 1393276479Sdim return nullptr; 1394218893Sdim} 1395218893Sdim 1396218893SdimValue *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1397288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 1398280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1399280031Sdim const Instruction *CxtI) { 1400280031Sdim return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), 1401234353Sdim RecursionLimit); 1402218893Sdim} 1403218893Sdim 1404296417Sdim/// Given operands for an LShr, see if we can fold the result. 1405296417Sdim/// If not, this returns null. 1406218893Sdimstatic Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1407234353Sdim const Query &Q, unsigned MaxRecurse) { 1408280031Sdim if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q, 1409280031Sdim MaxRecurse)) 1410280031Sdim return V; 1411218893Sdim 1412218893Sdim // (X << A) >> A -> X 1413218893Sdim Value *X; 1414280031Sdim if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1)))) 1415218893Sdim return X; 1416218893Sdim 1417276479Sdim return nullptr; 1418218893Sdim} 1419218893Sdim 1420218893SdimValue *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1421288943Sdim const DataLayout &DL, 1422234353Sdim const TargetLibraryInfo *TLI, 1423280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1424280031Sdim const Instruction *CxtI) { 1425280031Sdim return ::SimplifyLShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1426234353Sdim RecursionLimit); 1427218893Sdim} 1428218893Sdim 1429296417Sdim/// Given operands for an AShr, see if we can fold the result. 1430296417Sdim/// If not, this returns null. 1431218893Sdimstatic Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1432234353Sdim const Query &Q, unsigned MaxRecurse) { 1433280031Sdim if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q, 1434280031Sdim MaxRecurse)) 1435218893Sdim return V; 1436218893Sdim 1437218893Sdim // all ones >>a X -> all ones 1438218893Sdim if (match(Op0, m_AllOnes())) 1439218893Sdim return Op0; 1440218893Sdim 1441218893Sdim // (X << A) >> A -> X 1442218893Sdim Value *X; 1443280031Sdim if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1)))) 1444218893Sdim return X; 1445218893Sdim 1446276479Sdim // Arithmetic shifting an all-sign-bit value is a no-op. 1447280031Sdim unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); 1448276479Sdim if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 1449276479Sdim return Op0; 1450276479Sdim 1451276479Sdim return nullptr; 1452218893Sdim} 1453218893Sdim 1454218893SdimValue *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1455288943Sdim const DataLayout &DL, 1456234353Sdim const TargetLibraryInfo *TLI, 1457280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1458280031Sdim const Instruction *CxtI) { 1459280031Sdim return ::SimplifyAShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI), 1460234353Sdim RecursionLimit); 1461218893Sdim} 1462218893Sdim 1463280031Sdimstatic Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp, 1464280031Sdim ICmpInst *UnsignedICmp, bool IsAnd) { 1465280031Sdim Value *X, *Y; 1466280031Sdim 1467280031Sdim ICmpInst::Predicate EqPred; 1468280031Sdim if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) || 1469280031Sdim !ICmpInst::isEquality(EqPred)) 1470280031Sdim return nullptr; 1471280031Sdim 1472280031Sdim ICmpInst::Predicate UnsignedPred; 1473280031Sdim if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) && 1474280031Sdim ICmpInst::isUnsigned(UnsignedPred)) 1475280031Sdim ; 1476280031Sdim else if (match(UnsignedICmp, 1477280031Sdim m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) && 1478280031Sdim ICmpInst::isUnsigned(UnsignedPred)) 1479280031Sdim UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred); 1480280031Sdim else 1481280031Sdim return nullptr; 1482280031Sdim 1483280031Sdim // X < Y && Y != 0 --> X < Y 1484280031Sdim // X < Y || Y != 0 --> Y != 0 1485280031Sdim if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE) 1486280031Sdim return IsAnd ? UnsignedICmp : ZeroICmp; 1487280031Sdim 1488280031Sdim // X >= Y || Y != 0 --> true 1489280031Sdim // X >= Y || Y == 0 --> X >= Y 1490280031Sdim if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) { 1491280031Sdim if (EqPred == ICmpInst::ICMP_NE) 1492280031Sdim return getTrue(UnsignedICmp->getType()); 1493280031Sdim return UnsignedICmp; 1494280031Sdim } 1495280031Sdim 1496280031Sdim // X < Y && Y == 0 --> false 1497280031Sdim if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ && 1498280031Sdim IsAnd) 1499280031Sdim return getFalse(UnsignedICmp->getType()); 1500280031Sdim 1501280031Sdim return nullptr; 1502280031Sdim} 1503280031Sdim 1504296417Sdim/// Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range 1505296417Sdim/// of possible values cannot be satisfied. 1506280031Sdimstatic Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1507280031Sdim ICmpInst::Predicate Pred0, Pred1; 1508280031Sdim ConstantInt *CI1, *CI2; 1509280031Sdim Value *V; 1510280031Sdim 1511280031Sdim if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true)) 1512280031Sdim return X; 1513280031Sdim 1514280031Sdim if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1515280031Sdim m_ConstantInt(CI2)))) 1516280031Sdim return nullptr; 1517280031Sdim 1518280031Sdim if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1519280031Sdim return nullptr; 1520280031Sdim 1521280031Sdim Type *ITy = Op0->getType(); 1522280031Sdim 1523280031Sdim auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1524280031Sdim bool isNSW = AddInst->hasNoSignedWrap(); 1525280031Sdim bool isNUW = AddInst->hasNoUnsignedWrap(); 1526280031Sdim 1527280031Sdim const APInt &CI1V = CI1->getValue(); 1528280031Sdim const APInt &CI2V = CI2->getValue(); 1529280031Sdim const APInt Delta = CI2V - CI1V; 1530280031Sdim if (CI1V.isStrictlyPositive()) { 1531280031Sdim if (Delta == 2) { 1532280031Sdim if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT) 1533280031Sdim return getFalse(ITy); 1534280031Sdim if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1535280031Sdim return getFalse(ITy); 1536280031Sdim } 1537280031Sdim if (Delta == 1) { 1538280031Sdim if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT) 1539280031Sdim return getFalse(ITy); 1540280031Sdim if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW) 1541280031Sdim return getFalse(ITy); 1542280031Sdim } 1543280031Sdim } 1544280031Sdim if (CI1V.getBoolValue() && isNUW) { 1545280031Sdim if (Delta == 2) 1546280031Sdim if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT) 1547280031Sdim return getFalse(ITy); 1548280031Sdim if (Delta == 1) 1549280031Sdim if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT) 1550280031Sdim return getFalse(ITy); 1551280031Sdim } 1552280031Sdim 1553280031Sdim return nullptr; 1554280031Sdim} 1555280031Sdim 1556296417Sdim/// Given operands for an And, see if we can fold the result. 1557296417Sdim/// If not, this returns null. 1558234353Sdimstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, 1559234353Sdim unsigned MaxRecurse) { 1560199989Srdivacky if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1561199989Srdivacky if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1562199989Srdivacky Constant *Ops[] = { CLHS, CRHS }; 1563199481Srdivacky return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1564276479Sdim Ops, Q.DL, Q.TLI); 1565199481Srdivacky } 1566218893Sdim 1567199481Srdivacky // Canonicalize the constant to the RHS. 1568199481Srdivacky std::swap(Op0, Op1); 1569199481Srdivacky } 1570218893Sdim 1571199481Srdivacky // X & undef -> 0 1572218893Sdim if (match(Op1, m_Undef())) 1573199481Srdivacky return Constant::getNullValue(Op0->getType()); 1574218893Sdim 1575199481Srdivacky // X & X = X 1576199481Srdivacky if (Op0 == Op1) 1577199481Srdivacky return Op0; 1578218893Sdim 1579218893Sdim // X & 0 = 0 1580218893Sdim if (match(Op1, m_Zero())) 1581199481Srdivacky return Op1; 1582218893Sdim 1583218893Sdim // X & -1 = X 1584218893Sdim if (match(Op1, m_AllOnes())) 1585218893Sdim return Op0; 1586218893Sdim 1587199481Srdivacky // A & ~A = ~A & A = 0 1588218893Sdim if (match(Op0, m_Not(m_Specific(Op1))) || 1589218893Sdim match(Op1, m_Not(m_Specific(Op0)))) 1590199481Srdivacky return Constant::getNullValue(Op0->getType()); 1591218893Sdim 1592199481Srdivacky // (A | ?) & A = A 1593276479Sdim Value *A = nullptr, *B = nullptr; 1594199481Srdivacky if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1595199481Srdivacky (A == Op1 || B == Op1)) 1596199481Srdivacky return Op1; 1597218893Sdim 1598199481Srdivacky // A & (A | ?) = A 1599199481Srdivacky if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1600199481Srdivacky (A == Op0 || B == Op0)) 1601199481Srdivacky return Op0; 1602218893Sdim 1603234353Sdim // A & (-A) = A if A is a power of two or zero. 1604234353Sdim if (match(Op0, m_Neg(m_Specific(Op1))) || 1605234353Sdim match(Op1, m_Neg(m_Specific(Op0)))) { 1606288943Sdim if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, 1607288943Sdim Q.DT)) 1608234353Sdim return Op0; 1609288943Sdim if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, 1610288943Sdim Q.DT)) 1611234353Sdim return Op1; 1612234353Sdim } 1613234353Sdim 1614280031Sdim if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1615280031Sdim if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1616280031Sdim if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS)) 1617280031Sdim return V; 1618280031Sdim if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS)) 1619280031Sdim return V; 1620280031Sdim } 1621280031Sdim } 1622280031Sdim 1623218893Sdim // Try some generic simplifications for associative operations. 1624234353Sdim if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, 1625218893Sdim MaxRecurse)) 1626218893Sdim return V; 1627218893Sdim 1628218893Sdim // And distributes over Or. Try some generic simplifications based on this. 1629218893Sdim if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1630234353Sdim Q, MaxRecurse)) 1631218893Sdim return V; 1632218893Sdim 1633218893Sdim // And distributes over Xor. Try some generic simplifications based on this. 1634218893Sdim if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1635234353Sdim Q, MaxRecurse)) 1636218893Sdim return V; 1637218893Sdim 1638218893Sdim // If the operation is with the result of a select instruction, check whether 1639218893Sdim // operating on either branch of the select always yields the same value. 1640218893Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1641234353Sdim if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, 1642218893Sdim MaxRecurse)) 1643218893Sdim return V; 1644218893Sdim 1645218893Sdim // If the operation is with the result of a phi instruction, check whether 1646218893Sdim // operating on all incoming values of the phi always yields the same value. 1647218893Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1648234353Sdim if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q, 1649218893Sdim MaxRecurse)) 1650218893Sdim return V; 1651218893Sdim 1652276479Sdim return nullptr; 1653199481Srdivacky} 1654199481Srdivacky 1655288943SdimValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL, 1656234353Sdim const TargetLibraryInfo *TLI, 1657280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1658280031Sdim const Instruction *CxtI) { 1659280031Sdim return ::SimplifyAndInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1660280031Sdim RecursionLimit); 1661218893Sdim} 1662218893Sdim 1663296417Sdim/// Simplify (or (icmp ...) (icmp ...)) to true when we can tell that the union 1664296417Sdim/// contains all possible values. 1665280031Sdimstatic Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) { 1666280031Sdim ICmpInst::Predicate Pred0, Pred1; 1667280031Sdim ConstantInt *CI1, *CI2; 1668280031Sdim Value *V; 1669280031Sdim 1670280031Sdim if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false)) 1671280031Sdim return X; 1672280031Sdim 1673280031Sdim if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)), 1674280031Sdim m_ConstantInt(CI2)))) 1675280031Sdim return nullptr; 1676280031Sdim 1677280031Sdim if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1)))) 1678280031Sdim return nullptr; 1679280031Sdim 1680280031Sdim Type *ITy = Op0->getType(); 1681280031Sdim 1682280031Sdim auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0)); 1683280031Sdim bool isNSW = AddInst->hasNoSignedWrap(); 1684280031Sdim bool isNUW = AddInst->hasNoUnsignedWrap(); 1685280031Sdim 1686280031Sdim const APInt &CI1V = CI1->getValue(); 1687280031Sdim const APInt &CI2V = CI2->getValue(); 1688280031Sdim const APInt Delta = CI2V - CI1V; 1689280031Sdim if (CI1V.isStrictlyPositive()) { 1690280031Sdim if (Delta == 2) { 1691280031Sdim if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE) 1692280031Sdim return getTrue(ITy); 1693280031Sdim if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1694280031Sdim return getTrue(ITy); 1695280031Sdim } 1696280031Sdim if (Delta == 1) { 1697280031Sdim if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE) 1698280031Sdim return getTrue(ITy); 1699280031Sdim if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW) 1700280031Sdim return getTrue(ITy); 1701280031Sdim } 1702280031Sdim } 1703280031Sdim if (CI1V.getBoolValue() && isNUW) { 1704280031Sdim if (Delta == 2) 1705280031Sdim if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE) 1706280031Sdim return getTrue(ITy); 1707280031Sdim if (Delta == 1) 1708280031Sdim if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE) 1709280031Sdim return getTrue(ITy); 1710280031Sdim } 1711280031Sdim 1712280031Sdim return nullptr; 1713280031Sdim} 1714280031Sdim 1715296417Sdim/// Given operands for an Or, see if we can fold the result. 1716296417Sdim/// If not, this returns null. 1717234353Sdimstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, 1718234353Sdim unsigned MaxRecurse) { 1719199481Srdivacky if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1720199481Srdivacky if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1721199481Srdivacky Constant *Ops[] = { CLHS, CRHS }; 1722199481Srdivacky return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1723276479Sdim Ops, Q.DL, Q.TLI); 1724199481Srdivacky } 1725218893Sdim 1726199481Srdivacky // Canonicalize the constant to the RHS. 1727199481Srdivacky std::swap(Op0, Op1); 1728199481Srdivacky } 1729218893Sdim 1730199481Srdivacky // X | undef -> -1 1731218893Sdim if (match(Op1, m_Undef())) 1732199481Srdivacky return Constant::getAllOnesValue(Op0->getType()); 1733218893Sdim 1734199481Srdivacky // X | X = X 1735199481Srdivacky if (Op0 == Op1) 1736199481Srdivacky return Op0; 1737199481Srdivacky 1738218893Sdim // X | 0 = X 1739218893Sdim if (match(Op1, m_Zero())) 1740199481Srdivacky return Op0; 1741218893Sdim 1742218893Sdim // X | -1 = -1 1743218893Sdim if (match(Op1, m_AllOnes())) 1744218893Sdim return Op1; 1745218893Sdim 1746199481Srdivacky // A | ~A = ~A | A = -1 1747218893Sdim if (match(Op0, m_Not(m_Specific(Op1))) || 1748218893Sdim match(Op1, m_Not(m_Specific(Op0)))) 1749199481Srdivacky return Constant::getAllOnesValue(Op0->getType()); 1750218893Sdim 1751199481Srdivacky // (A & ?) | A = A 1752276479Sdim Value *A = nullptr, *B = nullptr; 1753199481Srdivacky if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1754199481Srdivacky (A == Op1 || B == Op1)) 1755199481Srdivacky return Op1; 1756218893Sdim 1757199481Srdivacky // A | (A & ?) = A 1758199481Srdivacky if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1759199481Srdivacky (A == Op0 || B == Op0)) 1760199481Srdivacky return Op0; 1761218893Sdim 1762219077Sdim // ~(A & ?) | A = -1 1763219077Sdim if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1764219077Sdim (A == Op1 || B == Op1)) 1765219077Sdim return Constant::getAllOnesValue(Op1->getType()); 1766219077Sdim 1767219077Sdim // A | ~(A & ?) = -1 1768219077Sdim if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1769219077Sdim (A == Op0 || B == Op0)) 1770219077Sdim return Constant::getAllOnesValue(Op0->getType()); 1771219077Sdim 1772280031Sdim if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) { 1773280031Sdim if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) { 1774280031Sdim if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS)) 1775280031Sdim return V; 1776280031Sdim if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS)) 1777280031Sdim return V; 1778280031Sdim } 1779280031Sdim } 1780280031Sdim 1781218893Sdim // Try some generic simplifications for associative operations. 1782234353Sdim if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, 1783218893Sdim MaxRecurse)) 1784218893Sdim return V; 1785218893Sdim 1786218893Sdim // Or distributes over And. Try some generic simplifications based on this. 1787234353Sdim if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, 1788234353Sdim MaxRecurse)) 1789218893Sdim return V; 1790218893Sdim 1791218893Sdim // If the operation is with the result of a select instruction, check whether 1792218893Sdim // operating on either branch of the select always yields the same value. 1793218893Sdim if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1794234353Sdim if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, 1795218893Sdim MaxRecurse)) 1796218893Sdim return V; 1797218893Sdim 1798276479Sdim // (A & C)|(B & D) 1799276479Sdim Value *C = nullptr, *D = nullptr; 1800276479Sdim if (match(Op0, m_And(m_Value(A), m_Value(C))) && 1801276479Sdim match(Op1, m_And(m_Value(B), m_Value(D)))) { 1802276479Sdim ConstantInt *C1 = dyn_cast<ConstantInt>(C); 1803276479Sdim ConstantInt *C2 = dyn_cast<ConstantInt>(D); 1804276479Sdim if (C1 && C2 && (C1->getValue() == ~C2->getValue())) { 1805276479Sdim // (A & C1)|(B & C2) 1806276479Sdim // If we have: ((V + N) & C1) | (V & C2) 1807276479Sdim // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 1808276479Sdim // replace with V+N. 1809276479Sdim Value *V1, *V2; 1810276479Sdim if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+ 1811276479Sdim match(A, m_Add(m_Value(V1), m_Value(V2)))) { 1812276479Sdim // Add commutes, try both ways. 1813280031Sdim if (V1 == B && 1814280031Sdim MaskedValueIsZero(V2, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1815276479Sdim return A; 1816280031Sdim if (V2 == B && 1817280031Sdim MaskedValueIsZero(V1, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1818276479Sdim return A; 1819276479Sdim } 1820276479Sdim // Or commutes, try both ways. 1821276479Sdim if ((C1->getValue() & (C1->getValue() + 1)) == 0 && 1822276479Sdim match(B, m_Add(m_Value(V1), m_Value(V2)))) { 1823276479Sdim // Add commutes, try both ways. 1824280031Sdim if (V1 == A && 1825280031Sdim MaskedValueIsZero(V2, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1826276479Sdim return B; 1827280031Sdim if (V2 == A && 1828280031Sdim MaskedValueIsZero(V1, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 1829276479Sdim return B; 1830276479Sdim } 1831276479Sdim } 1832276479Sdim } 1833276479Sdim 1834218893Sdim // If the operation is with the result of a phi instruction, check whether 1835218893Sdim // operating on all incoming values of the phi always yields the same value. 1836218893Sdim if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1837234353Sdim if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse)) 1838218893Sdim return V; 1839218893Sdim 1840276479Sdim return nullptr; 1841199481Srdivacky} 1842199481Srdivacky 1843288943SdimValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL, 1844234353Sdim const TargetLibraryInfo *TLI, 1845280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1846280031Sdim const Instruction *CxtI) { 1847280031Sdim return ::SimplifyOrInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1848280031Sdim RecursionLimit); 1849218893Sdim} 1850199481Srdivacky 1851296417Sdim/// Given operands for a Xor, see if we can fold the result. 1852296417Sdim/// If not, this returns null. 1853234353Sdimstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, 1854234353Sdim unsigned MaxRecurse) { 1855218893Sdim if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1856218893Sdim if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1857218893Sdim Constant *Ops[] = { CLHS, CRHS }; 1858218893Sdim return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1859276479Sdim Ops, Q.DL, Q.TLI); 1860218893Sdim } 1861218893Sdim 1862218893Sdim // Canonicalize the constant to the RHS. 1863218893Sdim std::swap(Op0, Op1); 1864218893Sdim } 1865218893Sdim 1866218893Sdim // A ^ undef -> undef 1867218893Sdim if (match(Op1, m_Undef())) 1868218893Sdim return Op1; 1869218893Sdim 1870218893Sdim // A ^ 0 = A 1871218893Sdim if (match(Op1, m_Zero())) 1872218893Sdim return Op0; 1873218893Sdim 1874218893Sdim // A ^ A = 0 1875218893Sdim if (Op0 == Op1) 1876218893Sdim return Constant::getNullValue(Op0->getType()); 1877218893Sdim 1878218893Sdim // A ^ ~A = ~A ^ A = -1 1879218893Sdim if (match(Op0, m_Not(m_Specific(Op1))) || 1880218893Sdim match(Op1, m_Not(m_Specific(Op0)))) 1881218893Sdim return Constant::getAllOnesValue(Op0->getType()); 1882218893Sdim 1883218893Sdim // Try some generic simplifications for associative operations. 1884234353Sdim if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, 1885218893Sdim MaxRecurse)) 1886218893Sdim return V; 1887218893Sdim 1888218893Sdim // Threading Xor over selects and phi nodes is pointless, so don't bother. 1889218893Sdim // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1890218893Sdim // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1891218893Sdim // only if B and C are equal. If B and C are equal then (since we assume 1892218893Sdim // that operands have already been simplified) "select(cond, B, C)" should 1893218893Sdim // have been simplified to the common value of B and C already. Analysing 1894218893Sdim // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1895218893Sdim // for threading over phi nodes. 1896218893Sdim 1897276479Sdim return nullptr; 1898218893Sdim} 1899218893Sdim 1900288943SdimValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL, 1901234353Sdim const TargetLibraryInfo *TLI, 1902280031Sdim const DominatorTree *DT, AssumptionCache *AC, 1903280031Sdim const Instruction *CxtI) { 1904280031Sdim return ::SimplifyXorInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), 1905280031Sdim RecursionLimit); 1906218893Sdim} 1907218893Sdim 1908226633Sdimstatic Type *GetCompareTy(Value *Op) { 1909199481Srdivacky return CmpInst::makeCmpResultType(Op->getType()); 1910199481Srdivacky} 1911199481Srdivacky 1912296417Sdim/// Rummage around inside V looking for something equivalent to the comparison 1913296417Sdim/// "LHS Pred RHS". Return such a value if found, otherwise return null. 1914296417Sdim/// Helper function for analyzing max/min idioms. 1915223017Sdimstatic Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1916223017Sdim Value *LHS, Value *RHS) { 1917223017Sdim SelectInst *SI = dyn_cast<SelectInst>(V); 1918223017Sdim if (!SI) 1919276479Sdim return nullptr; 1920223017Sdim CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1921223017Sdim if (!Cmp) 1922276479Sdim return nullptr; 1923223017Sdim Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1924223017Sdim if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1925223017Sdim return Cmp; 1926223017Sdim if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1927223017Sdim LHS == CmpRHS && RHS == CmpLHS) 1928223017Sdim return Cmp; 1929276479Sdim return nullptr; 1930223017Sdim} 1931223017Sdim 1932249423Sdim// A significant optimization not implemented here is assuming that alloca 1933249423Sdim// addresses are not equal to incoming argument values. They don't *alias*, 1934249423Sdim// as we say, but that doesn't mean they aren't equal, so we take a 1935249423Sdim// conservative approach. 1936249423Sdim// 1937249423Sdim// This is inspired in part by C++11 5.10p1: 1938249423Sdim// "Two pointers of the same type compare equal if and only if they are both 1939249423Sdim// null, both point to the same function, or both represent the same 1940249423Sdim// address." 1941249423Sdim// 1942249423Sdim// This is pretty permissive. 1943249423Sdim// 1944249423Sdim// It's also partly due to C11 6.5.9p6: 1945249423Sdim// "Two pointers compare equal if and only if both are null pointers, both are 1946249423Sdim// pointers to the same object (including a pointer to an object and a 1947249423Sdim// subobject at its beginning) or function, both are pointers to one past the 1948249423Sdim// last element of the same array object, or one is a pointer to one past the 1949249423Sdim// end of one array object and the other is a pointer to the start of a 1950251662Sdim// different array object that happens to immediately follow the first array 1951249423Sdim// object in the address space.) 1952249423Sdim// 1953249423Sdim// C11's version is more restrictive, however there's no reason why an argument 1954249423Sdim// couldn't be a one-past-the-end value for a stack object in the caller and be 1955249423Sdim// equal to the beginning of a stack object in the callee. 1956249423Sdim// 1957249423Sdim// If the C and C++ standards are ever made sufficiently restrictive in this 1958249423Sdim// area, it may be possible to update LLVM's semantics accordingly and reinstate 1959249423Sdim// this optimization. 1960288943Sdimstatic Constant *computePointerICmp(const DataLayout &DL, 1961249423Sdim const TargetLibraryInfo *TLI, 1962288943Sdim CmpInst::Predicate Pred, Value *LHS, 1963288943Sdim Value *RHS) { 1964249423Sdim // First, skip past any trivial no-ops. 1965249423Sdim LHS = LHS->stripPointerCasts(); 1966249423Sdim RHS = RHS->stripPointerCasts(); 1967249423Sdim 1968249423Sdim // A non-null pointer is not equal to a null pointer. 1969261991Sdim if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) && 1970249423Sdim (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) 1971249423Sdim return ConstantInt::get(GetCompareTy(LHS), 1972249423Sdim !CmpInst::isTrueWhenEqual(Pred)); 1973249423Sdim 1974234353Sdim // We can only fold certain predicates on pointer comparisons. 1975234353Sdim switch (Pred) { 1976234353Sdim default: 1977276479Sdim return nullptr; 1978234353Sdim 1979234353Sdim // Equality comaprisons are easy to fold. 1980234353Sdim case CmpInst::ICMP_EQ: 1981234353Sdim case CmpInst::ICMP_NE: 1982234353Sdim break; 1983234353Sdim 1984234353Sdim // We can only handle unsigned relational comparisons because 'inbounds' on 1985234353Sdim // a GEP only protects against unsigned wrapping. 1986234353Sdim case CmpInst::ICMP_UGT: 1987234353Sdim case CmpInst::ICMP_UGE: 1988234353Sdim case CmpInst::ICMP_ULT: 1989234353Sdim case CmpInst::ICMP_ULE: 1990234353Sdim // However, we have to switch them to their signed variants to handle 1991234353Sdim // negative indices from the base pointer. 1992234353Sdim Pred = ICmpInst::getSignedPredicate(Pred); 1993234353Sdim break; 1994234353Sdim } 1995234353Sdim 1996249423Sdim // Strip off any constant offsets so that we can reason about them. 1997249423Sdim // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets 1998249423Sdim // here and compare base addresses like AliasAnalysis does, however there are 1999249423Sdim // numerous hazards. AliasAnalysis and its utilities rely on special rules 2000249423Sdim // governing loads and stores which don't apply to icmps. Also, AliasAnalysis 2001249423Sdim // doesn't need to guarantee pointer inequality when it says NoAlias. 2002276479Sdim Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 2003276479Sdim Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 2004234353Sdim 2005249423Sdim // If LHS and RHS are related via constant offsets to the same base 2006249423Sdim // value, we can replace it with an icmp which just compares the offsets. 2007249423Sdim if (LHS == RHS) 2008249423Sdim return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); 2009234353Sdim 2010249423Sdim // Various optimizations for (in)equality comparisons. 2011249423Sdim if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { 2012249423Sdim // Different non-empty allocations that exist at the same time have 2013249423Sdim // different addresses (if the program can tell). Global variables always 2014249423Sdim // exist, so they always exist during the lifetime of each other and all 2015249423Sdim // allocas. Two different allocas usually have different addresses... 2016249423Sdim // 2017249423Sdim // However, if there's an @llvm.stackrestore dynamically in between two 2018249423Sdim // allocas, they may have the same address. It's tempting to reduce the 2019249423Sdim // scope of the problem by only looking at *static* allocas here. That would 2020249423Sdim // cover the majority of allocas while significantly reducing the likelihood 2021249423Sdim // of having an @llvm.stackrestore pop up in the middle. However, it's not 2022249423Sdim // actually impossible for an @llvm.stackrestore to pop up in the middle of 2023249423Sdim // an entry block. Also, if we have a block that's not attached to a 2024249423Sdim // function, we can't tell if it's "static" under the current definition. 2025249423Sdim // Theoretically, this problem could be fixed by creating a new kind of 2026249423Sdim // instruction kind specifically for static allocas. Such a new instruction 2027249423Sdim // could be required to be at the top of the entry block, thus preventing it 2028249423Sdim // from being subject to a @llvm.stackrestore. Instcombine could even 2029249423Sdim // convert regular allocas into these special allocas. It'd be nifty. 2030249423Sdim // However, until then, this problem remains open. 2031249423Sdim // 2032249423Sdim // So, we'll assume that two non-empty allocas have different addresses 2033249423Sdim // for now. 2034249423Sdim // 2035249423Sdim // With all that, if the offsets are within the bounds of their allocations 2036249423Sdim // (and not one-past-the-end! so we can't use inbounds!), and their 2037249423Sdim // allocations aren't the same, the pointers are not equal. 2038249423Sdim // 2039249423Sdim // Note that it's not necessary to check for LHS being a global variable 2040249423Sdim // address, due to canonicalization and constant folding. 2041249423Sdim if (isa<AllocaInst>(LHS) && 2042249423Sdim (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) { 2043249423Sdim ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset); 2044249423Sdim ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset); 2045249423Sdim uint64_t LHSSize, RHSSize; 2046249423Sdim if (LHSOffsetCI && RHSOffsetCI && 2047276479Sdim getObjectSize(LHS, LHSSize, DL, TLI) && 2048276479Sdim getObjectSize(RHS, RHSSize, DL, TLI)) { 2049249423Sdim const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); 2050249423Sdim const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); 2051249423Sdim if (!LHSOffsetValue.isNegative() && 2052249423Sdim !RHSOffsetValue.isNegative() && 2053249423Sdim LHSOffsetValue.ult(LHSSize) && 2054249423Sdim RHSOffsetValue.ult(RHSSize)) { 2055249423Sdim return ConstantInt::get(GetCompareTy(LHS), 2056249423Sdim !CmpInst::isTrueWhenEqual(Pred)); 2057249423Sdim } 2058249423Sdim } 2059249423Sdim 2060249423Sdim // Repeat the above check but this time without depending on DataLayout 2061249423Sdim // or being able to compute a precise size. 2062249423Sdim if (!cast<PointerType>(LHS->getType())->isEmptyTy() && 2063249423Sdim !cast<PointerType>(RHS->getType())->isEmptyTy() && 2064249423Sdim LHSOffset->isNullValue() && 2065249423Sdim RHSOffset->isNullValue()) 2066249423Sdim return ConstantInt::get(GetCompareTy(LHS), 2067249423Sdim !CmpInst::isTrueWhenEqual(Pred)); 2068249423Sdim } 2069261991Sdim 2070261991Sdim // Even if an non-inbounds GEP occurs along the path we can still optimize 2071261991Sdim // equality comparisons concerning the result. We avoid walking the whole 2072261991Sdim // chain again by starting where the last calls to 2073261991Sdim // stripAndComputeConstantOffsets left off and accumulate the offsets. 2074276479Sdim Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true); 2075276479Sdim Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true); 2076261991Sdim if (LHS == RHS) 2077261991Sdim return ConstantExpr::getICmp(Pred, 2078261991Sdim ConstantExpr::getAdd(LHSOffset, LHSNoBound), 2079261991Sdim ConstantExpr::getAdd(RHSOffset, RHSNoBound)); 2080280031Sdim 2081280031Sdim // If one side of the equality comparison must come from a noalias call 2082280031Sdim // (meaning a system memory allocation function), and the other side must 2083280031Sdim // come from a pointer that cannot overlap with dynamically-allocated 2084280031Sdim // memory within the lifetime of the current function (allocas, byval 2085280031Sdim // arguments, globals), then determine the comparison result here. 2086280031Sdim SmallVector<Value *, 8> LHSUObjs, RHSUObjs; 2087280031Sdim GetUnderlyingObjects(LHS, LHSUObjs, DL); 2088280031Sdim GetUnderlyingObjects(RHS, RHSUObjs, DL); 2089280031Sdim 2090280031Sdim // Is the set of underlying objects all noalias calls? 2091280031Sdim auto IsNAC = [](SmallVectorImpl<Value *> &Objects) { 2092296417Sdim return std::all_of(Objects.begin(), Objects.end(), isNoAliasCall); 2093280031Sdim }; 2094280031Sdim 2095280031Sdim // Is the set of underlying objects all things which must be disjoint from 2096280031Sdim // noalias calls. For allocas, we consider only static ones (dynamic 2097280031Sdim // allocas might be transformed into calls to malloc not simultaneously 2098280031Sdim // live with the compared-to allocation). For globals, we exclude symbols 2099280031Sdim // that might be resolve lazily to symbols in another dynamically-loaded 2100280031Sdim // library (and, thus, could be malloc'ed by the implementation). 2101280031Sdim auto IsAllocDisjoint = [](SmallVectorImpl<Value *> &Objects) { 2102296417Sdim return std::all_of(Objects.begin(), Objects.end(), [](Value *V) { 2103296417Sdim if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) 2104296417Sdim return AI->getParent() && AI->getFunction() && AI->isStaticAlloca(); 2105296417Sdim if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2106296417Sdim return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() || 2107296417Sdim GV->hasProtectedVisibility() || GV->hasUnnamedAddr()) && 2108296417Sdim !GV->isThreadLocal(); 2109296417Sdim if (const Argument *A = dyn_cast<Argument>(V)) 2110296417Sdim return A->hasByValAttr(); 2111296417Sdim return false; 2112296417Sdim }); 2113280031Sdim }; 2114280031Sdim 2115280031Sdim if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) || 2116280031Sdim (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs))) 2117280031Sdim return ConstantInt::get(GetCompareTy(LHS), 2118280031Sdim !CmpInst::isTrueWhenEqual(Pred)); 2119249423Sdim } 2120249423Sdim 2121249423Sdim // Otherwise, fail. 2122276479Sdim return nullptr; 2123234353Sdim} 2124234353Sdim 2125296417Sdim/// Given operands for an ICmpInst, see if we can fold the result. 2126296417Sdim/// If not, this returns null. 2127218893Sdimstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2128234353Sdim const Query &Q, unsigned MaxRecurse) { 2129199481Srdivacky CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2130199481Srdivacky assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 2131218893Sdim 2132199481Srdivacky if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2133199481Srdivacky if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2134276479Sdim return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 2135199481Srdivacky 2136199481Srdivacky // If we have a constant, make sure it is on the RHS. 2137199481Srdivacky std::swap(LHS, RHS); 2138199481Srdivacky Pred = CmpInst::getSwappedPredicate(Pred); 2139199481Srdivacky } 2140218893Sdim 2141226633Sdim Type *ITy = GetCompareTy(LHS); // The return type. 2142226633Sdim Type *OpTy = LHS->getType(); // The operand type. 2143218893Sdim 2144199481Srdivacky // icmp X, X -> true/false 2145204792Srdivacky // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 2146204792Srdivacky // because X could be 0. 2147204792Srdivacky if (LHS == RHS || isa<UndefValue>(RHS)) 2148199481Srdivacky return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 2149218893Sdim 2150218893Sdim // Special case logic when the operands have i1 type. 2151234353Sdim if (OpTy->getScalarType()->isIntegerTy(1)) { 2152218893Sdim switch (Pred) { 2153218893Sdim default: break; 2154218893Sdim case ICmpInst::ICMP_EQ: 2155218893Sdim // X == 1 -> X 2156218893Sdim if (match(RHS, m_One())) 2157218893Sdim return LHS; 2158218893Sdim break; 2159218893Sdim case ICmpInst::ICMP_NE: 2160218893Sdim // X != 0 -> X 2161218893Sdim if (match(RHS, m_Zero())) 2162218893Sdim return LHS; 2163218893Sdim break; 2164218893Sdim case ICmpInst::ICMP_UGT: 2165218893Sdim // X >u 0 -> X 2166218893Sdim if (match(RHS, m_Zero())) 2167218893Sdim return LHS; 2168218893Sdim break; 2169218893Sdim case ICmpInst::ICMP_UGE: 2170218893Sdim // X >=u 1 -> X 2171218893Sdim if (match(RHS, m_One())) 2172218893Sdim return LHS; 2173296417Sdim if (isImpliedCondition(RHS, LHS, Q.DL)) 2174296417Sdim return getTrue(ITy); 2175218893Sdim break; 2176296417Sdim case ICmpInst::ICMP_SGE: 2177296417Sdim /// For signed comparison, the values for an i1 are 0 and -1 2178296417Sdim /// respectively. This maps into a truth table of: 2179296417Sdim /// LHS | RHS | LHS >=s RHS | LHS implies RHS 2180296417Sdim /// 0 | 0 | 1 (0 >= 0) | 1 2181296417Sdim /// 0 | 1 | 1 (0 >= -1) | 1 2182296417Sdim /// 1 | 0 | 0 (-1 >= 0) | 0 2183296417Sdim /// 1 | 1 | 1 (-1 >= -1) | 1 2184296417Sdim if (isImpliedCondition(LHS, RHS, Q.DL)) 2185296417Sdim return getTrue(ITy); 2186296417Sdim break; 2187218893Sdim case ICmpInst::ICMP_SLT: 2188218893Sdim // X <s 0 -> X 2189218893Sdim if (match(RHS, m_Zero())) 2190218893Sdim return LHS; 2191218893Sdim break; 2192218893Sdim case ICmpInst::ICMP_SLE: 2193218893Sdim // X <=s -1 -> X 2194218893Sdim if (match(RHS, m_One())) 2195218893Sdim return LHS; 2196218893Sdim break; 2197296417Sdim case ICmpInst::ICMP_ULE: 2198296417Sdim if (isImpliedCondition(LHS, RHS, Q.DL)) 2199296417Sdim return getTrue(ITy); 2200296417Sdim break; 2201218893Sdim } 2202218893Sdim } 2203218893Sdim 2204218893Sdim // If we are comparing with zero then try hard since this is a common case. 2205218893Sdim if (match(RHS, m_Zero())) { 2206218893Sdim bool LHSKnownNonNegative, LHSKnownNegative; 2207199481Srdivacky switch (Pred) { 2208234353Sdim default: llvm_unreachable("Unknown ICmp predicate!"); 2209218893Sdim case ICmpInst::ICMP_ULT: 2210226633Sdim return getFalse(ITy); 2211218893Sdim case ICmpInst::ICMP_UGE: 2212226633Sdim return getTrue(ITy); 2213218893Sdim case ICmpInst::ICMP_EQ: 2214199481Srdivacky case ICmpInst::ICMP_ULE: 2215280031Sdim if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2216226633Sdim return getFalse(ITy); 2217199481Srdivacky break; 2218218893Sdim case ICmpInst::ICMP_NE: 2219218893Sdim case ICmpInst::ICMP_UGT: 2220280031Sdim if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2221226633Sdim return getTrue(ITy); 2222218893Sdim break; 2223218893Sdim case ICmpInst::ICMP_SLT: 2224280031Sdim ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2225280031Sdim Q.CxtI, Q.DT); 2226218893Sdim if (LHSKnownNegative) 2227226633Sdim return getTrue(ITy); 2228218893Sdim if (LHSKnownNonNegative) 2229226633Sdim return getFalse(ITy); 2230218893Sdim break; 2231199481Srdivacky case ICmpInst::ICMP_SLE: 2232280031Sdim ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2233280031Sdim Q.CxtI, Q.DT); 2234218893Sdim if (LHSKnownNegative) 2235226633Sdim return getTrue(ITy); 2236280031Sdim if (LHSKnownNonNegative && 2237280031Sdim isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2238226633Sdim return getFalse(ITy); 2239199481Srdivacky break; 2240218893Sdim case ICmpInst::ICMP_SGE: 2241280031Sdim ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2242280031Sdim Q.CxtI, Q.DT); 2243218893Sdim if (LHSKnownNegative) 2244226633Sdim return getFalse(ITy); 2245218893Sdim if (LHSKnownNonNegative) 2246226633Sdim return getTrue(ITy); 2247218893Sdim break; 2248218893Sdim case ICmpInst::ICMP_SGT: 2249280031Sdim ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC, 2250280031Sdim Q.CxtI, Q.DT); 2251218893Sdim if (LHSKnownNegative) 2252226633Sdim return getFalse(ITy); 2253280031Sdim if (LHSKnownNonNegative && 2254280031Sdim isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) 2255226633Sdim return getTrue(ITy); 2256218893Sdim break; 2257218893Sdim } 2258218893Sdim } 2259218893Sdim 2260218893Sdim // See if we are doing a comparison with a constant integer. 2261218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2262221345Sdim // Rule out tautological comparisons (eg., ult 0 or uge 0). 2263221345Sdim ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 2264221345Sdim if (RHS_CR.isEmptySet()) 2265221345Sdim return ConstantInt::getFalse(CI->getContext()); 2266221345Sdim if (RHS_CR.isFullSet()) 2267221345Sdim return ConstantInt::getTrue(CI->getContext()); 2268221345Sdim 2269221345Sdim // Many binary operators with constant RHS have easy to compute constant 2270221345Sdim // range. Use them to check whether the comparison is a tautology. 2271276479Sdim unsigned Width = CI->getBitWidth(); 2272221345Sdim APInt Lower = APInt(Width, 0); 2273221345Sdim APInt Upper = APInt(Width, 0); 2274221345Sdim ConstantInt *CI2; 2275221345Sdim if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 2276221345Sdim // 'urem x, CI2' produces [0, CI2). 2277221345Sdim Upper = CI2->getValue(); 2278221345Sdim } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 2279221345Sdim // 'srem x, CI2' produces (-|CI2|, |CI2|). 2280221345Sdim Upper = CI2->getValue().abs(); 2281221345Sdim Lower = (-Upper) + 1; 2282234353Sdim } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 2283234353Sdim // 'udiv CI2, x' produces [0, CI2]. 2284234353Sdim Upper = CI2->getValue() + 1; 2285221345Sdim } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 2286221345Sdim // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 2287221345Sdim APInt NegOne = APInt::getAllOnesValue(Width); 2288221345Sdim if (!CI2->isZero()) 2289221345Sdim Upper = NegOne.udiv(CI2->getValue()) + 1; 2290276479Sdim } else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) { 2291276479Sdim if (CI2->isMinSignedValue()) { 2292276479Sdim // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. 2293276479Sdim Lower = CI2->getValue(); 2294276479Sdim Upper = Lower.lshr(1) + 1; 2295276479Sdim } else { 2296276479Sdim // 'sdiv CI2, x' produces [-|CI2|, |CI2|]. 2297276479Sdim Upper = CI2->getValue().abs() + 1; 2298276479Sdim Lower = (-Upper) + 1; 2299276479Sdim } 2300221345Sdim } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 2301221345Sdim APInt IntMin = APInt::getSignedMinValue(Width); 2302221345Sdim APInt IntMax = APInt::getSignedMaxValue(Width); 2303276479Sdim APInt Val = CI2->getValue(); 2304276479Sdim if (Val.isAllOnesValue()) { 2305276479Sdim // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] 2306276479Sdim // where CI2 != -1 and CI2 != 0 and CI2 != 1 2307276479Sdim Lower = IntMin + 1; 2308276479Sdim Upper = IntMax + 1; 2309276479Sdim } else if (Val.countLeadingZeros() < Width - 1) { 2310276479Sdim // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2] 2311276479Sdim // where CI2 != -1 and CI2 != 0 and CI2 != 1 2312221345Sdim Lower = IntMin.sdiv(Val); 2313276479Sdim Upper = IntMax.sdiv(Val); 2314276479Sdim if (Lower.sgt(Upper)) 2315276479Sdim std::swap(Lower, Upper); 2316276479Sdim Upper = Upper + 1; 2317276479Sdim assert(Upper != Lower && "Upper part of range has wrapped!"); 2318221345Sdim } 2319280031Sdim } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) { 2320280031Sdim // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)] 2321280031Sdim Lower = CI2->getValue(); 2322280031Sdim Upper = Lower.shl(Lower.countLeadingZeros()) + 1; 2323280031Sdim } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) { 2324280031Sdim if (CI2->isNegative()) { 2325280031Sdim // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2] 2326280031Sdim unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1; 2327280031Sdim Lower = CI2->getValue().shl(ShiftAmount); 2328280031Sdim Upper = CI2->getValue() + 1; 2329280031Sdim } else { 2330280031Sdim // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1] 2331280031Sdim unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1; 2332280031Sdim Lower = CI2->getValue(); 2333280031Sdim Upper = CI2->getValue().shl(ShiftAmount) + 1; 2334280031Sdim } 2335221345Sdim } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 2336221345Sdim // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 2337221345Sdim APInt NegOne = APInt::getAllOnesValue(Width); 2338221345Sdim if (CI2->getValue().ult(Width)) 2339221345Sdim Upper = NegOne.lshr(CI2->getValue()) + 1; 2340276479Sdim } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) { 2341276479Sdim // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2]. 2342276479Sdim unsigned ShiftAmount = Width - 1; 2343276479Sdim if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2344276479Sdim ShiftAmount = CI2->getValue().countTrailingZeros(); 2345276479Sdim Lower = CI2->getValue().lshr(ShiftAmount); 2346276479Sdim Upper = CI2->getValue() + 1; 2347221345Sdim } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 2348221345Sdim // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 2349221345Sdim APInt IntMin = APInt::getSignedMinValue(Width); 2350221345Sdim APInt IntMax = APInt::getSignedMaxValue(Width); 2351221345Sdim if (CI2->getValue().ult(Width)) { 2352221345Sdim Lower = IntMin.ashr(CI2->getValue()); 2353221345Sdim Upper = IntMax.ashr(CI2->getValue()) + 1; 2354221345Sdim } 2355276479Sdim } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) { 2356276479Sdim unsigned ShiftAmount = Width - 1; 2357276479Sdim if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 2358276479Sdim ShiftAmount = CI2->getValue().countTrailingZeros(); 2359276479Sdim if (CI2->isNegative()) { 2360276479Sdim // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)] 2361276479Sdim Lower = CI2->getValue(); 2362276479Sdim Upper = CI2->getValue().ashr(ShiftAmount) + 1; 2363276479Sdim } else { 2364276479Sdim // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2] 2365276479Sdim Lower = CI2->getValue().ashr(ShiftAmount); 2366276479Sdim Upper = CI2->getValue() + 1; 2367276479Sdim } 2368221345Sdim } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 2369221345Sdim // 'or x, CI2' produces [CI2, UINT_MAX]. 2370221345Sdim Lower = CI2->getValue(); 2371221345Sdim } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 2372221345Sdim // 'and x, CI2' produces [0, CI2]. 2373221345Sdim Upper = CI2->getValue() + 1; 2374296417Sdim } else if (match(LHS, m_NUWAdd(m_Value(), m_ConstantInt(CI2)))) { 2375296417Sdim // 'add nuw x, CI2' produces [CI2, UINT_MAX]. 2376296417Sdim Lower = CI2->getValue(); 2377199481Srdivacky } 2378296417Sdim 2379296417Sdim ConstantRange LHS_CR = Lower != Upper ? ConstantRange(Lower, Upper) 2380296417Sdim : ConstantRange(Width, true); 2381296417Sdim 2382296417Sdim if (auto *I = dyn_cast<Instruction>(LHS)) 2383296417Sdim if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) 2384296417Sdim LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges)); 2385296417Sdim 2386296417Sdim if (!LHS_CR.isFullSet()) { 2387221345Sdim if (RHS_CR.contains(LHS_CR)) 2388221345Sdim return ConstantInt::getTrue(RHS->getContext()); 2389221345Sdim if (RHS_CR.inverse().contains(LHS_CR)) 2390221345Sdim return ConstantInt::getFalse(RHS->getContext()); 2391221345Sdim } 2392199481Srdivacky } 2393218893Sdim 2394296417Sdim // If both operands have range metadata, use the metadata 2395296417Sdim // to simplify the comparison. 2396296417Sdim if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) { 2397296417Sdim auto RHS_Instr = dyn_cast<Instruction>(RHS); 2398296417Sdim auto LHS_Instr = dyn_cast<Instruction>(LHS); 2399296417Sdim 2400296417Sdim if (RHS_Instr->getMetadata(LLVMContext::MD_range) && 2401296417Sdim LHS_Instr->getMetadata(LLVMContext::MD_range)) { 2402296417Sdim auto RHS_CR = getConstantRangeFromMetadata( 2403296417Sdim *RHS_Instr->getMetadata(LLVMContext::MD_range)); 2404296417Sdim auto LHS_CR = getConstantRangeFromMetadata( 2405296417Sdim *LHS_Instr->getMetadata(LLVMContext::MD_range)); 2406296417Sdim 2407296417Sdim auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR); 2408296417Sdim if (Satisfied_CR.contains(LHS_CR)) 2409296417Sdim return ConstantInt::getTrue(RHS->getContext()); 2410296417Sdim 2411296417Sdim auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion( 2412296417Sdim CmpInst::getInversePredicate(Pred), RHS_CR); 2413296417Sdim if (InversedSatisfied_CR.contains(LHS_CR)) 2414296417Sdim return ConstantInt::getFalse(RHS->getContext()); 2415296417Sdim } 2416296417Sdim } 2417296417Sdim 2418218893Sdim // Compare of cast, for example (zext X) != 0 -> X != 0 2419218893Sdim if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 2420218893Sdim Instruction *LI = cast<CastInst>(LHS); 2421218893Sdim Value *SrcOp = LI->getOperand(0); 2422226633Sdim Type *SrcTy = SrcOp->getType(); 2423226633Sdim Type *DstTy = LI->getType(); 2424218893Sdim 2425218893Sdim // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 2426218893Sdim // if the integer type is the same size as the pointer type. 2427288943Sdim if (MaxRecurse && isa<PtrToIntInst>(LI) && 2428288943Sdim Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { 2429218893Sdim if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2430218893Sdim // Transfer the cast to the constant. 2431218893Sdim if (Value *V = SimplifyICmpInst(Pred, SrcOp, 2432218893Sdim ConstantExpr::getIntToPtr(RHSC, SrcTy), 2433234353Sdim Q, MaxRecurse-1)) 2434218893Sdim return V; 2435218893Sdim } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 2436218893Sdim if (RI->getOperand(0)->getType() == SrcTy) 2437218893Sdim // Compare without the cast. 2438218893Sdim if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2439234353Sdim Q, MaxRecurse-1)) 2440218893Sdim return V; 2441218893Sdim } 2442218893Sdim } 2443218893Sdim 2444218893Sdim if (isa<ZExtInst>(LHS)) { 2445218893Sdim // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 2446218893Sdim // same type. 2447218893Sdim if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 2448218893Sdim if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2449218893Sdim // Compare X and Y. Note that signed predicates become unsigned. 2450218893Sdim if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2451234353Sdim SrcOp, RI->getOperand(0), Q, 2452218893Sdim MaxRecurse-1)) 2453218893Sdim return V; 2454218893Sdim } 2455218893Sdim // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 2456218893Sdim // too. If not, then try to deduce the result of the comparison. 2457218893Sdim else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2458218893Sdim // Compute the constant that would happen if we truncated to SrcTy then 2459218893Sdim // reextended to DstTy. 2460218893Sdim Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2461218893Sdim Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 2462218893Sdim 2463218893Sdim // If the re-extended constant didn't change then this is effectively 2464218893Sdim // also a case of comparing two zero-extended values. 2465218893Sdim if (RExt == CI && MaxRecurse) 2466218893Sdim if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2467234353Sdim SrcOp, Trunc, Q, MaxRecurse-1)) 2468218893Sdim return V; 2469218893Sdim 2470218893Sdim // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 2471218893Sdim // there. Use this to work out the result of the comparison. 2472218893Sdim if (RExt != CI) { 2473218893Sdim switch (Pred) { 2474234353Sdim default: llvm_unreachable("Unknown ICmp predicate!"); 2475218893Sdim // LHS <u RHS. 2476218893Sdim case ICmpInst::ICMP_EQ: 2477218893Sdim case ICmpInst::ICMP_UGT: 2478218893Sdim case ICmpInst::ICMP_UGE: 2479218893Sdim return ConstantInt::getFalse(CI->getContext()); 2480218893Sdim 2481218893Sdim case ICmpInst::ICMP_NE: 2482218893Sdim case ICmpInst::ICMP_ULT: 2483218893Sdim case ICmpInst::ICMP_ULE: 2484218893Sdim return ConstantInt::getTrue(CI->getContext()); 2485218893Sdim 2486218893Sdim // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 2487218893Sdim // is non-negative then LHS <s RHS. 2488218893Sdim case ICmpInst::ICMP_SGT: 2489218893Sdim case ICmpInst::ICMP_SGE: 2490218893Sdim return CI->getValue().isNegative() ? 2491218893Sdim ConstantInt::getTrue(CI->getContext()) : 2492218893Sdim ConstantInt::getFalse(CI->getContext()); 2493218893Sdim 2494218893Sdim case ICmpInst::ICMP_SLT: 2495218893Sdim case ICmpInst::ICMP_SLE: 2496218893Sdim return CI->getValue().isNegative() ? 2497218893Sdim ConstantInt::getFalse(CI->getContext()) : 2498218893Sdim ConstantInt::getTrue(CI->getContext()); 2499218893Sdim } 2500218893Sdim } 2501218893Sdim } 2502218893Sdim } 2503218893Sdim 2504218893Sdim if (isa<SExtInst>(LHS)) { 2505218893Sdim // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 2506218893Sdim // same type. 2507218893Sdim if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 2508218893Sdim if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2509218893Sdim // Compare X and Y. Note that the predicate does not change. 2510218893Sdim if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2511234353Sdim Q, MaxRecurse-1)) 2512218893Sdim return V; 2513218893Sdim } 2514218893Sdim // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 2515218893Sdim // too. If not, then try to deduce the result of the comparison. 2516218893Sdim else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2517218893Sdim // Compute the constant that would happen if we truncated to SrcTy then 2518218893Sdim // reextended to DstTy. 2519218893Sdim Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2520218893Sdim Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 2521218893Sdim 2522218893Sdim // If the re-extended constant didn't change then this is effectively 2523218893Sdim // also a case of comparing two sign-extended values. 2524218893Sdim if (RExt == CI && MaxRecurse) 2525234353Sdim if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1)) 2526218893Sdim return V; 2527218893Sdim 2528218893Sdim // Otherwise the upper bits of LHS are all equal, while RHS has varying 2529218893Sdim // bits there. Use this to work out the result of the comparison. 2530218893Sdim if (RExt != CI) { 2531218893Sdim switch (Pred) { 2532234353Sdim default: llvm_unreachable("Unknown ICmp predicate!"); 2533218893Sdim case ICmpInst::ICMP_EQ: 2534218893Sdim return ConstantInt::getFalse(CI->getContext()); 2535218893Sdim case ICmpInst::ICMP_NE: 2536218893Sdim return ConstantInt::getTrue(CI->getContext()); 2537218893Sdim 2538218893Sdim // If RHS is non-negative then LHS <s RHS. If RHS is negative then 2539218893Sdim // LHS >s RHS. 2540218893Sdim case ICmpInst::ICMP_SGT: 2541218893Sdim case ICmpInst::ICMP_SGE: 2542218893Sdim return CI->getValue().isNegative() ? 2543218893Sdim ConstantInt::getTrue(CI->getContext()) : 2544218893Sdim ConstantInt::getFalse(CI->getContext()); 2545218893Sdim case ICmpInst::ICMP_SLT: 2546218893Sdim case ICmpInst::ICMP_SLE: 2547218893Sdim return CI->getValue().isNegative() ? 2548218893Sdim ConstantInt::getFalse(CI->getContext()) : 2549218893Sdim ConstantInt::getTrue(CI->getContext()); 2550218893Sdim 2551218893Sdim // If LHS is non-negative then LHS <u RHS. If LHS is negative then 2552218893Sdim // LHS >u RHS. 2553218893Sdim case ICmpInst::ICMP_UGT: 2554218893Sdim case ICmpInst::ICMP_UGE: 2555218893Sdim // Comparison is true iff the LHS <s 0. 2556218893Sdim if (MaxRecurse) 2557218893Sdim if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 2558218893Sdim Constant::getNullValue(SrcTy), 2559234353Sdim Q, MaxRecurse-1)) 2560218893Sdim return V; 2561218893Sdim break; 2562218893Sdim case ICmpInst::ICMP_ULT: 2563218893Sdim case ICmpInst::ICMP_ULE: 2564218893Sdim // Comparison is true iff the LHS >=s 0. 2565218893Sdim if (MaxRecurse) 2566218893Sdim if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 2567218893Sdim Constant::getNullValue(SrcTy), 2568234353Sdim Q, MaxRecurse-1)) 2569218893Sdim return V; 2570218893Sdim break; 2571218893Sdim } 2572218893Sdim } 2573218893Sdim } 2574218893Sdim } 2575218893Sdim } 2576218893Sdim 2577296417Sdim // icmp eq|ne X, Y -> false|true if X != Y 2578296417Sdim if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) && 2579296417Sdim isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) { 2580296417Sdim LLVMContext &Ctx = LHS->getType()->getContext(); 2581296417Sdim return Pred == ICmpInst::ICMP_NE ? 2582296417Sdim ConstantInt::getTrue(Ctx) : ConstantInt::getFalse(Ctx); 2583296417Sdim } 2584296417Sdim 2585218893Sdim // Special logic for binary operators. 2586218893Sdim BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 2587218893Sdim BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 2588218893Sdim if (MaxRecurse && (LBO || RBO)) { 2589218893Sdim // Analyze the case when either LHS or RHS is an add instruction. 2590276479Sdim Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 2591218893Sdim // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 2592218893Sdim bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 2593218893Sdim if (LBO && LBO->getOpcode() == Instruction::Add) { 2594218893Sdim A = LBO->getOperand(0); B = LBO->getOperand(1); 2595218893Sdim NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 2596218893Sdim (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 2597218893Sdim (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 2598218893Sdim } 2599218893Sdim if (RBO && RBO->getOpcode() == Instruction::Add) { 2600218893Sdim C = RBO->getOperand(0); D = RBO->getOperand(1); 2601218893Sdim NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 2602218893Sdim (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 2603218893Sdim (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 2604218893Sdim } 2605218893Sdim 2606218893Sdim // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 2607218893Sdim if ((A == RHS || B == RHS) && NoLHSWrapProblem) 2608218893Sdim if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 2609218893Sdim Constant::getNullValue(RHS->getType()), 2610234353Sdim Q, MaxRecurse-1)) 2611218893Sdim return V; 2612218893Sdim 2613218893Sdim // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 2614218893Sdim if ((C == LHS || D == LHS) && NoRHSWrapProblem) 2615218893Sdim if (Value *V = SimplifyICmpInst(Pred, 2616218893Sdim Constant::getNullValue(LHS->getType()), 2617234353Sdim C == LHS ? D : C, Q, MaxRecurse-1)) 2618218893Sdim return V; 2619218893Sdim 2620218893Sdim // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 2621218893Sdim if (A && C && (A == C || A == D || B == C || B == D) && 2622218893Sdim NoLHSWrapProblem && NoRHSWrapProblem) { 2623218893Sdim // Determine Y and Z in the form icmp (X+Y), (X+Z). 2624243830Sdim Value *Y, *Z; 2625243830Sdim if (A == C) { 2626243830Sdim // C + B == C + D -> B == D 2627243830Sdim Y = B; 2628243830Sdim Z = D; 2629243830Sdim } else if (A == D) { 2630243830Sdim // D + B == C + D -> B == C 2631243830Sdim Y = B; 2632243830Sdim Z = C; 2633243830Sdim } else if (B == C) { 2634243830Sdim // A + C == C + D -> A == D 2635243830Sdim Y = A; 2636243830Sdim Z = D; 2637243830Sdim } else { 2638243830Sdim assert(B == D); 2639243830Sdim // A + D == C + D -> A == C 2640243830Sdim Y = A; 2641243830Sdim Z = C; 2642243830Sdim } 2643234353Sdim if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1)) 2644218893Sdim return V; 2645218893Sdim } 2646218893Sdim } 2647218893Sdim 2648280031Sdim // icmp pred (or X, Y), X 2649280031Sdim if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)), 2650280031Sdim m_Or(m_Specific(RHS), m_Value())))) { 2651280031Sdim if (Pred == ICmpInst::ICMP_ULT) 2652280031Sdim return getFalse(ITy); 2653280031Sdim if (Pred == ICmpInst::ICMP_UGE) 2654280031Sdim return getTrue(ITy); 2655280031Sdim } 2656280031Sdim // icmp pred X, (or X, Y) 2657280031Sdim if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)), 2658280031Sdim m_Or(m_Specific(LHS), m_Value())))) { 2659280031Sdim if (Pred == ICmpInst::ICMP_ULE) 2660280031Sdim return getTrue(ITy); 2661280031Sdim if (Pred == ICmpInst::ICMP_UGT) 2662280031Sdim return getFalse(ITy); 2663280031Sdim } 2664280031Sdim 2665280031Sdim // icmp pred (and X, Y), X 2666280031Sdim if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)), 2667280031Sdim m_And(m_Specific(RHS), m_Value())))) { 2668280031Sdim if (Pred == ICmpInst::ICMP_UGT) 2669280031Sdim return getFalse(ITy); 2670280031Sdim if (Pred == ICmpInst::ICMP_ULE) 2671280031Sdim return getTrue(ITy); 2672280031Sdim } 2673280031Sdim // icmp pred X, (and X, Y) 2674280031Sdim if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)), 2675280031Sdim m_And(m_Specific(LHS), m_Value())))) { 2676280031Sdim if (Pred == ICmpInst::ICMP_UGE) 2677280031Sdim return getTrue(ITy); 2678280031Sdim if (Pred == ICmpInst::ICMP_ULT) 2679280031Sdim return getFalse(ITy); 2680280031Sdim } 2681280031Sdim 2682276479Sdim // 0 - (zext X) pred C 2683276479Sdim if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) { 2684276479Sdim if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 2685276479Sdim if (RHSC->getValue().isStrictlyPositive()) { 2686276479Sdim if (Pred == ICmpInst::ICMP_SLT) 2687276479Sdim return ConstantInt::getTrue(RHSC->getContext()); 2688276479Sdim if (Pred == ICmpInst::ICMP_SGE) 2689276479Sdim return ConstantInt::getFalse(RHSC->getContext()); 2690276479Sdim if (Pred == ICmpInst::ICMP_EQ) 2691276479Sdim return ConstantInt::getFalse(RHSC->getContext()); 2692276479Sdim if (Pred == ICmpInst::ICMP_NE) 2693276479Sdim return ConstantInt::getTrue(RHSC->getContext()); 2694276479Sdim } 2695276479Sdim if (RHSC->getValue().isNonNegative()) { 2696276479Sdim if (Pred == ICmpInst::ICMP_SLE) 2697276479Sdim return ConstantInt::getTrue(RHSC->getContext()); 2698276479Sdim if (Pred == ICmpInst::ICMP_SGT) 2699276479Sdim return ConstantInt::getFalse(RHSC->getContext()); 2700276479Sdim } 2701276479Sdim } 2702276479Sdim } 2703276479Sdim 2704261991Sdim // icmp pred (urem X, Y), Y 2705221345Sdim if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 2706221345Sdim bool KnownNonNegative, KnownNegative; 2707221345Sdim switch (Pred) { 2708221345Sdim default: 2709221345Sdim break; 2710221345Sdim case ICmpInst::ICMP_SGT: 2711221345Sdim case ICmpInst::ICMP_SGE: 2712280031Sdim ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2713280031Sdim Q.CxtI, Q.DT); 2714221345Sdim if (!KnownNonNegative) 2715221345Sdim break; 2716221345Sdim // fall-through 2717221345Sdim case ICmpInst::ICMP_EQ: 2718221345Sdim case ICmpInst::ICMP_UGT: 2719221345Sdim case ICmpInst::ICMP_UGE: 2720226633Sdim return getFalse(ITy); 2721221345Sdim case ICmpInst::ICMP_SLT: 2722221345Sdim case ICmpInst::ICMP_SLE: 2723280031Sdim ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2724280031Sdim Q.CxtI, Q.DT); 2725221345Sdim if (!KnownNonNegative) 2726221345Sdim break; 2727221345Sdim // fall-through 2728221345Sdim case ICmpInst::ICMP_NE: 2729221345Sdim case ICmpInst::ICMP_ULT: 2730221345Sdim case ICmpInst::ICMP_ULE: 2731226633Sdim return getTrue(ITy); 2732221345Sdim } 2733221345Sdim } 2734261991Sdim 2735261991Sdim // icmp pred X, (urem Y, X) 2736221345Sdim if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 2737221345Sdim bool KnownNonNegative, KnownNegative; 2738221345Sdim switch (Pred) { 2739221345Sdim default: 2740221345Sdim break; 2741221345Sdim case ICmpInst::ICMP_SGT: 2742221345Sdim case ICmpInst::ICMP_SGE: 2743280031Sdim ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2744280031Sdim Q.CxtI, Q.DT); 2745221345Sdim if (!KnownNonNegative) 2746221345Sdim break; 2747221345Sdim // fall-through 2748221345Sdim case ICmpInst::ICMP_NE: 2749221345Sdim case ICmpInst::ICMP_UGT: 2750221345Sdim case ICmpInst::ICMP_UGE: 2751226633Sdim return getTrue(ITy); 2752221345Sdim case ICmpInst::ICMP_SLT: 2753221345Sdim case ICmpInst::ICMP_SLE: 2754280031Sdim ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC, 2755280031Sdim Q.CxtI, Q.DT); 2756221345Sdim if (!KnownNonNegative) 2757221345Sdim break; 2758221345Sdim // fall-through 2759221345Sdim case ICmpInst::ICMP_EQ: 2760221345Sdim case ICmpInst::ICMP_ULT: 2761221345Sdim case ICmpInst::ICMP_ULE: 2762226633Sdim return getFalse(ITy); 2763221345Sdim } 2764221345Sdim } 2765221345Sdim 2766234353Sdim // x udiv y <=u x. 2767234353Sdim if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 2768234353Sdim // icmp pred (X /u Y), X 2769234353Sdim if (Pred == ICmpInst::ICMP_UGT) 2770234353Sdim return getFalse(ITy); 2771234353Sdim if (Pred == ICmpInst::ICMP_ULE) 2772234353Sdim return getTrue(ITy); 2773234353Sdim } 2774234353Sdim 2775280031Sdim // handle: 2776280031Sdim // CI2 << X == CI 2777280031Sdim // CI2 << X != CI 2778280031Sdim // 2779280031Sdim // where CI2 is a power of 2 and CI isn't 2780280031Sdim if (auto *CI = dyn_cast<ConstantInt>(RHS)) { 2781280031Sdim const APInt *CI2Val, *CIVal = &CI->getValue(); 2782280031Sdim if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) && 2783280031Sdim CI2Val->isPowerOf2()) { 2784280031Sdim if (!CIVal->isPowerOf2()) { 2785280031Sdim // CI2 << X can equal zero in some circumstances, 2786280031Sdim // this simplification is unsafe if CI is zero. 2787280031Sdim // 2788280031Sdim // We know it is safe if: 2789280031Sdim // - The shift is nsw, we can't shift out the one bit. 2790280031Sdim // - The shift is nuw, we can't shift out the one bit. 2791280031Sdim // - CI2 is one 2792280031Sdim // - CI isn't zero 2793280031Sdim if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() || 2794280031Sdim *CI2Val == 1 || !CI->isZero()) { 2795280031Sdim if (Pred == ICmpInst::ICMP_EQ) 2796280031Sdim return ConstantInt::getFalse(RHS->getContext()); 2797280031Sdim if (Pred == ICmpInst::ICMP_NE) 2798280031Sdim return ConstantInt::getTrue(RHS->getContext()); 2799280031Sdim } 2800280031Sdim } 2801280031Sdim if (CIVal->isSignBit() && *CI2Val == 1) { 2802280031Sdim if (Pred == ICmpInst::ICMP_UGT) 2803280031Sdim return ConstantInt::getFalse(RHS->getContext()); 2804280031Sdim if (Pred == ICmpInst::ICMP_ULE) 2805280031Sdim return ConstantInt::getTrue(RHS->getContext()); 2806280031Sdim } 2807280031Sdim } 2808280031Sdim } 2809280031Sdim 2810221345Sdim if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 2811221345Sdim LBO->getOperand(1) == RBO->getOperand(1)) { 2812221345Sdim switch (LBO->getOpcode()) { 2813221345Sdim default: break; 2814221345Sdim case Instruction::UDiv: 2815221345Sdim case Instruction::LShr: 2816221345Sdim if (ICmpInst::isSigned(Pred)) 2817221345Sdim break; 2818221345Sdim // fall-through 2819221345Sdim case Instruction::SDiv: 2820221345Sdim case Instruction::AShr: 2821223017Sdim if (!LBO->isExact() || !RBO->isExact()) 2822221345Sdim break; 2823221345Sdim if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2824234353Sdim RBO->getOperand(0), Q, MaxRecurse-1)) 2825221345Sdim return V; 2826221345Sdim break; 2827221345Sdim case Instruction::Shl: { 2828226633Sdim bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2829221345Sdim bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2830221345Sdim if (!NUW && !NSW) 2831221345Sdim break; 2832221345Sdim if (!NSW && ICmpInst::isSigned(Pred)) 2833221345Sdim break; 2834221345Sdim if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2835234353Sdim RBO->getOperand(0), Q, MaxRecurse-1)) 2836221345Sdim return V; 2837221345Sdim break; 2838221345Sdim } 2839221345Sdim } 2840221345Sdim } 2841221345Sdim 2842223017Sdim // Simplify comparisons involving max/min. 2843223017Sdim Value *A, *B; 2844223017Sdim CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2845223017Sdim CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2846223017Sdim 2847223017Sdim // Signed variants on "max(a,b)>=a -> true". 2848223017Sdim if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2849223017Sdim if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2850223017Sdim EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2851223017Sdim // We analyze this as smax(A, B) pred A. 2852223017Sdim P = Pred; 2853223017Sdim } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2854223017Sdim (A == LHS || B == LHS)) { 2855223017Sdim if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2856223017Sdim EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2857223017Sdim // We analyze this as smax(A, B) swapped-pred A. 2858223017Sdim P = CmpInst::getSwappedPredicate(Pred); 2859223017Sdim } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2860223017Sdim (A == RHS || B == RHS)) { 2861223017Sdim if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2862223017Sdim EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2863223017Sdim // We analyze this as smax(-A, -B) swapped-pred -A. 2864223017Sdim // Note that we do not need to actually form -A or -B thanks to EqP. 2865223017Sdim P = CmpInst::getSwappedPredicate(Pred); 2866223017Sdim } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2867223017Sdim (A == LHS || B == LHS)) { 2868223017Sdim if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2869223017Sdim EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2870223017Sdim // We analyze this as smax(-A, -B) pred -A. 2871223017Sdim // Note that we do not need to actually form -A or -B thanks to EqP. 2872223017Sdim P = Pred; 2873223017Sdim } 2874223017Sdim if (P != CmpInst::BAD_ICMP_PREDICATE) { 2875223017Sdim // Cases correspond to "max(A, B) p A". 2876223017Sdim switch (P) { 2877223017Sdim default: 2878223017Sdim break; 2879223017Sdim case CmpInst::ICMP_EQ: 2880223017Sdim case CmpInst::ICMP_SLE: 2881223017Sdim // Equivalent to "A EqP B". This may be the same as the condition tested 2882223017Sdim // in the max/min; if so, we can just return that. 2883223017Sdim if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2884223017Sdim return V; 2885223017Sdim if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2886223017Sdim return V; 2887223017Sdim // Otherwise, see if "A EqP B" simplifies. 2888223017Sdim if (MaxRecurse) 2889234353Sdim if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2890223017Sdim return V; 2891223017Sdim break; 2892223017Sdim case CmpInst::ICMP_NE: 2893223017Sdim case CmpInst::ICMP_SGT: { 2894223017Sdim CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2895223017Sdim // Equivalent to "A InvEqP B". This may be the same as the condition 2896223017Sdim // tested in the max/min; if so, we can just return that. 2897223017Sdim if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2898223017Sdim return V; 2899223017Sdim if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2900223017Sdim return V; 2901223017Sdim // Otherwise, see if "A InvEqP B" simplifies. 2902223017Sdim if (MaxRecurse) 2903234353Sdim if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2904223017Sdim return V; 2905223017Sdim break; 2906223017Sdim } 2907223017Sdim case CmpInst::ICMP_SGE: 2908223017Sdim // Always true. 2909226633Sdim return getTrue(ITy); 2910223017Sdim case CmpInst::ICMP_SLT: 2911223017Sdim // Always false. 2912226633Sdim return getFalse(ITy); 2913223017Sdim } 2914223017Sdim } 2915223017Sdim 2916223017Sdim // Unsigned variants on "max(a,b)>=a -> true". 2917223017Sdim P = CmpInst::BAD_ICMP_PREDICATE; 2918223017Sdim if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2919223017Sdim if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2920223017Sdim EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2921223017Sdim // We analyze this as umax(A, B) pred A. 2922223017Sdim P = Pred; 2923223017Sdim } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2924223017Sdim (A == LHS || B == LHS)) { 2925223017Sdim if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2926223017Sdim EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2927223017Sdim // We analyze this as umax(A, B) swapped-pred A. 2928223017Sdim P = CmpInst::getSwappedPredicate(Pred); 2929223017Sdim } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2930223017Sdim (A == RHS || B == RHS)) { 2931223017Sdim if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2932223017Sdim EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2933223017Sdim // We analyze this as umax(-A, -B) swapped-pred -A. 2934223017Sdim // Note that we do not need to actually form -A or -B thanks to EqP. 2935223017Sdim P = CmpInst::getSwappedPredicate(Pred); 2936223017Sdim } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2937223017Sdim (A == LHS || B == LHS)) { 2938223017Sdim if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2939223017Sdim EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2940223017Sdim // We analyze this as umax(-A, -B) pred -A. 2941223017Sdim // Note that we do not need to actually form -A or -B thanks to EqP. 2942223017Sdim P = Pred; 2943223017Sdim } 2944223017Sdim if (P != CmpInst::BAD_ICMP_PREDICATE) { 2945223017Sdim // Cases correspond to "max(A, B) p A". 2946223017Sdim switch (P) { 2947223017Sdim default: 2948223017Sdim break; 2949223017Sdim case CmpInst::ICMP_EQ: 2950223017Sdim case CmpInst::ICMP_ULE: 2951223017Sdim // Equivalent to "A EqP B". This may be the same as the condition tested 2952223017Sdim // in the max/min; if so, we can just return that. 2953223017Sdim if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2954223017Sdim return V; 2955223017Sdim if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2956223017Sdim return V; 2957223017Sdim // Otherwise, see if "A EqP B" simplifies. 2958223017Sdim if (MaxRecurse) 2959234353Sdim if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2960223017Sdim return V; 2961223017Sdim break; 2962223017Sdim case CmpInst::ICMP_NE: 2963223017Sdim case CmpInst::ICMP_UGT: { 2964223017Sdim CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2965223017Sdim // Equivalent to "A InvEqP B". This may be the same as the condition 2966223017Sdim // tested in the max/min; if so, we can just return that. 2967223017Sdim if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2968223017Sdim return V; 2969223017Sdim if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2970223017Sdim return V; 2971223017Sdim // Otherwise, see if "A InvEqP B" simplifies. 2972223017Sdim if (MaxRecurse) 2973234353Sdim if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2974223017Sdim return V; 2975223017Sdim break; 2976223017Sdim } 2977223017Sdim case CmpInst::ICMP_UGE: 2978223017Sdim // Always true. 2979226633Sdim return getTrue(ITy); 2980223017Sdim case CmpInst::ICMP_ULT: 2981223017Sdim // Always false. 2982226633Sdim return getFalse(ITy); 2983223017Sdim } 2984223017Sdim } 2985223017Sdim 2986223017Sdim // Variants on "max(x,y) >= min(x,z)". 2987223017Sdim Value *C, *D; 2988223017Sdim if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2989223017Sdim match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2990223017Sdim (A == C || A == D || B == C || B == D)) { 2991223017Sdim // max(x, ?) pred min(x, ?). 2992223017Sdim if (Pred == CmpInst::ICMP_SGE) 2993223017Sdim // Always true. 2994226633Sdim return getTrue(ITy); 2995223017Sdim if (Pred == CmpInst::ICMP_SLT) 2996223017Sdim // Always false. 2997226633Sdim return getFalse(ITy); 2998223017Sdim } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2999223017Sdim match(RHS, m_SMax(m_Value(C), m_Value(D))) && 3000223017Sdim (A == C || A == D || B == C || B == D)) { 3001223017Sdim // min(x, ?) pred max(x, ?). 3002223017Sdim if (Pred == CmpInst::ICMP_SLE) 3003223017Sdim // Always true. 3004226633Sdim return getTrue(ITy); 3005223017Sdim if (Pred == CmpInst::ICMP_SGT) 3006223017Sdim // Always false. 3007226633Sdim return getFalse(ITy); 3008223017Sdim } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 3009223017Sdim match(RHS, m_UMin(m_Value(C), m_Value(D))) && 3010223017Sdim (A == C || A == D || B == C || B == D)) { 3011223017Sdim // max(x, ?) pred min(x, ?). 3012223017Sdim if (Pred == CmpInst::ICMP_UGE) 3013223017Sdim // Always true. 3014226633Sdim return getTrue(ITy); 3015223017Sdim if (Pred == CmpInst::ICMP_ULT) 3016223017Sdim // Always false. 3017226633Sdim return getFalse(ITy); 3018223017Sdim } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 3019223017Sdim match(RHS, m_UMax(m_Value(C), m_Value(D))) && 3020223017Sdim (A == C || A == D || B == C || B == D)) { 3021223017Sdim // min(x, ?) pred max(x, ?). 3022223017Sdim if (Pred == CmpInst::ICMP_ULE) 3023223017Sdim // Always true. 3024226633Sdim return getTrue(ITy); 3025223017Sdim if (Pred == CmpInst::ICMP_UGT) 3026223017Sdim // Always false. 3027226633Sdim return getFalse(ITy); 3028223017Sdim } 3029223017Sdim 3030234353Sdim // Simplify comparisons of related pointers using a powerful, recursive 3031234353Sdim // GEP-walk when we have target data available.. 3032249423Sdim if (LHS->getType()->isPointerTy()) 3033276479Sdim if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS)) 3034234353Sdim return C; 3035234353Sdim 3036234353Sdim if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) { 3037234353Sdim if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) { 3038234353Sdim if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && 3039234353Sdim GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() && 3040234353Sdim (ICmpInst::isEquality(Pred) || 3041234353Sdim (GLHS->isInBounds() && GRHS->isInBounds() && 3042234353Sdim Pred == ICmpInst::getSignedPredicate(Pred)))) { 3043234353Sdim // The bases are equal and the indices are constant. Build a constant 3044234353Sdim // expression GEP with the same indices and a null base pointer to see 3045234353Sdim // what constant folding can make out of it. 3046234353Sdim Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); 3047234353Sdim SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); 3048288943Sdim Constant *NewLHS = ConstantExpr::getGetElementPtr( 3049288943Sdim GLHS->getSourceElementType(), Null, IndicesLHS); 3050234353Sdim 3051234353Sdim SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); 3052288943Sdim Constant *NewRHS = ConstantExpr::getGetElementPtr( 3053288943Sdim GLHS->getSourceElementType(), Null, IndicesRHS); 3054234353Sdim return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); 3055234353Sdim } 3056234353Sdim } 3057234353Sdim } 3058234353Sdim 3059280031Sdim // If a bit is known to be zero for A and known to be one for B, 3060280031Sdim // then A and B cannot be equal. 3061280031Sdim if (ICmpInst::isEquality(Pred)) { 3062280031Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 3063280031Sdim uint32_t BitWidth = CI->getBitWidth(); 3064280031Sdim APInt LHSKnownZero(BitWidth, 0); 3065280031Sdim APInt LHSKnownOne(BitWidth, 0); 3066280031Sdim computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC, 3067280031Sdim Q.CxtI, Q.DT); 3068280031Sdim const APInt &RHSVal = CI->getValue(); 3069280031Sdim if (((LHSKnownZero & RHSVal) != 0) || ((LHSKnownOne & ~RHSVal) != 0)) 3070280031Sdim return Pred == ICmpInst::ICMP_EQ 3071280031Sdim ? ConstantInt::getFalse(CI->getContext()) 3072280031Sdim : ConstantInt::getTrue(CI->getContext()); 3073280031Sdim } 3074280031Sdim } 3075280031Sdim 3076218893Sdim // If the comparison is with the result of a select instruction, check whether 3077218893Sdim // comparing with either branch of the select always yields the same value. 3078218893Sdim if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3079234353Sdim if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 3080218893Sdim return V; 3081218893Sdim 3082218893Sdim // If the comparison is with the result of a phi instruction, check whether 3083218893Sdim // doing the compare with each incoming phi value yields a common result. 3084218893Sdim if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3085234353Sdim if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3086218893Sdim return V; 3087218893Sdim 3088276479Sdim return nullptr; 3089199481Srdivacky} 3090199481Srdivacky 3091218893SdimValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3092288943Sdim const DataLayout &DL, 3093234353Sdim const TargetLibraryInfo *TLI, 3094280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3095296417Sdim const Instruction *CxtI) { 3096280031Sdim return ::SimplifyICmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3097234353Sdim RecursionLimit); 3098218893Sdim} 3099218893Sdim 3100296417Sdim/// Given operands for an FCmpInst, see if we can fold the result. 3101296417Sdim/// If not, this returns null. 3102218893Sdimstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3103288943Sdim FastMathFlags FMF, const Query &Q, 3104288943Sdim unsigned MaxRecurse) { 3105199481Srdivacky CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 3106199481Srdivacky assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 3107199481Srdivacky 3108199481Srdivacky if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 3109199481Srdivacky if (Constant *CRHS = dyn_cast<Constant>(RHS)) 3110276479Sdim return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 3111218893Sdim 3112199481Srdivacky // If we have a constant, make sure it is on the RHS. 3113199481Srdivacky std::swap(LHS, RHS); 3114199481Srdivacky Pred = CmpInst::getSwappedPredicate(Pred); 3115199481Srdivacky } 3116218893Sdim 3117199481Srdivacky // Fold trivial predicates. 3118199481Srdivacky if (Pred == FCmpInst::FCMP_FALSE) 3119199481Srdivacky return ConstantInt::get(GetCompareTy(LHS), 0); 3120199481Srdivacky if (Pred == FCmpInst::FCMP_TRUE) 3121199481Srdivacky return ConstantInt::get(GetCompareTy(LHS), 1); 3122199481Srdivacky 3123288943Sdim // UNO/ORD predicates can be trivially folded if NaNs are ignored. 3124288943Sdim if (FMF.noNaNs()) { 3125288943Sdim if (Pred == FCmpInst::FCMP_UNO) 3126288943Sdim return ConstantInt::get(GetCompareTy(LHS), 0); 3127288943Sdim if (Pred == FCmpInst::FCMP_ORD) 3128288943Sdim return ConstantInt::get(GetCompareTy(LHS), 1); 3129288943Sdim } 3130199481Srdivacky 3131288943Sdim // fcmp pred x, undef and fcmp pred undef, x 3132288943Sdim // fold to true if unordered, false if ordered 3133288943Sdim if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) { 3134288943Sdim // Choosing NaN for the undef will always make unordered comparison succeed 3135288943Sdim // and ordered comparison fail. 3136288943Sdim return ConstantInt::get(GetCompareTy(LHS), CmpInst::isUnordered(Pred)); 3137288943Sdim } 3138288943Sdim 3139199481Srdivacky // fcmp x,x -> true/false. Not all compares are foldable. 3140199481Srdivacky if (LHS == RHS) { 3141199481Srdivacky if (CmpInst::isTrueWhenEqual(Pred)) 3142199481Srdivacky return ConstantInt::get(GetCompareTy(LHS), 1); 3143199481Srdivacky if (CmpInst::isFalseWhenEqual(Pred)) 3144199481Srdivacky return ConstantInt::get(GetCompareTy(LHS), 0); 3145199481Srdivacky } 3146218893Sdim 3147199481Srdivacky // Handle fcmp with constant RHS 3148288943Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 3149199481Srdivacky // If the constant is a nan, see if we can fold the comparison based on it. 3150288943Sdim if (CFP->getValueAPF().isNaN()) { 3151288943Sdim if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 3152288943Sdim return ConstantInt::getFalse(CFP->getContext()); 3153288943Sdim assert(FCmpInst::isUnordered(Pred) && 3154288943Sdim "Comparison must be either ordered or unordered!"); 3155288943Sdim // True if unordered. 3156288943Sdim return ConstantInt::getTrue(CFP->getContext()); 3157288943Sdim } 3158288943Sdim // Check whether the constant is an infinity. 3159288943Sdim if (CFP->getValueAPF().isInfinity()) { 3160288943Sdim if (CFP->getValueAPF().isNegative()) { 3161288943Sdim switch (Pred) { 3162288943Sdim case FCmpInst::FCMP_OLT: 3163288943Sdim // No value is ordered and less than negative infinity. 3164199481Srdivacky return ConstantInt::getFalse(CFP->getContext()); 3165288943Sdim case FCmpInst::FCMP_UGE: 3166288943Sdim // All values are unordered with or at least negative infinity. 3167288943Sdim return ConstantInt::getTrue(CFP->getContext()); 3168288943Sdim default: 3169288943Sdim break; 3170204642Srdivacky } 3171288943Sdim } else { 3172288943Sdim switch (Pred) { 3173288943Sdim case FCmpInst::FCMP_OGT: 3174288943Sdim // No value is ordered and greater than infinity. 3175288943Sdim return ConstantInt::getFalse(CFP->getContext()); 3176288943Sdim case FCmpInst::FCMP_ULE: 3177288943Sdim // All values are unordered with and at most infinity. 3178288943Sdim return ConstantInt::getTrue(CFP->getContext()); 3179288943Sdim default: 3180288943Sdim break; 3181288943Sdim } 3182204642Srdivacky } 3183199481Srdivacky } 3184288943Sdim if (CFP->getValueAPF().isZero()) { 3185288943Sdim switch (Pred) { 3186288943Sdim case FCmpInst::FCMP_UGE: 3187288943Sdim if (CannotBeOrderedLessThanZero(LHS)) 3188288943Sdim return ConstantInt::getTrue(CFP->getContext()); 3189288943Sdim break; 3190288943Sdim case FCmpInst::FCMP_OLT: 3191288943Sdim // X < 0 3192288943Sdim if (CannotBeOrderedLessThanZero(LHS)) 3193288943Sdim return ConstantInt::getFalse(CFP->getContext()); 3194288943Sdim break; 3195288943Sdim default: 3196288943Sdim break; 3197288943Sdim } 3198288943Sdim } 3199199481Srdivacky } 3200218893Sdim 3201218893Sdim // If the comparison is with the result of a select instruction, check whether 3202218893Sdim // comparing with either branch of the select always yields the same value. 3203218893Sdim if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3204234353Sdim if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 3205218893Sdim return V; 3206218893Sdim 3207218893Sdim // If the comparison is with the result of a phi instruction, check whether 3208218893Sdim // doing the compare with each incoming phi value yields a common result. 3209218893Sdim if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3210234353Sdim if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 3211218893Sdim return V; 3212218893Sdim 3213276479Sdim return nullptr; 3214199481Srdivacky} 3215199481Srdivacky 3216218893SdimValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3217288943Sdim FastMathFlags FMF, const DataLayout &DL, 3218234353Sdim const TargetLibraryInfo *TLI, 3219280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3220280031Sdim const Instruction *CxtI) { 3221288943Sdim return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, 3222288943Sdim Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3223218893Sdim} 3224218893Sdim 3225296417Sdim/// See if V simplifies when its operand Op is replaced with RepOp. 3226288943Sdimstatic const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, 3227288943Sdim const Query &Q, 3228288943Sdim unsigned MaxRecurse) { 3229288943Sdim // Trivial replacement. 3230288943Sdim if (V == Op) 3231288943Sdim return RepOp; 3232288943Sdim 3233288943Sdim auto *I = dyn_cast<Instruction>(V); 3234288943Sdim if (!I) 3235288943Sdim return nullptr; 3236288943Sdim 3237288943Sdim // If this is a binary operator, try to simplify it with the replaced op. 3238288943Sdim if (auto *B = dyn_cast<BinaryOperator>(I)) { 3239288943Sdim // Consider: 3240288943Sdim // %cmp = icmp eq i32 %x, 2147483647 3241288943Sdim // %add = add nsw i32 %x, 1 3242288943Sdim // %sel = select i1 %cmp, i32 -2147483648, i32 %add 3243288943Sdim // 3244288943Sdim // We can't replace %sel with %add unless we strip away the flags. 3245288943Sdim if (isa<OverflowingBinaryOperator>(B)) 3246288943Sdim if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap()) 3247288943Sdim return nullptr; 3248288943Sdim if (isa<PossiblyExactOperator>(B)) 3249288943Sdim if (B->isExact()) 3250288943Sdim return nullptr; 3251288943Sdim 3252288943Sdim if (MaxRecurse) { 3253288943Sdim if (B->getOperand(0) == Op) 3254288943Sdim return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q, 3255288943Sdim MaxRecurse - 1); 3256288943Sdim if (B->getOperand(1) == Op) 3257288943Sdim return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q, 3258288943Sdim MaxRecurse - 1); 3259288943Sdim } 3260288943Sdim } 3261288943Sdim 3262288943Sdim // Same for CmpInsts. 3263288943Sdim if (CmpInst *C = dyn_cast<CmpInst>(I)) { 3264288943Sdim if (MaxRecurse) { 3265288943Sdim if (C->getOperand(0) == Op) 3266288943Sdim return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q, 3267288943Sdim MaxRecurse - 1); 3268288943Sdim if (C->getOperand(1) == Op) 3269288943Sdim return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q, 3270288943Sdim MaxRecurse - 1); 3271288943Sdim } 3272288943Sdim } 3273288943Sdim 3274288943Sdim // TODO: We could hand off more cases to instsimplify here. 3275288943Sdim 3276288943Sdim // If all operands are constant after substituting Op for RepOp then we can 3277288943Sdim // constant fold the instruction. 3278288943Sdim if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) { 3279288943Sdim // Build a list of all constant operands. 3280288943Sdim SmallVector<Constant *, 8> ConstOps; 3281288943Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 3282288943Sdim if (I->getOperand(i) == Op) 3283288943Sdim ConstOps.push_back(CRepOp); 3284288943Sdim else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i))) 3285288943Sdim ConstOps.push_back(COp); 3286288943Sdim else 3287288943Sdim break; 3288288943Sdim } 3289288943Sdim 3290288943Sdim // All operands were constants, fold it. 3291288943Sdim if (ConstOps.size() == I->getNumOperands()) { 3292288943Sdim if (CmpInst *C = dyn_cast<CmpInst>(I)) 3293288943Sdim return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0], 3294288943Sdim ConstOps[1], Q.DL, Q.TLI); 3295288943Sdim 3296288943Sdim if (LoadInst *LI = dyn_cast<LoadInst>(I)) 3297288943Sdim if (!LI->isVolatile()) 3298288943Sdim return ConstantFoldLoadFromConstPtr(ConstOps[0], Q.DL); 3299288943Sdim 3300288943Sdim return ConstantFoldInstOperands(I->getOpcode(), I->getType(), ConstOps, 3301288943Sdim Q.DL, Q.TLI); 3302288943Sdim } 3303288943Sdim } 3304288943Sdim 3305288943Sdim return nullptr; 3306288943Sdim} 3307288943Sdim 3308296417Sdim/// Given operands for a SelectInst, see if we can fold the result. 3309296417Sdim/// If not, this returns null. 3310234353Sdimstatic Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, 3311234353Sdim Value *FalseVal, const Query &Q, 3312234353Sdim unsigned MaxRecurse) { 3313207618Srdivacky // select true, X, Y -> X 3314207618Srdivacky // select false, X, Y -> Y 3315276479Sdim if (Constant *CB = dyn_cast<Constant>(CondVal)) { 3316276479Sdim if (CB->isAllOnesValue()) 3317276479Sdim return TrueVal; 3318276479Sdim if (CB->isNullValue()) 3319276479Sdim return FalseVal; 3320276479Sdim } 3321218893Sdim 3322207618Srdivacky // select C, X, X -> X 3323207618Srdivacky if (TrueVal == FalseVal) 3324207618Srdivacky return TrueVal; 3325218893Sdim 3326207618Srdivacky if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 3327207618Srdivacky if (isa<Constant>(TrueVal)) 3328207618Srdivacky return TrueVal; 3329207618Srdivacky return FalseVal; 3330207618Srdivacky } 3331224145Sdim if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 3332224145Sdim return FalseVal; 3333224145Sdim if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 3334224145Sdim return TrueVal; 3335218893Sdim 3336288943Sdim if (const auto *ICI = dyn_cast<ICmpInst>(CondVal)) { 3337288943Sdim unsigned BitWidth = Q.DL.getTypeSizeInBits(TrueVal->getType()); 3338280031Sdim ICmpInst::Predicate Pred = ICI->getPredicate(); 3339288943Sdim Value *CmpLHS = ICI->getOperand(0); 3340288943Sdim Value *CmpRHS = ICI->getOperand(1); 3341280031Sdim APInt MinSignedValue = APInt::getSignBit(BitWidth); 3342280031Sdim Value *X; 3343280031Sdim const APInt *Y; 3344280031Sdim bool TrueWhenUnset; 3345280031Sdim bool IsBitTest = false; 3346280031Sdim if (ICmpInst::isEquality(Pred) && 3347288943Sdim match(CmpLHS, m_And(m_Value(X), m_APInt(Y))) && 3348288943Sdim match(CmpRHS, m_Zero())) { 3349280031Sdim IsBitTest = true; 3350280031Sdim TrueWhenUnset = Pred == ICmpInst::ICMP_EQ; 3351288943Sdim } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) { 3352288943Sdim X = CmpLHS; 3353280031Sdim Y = &MinSignedValue; 3354280031Sdim IsBitTest = true; 3355280031Sdim TrueWhenUnset = false; 3356288943Sdim } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) { 3357288943Sdim X = CmpLHS; 3358280031Sdim Y = &MinSignedValue; 3359280031Sdim IsBitTest = true; 3360280031Sdim TrueWhenUnset = true; 3361280031Sdim } 3362280031Sdim if (IsBitTest) { 3363280031Sdim const APInt *C; 3364280031Sdim // (X & Y) == 0 ? X & ~Y : X --> X 3365280031Sdim // (X & Y) != 0 ? X & ~Y : X --> X & ~Y 3366280031Sdim if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) && 3367280031Sdim *Y == ~*C) 3368280031Sdim return TrueWhenUnset ? FalseVal : TrueVal; 3369280031Sdim // (X & Y) == 0 ? X : X & ~Y --> X & ~Y 3370280031Sdim // (X & Y) != 0 ? X : X & ~Y --> X 3371280031Sdim if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) && 3372280031Sdim *Y == ~*C) 3373280031Sdim return TrueWhenUnset ? FalseVal : TrueVal; 3374280031Sdim 3375280031Sdim if (Y->isPowerOf2()) { 3376280031Sdim // (X & Y) == 0 ? X | Y : X --> X | Y 3377280031Sdim // (X & Y) != 0 ? X | Y : X --> X 3378280031Sdim if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) && 3379280031Sdim *Y == *C) 3380280031Sdim return TrueWhenUnset ? TrueVal : FalseVal; 3381280031Sdim // (X & Y) == 0 ? X : X | Y --> X 3382280031Sdim // (X & Y) != 0 ? X : X | Y --> X | Y 3383280031Sdim if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) && 3384280031Sdim *Y == *C) 3385280031Sdim return TrueWhenUnset ? TrueVal : FalseVal; 3386280031Sdim } 3387280031Sdim } 3388288943Sdim if (ICI->hasOneUse()) { 3389288943Sdim const APInt *C; 3390288943Sdim if (match(CmpRHS, m_APInt(C))) { 3391288943Sdim // X < MIN ? T : F --> F 3392288943Sdim if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue()) 3393288943Sdim return FalseVal; 3394288943Sdim // X < MIN ? T : F --> F 3395288943Sdim if (Pred == ICmpInst::ICMP_ULT && C->isMinValue()) 3396288943Sdim return FalseVal; 3397288943Sdim // X > MAX ? T : F --> F 3398288943Sdim if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue()) 3399288943Sdim return FalseVal; 3400288943Sdim // X > MAX ? T : F --> F 3401288943Sdim if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue()) 3402288943Sdim return FalseVal; 3403288943Sdim } 3404288943Sdim } 3405288943Sdim 3406288943Sdim // If we have an equality comparison then we know the value in one of the 3407288943Sdim // arms of the select. See if substituting this value into the arm and 3408288943Sdim // simplifying the result yields the same value as the other arm. 3409288943Sdim if (Pred == ICmpInst::ICMP_EQ) { 3410288943Sdim if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == 3411288943Sdim TrueVal || 3412288943Sdim SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == 3413288943Sdim TrueVal) 3414288943Sdim return FalseVal; 3415288943Sdim if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == 3416288943Sdim FalseVal || 3417288943Sdim SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == 3418288943Sdim FalseVal) 3419288943Sdim return FalseVal; 3420288943Sdim } else if (Pred == ICmpInst::ICMP_NE) { 3421288943Sdim if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == 3422288943Sdim FalseVal || 3423288943Sdim SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == 3424288943Sdim FalseVal) 3425288943Sdim return TrueVal; 3426288943Sdim if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == 3427288943Sdim TrueVal || 3428288943Sdim SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == 3429288943Sdim TrueVal) 3430288943Sdim return TrueVal; 3431288943Sdim } 3432280031Sdim } 3433280031Sdim 3434276479Sdim return nullptr; 3435207618Srdivacky} 3436207618Srdivacky 3437234353SdimValue *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 3438288943Sdim const DataLayout &DL, 3439234353Sdim const TargetLibraryInfo *TLI, 3440280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3441280031Sdim const Instruction *CxtI) { 3442280031Sdim return ::SimplifySelectInst(Cond, TrueVal, FalseVal, 3443280031Sdim Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3444234353Sdim} 3445234353Sdim 3446296417Sdim/// Given operands for an GetElementPtrInst, see if we can fold the result. 3447296417Sdim/// If not, this returns null. 3448288943Sdimstatic Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops, 3449288943Sdim const Query &Q, unsigned) { 3450218893Sdim // The type of the GEP pointer operand. 3451288943Sdim unsigned AS = 3452288943Sdim cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace(); 3453218893Sdim 3454199989Srdivacky // getelementptr P -> P. 3455226633Sdim if (Ops.size() == 1) 3456199989Srdivacky return Ops[0]; 3457199989Srdivacky 3458280031Sdim // Compute the (pointer) type returned by the GEP instruction. 3459288943Sdim Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1)); 3460280031Sdim Type *GEPTy = PointerType::get(LastType, AS); 3461280031Sdim if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType())) 3462280031Sdim GEPTy = VectorType::get(GEPTy, VT->getNumElements()); 3463280031Sdim 3464280031Sdim if (isa<UndefValue>(Ops[0])) 3465218893Sdim return UndefValue::get(GEPTy); 3466199989Srdivacky 3467226633Sdim if (Ops.size() == 2) { 3468218893Sdim // getelementptr P, 0 -> P. 3469276479Sdim if (match(Ops[1], m_Zero())) 3470276479Sdim return Ops[0]; 3471280031Sdim 3472288943Sdim Type *Ty = SrcTy; 3473288943Sdim if (Ty->isSized()) { 3474280031Sdim Value *P; 3475280031Sdim uint64_t C; 3476288943Sdim uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty); 3477280031Sdim // getelementptr P, N -> P if P points to a type of zero size. 3478280031Sdim if (TyAllocSize == 0) 3479218893Sdim return Ops[0]; 3480280031Sdim 3481280031Sdim // The following transforms are only safe if the ptrtoint cast 3482280031Sdim // doesn't truncate the pointers. 3483280031Sdim if (Ops[1]->getType()->getScalarSizeInBits() == 3484288943Sdim Q.DL.getPointerSizeInBits(AS)) { 3485280031Sdim auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { 3486280031Sdim if (match(P, m_Zero())) 3487280031Sdim return Constant::getNullValue(GEPTy); 3488280031Sdim Value *Temp; 3489280031Sdim if (match(P, m_PtrToInt(m_Value(Temp)))) 3490280031Sdim if (Temp->getType() == GEPTy) 3491280031Sdim return Temp; 3492280031Sdim return nullptr; 3493280031Sdim }; 3494280031Sdim 3495280031Sdim // getelementptr V, (sub P, V) -> P if P points to a type of size 1. 3496280031Sdim if (TyAllocSize == 1 && 3497280031Sdim match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))))) 3498280031Sdim if (Value *R = PtrToIntOrZero(P)) 3499280031Sdim return R; 3500280031Sdim 3501280031Sdim // getelementptr V, (ashr (sub P, V), C) -> Q 3502280031Sdim // if P points to a type of size 1 << C. 3503280031Sdim if (match(Ops[1], 3504280031Sdim m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3505280031Sdim m_ConstantInt(C))) && 3506280031Sdim TyAllocSize == 1ULL << C) 3507280031Sdim if (Value *R = PtrToIntOrZero(P)) 3508280031Sdim return R; 3509280031Sdim 3510280031Sdim // getelementptr V, (sdiv (sub P, V), C) -> Q 3511280031Sdim // if P points to a type of size C. 3512280031Sdim if (match(Ops[1], 3513280031Sdim m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), 3514280031Sdim m_SpecificInt(TyAllocSize)))) 3515280031Sdim if (Value *R = PtrToIntOrZero(P)) 3516280031Sdim return R; 3517280031Sdim } 3518218893Sdim } 3519218893Sdim } 3520218893Sdim 3521199989Srdivacky // Check to see if this is constant foldable. 3522226633Sdim for (unsigned i = 0, e = Ops.size(); i != e; ++i) 3523199989Srdivacky if (!isa<Constant>(Ops[i])) 3524276479Sdim return nullptr; 3525218893Sdim 3526288943Sdim return ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]), 3527288943Sdim Ops.slice(1)); 3528199989Srdivacky} 3529199989Srdivacky 3530288943SdimValue *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout &DL, 3531234353Sdim const TargetLibraryInfo *TLI, 3532280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3533280031Sdim const Instruction *CxtI) { 3534288943Sdim return ::SimplifyGEPInst( 3535288943Sdim cast<PointerType>(Ops[0]->getType()->getScalarType())->getElementType(), 3536288943Sdim Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3537234353Sdim} 3538234353Sdim 3539296417Sdim/// Given operands for an InsertValueInst, see if we can fold the result. 3540296417Sdim/// If not, this returns null. 3541234353Sdimstatic Value *SimplifyInsertValueInst(Value *Agg, Value *Val, 3542234353Sdim ArrayRef<unsigned> Idxs, const Query &Q, 3543234353Sdim unsigned) { 3544226633Sdim if (Constant *CAgg = dyn_cast<Constant>(Agg)) 3545226633Sdim if (Constant *CVal = dyn_cast<Constant>(Val)) 3546226633Sdim return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 3547226633Sdim 3548226633Sdim // insertvalue x, undef, n -> x 3549226633Sdim if (match(Val, m_Undef())) 3550226633Sdim return Agg; 3551226633Sdim 3552226633Sdim // insertvalue x, (extractvalue y, n), n 3553226633Sdim if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 3554226633Sdim if (EV->getAggregateOperand()->getType() == Agg->getType() && 3555226633Sdim EV->getIndices() == Idxs) { 3556226633Sdim // insertvalue undef, (extractvalue y, n), n -> y 3557226633Sdim if (match(Agg, m_Undef())) 3558226633Sdim return EV->getAggregateOperand(); 3559226633Sdim 3560226633Sdim // insertvalue y, (extractvalue y, n), n -> y 3561226633Sdim if (Agg == EV->getAggregateOperand()) 3562226633Sdim return Agg; 3563226633Sdim } 3564226633Sdim 3565276479Sdim return nullptr; 3566226633Sdim} 3567226633Sdim 3568280031SdimValue *llvm::SimplifyInsertValueInst( 3569288943Sdim Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL, 3570280031Sdim const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, 3571280031Sdim const Instruction *CxtI) { 3572280031Sdim return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI), 3573234353Sdim RecursionLimit); 3574234353Sdim} 3575234353Sdim 3576296417Sdim/// Given operands for an ExtractValueInst, see if we can fold the result. 3577296417Sdim/// If not, this returns null. 3578288943Sdimstatic Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs, 3579288943Sdim const Query &, unsigned) { 3580288943Sdim if (auto *CAgg = dyn_cast<Constant>(Agg)) 3581288943Sdim return ConstantFoldExtractValueInstruction(CAgg, Idxs); 3582288943Sdim 3583288943Sdim // extractvalue x, (insertvalue y, elt, n), n -> elt 3584288943Sdim unsigned NumIdxs = Idxs.size(); 3585288943Sdim for (auto *IVI = dyn_cast<InsertValueInst>(Agg); IVI != nullptr; 3586288943Sdim IVI = dyn_cast<InsertValueInst>(IVI->getAggregateOperand())) { 3587288943Sdim ArrayRef<unsigned> InsertValueIdxs = IVI->getIndices(); 3588288943Sdim unsigned NumInsertValueIdxs = InsertValueIdxs.size(); 3589288943Sdim unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs); 3590288943Sdim if (InsertValueIdxs.slice(0, NumCommonIdxs) == 3591288943Sdim Idxs.slice(0, NumCommonIdxs)) { 3592288943Sdim if (NumIdxs == NumInsertValueIdxs) 3593288943Sdim return IVI->getInsertedValueOperand(); 3594288943Sdim break; 3595288943Sdim } 3596288943Sdim } 3597288943Sdim 3598288943Sdim return nullptr; 3599288943Sdim} 3600288943Sdim 3601288943SdimValue *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs, 3602288943Sdim const DataLayout &DL, 3603288943Sdim const TargetLibraryInfo *TLI, 3604288943Sdim const DominatorTree *DT, 3605288943Sdim AssumptionCache *AC, 3606288943Sdim const Instruction *CxtI) { 3607288943Sdim return ::SimplifyExtractValueInst(Agg, Idxs, Query(DL, TLI, DT, AC, CxtI), 3608288943Sdim RecursionLimit); 3609288943Sdim} 3610288943Sdim 3611296417Sdim/// Given operands for an ExtractElementInst, see if we can fold the result. 3612296417Sdim/// If not, this returns null. 3613288943Sdimstatic Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const Query &, 3614288943Sdim unsigned) { 3615288943Sdim if (auto *CVec = dyn_cast<Constant>(Vec)) { 3616288943Sdim if (auto *CIdx = dyn_cast<Constant>(Idx)) 3617288943Sdim return ConstantFoldExtractElementInstruction(CVec, CIdx); 3618288943Sdim 3619288943Sdim // The index is not relevant if our vector is a splat. 3620288943Sdim if (auto *Splat = CVec->getSplatValue()) 3621288943Sdim return Splat; 3622288943Sdim 3623288943Sdim if (isa<UndefValue>(Vec)) 3624288943Sdim return UndefValue::get(Vec->getType()->getVectorElementType()); 3625288943Sdim } 3626288943Sdim 3627288943Sdim // If extracting a specified index from the vector, see if we can recursively 3628288943Sdim // find a previously computed scalar that was inserted into the vector. 3629288943Sdim if (auto *IdxC = dyn_cast<ConstantInt>(Idx)) 3630288943Sdim if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue())) 3631288943Sdim return Elt; 3632288943Sdim 3633288943Sdim return nullptr; 3634288943Sdim} 3635288943Sdim 3636288943SdimValue *llvm::SimplifyExtractElementInst( 3637288943Sdim Value *Vec, Value *Idx, const DataLayout &DL, const TargetLibraryInfo *TLI, 3638288943Sdim const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { 3639288943Sdim return ::SimplifyExtractElementInst(Vec, Idx, Query(DL, TLI, DT, AC, CxtI), 3640288943Sdim RecursionLimit); 3641288943Sdim} 3642288943Sdim 3643296417Sdim/// See if we can fold the given phi. If not, returns null. 3644234353Sdimstatic Value *SimplifyPHINode(PHINode *PN, const Query &Q) { 3645218893Sdim // If all of the PHI's incoming values are the same then replace the PHI node 3646218893Sdim // with the common value. 3647276479Sdim Value *CommonValue = nullptr; 3648218893Sdim bool HasUndefInput = false; 3649288943Sdim for (Value *Incoming : PN->incoming_values()) { 3650218893Sdim // If the incoming value is the phi node itself, it can safely be skipped. 3651218893Sdim if (Incoming == PN) continue; 3652218893Sdim if (isa<UndefValue>(Incoming)) { 3653218893Sdim // Remember that we saw an undef value, but otherwise ignore them. 3654218893Sdim HasUndefInput = true; 3655218893Sdim continue; 3656218893Sdim } 3657218893Sdim if (CommonValue && Incoming != CommonValue) 3658276479Sdim return nullptr; // Not the same, bail out. 3659218893Sdim CommonValue = Incoming; 3660218893Sdim } 3661199989Srdivacky 3662218893Sdim // If CommonValue is null then all of the incoming values were either undef or 3663218893Sdim // equal to the phi node itself. 3664218893Sdim if (!CommonValue) 3665218893Sdim return UndefValue::get(PN->getType()); 3666218893Sdim 3667218893Sdim // If we have a PHI node like phi(X, undef, X), where X is defined by some 3668218893Sdim // instruction, we cannot return X as the result of the PHI node unless it 3669218893Sdim // dominates the PHI block. 3670218893Sdim if (HasUndefInput) 3671276479Sdim return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr; 3672218893Sdim 3673218893Sdim return CommonValue; 3674218893Sdim} 3675218893Sdim 3676234353Sdimstatic Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { 3677234353Sdim if (Constant *C = dyn_cast<Constant>(Op)) 3678276479Sdim return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI); 3679218893Sdim 3680276479Sdim return nullptr; 3681234353Sdim} 3682234353Sdim 3683288943SdimValue *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout &DL, 3684234353Sdim const TargetLibraryInfo *TLI, 3685280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3686280031Sdim const Instruction *CxtI) { 3687280031Sdim return ::SimplifyTruncInst(Op, Ty, Query(DL, TLI, DT, AC, CxtI), 3688280031Sdim RecursionLimit); 3689234353Sdim} 3690234353Sdim 3691199481Srdivacky//=== Helper functions for higher up the class hierarchy. 3692199481Srdivacky 3693296417Sdim/// Given operands for a BinaryOperator, see if we can fold the result. 3694296417Sdim/// If not, this returns null. 3695218893Sdimstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3696234353Sdim const Query &Q, unsigned MaxRecurse) { 3697199481Srdivacky switch (Opcode) { 3698218893Sdim case Instruction::Add: 3699218893Sdim return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3700234353Sdim Q, MaxRecurse); 3701249423Sdim case Instruction::FAdd: 3702249423Sdim return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3703249423Sdim 3704218893Sdim case Instruction::Sub: 3705218893Sdim return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3706234353Sdim Q, MaxRecurse); 3707249423Sdim case Instruction::FSub: 3708249423Sdim return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3709249423Sdim 3710234353Sdim case Instruction::Mul: return SimplifyMulInst (LHS, RHS, Q, MaxRecurse); 3711249423Sdim case Instruction::FMul: 3712249423Sdim return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3713234353Sdim case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); 3714234353Sdim case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); 3715288943Sdim case Instruction::FDiv: 3716288943Sdim return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3717234353Sdim case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); 3718234353Sdim case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); 3719288943Sdim case Instruction::FRem: 3720288943Sdim return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3721218893Sdim case Instruction::Shl: 3722218893Sdim return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 3723234353Sdim Q, MaxRecurse); 3724218893Sdim case Instruction::LShr: 3725234353Sdim return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3726218893Sdim case Instruction::AShr: 3727234353Sdim return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 3728234353Sdim case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse); 3729234353Sdim case Instruction::Or: return SimplifyOrInst (LHS, RHS, Q, MaxRecurse); 3730234353Sdim case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse); 3731199481Srdivacky default: 3732199481Srdivacky if (Constant *CLHS = dyn_cast<Constant>(LHS)) 3733199481Srdivacky if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 3734199481Srdivacky Constant *COps[] = {CLHS, CRHS}; 3735276479Sdim return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL, 3736234353Sdim Q.TLI); 3737199481Srdivacky } 3738218893Sdim 3739218893Sdim // If the operation is associative, try some generic simplifications. 3740218893Sdim if (Instruction::isAssociative(Opcode)) 3741234353Sdim if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse)) 3742218893Sdim return V; 3743218893Sdim 3744234353Sdim // If the operation is with the result of a select instruction check whether 3745218893Sdim // operating on either branch of the select always yields the same value. 3746218893Sdim if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 3747234353Sdim if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse)) 3748218893Sdim return V; 3749218893Sdim 3750218893Sdim // If the operation is with the result of a phi instruction, check whether 3751218893Sdim // operating on all incoming values of the phi always yields the same value. 3752218893Sdim if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 3753234353Sdim if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse)) 3754218893Sdim return V; 3755218893Sdim 3756276479Sdim return nullptr; 3757199481Srdivacky } 3758199481Srdivacky} 3759199481Srdivacky 3760296417Sdim/// Given operands for a BinaryOperator, see if we can fold the result. 3761296417Sdim/// If not, this returns null. 3762288943Sdim/// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the 3763288943Sdim/// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp. 3764288943Sdimstatic Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3765288943Sdim const FastMathFlags &FMF, const Query &Q, 3766288943Sdim unsigned MaxRecurse) { 3767288943Sdim switch (Opcode) { 3768288943Sdim case Instruction::FAdd: 3769288943Sdim return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse); 3770288943Sdim case Instruction::FSub: 3771288943Sdim return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse); 3772288943Sdim case Instruction::FMul: 3773288943Sdim return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse); 3774288943Sdim default: 3775288943Sdim return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse); 3776288943Sdim } 3777288943Sdim} 3778288943Sdim 3779218893SdimValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3780288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 3781280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3782280031Sdim const Instruction *CxtI) { 3783280031Sdim return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3784280031Sdim RecursionLimit); 3785218893Sdim} 3786218893Sdim 3787288943SdimValue *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, 3788288943Sdim const FastMathFlags &FMF, const DataLayout &DL, 3789288943Sdim const TargetLibraryInfo *TLI, 3790288943Sdim const DominatorTree *DT, AssumptionCache *AC, 3791288943Sdim const Instruction *CxtI) { 3792288943Sdim return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Query(DL, TLI, DT, AC, CxtI), 3793288943Sdim RecursionLimit); 3794288943Sdim} 3795288943Sdim 3796296417Sdim/// Given operands for a CmpInst, see if we can fold the result. 3797218893Sdimstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3798234353Sdim const Query &Q, unsigned MaxRecurse) { 3799199481Srdivacky if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 3800234353Sdim return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 3801288943Sdim return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse); 3802199481Srdivacky} 3803199481Srdivacky 3804218893SdimValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 3805288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 3806280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3807280031Sdim const Instruction *CxtI) { 3808280031Sdim return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), 3809234353Sdim RecursionLimit); 3810218893Sdim} 3811199481Srdivacky 3812249423Sdimstatic bool IsIdempotent(Intrinsic::ID ID) { 3813249423Sdim switch (ID) { 3814249423Sdim default: return false; 3815234353Sdim 3816249423Sdim // Unary idempotent: f(f(x)) = f(x) 3817249423Sdim case Intrinsic::fabs: 3818249423Sdim case Intrinsic::floor: 3819249423Sdim case Intrinsic::ceil: 3820249423Sdim case Intrinsic::trunc: 3821249423Sdim case Intrinsic::rint: 3822249423Sdim case Intrinsic::nearbyint: 3823261991Sdim case Intrinsic::round: 3824249423Sdim return true; 3825249423Sdim } 3826249423Sdim} 3827249423Sdim 3828249423Sdimtemplate <typename IterTy> 3829288943Sdimstatic Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd, 3830249423Sdim const Query &Q, unsigned MaxRecurse) { 3831288943Sdim Intrinsic::ID IID = F->getIntrinsicID(); 3832288943Sdim unsigned NumOperands = std::distance(ArgBegin, ArgEnd); 3833288943Sdim Type *ReturnType = F->getReturnType(); 3834288943Sdim 3835288943Sdim // Binary Ops 3836288943Sdim if (NumOperands == 2) { 3837288943Sdim Value *LHS = *ArgBegin; 3838288943Sdim Value *RHS = *(ArgBegin + 1); 3839288943Sdim if (IID == Intrinsic::usub_with_overflow || 3840288943Sdim IID == Intrinsic::ssub_with_overflow) { 3841288943Sdim // X - X -> { 0, false } 3842288943Sdim if (LHS == RHS) 3843288943Sdim return Constant::getNullValue(ReturnType); 3844288943Sdim 3845288943Sdim // X - undef -> undef 3846288943Sdim // undef - X -> undef 3847288943Sdim if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) 3848288943Sdim return UndefValue::get(ReturnType); 3849288943Sdim } 3850288943Sdim 3851288943Sdim if (IID == Intrinsic::uadd_with_overflow || 3852288943Sdim IID == Intrinsic::sadd_with_overflow) { 3853288943Sdim // X + undef -> undef 3854288943Sdim if (isa<UndefValue>(RHS)) 3855288943Sdim return UndefValue::get(ReturnType); 3856288943Sdim } 3857288943Sdim 3858288943Sdim if (IID == Intrinsic::umul_with_overflow || 3859288943Sdim IID == Intrinsic::smul_with_overflow) { 3860288943Sdim // X * 0 -> { 0, false } 3861288943Sdim if (match(RHS, m_Zero())) 3862288943Sdim return Constant::getNullValue(ReturnType); 3863288943Sdim 3864288943Sdim // X * undef -> { 0, false } 3865288943Sdim if (match(RHS, m_Undef())) 3866288943Sdim return Constant::getNullValue(ReturnType); 3867288943Sdim } 3868288943Sdim } 3869288943Sdim 3870249423Sdim // Perform idempotent optimizations 3871249423Sdim if (!IsIdempotent(IID)) 3872276479Sdim return nullptr; 3873249423Sdim 3874249423Sdim // Unary Ops 3875288943Sdim if (NumOperands == 1) 3876249423Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) 3877249423Sdim if (II->getIntrinsicID() == IID) 3878249423Sdim return II; 3879249423Sdim 3880276479Sdim return nullptr; 3881234353Sdim} 3882234353Sdim 3883249423Sdimtemplate <typename IterTy> 3884249423Sdimstatic Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, 3885249423Sdim const Query &Q, unsigned MaxRecurse) { 3886249423Sdim Type *Ty = V->getType(); 3887249423Sdim if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 3888249423Sdim Ty = PTy->getElementType(); 3889249423Sdim FunctionType *FTy = cast<FunctionType>(Ty); 3890249423Sdim 3891249423Sdim // call undef -> undef 3892249423Sdim if (isa<UndefValue>(V)) 3893249423Sdim return UndefValue::get(FTy->getReturnType()); 3894249423Sdim 3895249423Sdim Function *F = dyn_cast<Function>(V); 3896249423Sdim if (!F) 3897276479Sdim return nullptr; 3898249423Sdim 3899288943Sdim if (F->isIntrinsic()) 3900288943Sdim if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse)) 3901249423Sdim return Ret; 3902249423Sdim 3903249423Sdim if (!canConstantFoldCallTo(F)) 3904276479Sdim return nullptr; 3905249423Sdim 3906249423Sdim SmallVector<Constant *, 4> ConstantArgs; 3907249423Sdim ConstantArgs.reserve(ArgEnd - ArgBegin); 3908249423Sdim for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { 3909249423Sdim Constant *C = dyn_cast<Constant>(*I); 3910249423Sdim if (!C) 3911276479Sdim return nullptr; 3912249423Sdim ConstantArgs.push_back(C); 3913249423Sdim } 3914249423Sdim 3915249423Sdim return ConstantFoldCall(F, ConstantArgs, Q.TLI); 3916249423Sdim} 3917249423Sdim 3918249423SdimValue *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, 3919288943Sdim User::op_iterator ArgEnd, const DataLayout &DL, 3920280031Sdim const TargetLibraryInfo *TLI, const DominatorTree *DT, 3921280031Sdim AssumptionCache *AC, const Instruction *CxtI) { 3922280031Sdim return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI), 3923249423Sdim RecursionLimit); 3924249423Sdim} 3925249423Sdim 3926249423SdimValue *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, 3927288943Sdim const DataLayout &DL, const TargetLibraryInfo *TLI, 3928280031Sdim const DominatorTree *DT, AssumptionCache *AC, 3929280031Sdim const Instruction *CxtI) { 3930280031Sdim return ::SimplifyCall(V, Args.begin(), Args.end(), 3931280031Sdim Query(DL, TLI, DT, AC, CxtI), RecursionLimit); 3932249423Sdim} 3933249423Sdim 3934296417Sdim/// See if we can compute a simplified version of this instruction. 3935296417Sdim/// If not, this returns null. 3936288943SdimValue *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, 3937234353Sdim const TargetLibraryInfo *TLI, 3938280031Sdim const DominatorTree *DT, AssumptionCache *AC) { 3939218893Sdim Value *Result; 3940218893Sdim 3941199481Srdivacky switch (I->getOpcode()) { 3942199481Srdivacky default: 3943276479Sdim Result = ConstantFoldInstruction(I, DL, TLI); 3944218893Sdim break; 3945249423Sdim case Instruction::FAdd: 3946249423Sdim Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), 3947280031Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 3948249423Sdim break; 3949199989Srdivacky case Instruction::Add: 3950218893Sdim Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 3951218893Sdim cast<BinaryOperator>(I)->hasNoSignedWrap(), 3952280031Sdim cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3953280031Sdim TLI, DT, AC, I); 3954218893Sdim break; 3955249423Sdim case Instruction::FSub: 3956249423Sdim Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), 3957280031Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 3958249423Sdim break; 3959218893Sdim case Instruction::Sub: 3960218893Sdim Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 3961218893Sdim cast<BinaryOperator>(I)->hasNoSignedWrap(), 3962280031Sdim cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 3963280031Sdim TLI, DT, AC, I); 3964218893Sdim break; 3965249423Sdim case Instruction::FMul: 3966249423Sdim Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), 3967280031Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 3968249423Sdim break; 3969218893Sdim case Instruction::Mul: 3970280031Sdim Result = 3971280031Sdim SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 3972218893Sdim break; 3973218893Sdim case Instruction::SDiv: 3974280031Sdim Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3975280031Sdim AC, I); 3976218893Sdim break; 3977218893Sdim case Instruction::UDiv: 3978280031Sdim Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3979280031Sdim AC, I); 3980218893Sdim break; 3981218893Sdim case Instruction::FDiv: 3982288943Sdim Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), 3983288943Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 3984218893Sdim break; 3985221345Sdim case Instruction::SRem: 3986280031Sdim Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3987280031Sdim AC, I); 3988221345Sdim break; 3989221345Sdim case Instruction::URem: 3990280031Sdim Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, 3991280031Sdim AC, I); 3992221345Sdim break; 3993221345Sdim case Instruction::FRem: 3994288943Sdim Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), 3995288943Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 3996221345Sdim break; 3997218893Sdim case Instruction::Shl: 3998218893Sdim Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 3999218893Sdim cast<BinaryOperator>(I)->hasNoSignedWrap(), 4000280031Sdim cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL, 4001280031Sdim TLI, DT, AC, I); 4002218893Sdim break; 4003218893Sdim case Instruction::LShr: 4004218893Sdim Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 4005280031Sdim cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 4006280031Sdim AC, I); 4007218893Sdim break; 4008218893Sdim case Instruction::AShr: 4009218893Sdim Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 4010280031Sdim cast<BinaryOperator>(I)->isExact(), DL, TLI, DT, 4011280031Sdim AC, I); 4012218893Sdim break; 4013199481Srdivacky case Instruction::And: 4014280031Sdim Result = 4015280031Sdim SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 4016218893Sdim break; 4017199481Srdivacky case Instruction::Or: 4018280031Sdim Result = 4019280031Sdim SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 4020218893Sdim break; 4021218893Sdim case Instruction::Xor: 4022280031Sdim Result = 4023280031Sdim SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I); 4024218893Sdim break; 4025199481Srdivacky case Instruction::ICmp: 4026280031Sdim Result = 4027280031Sdim SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), I->getOperand(0), 4028280031Sdim I->getOperand(1), DL, TLI, DT, AC, I); 4029218893Sdim break; 4030199481Srdivacky case Instruction::FCmp: 4031288943Sdim Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 4032288943Sdim I->getOperand(0), I->getOperand(1), 4033288943Sdim I->getFastMathFlags(), DL, TLI, DT, AC, I); 4034218893Sdim break; 4035207618Srdivacky case Instruction::Select: 4036218893Sdim Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 4037280031Sdim I->getOperand(2), DL, TLI, DT, AC, I); 4038218893Sdim break; 4039199989Srdivacky case Instruction::GetElementPtr: { 4040199989Srdivacky SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 4041280031Sdim Result = SimplifyGEPInst(Ops, DL, TLI, DT, AC, I); 4042218893Sdim break; 4043199481Srdivacky } 4044226633Sdim case Instruction::InsertValue: { 4045226633Sdim InsertValueInst *IV = cast<InsertValueInst>(I); 4046226633Sdim Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 4047226633Sdim IV->getInsertedValueOperand(), 4048280031Sdim IV->getIndices(), DL, TLI, DT, AC, I); 4049226633Sdim break; 4050226633Sdim } 4051288943Sdim case Instruction::ExtractValue: { 4052288943Sdim auto *EVI = cast<ExtractValueInst>(I); 4053288943Sdim Result = SimplifyExtractValueInst(EVI->getAggregateOperand(), 4054288943Sdim EVI->getIndices(), DL, TLI, DT, AC, I); 4055288943Sdim break; 4056288943Sdim } 4057288943Sdim case Instruction::ExtractElement: { 4058288943Sdim auto *EEI = cast<ExtractElementInst>(I); 4059288943Sdim Result = SimplifyExtractElementInst( 4060288943Sdim EEI->getVectorOperand(), EEI->getIndexOperand(), DL, TLI, DT, AC, I); 4061288943Sdim break; 4062288943Sdim } 4063218893Sdim case Instruction::PHI: 4064280031Sdim Result = SimplifyPHINode(cast<PHINode>(I), Query(DL, TLI, DT, AC, I)); 4065218893Sdim break; 4066249423Sdim case Instruction::Call: { 4067249423Sdim CallSite CS(cast<CallInst>(I)); 4068280031Sdim Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), DL, 4069280031Sdim TLI, DT, AC, I); 4070234353Sdim break; 4071249423Sdim } 4072234353Sdim case Instruction::Trunc: 4073280031Sdim Result = 4074280031Sdim SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT, AC, I); 4075234353Sdim break; 4076199989Srdivacky } 4077218893Sdim 4078296417Sdim // In general, it is possible for computeKnownBits to determine all bits in a 4079296417Sdim // value even when the operands are not all constants. 4080296417Sdim if (!Result && I->getType()->isIntegerTy()) { 4081296417Sdim unsigned BitWidth = I->getType()->getScalarSizeInBits(); 4082296417Sdim APInt KnownZero(BitWidth, 0); 4083296417Sdim APInt KnownOne(BitWidth, 0); 4084296417Sdim computeKnownBits(I, KnownZero, KnownOne, DL, /*Depth*/0, AC, I, DT); 4085296417Sdim if ((KnownZero | KnownOne).isAllOnesValue()) 4086296417Sdim Result = ConstantInt::get(I->getContext(), KnownOne); 4087296417Sdim } 4088296417Sdim 4089218893Sdim /// If called on unreachable code, the above logic may report that the 4090218893Sdim /// instruction simplified to itself. Make life easier for users by 4091218893Sdim /// detecting that case here, returning a safe value instead. 4092218893Sdim return Result == I ? UndefValue::get(I->getType()) : Result; 4093199481Srdivacky} 4094199481Srdivacky 4095234353Sdim/// \brief Implementation of recursive simplification through an instructions 4096234353Sdim/// uses. 4097199481Srdivacky/// 4098234353Sdim/// This is the common implementation of the recursive simplification routines. 4099234353Sdim/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to 4100234353Sdim/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of 4101234353Sdim/// instructions to process and attempt to simplify it using 4102234353Sdim/// InstructionSimplify. 4103234353Sdim/// 4104234353Sdim/// This routine returns 'true' only when *it* simplifies something. The passed 4105234353Sdim/// in simplified value does not count toward this. 4106234353Sdimstatic bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, 4107234353Sdim const TargetLibraryInfo *TLI, 4108280031Sdim const DominatorTree *DT, 4109280031Sdim AssumptionCache *AC) { 4110234353Sdim bool Simplified = false; 4111234353Sdim SmallSetVector<Instruction *, 8> Worklist; 4112288943Sdim const DataLayout &DL = I->getModule()->getDataLayout(); 4113218893Sdim 4114234353Sdim // If we have an explicit value to collapse to, do that round of the 4115234353Sdim // simplification loop by hand initially. 4116234353Sdim if (SimpleV) { 4117276479Sdim for (User *U : I->users()) 4118276479Sdim if (U != I) 4119276479Sdim Worklist.insert(cast<Instruction>(U)); 4120218893Sdim 4121234353Sdim // Replace the instruction with its simplified value. 4122234353Sdim I->replaceAllUsesWith(SimpleV); 4123210299Sed 4124234353Sdim // Gracefully handle edge cases where the instruction is not wired into any 4125234353Sdim // parent block. 4126234353Sdim if (I->getParent()) 4127234353Sdim I->eraseFromParent(); 4128234353Sdim } else { 4129234353Sdim Worklist.insert(I); 4130234353Sdim } 4131218893Sdim 4132234353Sdim // Note that we must test the size on each iteration, the worklist can grow. 4133234353Sdim for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { 4134234353Sdim I = Worklist[Idx]; 4135218893Sdim 4136234353Sdim // See if this instruction simplifies. 4137280031Sdim SimpleV = SimplifyInstruction(I, DL, TLI, DT, AC); 4138234353Sdim if (!SimpleV) 4139234353Sdim continue; 4140218893Sdim 4141234353Sdim Simplified = true; 4142218893Sdim 4143234353Sdim // Stash away all the uses of the old instruction so we can check them for 4144234353Sdim // recursive simplifications after a RAUW. This is cheaper than checking all 4145234353Sdim // uses of To on the recursive step in most cases. 4146276479Sdim for (User *U : I->users()) 4147276479Sdim Worklist.insert(cast<Instruction>(U)); 4148234353Sdim 4149234353Sdim // Replace the instruction with its simplified value. 4150234353Sdim I->replaceAllUsesWith(SimpleV); 4151234353Sdim 4152234353Sdim // Gracefully handle edge cases where the instruction is not wired into any 4153234353Sdim // parent block. 4154234353Sdim if (I->getParent()) 4155234353Sdim I->eraseFromParent(); 4156199481Srdivacky } 4157234353Sdim return Simplified; 4158234353Sdim} 4159218893Sdim 4160288943Sdimbool llvm::recursivelySimplifyInstruction(Instruction *I, 4161234353Sdim const TargetLibraryInfo *TLI, 4162280031Sdim const DominatorTree *DT, 4163280031Sdim AssumptionCache *AC) { 4164288943Sdim return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC); 4165234353Sdim} 4166218893Sdim 4167234353Sdimbool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, 4168234353Sdim const TargetLibraryInfo *TLI, 4169280031Sdim const DominatorTree *DT, 4170280031Sdim AssumptionCache *AC) { 4171234353Sdim assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); 4172234353Sdim assert(SimpleV && "Must provide a simplified value."); 4173288943Sdim return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC); 4174199481Srdivacky} 4175