Index: head/contrib/llvm/lib/Analysis/InstructionSimplify.cpp =================================================================== --- head/contrib/llvm/lib/Analysis/InstructionSimplify.cpp (revision 331064) +++ head/contrib/llvm/lib/Analysis/InstructionSimplify.cpp (revision 331065) @@ -1,4955 +1,4955 @@ //===- InstructionSimplify.cpp - Fold instruction operands ----------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements routines for folding instructions into simpler forms // that do not require creating new instructions. This does constant folding // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either // returning a constant ("and i32 %x, 0" -> "0") or an already existing value // ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been // simplified: This is usually true and assuming it simplifies the logic (if // they have not been simplified then results are correct but maybe suboptimal). // //===----------------------------------------------------------------------===// #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/CmpInstAnalysis.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/KnownBits.h" #include using namespace llvm; using namespace llvm::PatternMatch; #define DEBUG_TYPE "instsimplify" enum { RecursionLimit = 3 }; STATISTIC(NumExpand, "Number of expansions"); STATISTIC(NumReassoc, "Number of reassociations"); static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned); static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &, unsigned); static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &, const SimplifyQuery &, unsigned); static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &, unsigned); static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse); static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned); static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned); static Value *SimplifyCastInst(unsigned, Value *, Type *, const SimplifyQuery &, unsigned); /// For a boolean type or a vector of boolean type, return false or a vector /// with every element false. static Constant *getFalse(Type *Ty) { return ConstantInt::getFalse(Ty); } /// For a boolean type or a vector of boolean type, return true or a vector /// with every element true. static Constant *getTrue(Type *Ty) { return ConstantInt::getTrue(Ty); } /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, Value *RHS) { CmpInst *Cmp = dyn_cast(V); if (!Cmp) return false; CmpInst::Predicate CPred = Cmp->getPredicate(); Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); if (CPred == Pred && CLHS == LHS && CRHS == RHS) return true; return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && CRHS == LHS; } /// Does the given value dominate the specified phi node? static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { Instruction *I = dyn_cast(V); if (!I) // Arguments and constants dominate all instructions. return true; // If we are processing instructions (and/or basic blocks) that have not been // fully added to a function, the parent nodes may still be null. Simply // return the conservative answer in these cases. if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) return false; // If we have a DominatorTree then do a precise test. if (DT) return DT->dominates(I, P); // Otherwise, if the instruction is in the entry block and is not an invoke, // then it obviously dominates all phi nodes. if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && !isa(I)) return true; return false; } /// Simplify "A op (B op' C)" by distributing op over op', turning it into /// "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". /// Returns the simplified value, or null if no simplification was performed. static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, Instruction::BinaryOps OpcodeToExpand, const SimplifyQuery &Q, unsigned MaxRecurse) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; // Check whether the expression has the form "(A op' B) op C". if (BinaryOperator *Op0 = dyn_cast(LHS)) if (Op0->getOpcode() == OpcodeToExpand) { // It does! Try turning it into "(A op C) op' (B op C)". Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; // Do "A op C" and "B op C" both simplify? if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { // They do! Return "L op' R" if it simplifies or is already available. // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) && L == B && R == A)) { ++NumExpand; return LHS; } // Otherwise return "L op' R" if it simplifies. if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { ++NumExpand; return V; } } } // Check whether the expression has the form "A op (B op' C)". if (BinaryOperator *Op1 = dyn_cast(RHS)) if (Op1->getOpcode() == OpcodeToExpand) { // It does! Try turning it into "(A op B) op' (A op C)". Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); // Do "A op B" and "A op C" both simplify? if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { // They do! Return "L op' R" if it simplifies or is already available. // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) && L == C && R == B)) { ++NumExpand; return RHS; } // Otherwise return "L op' R" if it simplifies. if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { ++NumExpand; return V; } } } return nullptr; } /// Generic simplifications for associative binary operations. /// Returns the simpler value, or null if none was found. static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; BinaryOperator *Op0 = dyn_cast(LHS); BinaryOperator *Op1 = dyn_cast(RHS); // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. if (Op0 && Op0->getOpcode() == Opcode) { Value *A = Op0->getOperand(0); Value *B = Op0->getOperand(1); Value *C = RHS; // Does "B op C" simplify? if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { // It does! Return "A op V" if it simplifies or is already available. // If V equals B then "A op V" is just the LHS. if (V == B) return LHS; // Otherwise return "A op V" if it simplifies. if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) { ++NumReassoc; return W; } } } // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. if (Op1 && Op1->getOpcode() == Opcode) { Value *A = LHS; Value *B = Op1->getOperand(0); Value *C = Op1->getOperand(1); // Does "A op B" simplify? if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) { // It does! Return "V op C" if it simplifies or is already available. // If V equals B then "V op C" is just the RHS. if (V == B) return RHS; // Otherwise return "V op C" if it simplifies. if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) { ++NumReassoc; return W; } } } // The remaining transforms require commutativity as well as associativity. if (!Instruction::isCommutative(Opcode)) return nullptr; // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. if (Op0 && Op0->getOpcode() == Opcode) { Value *A = Op0->getOperand(0); Value *B = Op0->getOperand(1); Value *C = RHS; // Does "C op A" simplify? if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { // It does! Return "V op B" if it simplifies or is already available. // If V equals A then "V op B" is just the LHS. if (V == A) return LHS; // Otherwise return "V op B" if it simplifies. if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) { ++NumReassoc; return W; } } } // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. if (Op1 && Op1->getOpcode() == Opcode) { Value *A = LHS; Value *B = Op1->getOperand(0); Value *C = Op1->getOperand(1); // Does "C op A" simplify? if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { // It does! Return "B op V" if it simplifies or is already available. // If V equals C then "B op V" is just the RHS. if (V == C) return RHS; // Otherwise return "B op V" if it simplifies. if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) { ++NumReassoc; return W; } } } return nullptr; } /// In the case of a binary operation with a select instruction as an operand, /// try to simplify the binop by seeing whether evaluating it on both branches /// of the select results in the same value. Returns the common value if so, /// otherwise returns null. static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; SelectInst *SI; if (isa(LHS)) { SI = cast(LHS); } else { assert(isa(RHS) && "No select instruction operand!"); SI = cast(RHS); } // Evaluate the BinOp on the true and false branches of the select. Value *TV; Value *FV; if (SI == LHS) { TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse); FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse); } else { TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse); FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse); } // If they simplified to the same value, then return the common value. // If they both failed to simplify then return null. if (TV == FV) return TV; // If one branch simplified to undef, return the other one. if (TV && isa(TV)) return FV; if (FV && isa(FV)) return TV; // If applying the operation did not change the true and false select values, // then the result of the binop is the select itself. if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) return SI; // If one branch simplified and the other did not, and the simplified // value is equal to the unsimplified one, return the simplified value. // For example, select (cond, X, X & Z) & Z -> X & Z. if ((FV && !TV) || (TV && !FV)) { // Check that the simplified value has the form "X op Y" where "op" is the // same as the original operation. Instruction *Simplified = dyn_cast(FV ? FV : TV); if (Simplified && Simplified->getOpcode() == unsigned(Opcode)) { // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". // We already know that "op" is the same as for the simplified value. See // if the operands match too. If so, return the simplified value. Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; if (Simplified->getOperand(0) == UnsimplifiedLHS && Simplified->getOperand(1) == UnsimplifiedRHS) return Simplified; if (Simplified->isCommutative() && Simplified->getOperand(1) == UnsimplifiedLHS && Simplified->getOperand(0) == UnsimplifiedRHS) return Simplified; } } return nullptr; } /// In the case of a comparison with a select instruction, try to simplify the /// comparison by seeing whether both branches of the select result in the same /// value. Returns the common value if so, otherwise returns null. static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; // Make sure the select is on the LHS. if (!isa(LHS)) { std::swap(LHS, RHS); Pred = CmpInst::getSwappedPredicate(Pred); } assert(isa(LHS) && "Not comparing with a select instruction!"); SelectInst *SI = cast(LHS); Value *Cond = SI->getCondition(); Value *TV = SI->getTrueValue(); Value *FV = SI->getFalseValue(); // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. // Does "cmp TV, RHS" simplify? Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); if (TCmp == Cond) { // It not only simplified, it simplified to the select condition. Replace // it with 'true'. TCmp = getTrue(Cond->getType()); } else if (!TCmp) { // It didn't simplify. However if "cmp TV, RHS" is equal to the select // condition then we can replace it with 'true'. Otherwise give up. if (!isSameCompare(Cond, Pred, TV, RHS)) return nullptr; TCmp = getTrue(Cond->getType()); } // Does "cmp FV, RHS" simplify? Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); if (FCmp == Cond) { // It not only simplified, it simplified to the select condition. Replace // it with 'false'. FCmp = getFalse(Cond->getType()); } else if (!FCmp) { // It didn't simplify. However if "cmp FV, RHS" is equal to the select // condition then we can replace it with 'false'. Otherwise give up. if (!isSameCompare(Cond, Pred, FV, RHS)) return nullptr; FCmp = getFalse(Cond->getType()); } // If both sides simplified to the same value, then use it as the result of // the original comparison. if (TCmp == FCmp) return TCmp; // The remaining cases only make sense if the select condition has the same // type as the result of the comparison, so bail out if this is not so. if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) return nullptr; // If the false value simplified to false, then the result of the compare // is equal to "Cond && TCmp". This also catches the case when the false // value simplified to false and the true value to true, returning "Cond". if (match(FCmp, m_Zero())) if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) return V; // If the true value simplified to true, then the result of the compare // is equal to "Cond || FCmp". if (match(TCmp, m_One())) if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) return V; // Finally, if the false value simplified to true and the true value to // false, then the result of the compare is equal to "!Cond". if (match(FCmp, m_One()) && match(TCmp, m_Zero())) if (Value *V = SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), Q, MaxRecurse)) return V; return nullptr; } /// In the case of a binary operation with an operand that is a PHI instruction, /// try to simplify the binop by seeing whether evaluating it on the incoming /// phi values yields the same result for every value. If so returns the common /// value, otherwise returns null. static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; PHINode *PI; if (isa(LHS)) { PI = cast(LHS); // Bail out if RHS and the phi may be mutually interdependent due to a loop. if (!ValueDominatesPHI(RHS, PI, Q.DT)) return nullptr; } else { assert(isa(RHS) && "No PHI instruction operand!"); PI = cast(RHS); // Bail out if LHS and the phi may be mutually interdependent due to a loop. if (!ValueDominatesPHI(LHS, PI, Q.DT)) return nullptr; } // Evaluate the BinOp on the incoming phi values. Value *CommonValue = nullptr; for (Value *Incoming : PI->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PI) continue; Value *V = PI == LHS ? SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) : SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse); // If the operation failed to simplify, or simplified to a different value // to previously, then give up. if (!V || (CommonValue && V != CommonValue)) return nullptr; CommonValue = V; } return CommonValue; } /// In the case of a comparison with a PHI instruction, try to simplify the /// comparison by seeing whether comparing with all of the incoming phi values /// yields the same result every time. If so returns the common result, /// otherwise returns null. static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return nullptr; // Make sure the phi is on the LHS. if (!isa(LHS)) { std::swap(LHS, RHS); Pred = CmpInst::getSwappedPredicate(Pred); } assert(isa(LHS) && "Not comparing with a phi instruction!"); PHINode *PI = cast(LHS); // Bail out if RHS and the phi may be mutually interdependent due to a loop. if (!ValueDominatesPHI(RHS, PI, Q.DT)) return nullptr; // Evaluate the BinOp on the incoming phi values. Value *CommonValue = nullptr; for (Value *Incoming : PI->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PI) continue; Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); // If the operation failed to simplify, or simplified to a different value // to previously, then give up. if (!V || (CommonValue && V != CommonValue)) return nullptr; CommonValue = V; } return CommonValue; } static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode, Value *&Op0, Value *&Op1, const SimplifyQuery &Q) { if (auto *CLHS = dyn_cast(Op0)) { if (auto *CRHS = dyn_cast(Op1)) return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL); // Canonicalize the constant to the RHS if this is a commutative operation. if (Instruction::isCommutative(Opcode)) std::swap(Op0, Op1); } return nullptr; } /// Given operands for an Add, see if we can fold the result. /// If not, this returns null. static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q)) return C; // X + undef -> undef if (match(Op1, m_Undef())) return Op1; // X + 0 -> X if (match(Op1, m_Zero())) return Op0; // X + (Y - X) -> Y // (Y - X) + X -> Y // Eg: X + -X -> 0 Value *Y = nullptr; if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) return Y; // X + ~X -> -1 since ~X = -X-1 Type *Ty = Op0->getType(); if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0)))) return Constant::getAllOnesValue(Ty); // add nsw/nuw (xor Y, signmask), signmask --> Y // The no-wrapping add guarantees that the top bit will be set by the add. // Therefore, the xor must be clearing the already set sign bit of Y. if ((isNSW || isNUW) && match(Op1, m_SignMask()) && match(Op0, m_Xor(m_Value(Y), m_SignMask()))) return Y; /// i1 add -> xor. if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1)) if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) return V; // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, MaxRecurse)) return V; // Threading Add over selects and phi nodes is pointless, so don't bother. // Threading over the select in "A + select(cond, B, C)" means evaluating // "A+B" and "A+C" and seeing if they are equal; but they are equal if and // only if B and C are equal. If B and C are equal then (since we assume // that operands have already been simplified) "select(cond, B, C)" should // have been simplified to the common value of B and C already. Analysing // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly // for threading over phi nodes. return nullptr; } Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Query) { return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query, RecursionLimit); } /// \brief Compute the base pointer and cumulative constant offsets for V. /// /// This strips all constant offsets off of V, leaving it the base pointer, and /// accumulates the total constant offset applied in the returned constant. It /// returns 0 if V is not a pointer, and returns the constant '0' if there are /// no constant offsets applied. /// /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. /// folding. static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V, bool AllowNonInbounds = false) { assert(V->getType()->isPtrOrPtrVectorTy()); Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); // Even though we don't look through PHI nodes, we could be called on an // instruction in an unreachable block, which may be on a cycle. SmallPtrSet Visited; Visited.insert(V); do { if (GEPOperator *GEP = dyn_cast(V)) { if ((!AllowNonInbounds && !GEP->isInBounds()) || !GEP->accumulateConstantOffset(DL, Offset)) break; V = GEP->getPointerOperand(); } else if (Operator::getOpcode(V) == Instruction::BitCast) { V = cast(V)->getOperand(0); } else if (GlobalAlias *GA = dyn_cast(V)) { if (GA->isInterposable()) break; V = GA->getAliasee(); } else { if (auto CS = CallSite(V)) if (Value *RV = CS.getReturnedArgOperand()) { V = RV; continue; } break; } assert(V->getType()->isPtrOrPtrVectorTy() && "Unexpected operand type!"); } while (Visited.insert(V).second); Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); if (V->getType()->isVectorTy()) return ConstantVector::getSplat(V->getType()->getVectorNumElements(), OffsetIntPtr); return OffsetIntPtr; } /// \brief Compute the constant difference between two pointer values. /// If the difference is not a constant, returns zero. static Constant *computePointerDifference(const DataLayout &DL, Value *LHS, Value *RHS) { Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); // If LHS and RHS are not related via constant offsets to the same base // value, there is nothing we can do here. if (LHS != RHS) return nullptr; // Otherwise, the difference of LHS - RHS can be computed as: // LHS - RHS // = (LHSOffset + Base) - (RHSOffset + Base) // = LHSOffset - RHSOffset return ConstantExpr::getSub(LHSOffset, RHSOffset); } /// Given operands for a Sub, see if we can fold the result. /// If not, this returns null. static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q)) return C; // X - undef -> undef // undef - X -> undef if (match(Op0, m_Undef()) || match(Op1, m_Undef())) return UndefValue::get(Op0->getType()); // X - 0 -> X if (match(Op1, m_Zero())) return Op0; // X - X -> 0 if (Op0 == Op1) return Constant::getNullValue(Op0->getType()); // Is this a negation? if (match(Op0, m_Zero())) { // 0 - X -> 0 if the sub is NUW. if (isNUW) return Op0; KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (Known.Zero.isMaxSignedValue()) { // Op1 is either 0 or the minimum signed value. If the sub is NSW, then // Op1 must be 0 because negating the minimum signed value is undefined. if (isNSW) return Op0; // 0 - X -> X if X is 0 or the minimum signed value. return Op1; } } // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. // For example, (X + Y) - Y -> X; (Y + X) - Y -> X Value *X = nullptr, *Y = nullptr, *Z = Op1; if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z // See if "V === Y - Z" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) // It does! Now see if "X + V" simplifies. if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { // It does, we successfully reassociated! ++NumReassoc; return W; } // See if "V === X - Z" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) // It does! Now see if "Y + V" simplifies. if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) { // It does, we successfully reassociated! ++NumReassoc; return W; } } // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. // For example, X - (X + 1) -> -1 X = Op0; if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) // See if "V === X - Y" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) // It does! Now see if "V - Z" simplifies. if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) { // It does, we successfully reassociated! ++NumReassoc; return W; } // See if "V === X - Z" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) // It does! Now see if "V - Y" simplifies. if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) { // It does, we successfully reassociated! ++NumReassoc; return W; } } // Z - (X - Y) -> (Z - X) + Y if everything simplifies. // For example, X - (X - Y) -> Y. Z = Op0; if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) // See if "V === Z - X" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1)) // It does! Now see if "V + Y" simplifies. if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) { // It does, we successfully reassociated! ++NumReassoc; return W; } // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies. if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) && match(Op1, m_Trunc(m_Value(Y)))) if (X->getType() == Y->getType()) // See if "V === X - Y" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) // It does! Now see if "trunc V" simplifies. if (Value *W = SimplifyCastInst(Instruction::Trunc, V, Op0->getType(), Q, MaxRecurse - 1)) // It does, return the simplified "trunc V". return W; // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). if (match(Op0, m_PtrToInt(m_Value(X))) && match(Op1, m_PtrToInt(m_Value(Y)))) if (Constant *Result = computePointerDifference(Q.DL, X, Y)) return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); // i1 sub -> xor. if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1)) if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) return V; // Threading Sub over selects and phi nodes is pointless, so don't bother. // Threading over the select in "A - select(cond, B, C)" means evaluating // "A-B" and "A-C" and seeing if they are equal; but they are equal if and // only if B and C are equal. If B and C are equal then (since we assume // that operands have already been simplified) "select(cond, B, C)" should // have been simplified to the common value of B and C already. Analysing // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly // for threading over phi nodes. return nullptr; } Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q) { return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit); } /// Given operands for a Mul, see if we can fold the result. /// If not, this returns null. static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q)) return C; // X * undef -> 0 if (match(Op1, m_Undef())) return Constant::getNullValue(Op0->getType()); // X * 0 -> 0 if (match(Op1, m_Zero())) return Op1; // X * 1 -> X if (match(Op1, m_One())) return Op0; // (X / Y) * Y -> X if the division is exact. Value *X = nullptr; if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) return X; // i1 mul -> and. if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1)) if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1)) return V; // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, MaxRecurse)) return V; // Mul distributes over Add. Try some generic simplifications based on this. if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, MaxRecurse)) return V; // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit); } /// Check for common or similar folds of integer division or integer remainder. /// This applies to all 4 opcodes (sdiv/udiv/srem/urem). static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) { Type *Ty = Op0->getType(); // X / undef -> undef // X % undef -> undef if (match(Op1, m_Undef())) return Op1; // X / 0 -> undef // X % 0 -> undef // We don't need to preserve faults! if (match(Op1, m_Zero())) return UndefValue::get(Ty); // If any element of a constant divisor vector is zero, the whole op is undef. auto *Op1C = dyn_cast(Op1); if (Op1C && Ty->isVectorTy()) { unsigned NumElts = Ty->getVectorNumElements(); for (unsigned i = 0; i != NumElts; ++i) { Constant *Elt = Op1C->getAggregateElement(i); if (Elt && Elt->isNullValue()) return UndefValue::get(Ty); } } // undef / X -> 0 // undef % X -> 0 if (match(Op0, m_Undef())) return Constant::getNullValue(Ty); // 0 / X -> 0 // 0 % X -> 0 if (match(Op0, m_Zero())) return Op0; // X / X -> 1 // X % X -> 0 if (Op0 == Op1) return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty); // X / 1 -> X // X % 1 -> 0 // If this is a boolean op (single-bit element type), we can't have // division-by-zero or remainder-by-zero, so assume the divisor is 1. if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1)) return IsDiv ? Op0 : Constant::getNullValue(Ty); return nullptr; } /// Given a predicate and two operands, return true if the comparison is true. /// This is a helper for div/rem simplification where we return some other value /// when we can prove a relationship between the operands. static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { Value *V = SimplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse); Constant *C = dyn_cast_or_null(V); return (C && C->isAllOnesValue()); } /// Return true if we can simplify X / Y to 0. Remainder can adapt that answer /// to simplify X % Y to X. static bool isDivZero(Value *X, Value *Y, const SimplifyQuery &Q, unsigned MaxRecurse, bool IsSigned) { // Recursion is always used, so bail out at once if we already hit the limit. if (!MaxRecurse--) return false; if (IsSigned) { // |X| / |Y| --> 0 // // We require that 1 operand is a simple constant. That could be extended to // 2 variables if we computed the sign bit for each. // // Make sure that a constant is not the minimum signed value because taking // the abs() of that is undefined. Type *Ty = X->getType(); const APInt *C; if (match(X, m_APInt(C)) && !C->isMinSignedValue()) { // Is the variable divisor magnitude always greater than the constant // dividend magnitude? // |Y| > |C| --> Y < -abs(C) or Y > abs(C) Constant *PosDividendC = ConstantInt::get(Ty, C->abs()); Constant *NegDividendC = ConstantInt::get(Ty, -C->abs()); if (isICmpTrue(CmpInst::ICMP_SLT, Y, NegDividendC, Q, MaxRecurse) || isICmpTrue(CmpInst::ICMP_SGT, Y, PosDividendC, Q, MaxRecurse)) return true; } if (match(Y, m_APInt(C))) { // Special-case: we can't take the abs() of a minimum signed value. If // that's the divisor, then all we have to do is prove that the dividend // is also not the minimum signed value. if (C->isMinSignedValue()) return isICmpTrue(CmpInst::ICMP_NE, X, Y, Q, MaxRecurse); // Is the variable dividend magnitude always less than the constant // divisor magnitude? // |X| < |C| --> X > -abs(C) and X < abs(C) Constant *PosDivisorC = ConstantInt::get(Ty, C->abs()); Constant *NegDivisorC = ConstantInt::get(Ty, -C->abs()); if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) && isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse)) return true; } return false; } // IsSigned == false. // Is the dividend unsigned less than the divisor? return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse); } /// These are simplifications common to SDiv and UDiv. static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q)) return C; if (Value *V = simplifyDivRem(Op0, Op1, true)) return V; bool IsSigned = Opcode == Instruction::SDiv; // (X * Y) / Y -> X if the multiplication does not overflow. Value *X = nullptr, *Y = nullptr; if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 OverflowingBinaryOperator *Mul = cast(Op0); // If the Mul knows it does not overflow, then we are good to go. if ((IsSigned && Mul->hasNoSignedWrap()) || (!IsSigned && Mul->hasNoUnsignedWrap())) return X; // If X has the form X = A / Y then X * Y cannot overflow. if (BinaryOperator *Div = dyn_cast(X)) if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) return X; } // (X rem Y) / Y -> 0 if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) return Constant::getNullValue(Op0->getType()); // (X /u C1) /u C2 -> 0 if C1 * C2 overflow ConstantInt *C1, *C2; if (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) && match(Op1, m_ConstantInt(C2))) { bool Overflow; (void)C1->getValue().umul_ov(C2->getValue(), Overflow); if (Overflow) return Constant::getNullValue(Op0->getType()); } // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) return V; if (isDivZero(Op0, Op1, Q, MaxRecurse, IsSigned)) return Constant::getNullValue(Op0->getType()); return nullptr; } /// These are simplifications common to SRem and URem. static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q)) return C; if (Value *V = simplifyDivRem(Op0, Op1, false)) return V; // (X % Y) % Y -> X % Y if ((Opcode == Instruction::SRem && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || (Opcode == Instruction::URem && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) return Op0; // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // If X / Y == 0, then X % Y == X. if (isDivZero(Op0, Op1, Q, MaxRecurse, Opcode == Instruction::SRem)) return Op0; return nullptr; } /// Given operands for an SDiv, see if we can fold the result. /// If not, this returns null. static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse); } Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit); } /// Given operands for a UDiv, see if we can fold the result. /// If not, this returns null. static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { return simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse); } Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyUDivInst(Op0, Op1, Q, RecursionLimit); } /// Given operands for an SRem, see if we can fold the result. /// If not, this returns null. static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse); } Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit); } /// Given operands for a URem, see if we can fold the result. /// If not, this returns null. static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse); } Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit); } /// Returns true if a shift by \c Amount always yields undef. static bool isUndefShift(Value *Amount) { Constant *C = dyn_cast(Amount); if (!C) return false; // X shift by undef -> undef because it may shift by the bitwidth. if (isa(C)) return true; // Shifting by the bitwidth or more is undefined. if (ConstantInt *CI = dyn_cast(C)) if (CI->getValue().getLimitedValue() >= CI->getType()->getScalarSizeInBits()) return true; // If all lanes of a vector shift are undefined the whole shift is. if (isa(C) || isa(C)) { for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I) if (!isUndefShift(C->getAggregateElement(I))) return false; return true; } return false; } /// Given operands for an Shl, LShr or AShr, see if we can fold the result. /// If not, this returns null. static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q)) return C; // 0 shift by X -> 0 if (match(Op0, m_Zero())) return Op0; // X shift by 0 -> X if (match(Op1, m_Zero())) return Op0; // Fold undefined shifts. if (isUndefShift(Op1)) return UndefValue::get(Op0->getType()); // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // If any bits in the shift amount make that value greater than or equal to // the number of bits in the type, the shift is undefined. KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (Known.One.getLimitedValue() >= Known.getBitWidth()) return UndefValue::get(Op0->getType()); // If all valid bits in the shift amount are known zero, the first operand is // unchanged. unsigned NumValidShiftBits = Log2_32_Ceil(Known.getBitWidth()); if (Known.countMinTrailingZeros() >= NumValidShiftBits) return Op0; return nullptr; } /// \brief Given operands for an Shl, LShr or AShr, see if we can /// fold the result. If not, this returns null. static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse)) return V; // X >> X -> 0 if (Op0 == Op1) return Constant::getNullValue(Op0->getType()); // undef >> X -> 0 // undef >> X -> undef (if it's exact) if (match(Op0, m_Undef())) return isExact ? Op0 : Constant::getNullValue(Op0->getType()); // The low bit cannot be shifted out of an exact shift if it is set. if (isExact) { KnownBits Op0Known = computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT); if (Op0Known.One[0]) return Op0; } return nullptr; } /// Given operands for an Shl, see if we can fold the result. /// If not, this returns null. static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse)) return V; // undef << X -> 0 // undef << X -> undef if (if it's NSW/NUW) if (match(Op0, m_Undef())) return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType()); // (X >> A) << A -> X Value *X; if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) return X; return nullptr; } Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q) { return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit); } /// Given operands for an LShr, see if we can fold the result. /// If not, this returns null. static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q, MaxRecurse)) return V; // (X << A) >> A -> X Value *X; if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1)))) return X; return nullptr; } Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q) { return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit); } /// Given operands for an AShr, see if we can fold the result. /// If not, this returns null. static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q, MaxRecurse)) return V; // all ones >>a X -> all ones if (match(Op0, m_AllOnes())) return Op0; // (X << A) >> A -> X Value *X; if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1)))) return X; // Arithmetic shifting an all-sign-bit value is a no-op. unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (NumSignBits == Op0->getType()->getScalarSizeInBits()) return Op0; return nullptr; } Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q) { return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit); } /// Commuted variants are assumed to be handled by calling this function again /// with the parameters swapped. static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp, ICmpInst *UnsignedICmp, bool IsAnd) { Value *X, *Y; ICmpInst::Predicate EqPred; if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) || !ICmpInst::isEquality(EqPred)) return nullptr; ICmpInst::Predicate UnsignedPred; if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) && ICmpInst::isUnsigned(UnsignedPred)) ; else if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) && ICmpInst::isUnsigned(UnsignedPred)) UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred); else return nullptr; // X < Y && Y != 0 --> X < Y // X < Y || Y != 0 --> Y != 0 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE) return IsAnd ? UnsignedICmp : ZeroICmp; // X >= Y || Y != 0 --> true // X >= Y || Y == 0 --> X >= Y if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) { if (EqPred == ICmpInst::ICMP_NE) return getTrue(UnsignedICmp->getType()); return UnsignedICmp; } // X < Y && Y == 0 --> false if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ && IsAnd) return getFalse(UnsignedICmp->getType()); return nullptr; } /// Commuted variants are assumed to be handled by calling this function again /// with the parameters swapped. static Value *simplifyAndOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) { ICmpInst::Predicate Pred0, Pred1; Value *A ,*B; if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) || !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B)))) return nullptr; // We have (icmp Pred0, A, B) & (icmp Pred1, A, B). // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we // can eliminate Op1 from this 'and'. if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1)) return Op0; // Check for any combination of predicates that are guaranteed to be disjoint. if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) || (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) || (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) || (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)) return getFalse(Op0->getType()); return nullptr; } /// Commuted variants are assumed to be handled by calling this function again /// with the parameters swapped. static Value *simplifyOrOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) { ICmpInst::Predicate Pred0, Pred1; Value *A ,*B; if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) || !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B)))) return nullptr; // We have (icmp Pred0, A, B) | (icmp Pred1, A, B). // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we // can eliminate Op0 from this 'or'. if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1)) return Op1; // Check for any combination of predicates that cover the entire range of // possibilities. if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) || (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) || (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) || (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE)) return getTrue(Op0->getType()); return nullptr; } /// Test if a pair of compares with a shared operand and 2 constants has an /// empty set intersection, full set union, or if one compare is a superset of /// the other. static Value *simplifyAndOrOfICmpsWithConstants(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd) { // Look for this pattern: {and/or} (icmp X, C0), (icmp X, C1)). if (Cmp0->getOperand(0) != Cmp1->getOperand(0)) return nullptr; const APInt *C0, *C1; if (!match(Cmp0->getOperand(1), m_APInt(C0)) || !match(Cmp1->getOperand(1), m_APInt(C1))) return nullptr; auto Range0 = ConstantRange::makeExactICmpRegion(Cmp0->getPredicate(), *C0); auto Range1 = ConstantRange::makeExactICmpRegion(Cmp1->getPredicate(), *C1); // For and-of-compares, check if the intersection is empty: // (icmp X, C0) && (icmp X, C1) --> empty set --> false if (IsAnd && Range0.intersectWith(Range1).isEmptySet()) return getFalse(Cmp0->getType()); // For or-of-compares, check if the union is full: // (icmp X, C0) || (icmp X, C1) --> full set --> true if (!IsAnd && Range0.unionWith(Range1).isFullSet()) return getTrue(Cmp0->getType()); // Is one range a superset of the other? // If this is and-of-compares, take the smaller set: // (icmp sgt X, 4) && (icmp sgt X, 42) --> icmp sgt X, 42 // If this is or-of-compares, take the larger set: // (icmp sgt X, 4) || (icmp sgt X, 42) --> icmp sgt X, 4 if (Range0.contains(Range1)) return IsAnd ? Cmp1 : Cmp0; if (Range1.contains(Range0)) return IsAnd ? Cmp0 : Cmp1; return nullptr; } static Value *simplifyAndOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) { // (icmp (add V, C0), C1) & (icmp V, C0) ICmpInst::Predicate Pred0, Pred1; const APInt *C0, *C1; Value *V; if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1)))) return nullptr; if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value()))) return nullptr; auto *AddInst = cast(Op0->getOperand(0)); if (AddInst->getOperand(1) != Op1->getOperand(1)) return nullptr; Type *ITy = Op0->getType(); bool isNSW = AddInst->hasNoSignedWrap(); bool isNUW = AddInst->hasNoUnsignedWrap(); const APInt Delta = *C1 - *C0; if (C0->isStrictlyPositive()) { if (Delta == 2) { if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT) return getFalse(ITy); if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW) return getFalse(ITy); } if (Delta == 1) { if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT) return getFalse(ITy); if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW) return getFalse(ITy); } } if (C0->getBoolValue() && isNUW) { if (Delta == 2) if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT) return getFalse(ITy); if (Delta == 1) if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT) return getFalse(ITy); } return nullptr; } static Value *simplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) { if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true)) return X; if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true)) return X; if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1)) return X; if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0)) return X; if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true)) return X; if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1)) return X; if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0)) return X; return nullptr; } static Value *simplifyOrOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) { // (icmp (add V, C0), C1) | (icmp V, C0) ICmpInst::Predicate Pred0, Pred1; const APInt *C0, *C1; Value *V; if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1)))) return nullptr; if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value()))) return nullptr; auto *AddInst = cast(Op0->getOperand(0)); if (AddInst->getOperand(1) != Op1->getOperand(1)) return nullptr; Type *ITy = Op0->getType(); bool isNSW = AddInst->hasNoSignedWrap(); bool isNUW = AddInst->hasNoUnsignedWrap(); const APInt Delta = *C1 - *C0; if (C0->isStrictlyPositive()) { if (Delta == 2) { if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE) return getTrue(ITy); if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW) return getTrue(ITy); } if (Delta == 1) { if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE) return getTrue(ITy); if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW) return getTrue(ITy); } } if (C0->getBoolValue() && isNUW) { if (Delta == 2) if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE) return getTrue(ITy); if (Delta == 1) if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE) return getTrue(ITy); } return nullptr; } static Value *simplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) { if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false)) return X; if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false)) return X; if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1)) return X; if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0)) return X; if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false)) return X; if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1)) return X; if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0)) return X; return nullptr; } static Value *simplifyAndOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) { Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1); if (LHS0->getType() != RHS0->getType()) return nullptr; FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) || (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) { // (fcmp ord NNAN, X) & (fcmp ord X, Y) --> fcmp ord X, Y // (fcmp ord NNAN, X) & (fcmp ord Y, X) --> fcmp ord Y, X // (fcmp ord X, NNAN) & (fcmp ord X, Y) --> fcmp ord X, Y // (fcmp ord X, NNAN) & (fcmp ord Y, X) --> fcmp ord Y, X // (fcmp uno NNAN, X) | (fcmp uno X, Y) --> fcmp uno X, Y // (fcmp uno NNAN, X) | (fcmp uno Y, X) --> fcmp uno Y, X // (fcmp uno X, NNAN) | (fcmp uno X, Y) --> fcmp uno X, Y // (fcmp uno X, NNAN) | (fcmp uno Y, X) --> fcmp uno Y, X if ((isKnownNeverNaN(LHS0) && (LHS1 == RHS0 || LHS1 == RHS1)) || (isKnownNeverNaN(LHS1) && (LHS0 == RHS0 || LHS0 == RHS1))) return RHS; // (fcmp ord X, Y) & (fcmp ord NNAN, X) --> fcmp ord X, Y // (fcmp ord Y, X) & (fcmp ord NNAN, X) --> fcmp ord Y, X // (fcmp ord X, Y) & (fcmp ord X, NNAN) --> fcmp ord X, Y // (fcmp ord Y, X) & (fcmp ord X, NNAN) --> fcmp ord Y, X // (fcmp uno X, Y) | (fcmp uno NNAN, X) --> fcmp uno X, Y // (fcmp uno Y, X) | (fcmp uno NNAN, X) --> fcmp uno Y, X // (fcmp uno X, Y) | (fcmp uno X, NNAN) --> fcmp uno X, Y // (fcmp uno Y, X) | (fcmp uno X, NNAN) --> fcmp uno Y, X if ((isKnownNeverNaN(RHS0) && (RHS1 == LHS0 || RHS1 == LHS1)) || (isKnownNeverNaN(RHS1) && (RHS0 == LHS0 || RHS0 == LHS1))) return LHS; } return nullptr; } static Value *simplifyAndOrOfCmps(Value *Op0, Value *Op1, bool IsAnd) { // Look through casts of the 'and' operands to find compares. auto *Cast0 = dyn_cast(Op0); auto *Cast1 = dyn_cast(Op1); if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() && Cast0->getSrcTy() == Cast1->getSrcTy()) { Op0 = Cast0->getOperand(0); Op1 = Cast1->getOperand(0); } Value *V = nullptr; auto *ICmp0 = dyn_cast(Op0); auto *ICmp1 = dyn_cast(Op1); if (ICmp0 && ICmp1) V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1) : simplifyOrOfICmps(ICmp0, ICmp1); auto *FCmp0 = dyn_cast(Op0); auto *FCmp1 = dyn_cast(Op1); if (FCmp0 && FCmp1) V = simplifyAndOrOfFCmps(FCmp0, FCmp1, IsAnd); if (!V) return nullptr; if (!Cast0) return V; // If we looked through casts, we can only handle a constant simplification // because we are not allowed to create a cast instruction here. if (auto *C = dyn_cast(V)) return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType()); return nullptr; } /// Given operands for an And, see if we can fold the result. /// If not, this returns null. static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q)) return C; // X & undef -> 0 if (match(Op1, m_Undef())) return Constant::getNullValue(Op0->getType()); // X & X = X if (Op0 == Op1) return Op0; // X & 0 = 0 if (match(Op1, m_Zero())) return Op1; // X & -1 = X if (match(Op1, m_AllOnes())) return Op0; // A & ~A = ~A & A = 0 if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0)))) return Constant::getNullValue(Op0->getType()); // (A | ?) & A = A if (match(Op0, m_c_Or(m_Specific(Op1), m_Value()))) return Op1; // A & (A | ?) = A if (match(Op1, m_c_Or(m_Specific(Op0), m_Value()))) return Op0; // A mask that only clears known zeros of a shifted value is a no-op. Value *X; const APInt *Mask; const APInt *ShAmt; if (match(Op1, m_APInt(Mask))) { // If all bits in the inverted and shifted mask are clear: // and (shl X, ShAmt), Mask --> shl X, ShAmt if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) && (~(*Mask)).lshr(*ShAmt).isNullValue()) return Op0; // If all bits in the inverted and shifted mask are clear: // and (lshr X, ShAmt), Mask --> lshr X, ShAmt if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) && (~(*Mask)).shl(*ShAmt).isNullValue()) return Op0; } // A & (-A) = A if A is a power of two or zero. if (match(Op0, m_Neg(m_Specific(Op1))) || match(Op1, m_Neg(m_Specific(Op0)))) { if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) return Op0; if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) return Op1; } if (Value *V = simplifyAndOrOfCmps(Op0, Op1, true)) return V; // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, MaxRecurse)) return V; // And distributes over Or. Try some generic simplifications based on this. if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, Q, MaxRecurse)) return V; // And distributes over Xor. Try some generic simplifications based on this. if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, MaxRecurse)) return V; // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit); } /// Given operands for an Or, see if we can fold the result. /// If not, this returns null. static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q)) return C; // X | undef -> -1 if (match(Op1, m_Undef())) return Constant::getAllOnesValue(Op0->getType()); // X | X = X if (Op0 == Op1) return Op0; // X | 0 = X if (match(Op1, m_Zero())) return Op0; // X | -1 = -1 if (match(Op1, m_AllOnes())) return Op1; // A | ~A = ~A | A = -1 if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0)))) return Constant::getAllOnesValue(Op0->getType()); // (A & ?) | A = A if (match(Op0, m_c_And(m_Specific(Op1), m_Value()))) return Op1; // A | (A & ?) = A if (match(Op1, m_c_And(m_Specific(Op0), m_Value()))) return Op0; // ~(A & ?) | A = -1 if (match(Op0, m_Not(m_c_And(m_Specific(Op1), m_Value())))) return Constant::getAllOnesValue(Op1->getType()); // A | ~(A & ?) = -1 if (match(Op1, m_Not(m_c_And(m_Specific(Op1), m_Value())))) return Constant::getAllOnesValue(Op0->getType()); Value *A, *B; // (A & ~B) | (A ^ B) -> (A ^ B) // (~B & A) | (A ^ B) -> (A ^ B) // (A & ~B) | (B ^ A) -> (B ^ A) // (~B & A) | (B ^ A) -> (B ^ A) if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) || match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))) return Op1; // Commute the 'or' operands. // (A ^ B) | (A & ~B) -> (A ^ B) // (A ^ B) | (~B & A) -> (A ^ B) // (B ^ A) | (A & ~B) -> (B ^ A) // (B ^ A) | (~B & A) -> (B ^ A) if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) || match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))) return Op0; // (A & B) | (~A ^ B) -> (~A ^ B) // (B & A) | (~A ^ B) -> (~A ^ B) // (A & B) | (B ^ ~A) -> (B ^ ~A) // (B & A) | (B ^ ~A) -> (B ^ ~A) if (match(Op0, m_And(m_Value(A), m_Value(B))) && (match(Op1, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) || match(Op1, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B))))) return Op1; // (~A ^ B) | (A & B) -> (~A ^ B) // (~A ^ B) | (B & A) -> (~A ^ B) // (B ^ ~A) | (A & B) -> (B ^ ~A) // (B ^ ~A) | (B & A) -> (B ^ ~A) if (match(Op1, m_And(m_Value(A), m_Value(B))) && (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) || match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B))))) return Op0; if (Value *V = simplifyAndOrOfCmps(Op0, Op1, false)) return V; // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, MaxRecurse)) return V; // Or distributes over And. Try some generic simplifications based on this. if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, MaxRecurse)) return V; // (A & C1)|(B & C2) const APInt *C1, *C2; if (match(Op0, m_And(m_Value(A), m_APInt(C1))) && match(Op1, m_And(m_Value(B), m_APInt(C2)))) { if (*C1 == ~*C2) { // (A & C1)|(B & C2) // If we have: ((V + N) & C1) | (V & C2) // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 // replace with V+N. Value *N; if (C2->isMask() && // C2 == 0+1+ match(A, m_c_Add(m_Specific(B), m_Value(N)))) { // Add commutes, try both ways. if (MaskedValueIsZero(N, *C2, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return A; } // Or commutes, try both ways. if (C1->isMask() && match(B, m_c_Add(m_Specific(A), m_Value(N)))) { // Add commutes, try both ways. if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return B; } } } // If the operation is with the result of a phi instruction, check whether // operating on all incoming values of the phi always yields the same value. if (isa(Op0) || isa(Op1)) if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit); } /// Given operands for a Xor, see if we can fold the result. /// If not, this returns null. static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q)) return C; // A ^ undef -> undef if (match(Op1, m_Undef())) return Op1; // A ^ 0 = A if (match(Op1, m_Zero())) return Op0; // A ^ A = 0 if (Op0 == Op1) return Constant::getNullValue(Op0->getType()); // A ^ ~A = ~A ^ A = -1 if (match(Op0, m_Not(m_Specific(Op1))) || match(Op1, m_Not(m_Specific(Op0)))) return Constant::getAllOnesValue(Op0->getType()); // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, MaxRecurse)) return V; // Threading Xor over selects and phi nodes is pointless, so don't bother. // Threading over the select in "A ^ select(cond, B, C)" means evaluating // "A^B" and "A^C" and seeing if they are equal; but they are equal if and // only if B and C are equal. If B and C are equal then (since we assume // that operands have already been simplified) "select(cond, B, C)" should // have been simplified to the common value of B and C already. Analysing // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly // for threading over phi nodes. return nullptr; } Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) { return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit); } static Type *GetCompareTy(Value *Op) { return CmpInst::makeCmpResultType(Op->getType()); } /// Rummage around inside V looking for something equivalent to the comparison /// "LHS Pred RHS". Return such a value if found, otherwise return null. /// Helper function for analyzing max/min idioms. static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, Value *LHS, Value *RHS) { SelectInst *SI = dyn_cast(V); if (!SI) return nullptr; CmpInst *Cmp = dyn_cast(SI->getCondition()); if (!Cmp) return nullptr; Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) return Cmp; if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && LHS == CmpRHS && RHS == CmpLHS) return Cmp; return nullptr; } // A significant optimization not implemented here is assuming that alloca // addresses are not equal to incoming argument values. They don't *alias*, // as we say, but that doesn't mean they aren't equal, so we take a // conservative approach. // // This is inspired in part by C++11 5.10p1: // "Two pointers of the same type compare equal if and only if they are both // null, both point to the same function, or both represent the same // address." // // This is pretty permissive. // // It's also partly due to C11 6.5.9p6: // "Two pointers compare equal if and only if both are null pointers, both are // pointers to the same object (including a pointer to an object and a // subobject at its beginning) or function, both are pointers to one past the // last element of the same array object, or one is a pointer to one past the // end of one array object and the other is a pointer to the start of a // different array object that happens to immediately follow the first array // object in the address space.) // // C11's version is more restrictive, however there's no reason why an argument // couldn't be a one-past-the-end value for a stack object in the caller and be // equal to the beginning of a stack object in the callee. // // If the C and C++ standards are ever made sufficiently restrictive in this // area, it may be possible to update LLVM's semantics accordingly and reinstate // this optimization. static Constant * computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, CmpInst::Predicate Pred, AssumptionCache *AC, const Instruction *CxtI, Value *LHS, Value *RHS) { // First, skip past any trivial no-ops. LHS = LHS->stripPointerCasts(); RHS = RHS->stripPointerCasts(); // A non-null pointer is not equal to a null pointer. if (llvm::isKnownNonZero(LHS, DL) && isa(RHS) && (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) return ConstantInt::get(GetCompareTy(LHS), !CmpInst::isTrueWhenEqual(Pred)); // We can only fold certain predicates on pointer comparisons. switch (Pred) { default: return nullptr; // Equality comaprisons are easy to fold. case CmpInst::ICMP_EQ: case CmpInst::ICMP_NE: break; // We can only handle unsigned relational comparisons because 'inbounds' on // a GEP only protects against unsigned wrapping. case CmpInst::ICMP_UGT: case CmpInst::ICMP_UGE: case CmpInst::ICMP_ULT: case CmpInst::ICMP_ULE: // However, we have to switch them to their signed variants to handle // negative indices from the base pointer. Pred = ICmpInst::getSignedPredicate(Pred); break; } // Strip off any constant offsets so that we can reason about them. // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets // here and compare base addresses like AliasAnalysis does, however there are // numerous hazards. AliasAnalysis and its utilities rely on special rules // governing loads and stores which don't apply to icmps. Also, AliasAnalysis // doesn't need to guarantee pointer inequality when it says NoAlias. Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); // If LHS and RHS are related via constant offsets to the same base // value, we can replace it with an icmp which just compares the offsets. if (LHS == RHS) return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); // Various optimizations for (in)equality comparisons. if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { // Different non-empty allocations that exist at the same time have // different addresses (if the program can tell). Global variables always // exist, so they always exist during the lifetime of each other and all // allocas. Two different allocas usually have different addresses... // // However, if there's an @llvm.stackrestore dynamically in between two // allocas, they may have the same address. It's tempting to reduce the // scope of the problem by only looking at *static* allocas here. That would // cover the majority of allocas while significantly reducing the likelihood // of having an @llvm.stackrestore pop up in the middle. However, it's not // actually impossible for an @llvm.stackrestore to pop up in the middle of // an entry block. Also, if we have a block that's not attached to a // function, we can't tell if it's "static" under the current definition. // Theoretically, this problem could be fixed by creating a new kind of // instruction kind specifically for static allocas. Such a new instruction // could be required to be at the top of the entry block, thus preventing it // from being subject to a @llvm.stackrestore. Instcombine could even // convert regular allocas into these special allocas. It'd be nifty. // However, until then, this problem remains open. // // So, we'll assume that two non-empty allocas have different addresses // for now. // // With all that, if the offsets are within the bounds of their allocations // (and not one-past-the-end! so we can't use inbounds!), and their // allocations aren't the same, the pointers are not equal. // // Note that it's not necessary to check for LHS being a global variable // address, due to canonicalization and constant folding. if (isa(LHS) && (isa(RHS) || isa(RHS))) { ConstantInt *LHSOffsetCI = dyn_cast(LHSOffset); ConstantInt *RHSOffsetCI = dyn_cast(RHSOffset); uint64_t LHSSize, RHSSize; if (LHSOffsetCI && RHSOffsetCI && getObjectSize(LHS, LHSSize, DL, TLI) && getObjectSize(RHS, RHSSize, DL, TLI)) { const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); if (!LHSOffsetValue.isNegative() && !RHSOffsetValue.isNegative() && LHSOffsetValue.ult(LHSSize) && RHSOffsetValue.ult(RHSSize)) { return ConstantInt::get(GetCompareTy(LHS), !CmpInst::isTrueWhenEqual(Pred)); } } // Repeat the above check but this time without depending on DataLayout // or being able to compute a precise size. if (!cast(LHS->getType())->isEmptyTy() && !cast(RHS->getType())->isEmptyTy() && LHSOffset->isNullValue() && RHSOffset->isNullValue()) return ConstantInt::get(GetCompareTy(LHS), !CmpInst::isTrueWhenEqual(Pred)); } // Even if an non-inbounds GEP occurs along the path we can still optimize // equality comparisons concerning the result. We avoid walking the whole // chain again by starting where the last calls to // stripAndComputeConstantOffsets left off and accumulate the offsets. Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true); Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true); if (LHS == RHS) return ConstantExpr::getICmp(Pred, ConstantExpr::getAdd(LHSOffset, LHSNoBound), ConstantExpr::getAdd(RHSOffset, RHSNoBound)); // If one side of the equality comparison must come from a noalias call // (meaning a system memory allocation function), and the other side must // come from a pointer that cannot overlap with dynamically-allocated // memory within the lifetime of the current function (allocas, byval // arguments, globals), then determine the comparison result here. SmallVector LHSUObjs, RHSUObjs; GetUnderlyingObjects(LHS, LHSUObjs, DL); GetUnderlyingObjects(RHS, RHSUObjs, DL); // Is the set of underlying objects all noalias calls? auto IsNAC = [](ArrayRef Objects) { return all_of(Objects, isNoAliasCall); }; // Is the set of underlying objects all things which must be disjoint from // noalias calls. For allocas, we consider only static ones (dynamic // allocas might be transformed into calls to malloc not simultaneously // live with the compared-to allocation). For globals, we exclude symbols // that might be resolve lazily to symbols in another dynamically-loaded // library (and, thus, could be malloc'ed by the implementation). auto IsAllocDisjoint = [](ArrayRef Objects) { return all_of(Objects, [](Value *V) { if (const AllocaInst *AI = dyn_cast(V)) return AI->getParent() && AI->getFunction() && AI->isStaticAlloca(); if (const GlobalValue *GV = dyn_cast(V)) return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() || GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) && !GV->isThreadLocal(); if (const Argument *A = dyn_cast(V)) return A->hasByValAttr(); return false; }); }; if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) || (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs))) return ConstantInt::get(GetCompareTy(LHS), !CmpInst::isTrueWhenEqual(Pred)); // Fold comparisons for non-escaping pointer even if the allocation call // cannot be elided. We cannot fold malloc comparison to null. Also, the // dynamic allocation call could be either of the operands. Value *MI = nullptr; if (isAllocLikeFn(LHS, TLI) && llvm::isKnownNonZero(RHS, DL, 0, nullptr, CxtI, DT)) MI = LHS; else if (isAllocLikeFn(RHS, TLI) && llvm::isKnownNonZero(LHS, DL, 0, nullptr, CxtI, DT)) MI = RHS; // FIXME: We should also fold the compare when the pointer escapes, but the // compare dominates the pointer escape if (MI && !PointerMayBeCaptured(MI, true, true)) return ConstantInt::get(GetCompareTy(LHS), CmpInst::isFalseWhenEqual(Pred)); } // Otherwise, fail. return nullptr; } /// Fold an icmp when its operands have i1 scalar type. static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q) { Type *ITy = GetCompareTy(LHS); // The return type. Type *OpTy = LHS->getType(); // The operand type. if (!OpTy->isIntOrIntVectorTy(1)) return nullptr; // A boolean compared to true/false can be simplified in 14 out of the 20 // (10 predicates * 2 constants) possible combinations. Cases not handled here // require a 'not' of the LHS, so those must be transformed in InstCombine. if (match(RHS, m_Zero())) { switch (Pred) { case CmpInst::ICMP_NE: // X != 0 -> X case CmpInst::ICMP_UGT: // X >u 0 -> X case CmpInst::ICMP_SLT: // X X return LHS; case CmpInst::ICMP_ULT: // X false case CmpInst::ICMP_SGT: // X >s 0 -> false return getFalse(ITy); case CmpInst::ICMP_UGE: // X >=u 0 -> true case CmpInst::ICMP_SLE: // X <=s 0 -> true return getTrue(ITy); default: break; } } else if (match(RHS, m_One())) { switch (Pred) { case CmpInst::ICMP_EQ: // X == 1 -> X case CmpInst::ICMP_UGE: // X >=u 1 -> X case CmpInst::ICMP_SLE: // X <=s -1 -> X return LHS; case CmpInst::ICMP_UGT: // X >u 1 -> false case CmpInst::ICMP_SLT: // X false return getFalse(ITy); case CmpInst::ICMP_ULE: // X <=u 1 -> true case CmpInst::ICMP_SGE: // X >=s -1 -> true return getTrue(ITy); default: break; } } switch (Pred) { default: break; case ICmpInst::ICMP_UGE: if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false)) return getTrue(ITy); break; case ICmpInst::ICMP_SGE: /// For signed comparison, the values for an i1 are 0 and -1 /// respectively. This maps into a truth table of: /// LHS | RHS | LHS >=s RHS | LHS implies RHS /// 0 | 0 | 1 (0 >= 0) | 1 /// 0 | 1 | 1 (0 >= -1) | 1 /// 1 | 0 | 0 (-1 >= 0) | 0 /// 1 | 1 | 1 (-1 >= -1) | 1 if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false)) return getTrue(ITy); break; case ICmpInst::ICMP_ULE: if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false)) return getTrue(ITy); break; } return nullptr; } /// Try hard to fold icmp with zero RHS because this is a common case. static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q) { if (!match(RHS, m_Zero())) return nullptr; Type *ITy = GetCompareTy(LHS); // The return type. switch (Pred) { default: llvm_unreachable("Unknown ICmp predicate!"); case ICmpInst::ICMP_ULT: return getFalse(ITy); case ICmpInst::ICMP_UGE: return getTrue(ITy); case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE: if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return getFalse(ITy); break; case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGT: if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return getTrue(ITy); break; case ICmpInst::ICMP_SLT: { KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (LHSKnown.isNegative()) return getTrue(ITy); if (LHSKnown.isNonNegative()) return getFalse(ITy); break; } case ICmpInst::ICMP_SLE: { KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (LHSKnown.isNegative()) return getTrue(ITy); if (LHSKnown.isNonNegative() && isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return getFalse(ITy); break; } case ICmpInst::ICMP_SGE: { KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (LHSKnown.isNegative()) return getFalse(ITy); if (LHSKnown.isNonNegative()) return getTrue(ITy); break; } case ICmpInst::ICMP_SGT: { KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (LHSKnown.isNegative()) return getFalse(ITy); if (LHSKnown.isNonNegative() && isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) return getTrue(ITy); break; } } return nullptr; } /// Many binary operators with a constant operand have an easy-to-compute /// range of outputs. This can be used to fold a comparison to always true or /// always false. static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) { unsigned Width = Lower.getBitWidth(); const APInt *C; switch (BO.getOpcode()) { case Instruction::Add: if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { // FIXME: If we have both nuw and nsw, we should reduce the range further. if (BO.hasNoUnsignedWrap()) { // 'add nuw x, C' produces [C, UINT_MAX]. Lower = *C; } else if (BO.hasNoSignedWrap()) { if (C->isNegative()) { // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C]. Lower = APInt::getSignedMinValue(Width); Upper = APInt::getSignedMaxValue(Width) + *C + 1; } else { // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX]. Lower = APInt::getSignedMinValue(Width) + *C; Upper = APInt::getSignedMaxValue(Width) + 1; } } } break; case Instruction::And: if (match(BO.getOperand(1), m_APInt(C))) // 'and x, C' produces [0, C]. Upper = *C + 1; break; case Instruction::Or: if (match(BO.getOperand(1), m_APInt(C))) // 'or x, C' produces [C, UINT_MAX]. Lower = *C; break; case Instruction::AShr: if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C]. Lower = APInt::getSignedMinValue(Width).ashr(*C); Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1; } else if (match(BO.getOperand(0), m_APInt(C))) { unsigned ShiftAmount = Width - 1; if (!C->isNullValue() && BO.isExact()) ShiftAmount = C->countTrailingZeros(); if (C->isNegative()) { // 'ashr C, x' produces [C, C >> (Width-1)] Lower = *C; Upper = C->ashr(ShiftAmount) + 1; } else { // 'ashr C, x' produces [C >> (Width-1), C] Lower = C->ashr(ShiftAmount); Upper = *C + 1; } } break; case Instruction::LShr: if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { // 'lshr x, C' produces [0, UINT_MAX >> C]. Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1; } else if (match(BO.getOperand(0), m_APInt(C))) { // 'lshr C, x' produces [C >> (Width-1), C]. unsigned ShiftAmount = Width - 1; if (!C->isNullValue() && BO.isExact()) ShiftAmount = C->countTrailingZeros(); Lower = C->lshr(ShiftAmount); Upper = *C + 1; } break; case Instruction::Shl: if (match(BO.getOperand(0), m_APInt(C))) { if (BO.hasNoUnsignedWrap()) { // 'shl nuw C, x' produces [C, C << CLZ(C)] Lower = *C; Upper = Lower.shl(Lower.countLeadingZeros()) + 1; } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw? if (C->isNegative()) { // 'shl nsw C, x' produces [C << CLO(C)-1, C] unsigned ShiftAmount = C->countLeadingOnes() - 1; Lower = C->shl(ShiftAmount); Upper = *C + 1; } else { // 'shl nsw C, x' produces [C, C << CLZ(C)-1] unsigned ShiftAmount = C->countLeadingZeros() - 1; Lower = *C; Upper = C->shl(ShiftAmount) + 1; } } } break; case Instruction::SDiv: if (match(BO.getOperand(1), m_APInt(C))) { APInt IntMin = APInt::getSignedMinValue(Width); APInt IntMax = APInt::getSignedMaxValue(Width); if (C->isAllOnesValue()) { // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] // where C != -1 and C != 0 and C != 1 Lower = IntMin + 1; Upper = IntMax + 1; } else if (C->countLeadingZeros() < Width - 1) { // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C] // where C != -1 and C != 0 and C != 1 Lower = IntMin.sdiv(*C); Upper = IntMax.sdiv(*C); if (Lower.sgt(Upper)) std::swap(Lower, Upper); Upper = Upper + 1; assert(Upper != Lower && "Upper part of range has wrapped!"); } } else if (match(BO.getOperand(0), m_APInt(C))) { if (C->isMinSignedValue()) { // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. Lower = *C; Upper = Lower.lshr(1) + 1; } else { // 'sdiv C, x' produces [-|C|, |C|]. Upper = C->abs() + 1; Lower = (-Upper) + 1; } } break; case Instruction::UDiv: if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { // 'udiv x, C' produces [0, UINT_MAX / C]. Upper = APInt::getMaxValue(Width).udiv(*C) + 1; } else if (match(BO.getOperand(0), m_APInt(C))) { // 'udiv C, x' produces [0, C]. Upper = *C + 1; } break; case Instruction::SRem: if (match(BO.getOperand(1), m_APInt(C))) { // 'srem x, C' produces (-|C|, |C|). Upper = C->abs(); Lower = (-Upper) + 1; } break; case Instruction::URem: if (match(BO.getOperand(1), m_APInt(C))) // 'urem x, C' produces [0, C). Upper = *C; break; default: break; } } static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, Value *RHS) { const APInt *C; if (!match(RHS, m_APInt(C))) return nullptr; // Rule out tautological comparisons (eg., ult 0 or uge 0). ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C); if (RHS_CR.isEmptySet()) return ConstantInt::getFalse(GetCompareTy(RHS)); if (RHS_CR.isFullSet()) return ConstantInt::getTrue(GetCompareTy(RHS)); // Find the range of possible values for binary operators. unsigned Width = C->getBitWidth(); APInt Lower = APInt(Width, 0); APInt Upper = APInt(Width, 0); if (auto *BO = dyn_cast(LHS)) setLimitsForBinOp(*BO, Lower, Upper); ConstantRange LHS_CR = Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true); if (auto *I = dyn_cast(LHS)) if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges)); if (!LHS_CR.isFullSet()) { if (RHS_CR.contains(LHS_CR)) return ConstantInt::getTrue(GetCompareTy(RHS)); if (RHS_CR.inverse().contains(LHS_CR)) return ConstantInt::getFalse(GetCompareTy(RHS)); } return nullptr; } /// TODO: A large part of this logic is duplicated in InstCombine's /// foldICmpBinOp(). We should be able to share that and avoid the code /// duplication. static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { Type *ITy = GetCompareTy(LHS); // The return type. BinaryOperator *LBO = dyn_cast(LHS); BinaryOperator *RBO = dyn_cast(RHS); if (MaxRecurse && (LBO || RBO)) { // Analyze the case when either LHS or RHS is an add instruction. Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; if (LBO && LBO->getOpcode() == Instruction::Add) { A = LBO->getOperand(0); B = LBO->getOperand(1); NoLHSWrapProblem = ICmpInst::isEquality(Pred) || (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); } if (RBO && RBO->getOpcode() == Instruction::Add) { C = RBO->getOperand(0); D = RBO->getOperand(1); NoRHSWrapProblem = ICmpInst::isEquality(Pred) || (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); } // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. if ((A == RHS || B == RHS) && NoLHSWrapProblem) if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, Constant::getNullValue(RHS->getType()), Q, MaxRecurse - 1)) return V; // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. if ((C == LHS || D == LHS) && NoRHSWrapProblem) if (Value *V = SimplifyICmpInst(Pred, Constant::getNullValue(LHS->getType()), C == LHS ? D : C, Q, MaxRecurse - 1)) return V; // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem && NoRHSWrapProblem) { // Determine Y and Z in the form icmp (X+Y), (X+Z). Value *Y, *Z; if (A == C) { // C + B == C + D -> B == D Y = B; Z = D; } else if (A == D) { // D + B == C + D -> B == C Y = B; Z = C; } else if (B == C) { // A + C == C + D -> A == D Y = A; Z = D; } else { assert(B == D); // A + D == C + D -> A == C Y = A; Z = C; } if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1)) return V; } } { Value *Y = nullptr; // icmp pred (or X, Y), X if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) { if (Pred == ICmpInst::ICMP_ULT) return getFalse(ITy); if (Pred == ICmpInst::ICMP_UGE) return getTrue(ITy); if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) { KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (RHSKnown.isNonNegative() && YKnown.isNegative()) return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy); if (RHSKnown.isNegative() || YKnown.isNonNegative()) return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy); } } // icmp pred X, (or X, Y) if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) { if (Pred == ICmpInst::ICMP_ULE) return getTrue(ITy); if (Pred == ICmpInst::ICMP_UGT) return getFalse(ITy); if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) { KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (LHSKnown.isNonNegative() && YKnown.isNegative()) return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy); if (LHSKnown.isNegative() || YKnown.isNonNegative()) return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy); } } } // icmp pred (and X, Y), X if (LBO && match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) { if (Pred == ICmpInst::ICMP_UGT) return getFalse(ITy); if (Pred == ICmpInst::ICMP_ULE) return getTrue(ITy); } // icmp pred X, (and X, Y) if (RBO && match(RBO, m_c_And(m_Value(), m_Specific(LHS)))) { if (Pred == ICmpInst::ICMP_UGE) return getTrue(ITy); if (Pred == ICmpInst::ICMP_ULT) return getFalse(ITy); } // 0 - (zext X) pred C if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) { if (ConstantInt *RHSC = dyn_cast(RHS)) { if (RHSC->getValue().isStrictlyPositive()) { if (Pred == ICmpInst::ICMP_SLT) return ConstantInt::getTrue(RHSC->getContext()); if (Pred == ICmpInst::ICMP_SGE) return ConstantInt::getFalse(RHSC->getContext()); if (Pred == ICmpInst::ICMP_EQ) return ConstantInt::getFalse(RHSC->getContext()); if (Pred == ICmpInst::ICMP_NE) return ConstantInt::getTrue(RHSC->getContext()); } if (RHSC->getValue().isNonNegative()) { if (Pred == ICmpInst::ICMP_SLE) return ConstantInt::getTrue(RHSC->getContext()); if (Pred == ICmpInst::ICMP_SGT) return ConstantInt::getFalse(RHSC->getContext()); } } } // icmp pred (urem X, Y), Y if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { switch (Pred) { default: break; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: { KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (!Known.isNonNegative()) break; LLVM_FALLTHROUGH; } case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: return getFalse(ITy); case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: { KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (!Known.isNonNegative()) break; LLVM_FALLTHROUGH; } case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: return getTrue(ITy); } } // icmp pred X, (urem Y, X) if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { switch (Pred) { default: break; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: { KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (!Known.isNonNegative()) break; LLVM_FALLTHROUGH; } case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: return getTrue(ITy); case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: { KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT); if (!Known.isNonNegative()) break; LLVM_FALLTHROUGH; } case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: return getFalse(ITy); } } // x >> y <=u x // x udiv y <=u x. if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) || match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) { // icmp pred (X op Y), X if (Pred == ICmpInst::ICMP_UGT) return getFalse(ITy); if (Pred == ICmpInst::ICMP_ULE) return getTrue(ITy); } // x >=u x >> y // x >=u x udiv y. if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) || match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) { // icmp pred X, (X op Y) if (Pred == ICmpInst::ICMP_ULT) return getFalse(ITy); if (Pred == ICmpInst::ICMP_UGE) return getTrue(ITy); } // handle: // CI2 << X == CI // CI2 << X != CI // // where CI2 is a power of 2 and CI isn't if (auto *CI = dyn_cast(RHS)) { const APInt *CI2Val, *CIVal = &CI->getValue(); if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) && CI2Val->isPowerOf2()) { if (!CIVal->isPowerOf2()) { // CI2 << X can equal zero in some circumstances, // this simplification is unsafe if CI is zero. // // We know it is safe if: // - The shift is nsw, we can't shift out the one bit. // - The shift is nuw, we can't shift out the one bit. // - CI2 is one // - CI isn't zero if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() || CI2Val->isOneValue() || !CI->isZero()) { if (Pred == ICmpInst::ICMP_EQ) return ConstantInt::getFalse(RHS->getContext()); if (Pred == ICmpInst::ICMP_NE) return ConstantInt::getTrue(RHS->getContext()); } } if (CIVal->isSignMask() && CI2Val->isOneValue()) { if (Pred == ICmpInst::ICMP_UGT) return ConstantInt::getFalse(RHS->getContext()); if (Pred == ICmpInst::ICMP_ULE) return ConstantInt::getTrue(RHS->getContext()); } } } if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && LBO->getOperand(1) == RBO->getOperand(1)) { switch (LBO->getOpcode()) { default: break; case Instruction::UDiv: case Instruction::LShr: if (ICmpInst::isSigned(Pred) || !LBO->isExact() || !RBO->isExact()) break; if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), RBO->getOperand(0), Q, MaxRecurse - 1)) return V; break; case Instruction::SDiv: if (!ICmpInst::isEquality(Pred) || !LBO->isExact() || !RBO->isExact()) break; if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), RBO->getOperand(0), Q, MaxRecurse - 1)) return V; break; case Instruction::AShr: if (!LBO->isExact() || !RBO->isExact()) break; if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), RBO->getOperand(0), Q, MaxRecurse - 1)) return V; break; case Instruction::Shl: { bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); if (!NUW && !NSW) break; if (!NSW && ICmpInst::isSigned(Pred)) break; if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), RBO->getOperand(0), Q, MaxRecurse - 1)) return V; break; } } } return nullptr; } /// Simplify integer comparisons where at least one operand of the compare /// matches an integer min/max idiom. static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { Type *ITy = GetCompareTy(LHS); // The return type. Value *A, *B; CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". // Signed variants on "max(a,b)>=a -> true". if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { if (A != RHS) std::swap(A, B); // smax(A, B) pred A. EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". // We analyze this as smax(A, B) pred A. P = Pred; } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && (A == LHS || B == LHS)) { if (A != LHS) std::swap(A, B); // A pred smax(A, B). EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". // We analyze this as smax(A, B) swapped-pred A. P = CmpInst::getSwappedPredicate(Pred); } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { if (A != RHS) std::swap(A, B); // smin(A, B) pred A. EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". // We analyze this as smax(-A, -B) swapped-pred -A. // Note that we do not need to actually form -A or -B thanks to EqP. P = CmpInst::getSwappedPredicate(Pred); } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && (A == LHS || B == LHS)) { if (A != LHS) std::swap(A, B); // A pred smin(A, B). EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". // We analyze this as smax(-A, -B) pred -A. // Note that we do not need to actually form -A or -B thanks to EqP. P = Pred; } if (P != CmpInst::BAD_ICMP_PREDICATE) { // Cases correspond to "max(A, B) p A". switch (P) { default: break; case CmpInst::ICMP_EQ: case CmpInst::ICMP_SLE: // Equivalent to "A EqP B". This may be the same as the condition tested // in the max/min; if so, we can just return that. if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) return V; if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) return V; // Otherwise, see if "A EqP B" simplifies. if (MaxRecurse) if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1)) return V; break; case CmpInst::ICMP_NE: case CmpInst::ICMP_SGT: { CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); // Equivalent to "A InvEqP B". This may be the same as the condition // tested in the max/min; if so, we can just return that. if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) return V; if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) return V; // Otherwise, see if "A InvEqP B" simplifies. if (MaxRecurse) if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1)) return V; break; } case CmpInst::ICMP_SGE: // Always true. return getTrue(ITy); case CmpInst::ICMP_SLT: // Always false. return getFalse(ITy); } } // Unsigned variants on "max(a,b)>=a -> true". P = CmpInst::BAD_ICMP_PREDICATE; if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { if (A != RHS) std::swap(A, B); // umax(A, B) pred A. EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". // We analyze this as umax(A, B) pred A. P = Pred; } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && (A == LHS || B == LHS)) { if (A != LHS) std::swap(A, B); // A pred umax(A, B). EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". // We analyze this as umax(A, B) swapped-pred A. P = CmpInst::getSwappedPredicate(Pred); } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { if (A != RHS) std::swap(A, B); // umin(A, B) pred A. EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". // We analyze this as umax(-A, -B) swapped-pred -A. // Note that we do not need to actually form -A or -B thanks to EqP. P = CmpInst::getSwappedPredicate(Pred); } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && (A == LHS || B == LHS)) { if (A != LHS) std::swap(A, B); // A pred umin(A, B). EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". // We analyze this as umax(-A, -B) pred -A. // Note that we do not need to actually form -A or -B thanks to EqP. P = Pred; } if (P != CmpInst::BAD_ICMP_PREDICATE) { // Cases correspond to "max(A, B) p A". switch (P) { default: break; case CmpInst::ICMP_EQ: case CmpInst::ICMP_ULE: // Equivalent to "A EqP B". This may be the same as the condition tested // in the max/min; if so, we can just return that. if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) return V; if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) return V; // Otherwise, see if "A EqP B" simplifies. if (MaxRecurse) if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1)) return V; break; case CmpInst::ICMP_NE: case CmpInst::ICMP_UGT: { CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); // Equivalent to "A InvEqP B". This may be the same as the condition // tested in the max/min; if so, we can just return that. if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) return V; if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) return V; // Otherwise, see if "A InvEqP B" simplifies. if (MaxRecurse) if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1)) return V; break; } case CmpInst::ICMP_UGE: // Always true. return getTrue(ITy); case CmpInst::ICMP_ULT: // Always false. return getFalse(ITy); } } // Variants on "max(x,y) >= min(x,z)". Value *C, *D; if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && match(RHS, m_SMin(m_Value(C), m_Value(D))) && (A == C || A == D || B == C || B == D)) { // max(x, ?) pred min(x, ?). if (Pred == CmpInst::ICMP_SGE) // Always true. return getTrue(ITy); if (Pred == CmpInst::ICMP_SLT) // Always false. return getFalse(ITy); } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && match(RHS, m_SMax(m_Value(C), m_Value(D))) && (A == C || A == D || B == C || B == D)) { // min(x, ?) pred max(x, ?). if (Pred == CmpInst::ICMP_SLE) // Always true. return getTrue(ITy); if (Pred == CmpInst::ICMP_SGT) // Always false. return getFalse(ITy); } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && match(RHS, m_UMin(m_Value(C), m_Value(D))) && (A == C || A == D || B == C || B == D)) { // max(x, ?) pred min(x, ?). if (Pred == CmpInst::ICMP_UGE) // Always true. return getTrue(ITy); if (Pred == CmpInst::ICMP_ULT) // Always false. return getFalse(ITy); } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && match(RHS, m_UMax(m_Value(C), m_Value(D))) && (A == C || A == D || B == C || B == D)) { // min(x, ?) pred max(x, ?). if (Pred == CmpInst::ICMP_ULE) // Always true. return getTrue(ITy); if (Pred == CmpInst::ICMP_UGT) // Always false. return getFalse(ITy); } return nullptr; } /// Given operands for an ICmpInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); if (Constant *CLHS = dyn_cast(LHS)) { if (Constant *CRHS = dyn_cast(RHS)) return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); // If we have a constant, make sure it is on the RHS. std::swap(LHS, RHS); Pred = CmpInst::getSwappedPredicate(Pred); } Type *ITy = GetCompareTy(LHS); // The return type. // icmp X, X -> true/false // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false // because X could be 0. if (LHS == RHS || isa(RHS)) return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q)) return V; if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q)) return V; if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS)) return V; // If both operands have range metadata, use the metadata // to simplify the comparison. if (isa(RHS) && isa(LHS)) { auto RHS_Instr = cast(RHS); auto LHS_Instr = cast(LHS); if (RHS_Instr->getMetadata(LLVMContext::MD_range) && LHS_Instr->getMetadata(LLVMContext::MD_range)) { auto RHS_CR = getConstantRangeFromMetadata( *RHS_Instr->getMetadata(LLVMContext::MD_range)); auto LHS_CR = getConstantRangeFromMetadata( *LHS_Instr->getMetadata(LLVMContext::MD_range)); auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR); if (Satisfied_CR.contains(LHS_CR)) return ConstantInt::getTrue(RHS->getContext()); auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion( CmpInst::getInversePredicate(Pred), RHS_CR); if (InversedSatisfied_CR.contains(LHS_CR)) return ConstantInt::getFalse(RHS->getContext()); } } // Compare of cast, for example (zext X) != 0 -> X != 0 if (isa(LHS) && (isa(RHS) || isa(RHS))) { Instruction *LI = cast(LHS); Value *SrcOp = LI->getOperand(0); Type *SrcTy = SrcOp->getType(); Type *DstTy = LI->getType(); // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input // if the integer type is the same size as the pointer type. if (MaxRecurse && isa(LI) && Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { if (Constant *RHSC = dyn_cast(RHS)) { // Transfer the cast to the constant. if (Value *V = SimplifyICmpInst(Pred, SrcOp, ConstantExpr::getIntToPtr(RHSC, SrcTy), Q, MaxRecurse-1)) return V; } else if (PtrToIntInst *RI = dyn_cast(RHS)) { if (RI->getOperand(0)->getType() == SrcTy) // Compare without the cast. if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), Q, MaxRecurse-1)) return V; } } if (isa(LHS)) { // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the // same type. if (ZExtInst *RI = dyn_cast(RHS)) { if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) // Compare X and Y. Note that signed predicates become unsigned. if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), SrcOp, RI->getOperand(0), Q, MaxRecurse-1)) return V; } // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended // too. If not, then try to deduce the result of the comparison. else if (ConstantInt *CI = dyn_cast(RHS)) { // Compute the constant that would happen if we truncated to SrcTy then // reextended to DstTy. Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); // If the re-extended constant didn't change then this is effectively // also a case of comparing two zero-extended values. if (RExt == CI && MaxRecurse) if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), SrcOp, Trunc, Q, MaxRecurse-1)) return V; // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit // there. Use this to work out the result of the comparison. if (RExt != CI) { switch (Pred) { default: llvm_unreachable("Unknown ICmp predicate!"); // LHS getContext()); case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: return ConstantInt::getTrue(CI->getContext()); // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS // is non-negative then LHS getValue().isNegative() ? ConstantInt::getTrue(CI->getContext()) : ConstantInt::getFalse(CI->getContext()); case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: return CI->getValue().isNegative() ? ConstantInt::getFalse(CI->getContext()) : ConstantInt::getTrue(CI->getContext()); } } } } if (isa(LHS)) { // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the // same type. if (SExtInst *RI = dyn_cast(RHS)) { if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) // Compare X and Y. Note that the predicate does not change. if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), Q, MaxRecurse-1)) return V; } // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended // too. If not, then try to deduce the result of the comparison. else if (ConstantInt *CI = dyn_cast(RHS)) { // Compute the constant that would happen if we truncated to SrcTy then // reextended to DstTy. Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); // If the re-extended constant didn't change then this is effectively // also a case of comparing two sign-extended values. if (RExt == CI && MaxRecurse) if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1)) return V; // Otherwise the upper bits of LHS are all equal, while RHS has varying // bits there. Use this to work out the result of the comparison. if (RExt != CI) { switch (Pred) { default: llvm_unreachable("Unknown ICmp predicate!"); case ICmpInst::ICMP_EQ: return ConstantInt::getFalse(CI->getContext()); case ICmpInst::ICMP_NE: return ConstantInt::getTrue(CI->getContext()); // If RHS is non-negative then LHS s RHS. case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: return CI->getValue().isNegative() ? ConstantInt::getTrue(CI->getContext()) : ConstantInt::getFalse(CI->getContext()); case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: return CI->getValue().isNegative() ? ConstantInt::getFalse(CI->getContext()) : ConstantInt::getTrue(CI->getContext()); // If LHS is non-negative then LHS u RHS. case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: // Comparison is true iff the LHS =s 0. if (MaxRecurse) if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, Constant::getNullValue(SrcTy), Q, MaxRecurse-1)) return V; break; } } } } } // icmp eq|ne X, Y -> false|true if X != Y if (ICmpInst::isEquality(Pred) && isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) { return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy); } if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse)) return V; if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse)) return V; // Simplify comparisons of related pointers using a powerful, recursive // GEP-walk when we have target data available.. if (LHS->getType()->isPointerTy()) if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI, LHS, RHS)) return C; if (auto *CLHS = dyn_cast(LHS)) if (auto *CRHS = dyn_cast(RHS)) if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) == Q.DL.getTypeSizeInBits(CLHS->getType()) && Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) == Q.DL.getTypeSizeInBits(CRHS->getType())) if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI, CLHS->getPointerOperand(), CRHS->getPointerOperand())) return C; if (GetElementPtrInst *GLHS = dyn_cast(LHS)) { if (GEPOperator *GRHS = dyn_cast(RHS)) { if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() && (ICmpInst::isEquality(Pred) || (GLHS->isInBounds() && GRHS->isInBounds() && Pred == ICmpInst::getSignedPredicate(Pred)))) { // The bases are equal and the indices are constant. Build a constant // expression GEP with the same indices and a null base pointer to see // what constant folding can make out of it. Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); SmallVector IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); Constant *NewLHS = ConstantExpr::getGetElementPtr( GLHS->getSourceElementType(), Null, IndicesLHS); SmallVector IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); Constant *NewRHS = ConstantExpr::getGetElementPtr( GLHS->getSourceElementType(), Null, IndicesRHS); return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); } } } // If the comparison is with the result of a select instruction, check whether // comparing with either branch of the select always yields the same value. if (isa(LHS) || isa(RHS)) if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) return V; // If the comparison is with the result of a phi instruction, check whether // doing the compare with each incoming phi value yields a common result. if (isa(LHS) || isa(RHS)) if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q) { return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit); } /// Given operands for an FCmpInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q, unsigned MaxRecurse) { CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); if (Constant *CLHS = dyn_cast(LHS)) { if (Constant *CRHS = dyn_cast(RHS)) return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); // If we have a constant, make sure it is on the RHS. std::swap(LHS, RHS); Pred = CmpInst::getSwappedPredicate(Pred); } // Fold trivial predicates. Type *RetTy = GetCompareTy(LHS); if (Pred == FCmpInst::FCMP_FALSE) return getFalse(RetTy); if (Pred == FCmpInst::FCMP_TRUE) return getTrue(RetTy); // UNO/ORD predicates can be trivially folded if NaNs are ignored. if (FMF.noNaNs()) { if (Pred == FCmpInst::FCMP_UNO) return getFalse(RetTy); if (Pred == FCmpInst::FCMP_ORD) return getTrue(RetTy); } // fcmp pred x, undef and fcmp pred undef, x // fold to true if unordered, false if ordered if (isa(LHS) || isa(RHS)) { // Choosing NaN for the undef will always make unordered comparison succeed // and ordered comparison fail. return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred)); } // fcmp x,x -> true/false. Not all compares are foldable. if (LHS == RHS) { if (CmpInst::isTrueWhenEqual(Pred)) return getTrue(RetTy); if (CmpInst::isFalseWhenEqual(Pred)) return getFalse(RetTy); } // Handle fcmp with constant RHS. const APFloat *C; if (match(RHS, m_APFloat(C))) { // If the constant is a nan, see if we can fold the comparison based on it. if (C->isNaN()) { if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" return getFalse(RetTy); assert(FCmpInst::isUnordered(Pred) && "Comparison must be either ordered or unordered!"); // True if unordered. return getTrue(RetTy); } // Check whether the constant is an infinity. if (C->isInfinity()) { if (C->isNegative()) { switch (Pred) { case FCmpInst::FCMP_OLT: // No value is ordered and less than negative infinity. return getFalse(RetTy); case FCmpInst::FCMP_UGE: // All values are unordered with or at least negative infinity. return getTrue(RetTy); default: break; } } else { switch (Pred) { case FCmpInst::FCMP_OGT: // No value is ordered and greater than infinity. return getFalse(RetTy); case FCmpInst::FCMP_ULE: // All values are unordered with and at most infinity. return getTrue(RetTy); default: break; } } } if (C->isZero()) { switch (Pred) { case FCmpInst::FCMP_UGE: if (CannotBeOrderedLessThanZero(LHS, Q.TLI)) return getTrue(RetTy); break; case FCmpInst::FCMP_OLT: // X < 0 if (CannotBeOrderedLessThanZero(LHS, Q.TLI)) return getFalse(RetTy); break; default: break; } } else if (C->isNegative()) { assert(!C->isNaN() && "Unexpected NaN constant!"); // TODO: We can catch more cases by using a range check rather than // relying on CannotBeOrderedLessThanZero. switch (Pred) { case FCmpInst::FCMP_UGE: case FCmpInst::FCMP_UGT: case FCmpInst::FCMP_UNE: // (X >= 0) implies (X > C) when (C < 0) if (CannotBeOrderedLessThanZero(LHS, Q.TLI)) return getTrue(RetTy); break; case FCmpInst::FCMP_OEQ: case FCmpInst::FCMP_OLE: case FCmpInst::FCMP_OLT: // (X >= 0) implies !(X < C) when (C < 0) if (CannotBeOrderedLessThanZero(LHS, Q.TLI)) return getFalse(RetTy); break; default: break; } } } // If the comparison is with the result of a select instruction, check whether // comparing with either branch of the select always yields the same value. if (isa(LHS) || isa(RHS)) if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) return V; // If the comparison is with the result of a phi instruction, check whether // doing the compare with each incoming phi value yields a common result. if (isa(LHS) || isa(RHS)) if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit); } /// See if V simplifies when its operand Op is replaced with RepOp. static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, const SimplifyQuery &Q, unsigned MaxRecurse) { // Trivial replacement. if (V == Op) return RepOp; // We cannot replace a constant, and shouldn't even try. if (isa(Op)) return nullptr; auto *I = dyn_cast(V); if (!I) return nullptr; // If this is a binary operator, try to simplify it with the replaced op. if (auto *B = dyn_cast(I)) { // Consider: // %cmp = icmp eq i32 %x, 2147483647 // %add = add nsw i32 %x, 1 // %sel = select i1 %cmp, i32 -2147483648, i32 %add // // We can't replace %sel with %add unless we strip away the flags. if (isa(B)) if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap()) return nullptr; if (isa(B)) if (B->isExact()) return nullptr; if (MaxRecurse) { if (B->getOperand(0) == Op) return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q, MaxRecurse - 1); if (B->getOperand(1) == Op) return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q, MaxRecurse - 1); } } // Same for CmpInsts. if (CmpInst *C = dyn_cast(I)) { if (MaxRecurse) { if (C->getOperand(0) == Op) return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q, MaxRecurse - 1); if (C->getOperand(1) == Op) return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q, MaxRecurse - 1); } } // TODO: We could hand off more cases to instsimplify here. // If all operands are constant after substituting Op for RepOp then we can // constant fold the instruction. if (Constant *CRepOp = dyn_cast(RepOp)) { // Build a list of all constant operands. SmallVector ConstOps; for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { if (I->getOperand(i) == Op) ConstOps.push_back(CRepOp); else if (Constant *COp = dyn_cast(I->getOperand(i))) ConstOps.push_back(COp); else break; } // All operands were constants, fold it. if (ConstOps.size() == I->getNumOperands()) { if (CmpInst *C = dyn_cast(I)) return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0], ConstOps[1], Q.DL, Q.TLI); if (LoadInst *LI = dyn_cast(I)) if (!LI->isVolatile()) return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL); return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI); } } return nullptr; } /// Try to simplify a select instruction when its condition operand is an /// integer comparison where one operand of the compare is a constant. static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X, const APInt *Y, bool TrueWhenUnset) { const APInt *C; // (X & Y) == 0 ? X & ~Y : X --> X // (X & Y) != 0 ? X & ~Y : X --> X & ~Y if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) && *Y == ~*C) return TrueWhenUnset ? FalseVal : TrueVal; // (X & Y) == 0 ? X : X & ~Y --> X & ~Y // (X & Y) != 0 ? X : X & ~Y --> X if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) && *Y == ~*C) return TrueWhenUnset ? FalseVal : TrueVal; if (Y->isPowerOf2()) { // (X & Y) == 0 ? X | Y : X --> X | Y // (X & Y) != 0 ? X | Y : X --> X if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) && *Y == *C) return TrueWhenUnset ? TrueVal : FalseVal; // (X & Y) == 0 ? X : X | Y --> X // (X & Y) != 0 ? X : X | Y --> X | Y if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) && *Y == *C) return TrueWhenUnset ? TrueVal : FalseVal; } return nullptr; } /// An alternative way to test if a bit is set or not uses sgt/slt instead of /// eq/ne. static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS, ICmpInst::Predicate Pred, Value *TrueVal, Value *FalseVal) { Value *X; APInt Mask; if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask)) return nullptr; return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask, Pred == ICmpInst::ICMP_EQ); } /// Try to simplify a select instruction when its condition operand is an /// integer comparison. static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q, unsigned MaxRecurse) { ICmpInst::Predicate Pred; Value *CmpLHS, *CmpRHS; if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS)))) return nullptr; if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) { Value *X; const APInt *Y; if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y)))) if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y, Pred == ICmpInst::ICMP_EQ)) return V; } // Check for other compares that behave like bit test. if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred, TrueVal, FalseVal)) return V; if (CondVal->hasOneUse()) { const APInt *C; if (match(CmpRHS, m_APInt(C))) { // X < MIN ? T : F --> F if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue()) return FalseVal; // X < MIN ? T : F --> F if (Pred == ICmpInst::ICMP_ULT && C->isMinValue()) return FalseVal; // X > MAX ? T : F --> F if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue()) return FalseVal; // X > MAX ? T : F --> F if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue()) return FalseVal; } } // If we have an equality comparison, then we know the value in one of the // arms of the select. See if substituting this value into the arm and // simplifying the result yields the same value as the other arm. if (Pred == ICmpInst::ICMP_EQ) { if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == TrueVal || SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == TrueVal) return FalseVal; if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == FalseVal || SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == FalseVal) return FalseVal; } else if (Pred == ICmpInst::ICMP_NE) { if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == FalseVal || SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == FalseVal) return TrueVal; if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == TrueVal || SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == TrueVal) return TrueVal; } return nullptr; } /// Given operands for a SelectInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q, unsigned MaxRecurse) { // select true, X, Y -> X // select false, X, Y -> Y if (Constant *CB = dyn_cast(CondVal)) { if (Constant *CT = dyn_cast(TrueVal)) if (Constant *CF = dyn_cast(FalseVal)) return ConstantFoldSelectInstruction(CB, CT, CF); if (CB->isAllOnesValue()) return TrueVal; if (CB->isNullValue()) return FalseVal; } // select C, X, X -> X if (TrueVal == FalseVal) return TrueVal; if (isa(CondVal)) { // select undef, X, Y -> X or Y if (isa(FalseVal)) return FalseVal; return TrueVal; } if (isa(TrueVal)) // select C, undef, X -> X return FalseVal; if (isa(FalseVal)) // select C, X, undef -> X return TrueVal; if (Value *V = simplifySelectWithICmpCond(CondVal, TrueVal, FalseVal, Q, MaxRecurse)) return V; return nullptr; } Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q) { return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit); } /// Given operands for an GetElementPtrInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef Ops, const SimplifyQuery &Q, unsigned) { // The type of the GEP pointer operand. unsigned AS = cast(Ops[0]->getType()->getScalarType())->getAddressSpace(); // getelementptr P -> P. if (Ops.size() == 1) return Ops[0]; // Compute the (pointer) type returned by the GEP instruction. Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1)); Type *GEPTy = PointerType::get(LastType, AS); if (VectorType *VT = dyn_cast(Ops[0]->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); else if (VectorType *VT = dyn_cast(Ops[1]->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); if (isa(Ops[0])) return UndefValue::get(GEPTy); if (Ops.size() == 2) { // getelementptr P, 0 -> P. - if (match(Ops[1], m_Zero())) + if (match(Ops[1], m_Zero()) && Ops[0]->getType() == GEPTy) return Ops[0]; Type *Ty = SrcTy; if (Ty->isSized()) { Value *P; uint64_t C; uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty); // getelementptr P, N -> P if P points to a type of zero size. - if (TyAllocSize == 0) + if (TyAllocSize == 0 && Ops[0]->getType() == GEPTy) return Ops[0]; // The following transforms are only safe if the ptrtoint cast // doesn't truncate the pointers. if (Ops[1]->getType()->getScalarSizeInBits() == Q.DL.getPointerSizeInBits(AS)) { auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { if (match(P, m_Zero())) return Constant::getNullValue(GEPTy); Value *Temp; if (match(P, m_PtrToInt(m_Value(Temp)))) if (Temp->getType() == GEPTy) return Temp; return nullptr; }; // getelementptr V, (sub P, V) -> P if P points to a type of size 1. if (TyAllocSize == 1 && match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))))) if (Value *R = PtrToIntOrZero(P)) return R; // getelementptr V, (ashr (sub P, V), C) -> Q // if P points to a type of size 1 << C. if (match(Ops[1], m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), m_ConstantInt(C))) && TyAllocSize == 1ULL << C) if (Value *R = PtrToIntOrZero(P)) return R; // getelementptr V, (sdiv (sub P, V), C) -> Q // if P points to a type of size C. if (match(Ops[1], m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))), m_SpecificInt(TyAllocSize)))) if (Value *R = PtrToIntOrZero(P)) return R; } } } if (Q.DL.getTypeAllocSize(LastType) == 1 && all_of(Ops.slice(1).drop_back(1), [](Value *Idx) { return match(Idx, m_Zero()); })) { unsigned PtrWidth = Q.DL.getPointerSizeInBits(Ops[0]->getType()->getPointerAddressSpace()); if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == PtrWidth) { APInt BasePtrOffset(PtrWidth, 0); Value *StrippedBasePtr = Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL, BasePtrOffset); // gep (gep V, C), (sub 0, V) -> C if (match(Ops.back(), m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) { auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset); return ConstantExpr::getIntToPtr(CI, GEPTy); } // gep (gep V, C), (xor V, -1) -> C-1 if (match(Ops.back(), m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) { auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1); return ConstantExpr::getIntToPtr(CI, GEPTy); } } } // Check to see if this is constant foldable. if (!all_of(Ops, [](Value *V) { return isa(V); })) return nullptr; auto *CE = ConstantExpr::getGetElementPtr(SrcTy, cast(Ops[0]), Ops.slice(1)); if (auto *CEFolded = ConstantFoldConstant(CE, Q.DL)) return CEFolded; return CE; } Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef Ops, const SimplifyQuery &Q) { return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit); } /// Given operands for an InsertValueInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef Idxs, const SimplifyQuery &Q, unsigned) { if (Constant *CAgg = dyn_cast(Agg)) if (Constant *CVal = dyn_cast(Val)) return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); // insertvalue x, undef, n -> x if (match(Val, m_Undef())) return Agg; // insertvalue x, (extractvalue y, n), n if (ExtractValueInst *EV = dyn_cast(Val)) if (EV->getAggregateOperand()->getType() == Agg->getType() && EV->getIndices() == Idxs) { // insertvalue undef, (extractvalue y, n), n -> y if (match(Agg, m_Undef())) return EV->getAggregateOperand(); // insertvalue y, (extractvalue y, n), n -> y if (Agg == EV->getAggregateOperand()) return Agg; } return nullptr; } Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef Idxs, const SimplifyQuery &Q) { return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit); } Value *llvm::SimplifyInsertElementInst(Value *Vec, Value *Val, Value *Idx, const SimplifyQuery &Q) { // Try to constant fold. auto *VecC = dyn_cast(Vec); auto *ValC = dyn_cast(Val); auto *IdxC = dyn_cast(Idx); if (VecC && ValC && IdxC) return ConstantFoldInsertElementInstruction(VecC, ValC, IdxC); // Fold into undef if index is out of bounds. if (auto *CI = dyn_cast(Idx)) { uint64_t NumElements = cast(Vec->getType())->getNumElements(); if (CI->uge(NumElements)) return UndefValue::get(Vec->getType()); } // If index is undef, it might be out of bounds (see above case) if (isa(Idx)) return UndefValue::get(Vec->getType()); return nullptr; } /// Given operands for an ExtractValueInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef Idxs, const SimplifyQuery &, unsigned) { if (auto *CAgg = dyn_cast(Agg)) return ConstantFoldExtractValueInstruction(CAgg, Idxs); // extractvalue x, (insertvalue y, elt, n), n -> elt unsigned NumIdxs = Idxs.size(); for (auto *IVI = dyn_cast(Agg); IVI != nullptr; IVI = dyn_cast(IVI->getAggregateOperand())) { ArrayRef InsertValueIdxs = IVI->getIndices(); unsigned NumInsertValueIdxs = InsertValueIdxs.size(); unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs); if (InsertValueIdxs.slice(0, NumCommonIdxs) == Idxs.slice(0, NumCommonIdxs)) { if (NumIdxs == NumInsertValueIdxs) return IVI->getInsertedValueOperand(); break; } } return nullptr; } Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef Idxs, const SimplifyQuery &Q) { return ::SimplifyExtractValueInst(Agg, Idxs, Q, RecursionLimit); } /// Given operands for an ExtractElementInst, see if we can fold the result. /// If not, this returns null. static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &, unsigned) { if (auto *CVec = dyn_cast(Vec)) { if (auto *CIdx = dyn_cast(Idx)) return ConstantFoldExtractElementInstruction(CVec, CIdx); // The index is not relevant if our vector is a splat. if (auto *Splat = CVec->getSplatValue()) return Splat; if (isa(Vec)) return UndefValue::get(Vec->getType()->getVectorElementType()); } // If extracting a specified index from the vector, see if we can recursively // find a previously computed scalar that was inserted into the vector. if (auto *IdxC = dyn_cast(Idx)) { if (IdxC->getValue().uge(Vec->getType()->getVectorNumElements())) // definitely out of bounds, thus undefined result return UndefValue::get(Vec->getType()->getVectorElementType()); if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue())) return Elt; } // An undef extract index can be arbitrarily chosen to be an out-of-range // index value, which would result in the instruction being undef. if (isa(Idx)) return UndefValue::get(Vec->getType()->getVectorElementType()); return nullptr; } Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &Q) { return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit); } /// See if we can fold the given phi. If not, returns null. static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) { // If all of the PHI's incoming values are the same then replace the PHI node // with the common value. Value *CommonValue = nullptr; bool HasUndefInput = false; for (Value *Incoming : PN->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PN) continue; if (isa(Incoming)) { // Remember that we saw an undef value, but otherwise ignore them. HasUndefInput = true; continue; } if (CommonValue && Incoming != CommonValue) return nullptr; // Not the same, bail out. CommonValue = Incoming; } // If CommonValue is null then all of the incoming values were either undef or // equal to the phi node itself. if (!CommonValue) return UndefValue::get(PN->getType()); // If we have a PHI node like phi(X, undef, X), where X is defined by some // instruction, we cannot return X as the result of the PHI node unless it // dominates the PHI block. if (HasUndefInput) return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr; return CommonValue; } static Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) { if (auto *C = dyn_cast(Op)) return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL); if (auto *CI = dyn_cast(Op)) { auto *Src = CI->getOperand(0); Type *SrcTy = Src->getType(); Type *MidTy = CI->getType(); Type *DstTy = Ty; if (Src->getType() == Ty) { auto FirstOp = static_cast(CI->getOpcode()); auto SecondOp = static_cast(CastOpc); Type *SrcIntPtrTy = SrcTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(SrcTy) : nullptr; Type *MidIntPtrTy = MidTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(MidTy) : nullptr; Type *DstIntPtrTy = DstTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(DstTy) : nullptr; if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy, SrcIntPtrTy, MidIntPtrTy, DstIntPtrTy) == Instruction::BitCast) return Src; } } // bitcast x -> x if (CastOpc == Instruction::BitCast) if (Op->getType() == Ty) return Op; return nullptr; } Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q) { return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit); } /// For the given destination element of a shuffle, peek through shuffles to /// match a root vector source operand that contains that element in the same /// vector lane (ie, the same mask index), so we can eliminate the shuffle(s). static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1, int MaskVal, Value *RootVec, unsigned MaxRecurse) { if (!MaxRecurse--) return nullptr; // Bail out if any mask value is undefined. That kind of shuffle may be // simplified further based on demanded bits or other folds. if (MaskVal == -1) return nullptr; // The mask value chooses which source operand we need to look at next. int InVecNumElts = Op0->getType()->getVectorNumElements(); int RootElt = MaskVal; Value *SourceOp = Op0; if (MaskVal >= InVecNumElts) { RootElt = MaskVal - InVecNumElts; SourceOp = Op1; } // If the source operand is a shuffle itself, look through it to find the // matching root vector. if (auto *SourceShuf = dyn_cast(SourceOp)) { return foldIdentityShuffles( DestElt, SourceShuf->getOperand(0), SourceShuf->getOperand(1), SourceShuf->getMaskValue(RootElt), RootVec, MaxRecurse); } // TODO: Look through bitcasts? What if the bitcast changes the vector element // size? // The source operand is not a shuffle. Initialize the root vector value for // this shuffle if that has not been done yet. if (!RootVec) RootVec = SourceOp; // Give up as soon as a source operand does not match the existing root value. if (RootVec != SourceOp) return nullptr; // The element must be coming from the same lane in the source vector // (although it may have crossed lanes in intermediate shuffles). if (RootElt != DestElt) return nullptr; return RootVec; } static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q, unsigned MaxRecurse) { if (isa(Mask)) return UndefValue::get(RetTy); Type *InVecTy = Op0->getType(); unsigned MaskNumElts = Mask->getType()->getVectorNumElements(); unsigned InVecNumElts = InVecTy->getVectorNumElements(); SmallVector Indices; ShuffleVectorInst::getShuffleMask(Mask, Indices); assert(MaskNumElts == Indices.size() && "Size of Indices not same as number of mask elements?"); // Canonicalization: If mask does not select elements from an input vector, // replace that input vector with undef. bool MaskSelects0 = false, MaskSelects1 = false; for (unsigned i = 0; i != MaskNumElts; ++i) { if (Indices[i] == -1) continue; if ((unsigned)Indices[i] < InVecNumElts) MaskSelects0 = true; else MaskSelects1 = true; } if (!MaskSelects0) Op0 = UndefValue::get(InVecTy); if (!MaskSelects1) Op1 = UndefValue::get(InVecTy); auto *Op0Const = dyn_cast(Op0); auto *Op1Const = dyn_cast(Op1); // If all operands are constant, constant fold the shuffle. if (Op0Const && Op1Const) return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask); // Canonicalization: if only one input vector is constant, it shall be the // second one. if (Op0Const && !Op1Const) { std::swap(Op0, Op1); ShuffleVectorInst::commuteShuffleMask(Indices, InVecNumElts); } // A shuffle of a splat is always the splat itself. Legal if the shuffle's // value type is same as the input vectors' type. if (auto *OpShuf = dyn_cast(Op0)) if (isa(Op1) && RetTy == InVecTy && OpShuf->getMask()->getSplatValue()) return Op0; // Don't fold a shuffle with undef mask elements. This may get folded in a // better way using demanded bits or other analysis. // TODO: Should we allow this? if (find(Indices, -1) != Indices.end()) return nullptr; // Check if every element of this shuffle can be mapped back to the // corresponding element of a single root vector. If so, we don't need this // shuffle. This handles simple identity shuffles as well as chains of // shuffles that may widen/narrow and/or move elements across lanes and back. Value *RootVec = nullptr; for (unsigned i = 0; i != MaskNumElts; ++i) { // Note that recursion is limited for each vector element, so if any element // exceeds the limit, this will fail to simplify. RootVec = foldIdentityShuffles(i, Op0, Op1, Indices[i], RootVec, MaxRecurse); // We can't replace a widening/narrowing shuffle with one of its operands. if (!RootVec || RootVec->getType() != RetTy) return nullptr; } return RootVec; } /// Given operands for a ShuffleVectorInst, fold the result or return null. Value *llvm::SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q) { return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit); } /// Given operands for an FAdd, see if we can fold the result. If not, this /// returns null. static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q)) return C; // fadd X, -0 ==> X if (match(Op1, m_NegZero())) return Op0; // fadd X, 0 ==> X, when we know X is not -0 if (match(Op1, m_Zero()) && (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI))) return Op0; // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 // where nnan and ninf have to occur at least once somewhere in this // expression Value *SubOp = nullptr; if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) SubOp = Op1; else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) SubOp = Op0; if (SubOp) { Instruction *FSub = cast(SubOp); if ((FMF.noNaNs() || FSub->hasNoNaNs()) && (FMF.noInfs() || FSub->hasNoInfs())) return Constant::getNullValue(Op0->getType()); } return nullptr; } /// Given operands for an FSub, see if we can fold the result. If not, this /// returns null. static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q)) return C; // fsub X, 0 ==> X if (match(Op1, m_Zero())) return Op0; // fsub X, -0 ==> X, when we know X is not -0 if (match(Op1, m_NegZero()) && (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI))) return Op0; // fsub -0.0, (fsub -0.0, X) ==> X Value *X; if (match(Op0, m_NegZero()) && match(Op1, m_FSub(m_NegZero(), m_Value(X)))) return X; // fsub 0.0, (fsub 0.0, X) ==> X if signed zeros are ignored. if (FMF.noSignedZeros() && match(Op0, m_AnyZero()) && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) return X; // fsub nnan x, x ==> 0.0 if (FMF.noNaNs() && Op0 == Op1) return Constant::getNullValue(Op0->getType()); return nullptr; } /// Given the operands for an FMul, see if we can fold the result static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q, unsigned MaxRecurse) { if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q)) return C; // fmul X, 1.0 ==> X if (match(Op1, m_FPOne())) return Op0; // fmul nnan nsz X, 0 ==> 0 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) return Op1; return nullptr; } Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit); } Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit); } Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit); } static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q, unsigned) { if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q)) return C; // undef / X -> undef (the undef could be a snan). if (match(Op0, m_Undef())) return Op0; // X / undef -> undef if (match(Op1, m_Undef())) return Op1; // X / 1.0 -> X if (match(Op1, m_FPOne())) return Op0; // 0 / X -> 0 // Requires that NaNs are off (X could be zero) and signed zeroes are // ignored (X could be positive or negative, so the output sign is unknown). if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) return Op0; if (FMF.noNaNs()) { // X / X -> 1.0 is legal when NaNs are ignored. if (Op0 == Op1) return ConstantFP::get(Op0->getType(), 1.0); // -X / X -> -1.0 and // X / -X -> -1.0 are legal when NaNs are ignored. // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored. if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) && BinaryOperator::getFNegArgument(Op0) == Op1) || (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) && BinaryOperator::getFNegArgument(Op1) == Op0)) return ConstantFP::get(Op0->getType(), -1.0); } return nullptr; } Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit); } static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q, unsigned) { if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q)) return C; // undef % X -> undef (the undef could be a snan). if (match(Op0, m_Undef())) return Op0; // X % undef -> undef if (match(Op1, m_Undef())) return Op1; // 0 % X -> 0 // Requires that NaNs are off (X could be zero) and signed zeroes are // ignored (X could be positive or negative, so the output sign is unknown). if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) return Op0; return nullptr; } Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit); } //=== Helper functions for higher up the class hierarchy. /// Given operands for a BinaryOperator, see if we can fold the result. /// If not, this returns null. static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { switch (Opcode) { case Instruction::Add: return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse); case Instruction::Sub: return SimplifySubInst(LHS, RHS, false, false, Q, MaxRecurse); case Instruction::Mul: return SimplifyMulInst(LHS, RHS, Q, MaxRecurse); case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); case Instruction::Shl: return SimplifyShlInst(LHS, RHS, false, false, Q, MaxRecurse); case Instruction::LShr: return SimplifyLShrInst(LHS, RHS, false, Q, MaxRecurse); case Instruction::AShr: return SimplifyAShrInst(LHS, RHS, false, Q, MaxRecurse); case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse); case Instruction::Or: return SimplifyOrInst(LHS, RHS, Q, MaxRecurse); case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse); case Instruction::FAdd: return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::FSub: return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::FMul: return SimplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); default: llvm_unreachable("Unexpected opcode"); } } /// Given operands for a BinaryOperator, see if we can fold the result. /// If not, this returns null. /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp. static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, const FastMathFlags &FMF, const SimplifyQuery &Q, unsigned MaxRecurse) { switch (Opcode) { case Instruction::FAdd: return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse); case Instruction::FSub: return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse); case Instruction::FMul: return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse); case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse); default: return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse); } } Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q) { return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit); } Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q) { return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit); } /// Given operands for a CmpInst, see if we can fold the result. static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse); } Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q) { return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit); } static bool IsIdempotent(Intrinsic::ID ID) { switch (ID) { default: return false; // Unary idempotent: f(f(x)) = f(x) case Intrinsic::fabs: case Intrinsic::floor: case Intrinsic::ceil: case Intrinsic::trunc: case Intrinsic::rint: case Intrinsic::nearbyint: case Intrinsic::round: case Intrinsic::canonicalize: return true; } } static Value *SimplifyRelativeLoad(Constant *Ptr, Constant *Offset, const DataLayout &DL) { GlobalValue *PtrSym; APInt PtrOffset; if (!IsConstantOffsetFromGlobal(Ptr, PtrSym, PtrOffset, DL)) return nullptr; Type *Int8PtrTy = Type::getInt8PtrTy(Ptr->getContext()); Type *Int32Ty = Type::getInt32Ty(Ptr->getContext()); Type *Int32PtrTy = Int32Ty->getPointerTo(); Type *Int64Ty = Type::getInt64Ty(Ptr->getContext()); auto *OffsetConstInt = dyn_cast(Offset); if (!OffsetConstInt || OffsetConstInt->getType()->getBitWidth() > 64) return nullptr; uint64_t OffsetInt = OffsetConstInt->getSExtValue(); if (OffsetInt % 4 != 0) return nullptr; Constant *C = ConstantExpr::getGetElementPtr( Int32Ty, ConstantExpr::getBitCast(Ptr, Int32PtrTy), ConstantInt::get(Int64Ty, OffsetInt / 4)); Constant *Loaded = ConstantFoldLoadFromConstPtr(C, Int32Ty, DL); if (!Loaded) return nullptr; auto *LoadedCE = dyn_cast(Loaded); if (!LoadedCE) return nullptr; if (LoadedCE->getOpcode() == Instruction::Trunc) { LoadedCE = dyn_cast(LoadedCE->getOperand(0)); if (!LoadedCE) return nullptr; } if (LoadedCE->getOpcode() != Instruction::Sub) return nullptr; auto *LoadedLHS = dyn_cast(LoadedCE->getOperand(0)); if (!LoadedLHS || LoadedLHS->getOpcode() != Instruction::PtrToInt) return nullptr; auto *LoadedLHSPtr = LoadedLHS->getOperand(0); Constant *LoadedRHS = LoadedCE->getOperand(1); GlobalValue *LoadedRHSSym; APInt LoadedRHSOffset; if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset, DL) || PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset) return nullptr; return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy); } static bool maskIsAllZeroOrUndef(Value *Mask) { auto *ConstMask = dyn_cast(Mask); if (!ConstMask) return false; if (ConstMask->isNullValue() || isa(ConstMask)) return true; for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E; ++I) { if (auto *MaskElt = ConstMask->getAggregateElement(I)) if (MaskElt->isNullValue() || isa(MaskElt)) continue; return false; } return true; } template static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd, const SimplifyQuery &Q, unsigned MaxRecurse) { Intrinsic::ID IID = F->getIntrinsicID(); unsigned NumOperands = std::distance(ArgBegin, ArgEnd); // Unary Ops if (NumOperands == 1) { // Perform idempotent optimizations if (IsIdempotent(IID)) { if (IntrinsicInst *II = dyn_cast(*ArgBegin)) { if (II->getIntrinsicID() == IID) return II; } } Value *IIOperand = *ArgBegin; Value *X; switch (IID) { case Intrinsic::fabs: { if (SignBitMustBeZero(IIOperand, Q.TLI)) return IIOperand; return nullptr; } case Intrinsic::bswap: { // bswap(bswap(x)) -> x if (match(IIOperand, m_BSwap(m_Value(X)))) return X; return nullptr; } case Intrinsic::bitreverse: { // bitreverse(bitreverse(x)) -> x if (match(IIOperand, m_BitReverse(m_Value(X)))) return X; return nullptr; } case Intrinsic::exp: { // exp(log(x)) -> x if (Q.CxtI->isFast() && match(IIOperand, m_Intrinsic(m_Value(X)))) return X; return nullptr; } case Intrinsic::exp2: { // exp2(log2(x)) -> x if (Q.CxtI->isFast() && match(IIOperand, m_Intrinsic(m_Value(X)))) return X; return nullptr; } case Intrinsic::log: { // log(exp(x)) -> x if (Q.CxtI->isFast() && match(IIOperand, m_Intrinsic(m_Value(X)))) return X; return nullptr; } case Intrinsic::log2: { // log2(exp2(x)) -> x if (Q.CxtI->isFast() && match(IIOperand, m_Intrinsic(m_Value(X)))) { return X; } return nullptr; } default: return nullptr; } } // Binary Ops if (NumOperands == 2) { Value *LHS = *ArgBegin; Value *RHS = *(ArgBegin + 1); Type *ReturnType = F->getReturnType(); switch (IID) { case Intrinsic::usub_with_overflow: case Intrinsic::ssub_with_overflow: { // X - X -> { 0, false } if (LHS == RHS) return Constant::getNullValue(ReturnType); // X - undef -> undef // undef - X -> undef if (isa(LHS) || isa(RHS)) return UndefValue::get(ReturnType); return nullptr; } case Intrinsic::uadd_with_overflow: case Intrinsic::sadd_with_overflow: { // X + undef -> undef if (isa(LHS) || isa(RHS)) return UndefValue::get(ReturnType); return nullptr; } case Intrinsic::umul_with_overflow: case Intrinsic::smul_with_overflow: { // 0 * X -> { 0, false } // X * 0 -> { 0, false } if (match(LHS, m_Zero()) || match(RHS, m_Zero())) return Constant::getNullValue(ReturnType); // undef * X -> { 0, false } // X * undef -> { 0, false } if (match(LHS, m_Undef()) || match(RHS, m_Undef())) return Constant::getNullValue(ReturnType); return nullptr; } case Intrinsic::load_relative: { Constant *C0 = dyn_cast(LHS); Constant *C1 = dyn_cast(RHS); if (C0 && C1) return SimplifyRelativeLoad(C0, C1, Q.DL); return nullptr; } case Intrinsic::powi: if (ConstantInt *Power = dyn_cast(RHS)) { // powi(x, 0) -> 1.0 if (Power->isZero()) return ConstantFP::get(LHS->getType(), 1.0); // powi(x, 1) -> x if (Power->isOne()) return LHS; } return nullptr; default: return nullptr; } } // Simplify calls to llvm.masked.load.* switch (IID) { case Intrinsic::masked_load: { Value *MaskArg = ArgBegin[2]; Value *PassthruArg = ArgBegin[3]; // If the mask is all zeros or undef, the "passthru" argument is the result. if (maskIsAllZeroOrUndef(MaskArg)) return PassthruArg; return nullptr; } default: return nullptr; } } template static Value *SimplifyCall(ImmutableCallSite CS, Value *V, IterTy ArgBegin, IterTy ArgEnd, const SimplifyQuery &Q, unsigned MaxRecurse) { Type *Ty = V->getType(); if (PointerType *PTy = dyn_cast(Ty)) Ty = PTy->getElementType(); FunctionType *FTy = cast(Ty); // call undef -> undef // call null -> undef if (isa(V) || isa(V)) return UndefValue::get(FTy->getReturnType()); Function *F = dyn_cast(V); if (!F) return nullptr; if (F->isIntrinsic()) if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse)) return Ret; if (!canConstantFoldCallTo(CS, F)) return nullptr; SmallVector ConstantArgs; ConstantArgs.reserve(ArgEnd - ArgBegin); for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { Constant *C = dyn_cast(*I); if (!C) return nullptr; ConstantArgs.push_back(C); } return ConstantFoldCall(CS, F, ConstantArgs, Q.TLI); } Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V, User::op_iterator ArgBegin, User::op_iterator ArgEnd, const SimplifyQuery &Q) { return ::SimplifyCall(CS, V, ArgBegin, ArgEnd, Q, RecursionLimit); } Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V, ArrayRef Args, const SimplifyQuery &Q) { return ::SimplifyCall(CS, V, Args.begin(), Args.end(), Q, RecursionLimit); } Value *llvm::SimplifyCall(ImmutableCallSite ICS, const SimplifyQuery &Q) { CallSite CS(const_cast(ICS.getInstruction())); return ::SimplifyCall(CS, CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), Q, RecursionLimit); } /// See if we can compute a simplified version of this instruction. /// If not, this returns null. Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ, OptimizationRemarkEmitter *ORE) { const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I); Value *Result; switch (I->getOpcode()) { default: Result = ConstantFoldInstruction(I, Q.DL, Q.TLI); break; case Instruction::FAdd: Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::Add: Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), cast(I)->hasNoSignedWrap(), cast(I)->hasNoUnsignedWrap(), Q); break; case Instruction::FSub: Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::Sub: Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), cast(I)->hasNoSignedWrap(), cast(I)->hasNoUnsignedWrap(), Q); break; case Instruction::FMul: Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::Mul: Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::SDiv: Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::UDiv: Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::FDiv: Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::SRem: Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::URem: Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::FRem: Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::Shl: Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), cast(I)->hasNoSignedWrap(), cast(I)->hasNoUnsignedWrap(), Q); break; case Instruction::LShr: Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), cast(I)->isExact(), Q); break; case Instruction::AShr: Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), cast(I)->isExact(), Q); break; case Instruction::And: Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::Or: Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::Xor: Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), Q); break; case Instruction::ICmp: Result = SimplifyICmpInst(cast(I)->getPredicate(), I->getOperand(0), I->getOperand(1), Q); break; case Instruction::FCmp: Result = SimplifyFCmpInst(cast(I)->getPredicate(), I->getOperand(0), I->getOperand(1), I->getFastMathFlags(), Q); break; case Instruction::Select: Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), I->getOperand(2), Q); break; case Instruction::GetElementPtr: { SmallVector Ops(I->op_begin(), I->op_end()); Result = SimplifyGEPInst(cast(I)->getSourceElementType(), Ops, Q); break; } case Instruction::InsertValue: { InsertValueInst *IV = cast(I); Result = SimplifyInsertValueInst(IV->getAggregateOperand(), IV->getInsertedValueOperand(), IV->getIndices(), Q); break; } case Instruction::InsertElement: { auto *IE = cast(I); Result = SimplifyInsertElementInst(IE->getOperand(0), IE->getOperand(1), IE->getOperand(2), Q); break; } case Instruction::ExtractValue: { auto *EVI = cast(I); Result = SimplifyExtractValueInst(EVI->getAggregateOperand(), EVI->getIndices(), Q); break; } case Instruction::ExtractElement: { auto *EEI = cast(I); Result = SimplifyExtractElementInst(EEI->getVectorOperand(), EEI->getIndexOperand(), Q); break; } case Instruction::ShuffleVector: { auto *SVI = cast(I); Result = SimplifyShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1), SVI->getMask(), SVI->getType(), Q); break; } case Instruction::PHI: Result = SimplifyPHINode(cast(I), Q); break; case Instruction::Call: { CallSite CS(cast(I)); Result = SimplifyCall(CS, Q); break; } #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc: #include "llvm/IR/Instruction.def" #undef HANDLE_CAST_INST Result = SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q); break; case Instruction::Alloca: // No simplifications for Alloca and it can't be constant folded. Result = nullptr; break; } // In general, it is possible for computeKnownBits to determine all bits in a // value even when the operands are not all constants. if (!Result && I->getType()->isIntOrIntVectorTy()) { KnownBits Known = computeKnownBits(I, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT, ORE); if (Known.isConstant()) Result = ConstantInt::get(I->getType(), Known.getConstant()); } /// If called on unreachable code, the above logic may report that the /// instruction simplified to itself. Make life easier for users by /// detecting that case here, returning a safe value instead. return Result == I ? UndefValue::get(I->getType()) : Result; } /// \brief Implementation of recursive simplification through an instruction's /// uses. /// /// This is the common implementation of the recursive simplification routines. /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of /// instructions to process and attempt to simplify it using /// InstructionSimplify. /// /// This routine returns 'true' only when *it* simplifies something. The passed /// in simplified value does not count toward this. static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { bool Simplified = false; SmallSetVector Worklist; const DataLayout &DL = I->getModule()->getDataLayout(); // If we have an explicit value to collapse to, do that round of the // simplification loop by hand initially. if (SimpleV) { for (User *U : I->users()) if (U != I) Worklist.insert(cast(U)); // Replace the instruction with its simplified value. I->replaceAllUsesWith(SimpleV); // Gracefully handle edge cases where the instruction is not wired into any // parent block. if (I->getParent() && !I->isEHPad() && !isa(I) && !I->mayHaveSideEffects()) I->eraseFromParent(); } else { Worklist.insert(I); } // Note that we must test the size on each iteration, the worklist can grow. for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { I = Worklist[Idx]; // See if this instruction simplifies. SimpleV = SimplifyInstruction(I, {DL, TLI, DT, AC}); if (!SimpleV) continue; Simplified = true; // Stash away all the uses of the old instruction so we can check them for // recursive simplifications after a RAUW. This is cheaper than checking all // uses of To on the recursive step in most cases. for (User *U : I->users()) Worklist.insert(cast(U)); // Replace the instruction with its simplified value. I->replaceAllUsesWith(SimpleV); // Gracefully handle edge cases where the instruction is not wired into any // parent block. if (I->getParent() && !I->isEHPad() && !isa(I) && !I->mayHaveSideEffects()) I->eraseFromParent(); } return Simplified; } bool llvm::recursivelySimplifyInstruction(Instruction *I, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC); } bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); assert(SimpleV && "Must provide a simplified value."); return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC); } namespace llvm { const SimplifyQuery getBestSimplifyQuery(Pass &P, Function &F) { auto *DTWP = P.getAnalysisIfAvailable(); auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; auto *TLIWP = P.getAnalysisIfAvailable(); auto *TLI = TLIWP ? &TLIWP->getTLI() : nullptr; auto *ACWP = P.getAnalysisIfAvailable(); auto *AC = ACWP ? &ACWP->getAssumptionCache(F) : nullptr; return {F.getParent()->getDataLayout(), TLI, DT, AC}; } const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &AR, const DataLayout &DL) { return {DL, &AR.TLI, &AR.DT, &AR.AC}; } template const SimplifyQuery getBestSimplifyQuery(AnalysisManager &AM, Function &F) { auto *DT = AM.template getCachedResult(F); auto *TLI = AM.template getCachedResult(F); auto *AC = AM.template getCachedResult(F); return {F.getParent()->getDataLayout(), TLI, DT, AC}; } template const SimplifyQuery getBestSimplifyQuery(AnalysisManager &, Function &); } Index: head/contrib/llvm/lib/IR/ConstantFold.cpp =================================================================== --- head/contrib/llvm/lib/IR/ConstantFold.cpp (revision 331064) +++ head/contrib/llvm/lib/IR/ConstantFold.cpp (revision 331065) @@ -1,2348 +1,2359 @@ //===- ConstantFold.cpp - LLVM constant folder ----------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements folding of constants for LLVM. This implements the // (internal) ConstantFold.h interface, which is used by the // ConstantExpr::get* methods to automatically fold constants when possible. // // The current constant folding implementation is implemented in two pieces: the // pieces that don't need DataLayout, and the pieces that do. This is to avoid // a dependence in IR on Target. // //===----------------------------------------------------------------------===// #include "ConstantFold.h" #include "llvm/ADT/APSInt.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Function.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ManagedStatic.h" #include "llvm/Support/MathExtras.h" using namespace llvm; using namespace llvm::PatternMatch; //===----------------------------------------------------------------------===// // ConstantFold*Instruction Implementations //===----------------------------------------------------------------------===// /// Convert the specified vector Constant node to the specified vector type. /// At this point, we know that the elements of the input vector constant are /// all simple integer or FP values. static Constant *BitCastConstantVector(Constant *CV, VectorType *DstTy) { if (CV->isAllOnesValue()) return Constant::getAllOnesValue(DstTy); if (CV->isNullValue()) return Constant::getNullValue(DstTy); // If this cast changes element count then we can't handle it here: // doing so requires endianness information. This should be handled by // Analysis/ConstantFolding.cpp unsigned NumElts = DstTy->getNumElements(); if (NumElts != CV->getType()->getVectorNumElements()) return nullptr; Type *DstEltTy = DstTy->getElementType(); SmallVector Result; Type *Ty = IntegerType::get(CV->getContext(), 32); for (unsigned i = 0; i != NumElts; ++i) { Constant *C = ConstantExpr::getExtractElement(CV, ConstantInt::get(Ty, i)); C = ConstantExpr::getBitCast(C, DstEltTy); Result.push_back(C); } return ConstantVector::get(Result); } /// This function determines which opcode to use to fold two constant cast /// expressions together. It uses CastInst::isEliminableCastPair to determine /// the opcode. Consequently its just a wrapper around that function. /// @brief Determine if it is valid to fold a cast of a cast static unsigned foldConstantCastPair( unsigned opc, ///< opcode of the second cast constant expression ConstantExpr *Op, ///< the first cast constant expression Type *DstTy ///< destination type of the first cast ) { assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!"); assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type"); assert(CastInst::isCast(opc) && "Invalid cast opcode"); // The types and opcodes for the two Cast constant expressions Type *SrcTy = Op->getOperand(0)->getType(); Type *MidTy = Op->getType(); Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode()); Instruction::CastOps secondOp = Instruction::CastOps(opc); // Assume that pointers are never more than 64 bits wide, and only use this // for the middle type. Otherwise we could end up folding away illegal // bitcasts between address spaces with different sizes. IntegerType *FakeIntPtrTy = Type::getInt64Ty(DstTy->getContext()); // Let CastInst::isEliminableCastPair do the heavy lifting. return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy, nullptr, FakeIntPtrTy, nullptr); } static Constant *FoldBitCast(Constant *V, Type *DestTy) { Type *SrcTy = V->getType(); if (SrcTy == DestTy) return V; // no-op cast // Check to see if we are casting a pointer to an aggregate to a pointer to // the first element. If so, return the appropriate GEP instruction. if (PointerType *PTy = dyn_cast(V->getType())) if (PointerType *DPTy = dyn_cast(DestTy)) if (PTy->getAddressSpace() == DPTy->getAddressSpace() && PTy->getElementType()->isSized()) { SmallVector IdxList; Value *Zero = Constant::getNullValue(Type::getInt32Ty(DPTy->getContext())); IdxList.push_back(Zero); Type *ElTy = PTy->getElementType(); while (ElTy != DPTy->getElementType()) { if (StructType *STy = dyn_cast(ElTy)) { if (STy->getNumElements() == 0) break; ElTy = STy->getElementType(0); IdxList.push_back(Zero); } else if (SequentialType *STy = dyn_cast(ElTy)) { ElTy = STy->getElementType(); IdxList.push_back(Zero); } else { break; } } if (ElTy == DPTy->getElementType()) // This GEP is inbounds because all indices are zero. return ConstantExpr::getInBoundsGetElementPtr(PTy->getElementType(), V, IdxList); } // Handle casts from one vector constant to another. We know that the src // and dest type have the same size (otherwise its an illegal cast). if (VectorType *DestPTy = dyn_cast(DestTy)) { if (VectorType *SrcTy = dyn_cast(V->getType())) { assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() && "Not cast between same sized vectors!"); SrcTy = nullptr; // First, check for null. Undef is already handled. if (isa(V)) return Constant::getNullValue(DestTy); // Handle ConstantVector and ConstantAggregateVector. return BitCastConstantVector(V, DestPTy); } // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts // This allows for other simplifications (although some of them // can only be handled by Analysis/ConstantFolding.cpp). if (isa(V) || isa(V)) return ConstantExpr::getBitCast(ConstantVector::get(V), DestPTy); } // Finally, implement bitcast folding now. The code below doesn't handle // bitcast right. if (isa(V)) // ptr->ptr cast. return ConstantPointerNull::get(cast(DestTy)); // Handle integral constant input. if (ConstantInt *CI = dyn_cast(V)) { if (DestTy->isIntegerTy()) // Integral -> Integral. This is a no-op because the bit widths must // be the same. Consequently, we just fold to V. return V; // See note below regarding the PPC_FP128 restriction. if (DestTy->isFloatingPointTy() && !DestTy->isPPC_FP128Ty()) return ConstantFP::get(DestTy->getContext(), APFloat(DestTy->getFltSemantics(), CI->getValue())); // Otherwise, can't fold this (vector?) return nullptr; } // Handle ConstantFP input: FP -> Integral. if (ConstantFP *FP = dyn_cast(V)) { // PPC_FP128 is really the sum of two consecutive doubles, where the first // double is always stored first in memory, regardless of the target // endianness. The memory layout of i128, however, depends on the target // endianness, and so we can't fold this without target endianness // information. This should instead be handled by // Analysis/ConstantFolding.cpp if (FP->getType()->isPPC_FP128Ty()) return nullptr; // Make sure dest type is compatible with the folded integer constant. if (!DestTy->isIntegerTy()) return nullptr; return ConstantInt::get(FP->getContext(), FP->getValueAPF().bitcastToAPInt()); } return nullptr; } /// V is an integer constant which only has a subset of its bytes used. /// The bytes used are indicated by ByteStart (which is the first byte used, /// counting from the least significant byte) and ByteSize, which is the number /// of bytes used. /// /// This function analyzes the specified constant to see if the specified byte /// range can be returned as a simplified constant. If so, the constant is /// returned, otherwise null is returned. static Constant *ExtractConstantBytes(Constant *C, unsigned ByteStart, unsigned ByteSize) { assert(C->getType()->isIntegerTy() && (cast(C->getType())->getBitWidth() & 7) == 0 && "Non-byte sized integer input"); unsigned CSize = cast(C->getType())->getBitWidth()/8; assert(ByteSize && "Must be accessing some piece"); assert(ByteStart+ByteSize <= CSize && "Extracting invalid piece from input"); assert(ByteSize != CSize && "Should not extract everything"); // Constant Integers are simple. if (ConstantInt *CI = dyn_cast(C)) { APInt V = CI->getValue(); if (ByteStart) V.lshrInPlace(ByteStart*8); V = V.trunc(ByteSize*8); return ConstantInt::get(CI->getContext(), V); } // In the input is a constant expr, we might be able to recursively simplify. // If not, we definitely can't do anything. ConstantExpr *CE = dyn_cast(C); if (!CE) return nullptr; switch (CE->getOpcode()) { default: return nullptr; case Instruction::Or: { Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); if (!RHS) return nullptr; // X | -1 -> -1. if (ConstantInt *RHSC = dyn_cast(RHS)) if (RHSC->isMinusOne()) return RHSC; Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); if (!LHS) return nullptr; return ConstantExpr::getOr(LHS, RHS); } case Instruction::And: { Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); if (!RHS) return nullptr; // X & 0 -> 0. if (RHS->isNullValue()) return RHS; Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); if (!LHS) return nullptr; return ConstantExpr::getAnd(LHS, RHS); } case Instruction::LShr: { ConstantInt *Amt = dyn_cast(CE->getOperand(1)); if (!Amt) return nullptr; unsigned ShAmt = Amt->getZExtValue(); // Cannot analyze non-byte shifts. if ((ShAmt & 7) != 0) return nullptr; ShAmt >>= 3; // If the extract is known to be all zeros, return zero. if (ByteStart >= CSize-ShAmt) return Constant::getNullValue(IntegerType::get(CE->getContext(), ByteSize*8)); // If the extract is known to be fully in the input, extract it. if (ByteStart+ByteSize+ShAmt <= CSize) return ExtractConstantBytes(CE->getOperand(0), ByteStart+ShAmt, ByteSize); // TODO: Handle the 'partially zero' case. return nullptr; } case Instruction::Shl: { ConstantInt *Amt = dyn_cast(CE->getOperand(1)); if (!Amt) return nullptr; unsigned ShAmt = Amt->getZExtValue(); // Cannot analyze non-byte shifts. if ((ShAmt & 7) != 0) return nullptr; ShAmt >>= 3; // If the extract is known to be all zeros, return zero. if (ByteStart+ByteSize <= ShAmt) return Constant::getNullValue(IntegerType::get(CE->getContext(), ByteSize*8)); // If the extract is known to be fully in the input, extract it. if (ByteStart >= ShAmt) return ExtractConstantBytes(CE->getOperand(0), ByteStart-ShAmt, ByteSize); // TODO: Handle the 'partially zero' case. return nullptr; } case Instruction::ZExt: { unsigned SrcBitSize = cast(CE->getOperand(0)->getType())->getBitWidth(); // If extracting something that is completely zero, return 0. if (ByteStart*8 >= SrcBitSize) return Constant::getNullValue(IntegerType::get(CE->getContext(), ByteSize*8)); // If exactly extracting the input, return it. if (ByteStart == 0 && ByteSize*8 == SrcBitSize) return CE->getOperand(0); // If extracting something completely in the input, if if the input is a // multiple of 8 bits, recurse. if ((SrcBitSize&7) == 0 && (ByteStart+ByteSize)*8 <= SrcBitSize) return ExtractConstantBytes(CE->getOperand(0), ByteStart, ByteSize); // Otherwise, if extracting a subset of the input, which is not multiple of // 8 bits, do a shift and trunc to get the bits. if ((ByteStart+ByteSize)*8 < SrcBitSize) { assert((SrcBitSize&7) && "Shouldn't get byte sized case here"); Constant *Res = CE->getOperand(0); if (ByteStart) Res = ConstantExpr::getLShr(Res, ConstantInt::get(Res->getType(), ByteStart*8)); return ConstantExpr::getTrunc(Res, IntegerType::get(C->getContext(), ByteSize*8)); } // TODO: Handle the 'partially zero' case. return nullptr; } } } /// Return a ConstantExpr with type DestTy for sizeof on Ty, with any known /// factors factored out. If Folded is false, return null if no factoring was /// possible, to avoid endlessly bouncing an unfoldable expression back into the /// top-level folder. static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded) { if (ArrayType *ATy = dyn_cast(Ty)) { Constant *N = ConstantInt::get(DestTy, ATy->getNumElements()); Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); return ConstantExpr::getNUWMul(E, N); } if (StructType *STy = dyn_cast(Ty)) if (!STy->isPacked()) { unsigned NumElems = STy->getNumElements(); // An empty struct has size zero. if (NumElems == 0) return ConstantExpr::getNullValue(DestTy); // Check for a struct with all members having the same size. Constant *MemberSize = getFoldedSizeOf(STy->getElementType(0), DestTy, true); bool AllSame = true; for (unsigned i = 1; i != NumElems; ++i) if (MemberSize != getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { AllSame = false; break; } if (AllSame) { Constant *N = ConstantInt::get(DestTy, NumElems); return ConstantExpr::getNUWMul(MemberSize, N); } } // Pointer size doesn't depend on the pointee type, so canonicalize them // to an arbitrary pointee. if (PointerType *PTy = dyn_cast(Ty)) if (!PTy->getElementType()->isIntegerTy(1)) return getFoldedSizeOf(PointerType::get(IntegerType::get(PTy->getContext(), 1), PTy->getAddressSpace()), DestTy, true); // If there's no interesting folding happening, bail so that we don't create // a constant that looks like it needs folding but really doesn't. if (!Folded) return nullptr; // Base case: Get a regular sizeof expression. Constant *C = ConstantExpr::getSizeOf(Ty); C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, DestTy, false), C, DestTy); return C; } /// Return a ConstantExpr with type DestTy for alignof on Ty, with any known /// factors factored out. If Folded is false, return null if no factoring was /// possible, to avoid endlessly bouncing an unfoldable expression back into the /// top-level folder. static Constant *getFoldedAlignOf(Type *Ty, Type *DestTy, bool Folded) { // The alignment of an array is equal to the alignment of the // array element. Note that this is not always true for vectors. if (ArrayType *ATy = dyn_cast(Ty)) { Constant *C = ConstantExpr::getAlignOf(ATy->getElementType()); C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, DestTy, false), C, DestTy); return C; } if (StructType *STy = dyn_cast(Ty)) { // Packed structs always have an alignment of 1. if (STy->isPacked()) return ConstantInt::get(DestTy, 1); // Otherwise, struct alignment is the maximum alignment of any member. // Without target data, we can't compare much, but we can check to see // if all the members have the same alignment. unsigned NumElems = STy->getNumElements(); // An empty struct has minimal alignment. if (NumElems == 0) return ConstantInt::get(DestTy, 1); // Check for a struct with all members having the same alignment. Constant *MemberAlign = getFoldedAlignOf(STy->getElementType(0), DestTy, true); bool AllSame = true; for (unsigned i = 1; i != NumElems; ++i) if (MemberAlign != getFoldedAlignOf(STy->getElementType(i), DestTy, true)) { AllSame = false; break; } if (AllSame) return MemberAlign; } // Pointer alignment doesn't depend on the pointee type, so canonicalize them // to an arbitrary pointee. if (PointerType *PTy = dyn_cast(Ty)) if (!PTy->getElementType()->isIntegerTy(1)) return getFoldedAlignOf(PointerType::get(IntegerType::get(PTy->getContext(), 1), PTy->getAddressSpace()), DestTy, true); // If there's no interesting folding happening, bail so that we don't create // a constant that looks like it needs folding but really doesn't. if (!Folded) return nullptr; // Base case: Get a regular alignof expression. Constant *C = ConstantExpr::getAlignOf(Ty); C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, DestTy, false), C, DestTy); return C; } /// Return a ConstantExpr with type DestTy for offsetof on Ty and FieldNo, with /// any known factors factored out. If Folded is false, return null if no /// factoring was possible, to avoid endlessly bouncing an unfoldable expression /// back into the top-level folder. static Constant *getFoldedOffsetOf(Type *Ty, Constant *FieldNo, Type *DestTy, bool Folded) { if (ArrayType *ATy = dyn_cast(Ty)) { Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, false, DestTy, false), FieldNo, DestTy); Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); return ConstantExpr::getNUWMul(E, N); } if (StructType *STy = dyn_cast(Ty)) if (!STy->isPacked()) { unsigned NumElems = STy->getNumElements(); // An empty struct has no members. if (NumElems == 0) return nullptr; // Check for a struct with all members having the same size. Constant *MemberSize = getFoldedSizeOf(STy->getElementType(0), DestTy, true); bool AllSame = true; for (unsigned i = 1; i != NumElems; ++i) if (MemberSize != getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { AllSame = false; break; } if (AllSame) { Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, false, DestTy, false), FieldNo, DestTy); return ConstantExpr::getNUWMul(MemberSize, N); } } // If there's no interesting folding happening, bail so that we don't create // a constant that looks like it needs folding but really doesn't. if (!Folded) return nullptr; // Base case: Get a regular offsetof expression. Constant *C = ConstantExpr::getOffsetOf(Ty, FieldNo); C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, DestTy, false), C, DestTy); return C; } Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V, Type *DestTy) { if (isa(V)) { // zext(undef) = 0, because the top bits will be zero. // sext(undef) = 0, because the top bits will all be the same. // [us]itofp(undef) = 0, because the result value is bounded. if (opc == Instruction::ZExt || opc == Instruction::SExt || opc == Instruction::UIToFP || opc == Instruction::SIToFP) return Constant::getNullValue(DestTy); return UndefValue::get(DestTy); } if (V->isNullValue() && !DestTy->isX86_MMXTy() && opc != Instruction::AddrSpaceCast) return Constant::getNullValue(DestTy); // If the cast operand is a constant expression, there's a few things we can // do to try to simplify it. if (ConstantExpr *CE = dyn_cast(V)) { if (CE->isCast()) { // Try hard to fold cast of cast because they are often eliminable. if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy)) return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy); } else if (CE->getOpcode() == Instruction::GetElementPtr && // Do not fold addrspacecast (gep 0, .., 0). It might make the // addrspacecast uncanonicalized. opc != Instruction::AddrSpaceCast && // Do not fold bitcast (gep) with inrange index, as this loses // information. !cast(CE)->getInRangeIndex().hasValue()) { // If all of the indexes in the GEP are null values, there is no pointer // adjustment going on. We might as well cast the source pointer. bool isAllNull = true; for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) if (!CE->getOperand(i)->isNullValue()) { isAllNull = false; break; } if (isAllNull) // This is casting one pointer type to another, always BitCast return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy); } } // If the cast operand is a constant vector, perform the cast by // operating on each element. In the cast of bitcasts, the element // count may be mismatched; don't attempt to handle that here. if ((isa(V) || isa(V)) && DestTy->isVectorTy() && DestTy->getVectorNumElements() == V->getType()->getVectorNumElements()) { SmallVector res; VectorType *DestVecTy = cast(DestTy); Type *DstEltTy = DestVecTy->getElementType(); Type *Ty = IntegerType::get(V->getContext(), 32); for (unsigned i = 0, e = V->getType()->getVectorNumElements(); i != e; ++i) { Constant *C = ConstantExpr::getExtractElement(V, ConstantInt::get(Ty, i)); res.push_back(ConstantExpr::getCast(opc, C, DstEltTy)); } return ConstantVector::get(res); } // We actually have to do a cast now. Perform the cast according to the // opcode specified. switch (opc) { default: llvm_unreachable("Failed to cast constant expression"); case Instruction::FPTrunc: case Instruction::FPExt: if (ConstantFP *FPC = dyn_cast(V)) { bool ignored; APFloat Val = FPC->getValueAPF(); Val.convert(DestTy->isHalfTy() ? APFloat::IEEEhalf() : DestTy->isFloatTy() ? APFloat::IEEEsingle() : DestTy->isDoubleTy() ? APFloat::IEEEdouble() : DestTy->isX86_FP80Ty() ? APFloat::x87DoubleExtended() : DestTy->isFP128Ty() ? APFloat::IEEEquad() : DestTy->isPPC_FP128Ty() ? APFloat::PPCDoubleDouble() : APFloat::Bogus(), APFloat::rmNearestTiesToEven, &ignored); return ConstantFP::get(V->getContext(), Val); } return nullptr; // Can't fold. case Instruction::FPToUI: case Instruction::FPToSI: if (ConstantFP *FPC = dyn_cast(V)) { const APFloat &V = FPC->getValueAPF(); bool ignored; uint32_t DestBitWidth = cast(DestTy)->getBitWidth(); APSInt IntVal(DestBitWidth, opc == Instruction::FPToUI); if (APFloat::opInvalidOp == V.convertToInteger(IntVal, APFloat::rmTowardZero, &ignored)) { // Undefined behavior invoked - the destination type can't represent // the input constant. return UndefValue::get(DestTy); } return ConstantInt::get(FPC->getContext(), IntVal); } return nullptr; // Can't fold. case Instruction::IntToPtr: //always treated as unsigned if (V->isNullValue()) // Is it an integral null value? return ConstantPointerNull::get(cast(DestTy)); return nullptr; // Other pointer types cannot be casted case Instruction::PtrToInt: // always treated as unsigned // Is it a null pointer value? if (V->isNullValue()) return ConstantInt::get(DestTy, 0); // If this is a sizeof-like expression, pull out multiplications by // known factors to expose them to subsequent folding. If it's an // alignof-like expression, factor out known factors. if (ConstantExpr *CE = dyn_cast(V)) if (CE->getOpcode() == Instruction::GetElementPtr && CE->getOperand(0)->isNullValue()) { // FIXME: Looks like getFoldedSizeOf(), getFoldedOffsetOf() and // getFoldedAlignOf() don't handle the case when DestTy is a vector of // pointers yet. We end up in asserts in CastInst::getCastOpcode (see // test/Analysis/ConstantFolding/cast-vector.ll). I've only seen this // happen in one "real" C-code test case, so it does not seem to be an // important optimization to handle vectors here. For now, simply bail // out. if (DestTy->isVectorTy()) return nullptr; GEPOperator *GEPO = cast(CE); Type *Ty = GEPO->getSourceElementType(); if (CE->getNumOperands() == 2) { // Handle a sizeof-like expression. Constant *Idx = CE->getOperand(1); bool isOne = isa(Idx) && cast(Idx)->isOne(); if (Constant *C = getFoldedSizeOf(Ty, DestTy, !isOne)) { Idx = ConstantExpr::getCast(CastInst::getCastOpcode(Idx, true, DestTy, false), Idx, DestTy); return ConstantExpr::getMul(C, Idx); } } else if (CE->getNumOperands() == 3 && CE->getOperand(1)->isNullValue()) { // Handle an alignof-like expression. if (StructType *STy = dyn_cast(Ty)) if (!STy->isPacked()) { ConstantInt *CI = cast(CE->getOperand(2)); if (CI->isOne() && STy->getNumElements() == 2 && STy->getElementType(0)->isIntegerTy(1)) { return getFoldedAlignOf(STy->getElementType(1), DestTy, false); } } // Handle an offsetof-like expression. if (Ty->isStructTy() || Ty->isArrayTy()) { if (Constant *C = getFoldedOffsetOf(Ty, CE->getOperand(2), DestTy, false)) return C; } } } // Other pointer types cannot be casted return nullptr; case Instruction::UIToFP: case Instruction::SIToFP: if (ConstantInt *CI = dyn_cast(V)) { const APInt &api = CI->getValue(); APFloat apf(DestTy->getFltSemantics(), APInt::getNullValue(DestTy->getPrimitiveSizeInBits())); if (APFloat::opOverflow & apf.convertFromAPInt(api, opc==Instruction::SIToFP, APFloat::rmNearestTiesToEven)) { // Undefined behavior invoked - the destination type can't represent // the input constant. return UndefValue::get(DestTy); } return ConstantFP::get(V->getContext(), apf); } return nullptr; case Instruction::ZExt: if (ConstantInt *CI = dyn_cast(V)) { uint32_t BitWidth = cast(DestTy)->getBitWidth(); return ConstantInt::get(V->getContext(), CI->getValue().zext(BitWidth)); } return nullptr; case Instruction::SExt: if (ConstantInt *CI = dyn_cast(V)) { uint32_t BitWidth = cast(DestTy)->getBitWidth(); return ConstantInt::get(V->getContext(), CI->getValue().sext(BitWidth)); } return nullptr; case Instruction::Trunc: { if (V->getType()->isVectorTy()) return nullptr; uint32_t DestBitWidth = cast(DestTy)->getBitWidth(); if (ConstantInt *CI = dyn_cast(V)) { return ConstantInt::get(V->getContext(), CI->getValue().trunc(DestBitWidth)); } // The input must be a constantexpr. See if we can simplify this based on // the bytes we are demanding. Only do this if the source and dest are an // even multiple of a byte. if ((DestBitWidth & 7) == 0 && (cast(V->getType())->getBitWidth() & 7) == 0) if (Constant *Res = ExtractConstantBytes(V, 0, DestBitWidth / 8)) return Res; return nullptr; } case Instruction::BitCast: return FoldBitCast(V, DestTy); case Instruction::AddrSpaceCast: return nullptr; } } Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond, Constant *V1, Constant *V2) { // Check for i1 and vector true/false conditions. if (Cond->isNullValue()) return V2; if (Cond->isAllOnesValue()) return V1; // If the condition is a vector constant, fold the result elementwise. if (ConstantVector *CondV = dyn_cast(Cond)) { SmallVector Result; Type *Ty = IntegerType::get(CondV->getContext(), 32); for (unsigned i = 0, e = V1->getType()->getVectorNumElements(); i != e;++i){ Constant *V; Constant *V1Element = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, i)); Constant *V2Element = ConstantExpr::getExtractElement(V2, ConstantInt::get(Ty, i)); Constant *Cond = dyn_cast(CondV->getOperand(i)); if (V1Element == V2Element) { V = V1Element; } else if (isa(Cond)) { V = isa(V1Element) ? V1Element : V2Element; } else { if (!isa(Cond)) break; V = Cond->isNullValue() ? V2Element : V1Element; } Result.push_back(V); } // If we were able to build the vector, return it. if (Result.size() == V1->getType()->getVectorNumElements()) return ConstantVector::get(Result); } if (isa(Cond)) { if (isa(V1)) return V1; return V2; } if (isa(V1)) return V2; if (isa(V2)) return V1; if (V1 == V2) return V1; if (ConstantExpr *TrueVal = dyn_cast(V1)) { if (TrueVal->getOpcode() == Instruction::Select) if (TrueVal->getOperand(0) == Cond) return ConstantExpr::getSelect(Cond, TrueVal->getOperand(1), V2); } if (ConstantExpr *FalseVal = dyn_cast(V2)) { if (FalseVal->getOpcode() == Instruction::Select) if (FalseVal->getOperand(0) == Cond) return ConstantExpr::getSelect(Cond, V1, FalseVal->getOperand(2)); } return nullptr; } Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val, Constant *Idx) { if (isa(Val)) // ee(undef, x) -> undef return UndefValue::get(Val->getType()->getVectorElementType()); if (Val->isNullValue()) // ee(zero, x) -> zero return Constant::getNullValue(Val->getType()->getVectorElementType()); // ee({w,x,y,z}, undef) -> undef if (isa(Idx)) return UndefValue::get(Val->getType()->getVectorElementType()); if (ConstantInt *CIdx = dyn_cast(Idx)) { // ee({w,x,y,z}, wrong_value) -> undef if (CIdx->uge(Val->getType()->getVectorNumElements())) return UndefValue::get(Val->getType()->getVectorElementType()); return Val->getAggregateElement(CIdx->getZExtValue()); } return nullptr; } Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val, Constant *Elt, Constant *Idx) { if (isa(Idx)) return UndefValue::get(Val->getType()); ConstantInt *CIdx = dyn_cast(Idx); if (!CIdx) return nullptr; unsigned NumElts = Val->getType()->getVectorNumElements(); if (CIdx->uge(NumElts)) return UndefValue::get(Val->getType()); SmallVector Result; Result.reserve(NumElts); auto *Ty = Type::getInt32Ty(Val->getContext()); uint64_t IdxVal = CIdx->getZExtValue(); for (unsigned i = 0; i != NumElts; ++i) { if (i == IdxVal) { Result.push_back(Elt); continue; } Constant *C = ConstantExpr::getExtractElement(Val, ConstantInt::get(Ty, i)); Result.push_back(C); } return ConstantVector::get(Result); } Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2, Constant *Mask) { unsigned MaskNumElts = Mask->getType()->getVectorNumElements(); Type *EltTy = V1->getType()->getVectorElementType(); // Undefined shuffle mask -> undefined value. if (isa(Mask)) return UndefValue::get(VectorType::get(EltTy, MaskNumElts)); // Don't break the bitcode reader hack. if (isa(Mask)) return nullptr; unsigned SrcNumElts = V1->getType()->getVectorNumElements(); // Loop over the shuffle mask, evaluating each element. SmallVector Result; for (unsigned i = 0; i != MaskNumElts; ++i) { int Elt = ShuffleVectorInst::getMaskValue(Mask, i); if (Elt == -1) { Result.push_back(UndefValue::get(EltTy)); continue; } Constant *InElt; if (unsigned(Elt) >= SrcNumElts*2) InElt = UndefValue::get(EltTy); else if (unsigned(Elt) >= SrcNumElts) { Type *Ty = IntegerType::get(V2->getContext(), 32); InElt = ConstantExpr::getExtractElement(V2, ConstantInt::get(Ty, Elt - SrcNumElts)); } else { Type *Ty = IntegerType::get(V1->getContext(), 32); InElt = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, Elt)); } Result.push_back(InElt); } return ConstantVector::get(Result); } Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg, ArrayRef Idxs) { // Base case: no indices, so return the entire value. if (Idxs.empty()) return Agg; if (Constant *C = Agg->getAggregateElement(Idxs[0])) return ConstantFoldExtractValueInstruction(C, Idxs.slice(1)); return nullptr; } Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val, ArrayRef Idxs) { // Base case: no indices, so replace the entire value. if (Idxs.empty()) return Val; unsigned NumElts; if (StructType *ST = dyn_cast(Agg->getType())) NumElts = ST->getNumElements(); else NumElts = cast(Agg->getType())->getNumElements(); SmallVector Result; for (unsigned i = 0; i != NumElts; ++i) { Constant *C = Agg->getAggregateElement(i); if (!C) return nullptr; if (Idxs[0] == i) C = ConstantFoldInsertValueInstruction(C, Val, Idxs.slice(1)); Result.push_back(C); } if (StructType *ST = dyn_cast(Agg->getType())) return ConstantStruct::get(ST, Result); if (ArrayType *AT = dyn_cast(Agg->getType())) return ConstantArray::get(AT, Result); return ConstantVector::get(Result); } Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1, Constant *C2) { assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected"); // Handle UndefValue up front. if (isa(C1) || isa(C2)) { switch (static_cast(Opcode)) { case Instruction::Xor: if (isa(C1) && isa(C2)) // Handle undef ^ undef -> 0 special case. This is a common // idiom (misuse). return Constant::getNullValue(C1->getType()); LLVM_FALLTHROUGH; case Instruction::Add: case Instruction::Sub: return UndefValue::get(C1->getType()); case Instruction::And: if (isa(C1) && isa(C2)) // undef & undef -> undef return C1; return Constant::getNullValue(C1->getType()); // undef & X -> 0 case Instruction::Mul: { // undef * undef -> undef if (isa(C1) && isa(C2)) return C1; const APInt *CV; // X * undef -> undef if X is odd if (match(C1, m_APInt(CV)) || match(C2, m_APInt(CV))) if ((*CV)[0]) return UndefValue::get(C1->getType()); // X * undef -> 0 otherwise return Constant::getNullValue(C1->getType()); } case Instruction::SDiv: case Instruction::UDiv: // X / undef -> undef if (isa(C2)) return C2; // undef / 0 -> undef // undef / 1 -> undef if (match(C2, m_Zero()) || match(C2, m_One())) return C1; // undef / X -> 0 otherwise return Constant::getNullValue(C1->getType()); case Instruction::URem: case Instruction::SRem: // X % undef -> undef if (match(C2, m_Undef())) return C2; // undef % 0 -> undef if (match(C2, m_Zero())) return C1; // undef % X -> 0 otherwise return Constant::getNullValue(C1->getType()); case Instruction::Or: // X | undef -> -1 if (isa(C1) && isa(C2)) // undef | undef -> undef return C1; return Constant::getAllOnesValue(C1->getType()); // undef | X -> ~0 case Instruction::LShr: // X >>l undef -> undef if (isa(C2)) return C2; // undef >>l 0 -> undef if (match(C2, m_Zero())) return C1; // undef >>l X -> 0 return Constant::getNullValue(C1->getType()); case Instruction::AShr: // X >>a undef -> undef if (isa(C2)) return C2; // undef >>a 0 -> undef if (match(C2, m_Zero())) return C1; // TODO: undef >>a X -> undef if the shift is exact // undef >>a X -> 0 return Constant::getNullValue(C1->getType()); case Instruction::Shl: // X << undef -> undef if (isa(C2)) return C2; // undef << 0 -> undef if (match(C2, m_Zero())) return C1; // undef << X -> 0 return Constant::getNullValue(C1->getType()); case Instruction::FAdd: case Instruction::FSub: case Instruction::FMul: case Instruction::FDiv: case Instruction::FRem: // TODO: UNDEF handling for binary float instructions. return nullptr; case Instruction::BinaryOpsEnd: llvm_unreachable("Invalid BinaryOp"); } } // At this point neither constant should be an UndefValue. assert(!isa(C1) && !isa(C2) && "Unexpected UndefValue"); // Handle simplifications when the RHS is a constant int. if (ConstantInt *CI2 = dyn_cast(C2)) { switch (Opcode) { case Instruction::Add: if (CI2->isZero()) return C1; // X + 0 == X break; case Instruction::Sub: if (CI2->isZero()) return C1; // X - 0 == X break; case Instruction::Mul: if (CI2->isZero()) return C2; // X * 0 == 0 if (CI2->isOne()) return C1; // X * 1 == X break; case Instruction::UDiv: case Instruction::SDiv: if (CI2->isOne()) return C1; // X / 1 == X if (CI2->isZero()) return UndefValue::get(CI2->getType()); // X / 0 == undef break; case Instruction::URem: case Instruction::SRem: if (CI2->isOne()) return Constant::getNullValue(CI2->getType()); // X % 1 == 0 if (CI2->isZero()) return UndefValue::get(CI2->getType()); // X % 0 == undef break; case Instruction::And: if (CI2->isZero()) return C2; // X & 0 == 0 if (CI2->isMinusOne()) return C1; // X & -1 == X if (ConstantExpr *CE1 = dyn_cast(C1)) { // (zext i32 to i64) & 4294967295 -> (zext i32 to i64) if (CE1->getOpcode() == Instruction::ZExt) { unsigned DstWidth = CI2->getType()->getBitWidth(); unsigned SrcWidth = CE1->getOperand(0)->getType()->getPrimitiveSizeInBits(); APInt PossiblySetBits(APInt::getLowBitsSet(DstWidth, SrcWidth)); if ((PossiblySetBits & CI2->getValue()) == PossiblySetBits) return C1; } // If and'ing the address of a global with a constant, fold it. if (CE1->getOpcode() == Instruction::PtrToInt && isa(CE1->getOperand(0))) { GlobalValue *GV = cast(CE1->getOperand(0)); // Functions are at least 4-byte aligned. unsigned GVAlign = GV->getAlignment(); if (isa(GV)) GVAlign = std::max(GVAlign, 4U); if (GVAlign > 1) { unsigned DstWidth = CI2->getType()->getBitWidth(); unsigned SrcWidth = std::min(DstWidth, Log2_32(GVAlign)); APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth)); // If checking bits we know are clear, return zero. if ((CI2->getValue() & BitsNotSet) == CI2->getValue()) return Constant::getNullValue(CI2->getType()); } } } break; case Instruction::Or: if (CI2->isZero()) return C1; // X | 0 == X if (CI2->isMinusOne()) return C2; // X | -1 == -1 break; case Instruction::Xor: if (CI2->isZero()) return C1; // X ^ 0 == X if (ConstantExpr *CE1 = dyn_cast(C1)) { switch (CE1->getOpcode()) { default: break; case Instruction::ICmp: case Instruction::FCmp: // cmp pred ^ true -> cmp !pred assert(CI2->isOne()); CmpInst::Predicate pred = (CmpInst::Predicate)CE1->getPredicate(); pred = CmpInst::getInversePredicate(pred); return ConstantExpr::getCompare(pred, CE1->getOperand(0), CE1->getOperand(1)); } } break; case Instruction::AShr: // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2 if (ConstantExpr *CE1 = dyn_cast(C1)) if (CE1->getOpcode() == Instruction::ZExt) // Top bits known zero. return ConstantExpr::getLShr(C1, C2); break; } } else if (isa(C1)) { // If C1 is a ConstantInt and C2 is not, swap the operands. if (Instruction::isCommutative(Opcode)) return ConstantExpr::get(Opcode, C2, C1); } if (ConstantInt *CI1 = dyn_cast(C1)) { if (ConstantInt *CI2 = dyn_cast(C2)) { const APInt &C1V = CI1->getValue(); const APInt &C2V = CI2->getValue(); switch (Opcode) { default: break; case Instruction::Add: return ConstantInt::get(CI1->getContext(), C1V + C2V); case Instruction::Sub: return ConstantInt::get(CI1->getContext(), C1V - C2V); case Instruction::Mul: return ConstantInt::get(CI1->getContext(), C1V * C2V); case Instruction::UDiv: assert(!CI2->isZero() && "Div by zero handled above"); return ConstantInt::get(CI1->getContext(), C1V.udiv(C2V)); case Instruction::SDiv: assert(!CI2->isZero() && "Div by zero handled above"); if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) return UndefValue::get(CI1->getType()); // MIN_INT / -1 -> undef return ConstantInt::get(CI1->getContext(), C1V.sdiv(C2V)); case Instruction::URem: assert(!CI2->isZero() && "Div by zero handled above"); return ConstantInt::get(CI1->getContext(), C1V.urem(C2V)); case Instruction::SRem: assert(!CI2->isZero() && "Div by zero handled above"); if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) return UndefValue::get(CI1->getType()); // MIN_INT % -1 -> undef return ConstantInt::get(CI1->getContext(), C1V.srem(C2V)); case Instruction::And: return ConstantInt::get(CI1->getContext(), C1V & C2V); case Instruction::Or: return ConstantInt::get(CI1->getContext(), C1V | C2V); case Instruction::Xor: return ConstantInt::get(CI1->getContext(), C1V ^ C2V); case Instruction::Shl: if (C2V.ult(C1V.getBitWidth())) return ConstantInt::get(CI1->getContext(), C1V.shl(C2V)); return UndefValue::get(C1->getType()); // too big shift is undef case Instruction::LShr: if (C2V.ult(C1V.getBitWidth())) return ConstantInt::get(CI1->getContext(), C1V.lshr(C2V)); return UndefValue::get(C1->getType()); // too big shift is undef case Instruction::AShr: if (C2V.ult(C1V.getBitWidth())) return ConstantInt::get(CI1->getContext(), C1V.ashr(C2V)); return UndefValue::get(C1->getType()); // too big shift is undef } } switch (Opcode) { case Instruction::SDiv: case Instruction::UDiv: case Instruction::URem: case Instruction::SRem: case Instruction::LShr: case Instruction::AShr: case Instruction::Shl: if (CI1->isZero()) return C1; break; default: break; } } else if (ConstantFP *CFP1 = dyn_cast(C1)) { if (ConstantFP *CFP2 = dyn_cast(C2)) { const APFloat &C1V = CFP1->getValueAPF(); const APFloat &C2V = CFP2->getValueAPF(); APFloat C3V = C1V; // copy for modification switch (Opcode) { default: break; case Instruction::FAdd: (void)C3V.add(C2V, APFloat::rmNearestTiesToEven); return ConstantFP::get(C1->getContext(), C3V); case Instruction::FSub: (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven); return ConstantFP::get(C1->getContext(), C3V); case Instruction::FMul: (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven); return ConstantFP::get(C1->getContext(), C3V); case Instruction::FDiv: (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven); return ConstantFP::get(C1->getContext(), C3V); case Instruction::FRem: (void)C3V.mod(C2V); return ConstantFP::get(C1->getContext(), C3V); } } } else if (VectorType *VTy = dyn_cast(C1->getType())) { // Perform elementwise folding. SmallVector Result; Type *Ty = IntegerType::get(VTy->getContext(), 32); for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { Constant *ExtractIdx = ConstantInt::get(Ty, i); Constant *LHS = ConstantExpr::getExtractElement(C1, ExtractIdx); Constant *RHS = ConstantExpr::getExtractElement(C2, ExtractIdx); // If any element of a divisor vector is zero, the whole op is undef. if ((Opcode == Instruction::SDiv || Opcode == Instruction::UDiv || Opcode == Instruction::SRem || Opcode == Instruction::URem) && RHS->isNullValue()) return UndefValue::get(VTy); Result.push_back(ConstantExpr::get(Opcode, LHS, RHS)); } return ConstantVector::get(Result); } if (ConstantExpr *CE1 = dyn_cast(C1)) { // There are many possible foldings we could do here. We should probably // at least fold add of a pointer with an integer into the appropriate // getelementptr. This will improve alias analysis a bit. // Given ((a + b) + c), if (b + c) folds to something interesting, return // (a + (b + c)). if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) { Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2); if (!isa(T) || cast(T)->getOpcode() != Opcode) return ConstantExpr::get(Opcode, CE1->getOperand(0), T); } } else if (isa(C2)) { // If C2 is a constant expr and C1 isn't, flop them around and fold the // other way if possible. if (Instruction::isCommutative(Opcode)) return ConstantFoldBinaryInstruction(Opcode, C2, C1); } // i1 can be simplified in many cases. if (C1->getType()->isIntegerTy(1)) { switch (Opcode) { case Instruction::Add: case Instruction::Sub: return ConstantExpr::getXor(C1, C2); case Instruction::Mul: return ConstantExpr::getAnd(C1, C2); case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: // We can assume that C2 == 0. If it were one the result would be // undefined because the shift value is as large as the bitwidth. return C1; case Instruction::SDiv: case Instruction::UDiv: // We can assume that C2 == 1. If it were zero the result would be // undefined through division by zero. return C1; case Instruction::URem: case Instruction::SRem: // We can assume that C2 == 1. If it were zero the result would be // undefined through division by zero. return ConstantInt::getFalse(C1->getContext()); default: break; } } // We don't know how to fold this. return nullptr; } /// This type is zero-sized if it's an array or structure of zero-sized types. /// The only leaf zero-sized type is an empty structure. static bool isMaybeZeroSizedType(Type *Ty) { if (StructType *STy = dyn_cast(Ty)) { if (STy->isOpaque()) return true; // Can't say. // If all of elements have zero size, this does too. for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) if (!isMaybeZeroSizedType(STy->getElementType(i))) return false; return true; } else if (ArrayType *ATy = dyn_cast(Ty)) { return isMaybeZeroSizedType(ATy->getElementType()); } return false; } /// Compare the two constants as though they were getelementptr indices. /// This allows coercion of the types to be the same thing. /// /// If the two constants are the "same" (after coercion), return 0. If the /// first is less than the second, return -1, if the second is less than the /// first, return 1. If the constants are not integral, return -2. /// static int IdxCompare(Constant *C1, Constant *C2, Type *ElTy) { if (C1 == C2) return 0; // Ok, we found a different index. If they are not ConstantInt, we can't do // anything with them. if (!isa(C1) || !isa(C2)) return -2; // don't know! // We cannot compare the indices if they don't fit in an int64_t. if (cast(C1)->getValue().getActiveBits() > 64 || cast(C2)->getValue().getActiveBits() > 64) return -2; // don't know! // Ok, we have two differing integer indices. Sign extend them to be the same // type. int64_t C1Val = cast(C1)->getSExtValue(); int64_t C2Val = cast(C2)->getSExtValue(); if (C1Val == C2Val) return 0; // They are equal // If the type being indexed over is really just a zero sized type, there is // no pointer difference being made here. if (isMaybeZeroSizedType(ElTy)) return -2; // dunno. // If they are really different, now that they are the same type, then we // found a difference! if (C1Val < C2Val) return -1; else return 1; } /// This function determines if there is anything we can decide about the two /// constants provided. This doesn't need to handle simple things like /// ConstantFP comparisons, but should instead handle ConstantExprs. /// If we can determine that the two constants have a particular relation to /// each other, we should return the corresponding FCmpInst predicate, /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in /// ConstantFoldCompareInstruction. /// /// To simplify this code we canonicalize the relation so that the first /// operand is always the most "complex" of the two. We consider ConstantFP /// to be the simplest, and ConstantExprs to be the most complex. static FCmpInst::Predicate evaluateFCmpRelation(Constant *V1, Constant *V2) { assert(V1->getType() == V2->getType() && "Cannot compare values of different types!"); // Handle degenerate case quickly if (V1 == V2) return FCmpInst::FCMP_OEQ; if (!isa(V1)) { if (!isa(V2)) { // Simple case, use the standard constant folder. ConstantInt *R = nullptr; R = dyn_cast( ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, V1, V2)); if (R && !R->isZero()) return FCmpInst::FCMP_OEQ; R = dyn_cast( ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, V1, V2)); if (R && !R->isZero()) return FCmpInst::FCMP_OLT; R = dyn_cast( ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, V1, V2)); if (R && !R->isZero()) return FCmpInst::FCMP_OGT; // Nothing more we can do return FCmpInst::BAD_FCMP_PREDICATE; } // If the first operand is simple and second is ConstantExpr, swap operands. FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(V2, V1); if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE) return FCmpInst::getSwappedPredicate(SwappedRelation); } else { // Ok, the LHS is known to be a constantexpr. The RHS can be any of a // constantexpr or a simple constant. ConstantExpr *CE1 = cast(V1); switch (CE1->getOpcode()) { case Instruction::FPTrunc: case Instruction::FPExt: case Instruction::UIToFP: case Instruction::SIToFP: // We might be able to do something with these but we don't right now. break; default: break; } } // There are MANY other foldings that we could perform here. They will // probably be added on demand, as they seem needed. return FCmpInst::BAD_FCMP_PREDICATE; } static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1, const GlobalValue *GV2) { auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) { if (GV->hasExternalWeakLinkage() || GV->hasWeakAnyLinkage()) return true; if (const auto *GVar = dyn_cast(GV)) { Type *Ty = GVar->getValueType(); // A global with opaque type might end up being zero sized. if (!Ty->isSized()) return true; // A global with an empty type might lie at the address of any other // global. if (Ty->isEmptyTy()) return true; } return false; }; // Don't try to decide equality of aliases. if (!isa(GV1) && !isa(GV2)) if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2)) return ICmpInst::ICMP_NE; return ICmpInst::BAD_ICMP_PREDICATE; } /// This function determines if there is anything we can decide about the two /// constants provided. This doesn't need to handle simple things like integer /// comparisons, but should instead handle ConstantExprs and GlobalValues. /// If we can determine that the two constants have a particular relation to /// each other, we should return the corresponding ICmp predicate, otherwise /// return ICmpInst::BAD_ICMP_PREDICATE. /// /// To simplify this code we canonicalize the relation so that the first /// operand is always the most "complex" of the two. We consider simple /// constants (like ConstantInt) to be the simplest, followed by /// GlobalValues, followed by ConstantExpr's (the most complex). /// static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2, bool isSigned) { assert(V1->getType() == V2->getType() && "Cannot compare different types of values!"); if (V1 == V2) return ICmpInst::ICMP_EQ; if (!isa(V1) && !isa(V1) && !isa(V1)) { if (!isa(V2) && !isa(V2) && !isa(V2)) { // We distilled this down to a simple case, use the standard constant // folder. ConstantInt *R = nullptr; ICmpInst::Predicate pred = ICmpInst::ICMP_EQ; R = dyn_cast(ConstantExpr::getICmp(pred, V1, V2)); if (R && !R->isZero()) return pred; pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; R = dyn_cast(ConstantExpr::getICmp(pred, V1, V2)); if (R && !R->isZero()) return pred; pred = isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; R = dyn_cast(ConstantExpr::getICmp(pred, V1, V2)); if (R && !R->isZero()) return pred; // If we couldn't figure it out, bail. return ICmpInst::BAD_ICMP_PREDICATE; } // If the first operand is simple, swap operands. ICmpInst::Predicate SwappedRelation = evaluateICmpRelation(V2, V1, isSigned); if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) return ICmpInst::getSwappedPredicate(SwappedRelation); } else if (const GlobalValue *GV = dyn_cast(V1)) { if (isa(V2)) { // Swap as necessary. ICmpInst::Predicate SwappedRelation = evaluateICmpRelation(V2, V1, isSigned); if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) return ICmpInst::getSwappedPredicate(SwappedRelation); return ICmpInst::BAD_ICMP_PREDICATE; } // Now we know that the RHS is a GlobalValue, BlockAddress or simple // constant (which, since the types must match, means that it's a // ConstantPointerNull). if (const GlobalValue *GV2 = dyn_cast(V2)) { return areGlobalsPotentiallyEqual(GV, GV2); } else if (isa(V2)) { return ICmpInst::ICMP_NE; // Globals never equal labels. } else { assert(isa(V2) && "Canonicalization guarantee!"); // GlobalVals can never be null unless they have external weak linkage. // We don't try to evaluate aliases here. if (!GV->hasExternalWeakLinkage() && !isa(GV)) return ICmpInst::ICMP_NE; } } else if (const BlockAddress *BA = dyn_cast(V1)) { if (isa(V2)) { // Swap as necessary. ICmpInst::Predicate SwappedRelation = evaluateICmpRelation(V2, V1, isSigned); if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) return ICmpInst::getSwappedPredicate(SwappedRelation); return ICmpInst::BAD_ICMP_PREDICATE; } // Now we know that the RHS is a GlobalValue, BlockAddress or simple // constant (which, since the types must match, means that it is a // ConstantPointerNull). if (const BlockAddress *BA2 = dyn_cast(V2)) { // Block address in another function can't equal this one, but block // addresses in the current function might be the same if blocks are // empty. if (BA2->getFunction() != BA->getFunction()) return ICmpInst::ICMP_NE; } else { // Block addresses aren't null, don't equal the address of globals. assert((isa(V2) || isa(V2)) && "Canonicalization guarantee!"); return ICmpInst::ICMP_NE; } } else { // Ok, the LHS is known to be a constantexpr. The RHS can be any of a // constantexpr, a global, block address, or a simple constant. ConstantExpr *CE1 = cast(V1); Constant *CE1Op0 = CE1->getOperand(0); switch (CE1->getOpcode()) { case Instruction::Trunc: case Instruction::FPTrunc: case Instruction::FPExt: case Instruction::FPToUI: case Instruction::FPToSI: break; // We can't evaluate floating point casts or truncations. case Instruction::UIToFP: case Instruction::SIToFP: case Instruction::BitCast: case Instruction::ZExt: case Instruction::SExt: // We can't evaluate floating point casts or truncations. if (CE1Op0->getType()->isFloatingPointTy()) break; // If the cast is not actually changing bits, and the second operand is a // null pointer, do the comparison with the pre-casted value. if (V2->isNullValue() && (CE1->getType()->isPointerTy() || CE1->getType()->isIntegerTy())) { if (CE1->getOpcode() == Instruction::ZExt) isSigned = false; if (CE1->getOpcode() == Instruction::SExt) isSigned = true; return evaluateICmpRelation(CE1Op0, Constant::getNullValue(CE1Op0->getType()), isSigned); } break; case Instruction::GetElementPtr: { GEPOperator *CE1GEP = cast(CE1); // Ok, since this is a getelementptr, we know that the constant has a // pointer type. Check the various cases. if (isa(V2)) { // If we are comparing a GEP to a null pointer, check to see if the base // of the GEP equals the null pointer. if (const GlobalValue *GV = dyn_cast(CE1Op0)) { if (GV->hasExternalWeakLinkage()) // Weak linkage GVals could be zero or not. We're comparing that // to null pointer so its greater-or-equal return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; else // If its not weak linkage, the GVal must have a non-zero address // so the result is greater-than return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; } else if (isa(CE1Op0)) { // If we are indexing from a null pointer, check to see if we have any // non-zero indices. for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i) if (!CE1->getOperand(i)->isNullValue()) // Offsetting from null, must not be equal. return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; // Only zero indexes from null, must still be zero. return ICmpInst::ICMP_EQ; } // Otherwise, we can't really say if the first operand is null or not. } else if (const GlobalValue *GV2 = dyn_cast(V2)) { if (isa(CE1Op0)) { if (GV2->hasExternalWeakLinkage()) // Weak linkage GVals could be zero or not. We're comparing it to // a null pointer, so its less-or-equal return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; else // If its not weak linkage, the GVal must have a non-zero address // so the result is less-than return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; } else if (const GlobalValue *GV = dyn_cast(CE1Op0)) { if (GV == GV2) { // If this is a getelementptr of the same global, then it must be // different. Because the types must match, the getelementptr could // only have at most one index, and because we fold getelementptr's // with a single zero index, it must be nonzero. assert(CE1->getNumOperands() == 2 && !CE1->getOperand(1)->isNullValue() && "Surprising getelementptr!"); return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; } else { if (CE1GEP->hasAllZeroIndices()) return areGlobalsPotentiallyEqual(GV, GV2); return ICmpInst::BAD_ICMP_PREDICATE; } } } else { ConstantExpr *CE2 = cast(V2); Constant *CE2Op0 = CE2->getOperand(0); // There are MANY other foldings that we could perform here. They will // probably be added on demand, as they seem needed. switch (CE2->getOpcode()) { default: break; case Instruction::GetElementPtr: // By far the most common case to handle is when the base pointers are // obviously to the same global. if (isa(CE1Op0) && isa(CE2Op0)) { // Don't know relative ordering, but check for inequality. if (CE1Op0 != CE2Op0) { GEPOperator *CE2GEP = cast(CE2); if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices()) return areGlobalsPotentiallyEqual(cast(CE1Op0), cast(CE2Op0)); return ICmpInst::BAD_ICMP_PREDICATE; } // Ok, we know that both getelementptr instructions are based on the // same global. From this, we can precisely determine the relative // ordering of the resultant pointers. unsigned i = 1; // The logic below assumes that the result of the comparison // can be determined by finding the first index that differs. // This doesn't work if there is over-indexing in any // subsequent indices, so check for that case first. if (!CE1->isGEPWithNoNotionalOverIndexing() || !CE2->isGEPWithNoNotionalOverIndexing()) return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. // Compare all of the operands the GEP's have in common. gep_type_iterator GTI = gep_type_begin(CE1); for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); ++i, ++GTI) switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i), GTI.getIndexedType())) { case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT; case 1: return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT; case -2: return ICmpInst::BAD_ICMP_PREDICATE; } // Ok, we ran out of things they have in common. If any leftovers // are non-zero then we have a difference, otherwise we are equal. for (; i < CE1->getNumOperands(); ++i) if (!CE1->getOperand(i)->isNullValue()) { if (isa(CE1->getOperand(i))) return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; else return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. } for (; i < CE2->getNumOperands(); ++i) if (!CE2->getOperand(i)->isNullValue()) { if (isa(CE2->getOperand(i))) return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; else return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. } return ICmpInst::ICMP_EQ; } } } break; } default: break; } } return ICmpInst::BAD_ICMP_PREDICATE; } Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred, Constant *C1, Constant *C2) { Type *ResultTy; if (VectorType *VT = dyn_cast(C1->getType())) ResultTy = VectorType::get(Type::getInt1Ty(C1->getContext()), VT->getNumElements()); else ResultTy = Type::getInt1Ty(C1->getContext()); // Fold FCMP_FALSE/FCMP_TRUE unconditionally. if (pred == FCmpInst::FCMP_FALSE) return Constant::getNullValue(ResultTy); if (pred == FCmpInst::FCMP_TRUE) return Constant::getAllOnesValue(ResultTy); // Handle some degenerate cases first if (isa(C1) || isa(C2)) { CmpInst::Predicate Predicate = CmpInst::Predicate(pred); bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate); // For EQ and NE, we can always pick a value for the undef to make the // predicate pass or fail, so we can return undef. // Also, if both operands are undef, we can return undef for int comparison. if (ICmpInst::isEquality(Predicate) || (isIntegerPredicate && C1 == C2)) return UndefValue::get(ResultTy); // Otherwise, for integer compare, pick the same value as the non-undef // operand, and fold it to true or false. if (isIntegerPredicate) return ConstantInt::get(ResultTy, CmpInst::isTrueWhenEqual(Predicate)); // Choosing NaN for the undef will always make unordered comparison succeed // and ordered comparison fails. return ConstantInt::get(ResultTy, CmpInst::isUnordered(Predicate)); } // icmp eq/ne(null,GV) -> false/true if (C1->isNullValue()) { if (const GlobalValue *GV = dyn_cast(C2)) // Don't try to evaluate aliases. External weak GV can be null. if (!isa(GV) && !GV->hasExternalWeakLinkage()) { if (pred == ICmpInst::ICMP_EQ) return ConstantInt::getFalse(C1->getContext()); else if (pred == ICmpInst::ICMP_NE) return ConstantInt::getTrue(C1->getContext()); } // icmp eq/ne(GV,null) -> false/true } else if (C2->isNullValue()) { if (const GlobalValue *GV = dyn_cast(C1)) // Don't try to evaluate aliases. External weak GV can be null. if (!isa(GV) && !GV->hasExternalWeakLinkage()) { if (pred == ICmpInst::ICMP_EQ) return ConstantInt::getFalse(C1->getContext()); else if (pred == ICmpInst::ICMP_NE) return ConstantInt::getTrue(C1->getContext()); } } // If the comparison is a comparison between two i1's, simplify it. if (C1->getType()->isIntegerTy(1)) { switch(pred) { case ICmpInst::ICMP_EQ: if (isa(C2)) return ConstantExpr::getXor(C1, ConstantExpr::getNot(C2)); return ConstantExpr::getXor(ConstantExpr::getNot(C1), C2); case ICmpInst::ICMP_NE: return ConstantExpr::getXor(C1, C2); default: break; } } if (isa(C1) && isa(C2)) { const APInt &V1 = cast(C1)->getValue(); const APInt &V2 = cast(C2)->getValue(); switch (pred) { default: llvm_unreachable("Invalid ICmp Predicate"); case ICmpInst::ICMP_EQ: return ConstantInt::get(ResultTy, V1 == V2); case ICmpInst::ICMP_NE: return ConstantInt::get(ResultTy, V1 != V2); case ICmpInst::ICMP_SLT: return ConstantInt::get(ResultTy, V1.slt(V2)); case ICmpInst::ICMP_SGT: return ConstantInt::get(ResultTy, V1.sgt(V2)); case ICmpInst::ICMP_SLE: return ConstantInt::get(ResultTy, V1.sle(V2)); case ICmpInst::ICMP_SGE: return ConstantInt::get(ResultTy, V1.sge(V2)); case ICmpInst::ICMP_ULT: return ConstantInt::get(ResultTy, V1.ult(V2)); case ICmpInst::ICMP_UGT: return ConstantInt::get(ResultTy, V1.ugt(V2)); case ICmpInst::ICMP_ULE: return ConstantInt::get(ResultTy, V1.ule(V2)); case ICmpInst::ICMP_UGE: return ConstantInt::get(ResultTy, V1.uge(V2)); } } else if (isa(C1) && isa(C2)) { const APFloat &C1V = cast(C1)->getValueAPF(); const APFloat &C2V = cast(C2)->getValueAPF(); APFloat::cmpResult R = C1V.compare(C2V); switch (pred) { default: llvm_unreachable("Invalid FCmp Predicate"); case FCmpInst::FCMP_FALSE: return Constant::getNullValue(ResultTy); case FCmpInst::FCMP_TRUE: return Constant::getAllOnesValue(ResultTy); case FCmpInst::FCMP_UNO: return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered); case FCmpInst::FCMP_ORD: return ConstantInt::get(ResultTy, R!=APFloat::cmpUnordered); case FCmpInst::FCMP_UEQ: return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || R==APFloat::cmpEqual); case FCmpInst::FCMP_OEQ: return ConstantInt::get(ResultTy, R==APFloat::cmpEqual); case FCmpInst::FCMP_UNE: return ConstantInt::get(ResultTy, R!=APFloat::cmpEqual); case FCmpInst::FCMP_ONE: return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || R==APFloat::cmpGreaterThan); case FCmpInst::FCMP_ULT: return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || R==APFloat::cmpLessThan); case FCmpInst::FCMP_OLT: return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan); case FCmpInst::FCMP_UGT: return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || R==APFloat::cmpGreaterThan); case FCmpInst::FCMP_OGT: return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan); case FCmpInst::FCMP_ULE: return ConstantInt::get(ResultTy, R!=APFloat::cmpGreaterThan); case FCmpInst::FCMP_OLE: return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || R==APFloat::cmpEqual); case FCmpInst::FCMP_UGE: return ConstantInt::get(ResultTy, R!=APFloat::cmpLessThan); case FCmpInst::FCMP_OGE: return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan || R==APFloat::cmpEqual); } } else if (C1->getType()->isVectorTy()) { // If we can constant fold the comparison of each element, constant fold // the whole vector comparison. SmallVector ResElts; Type *Ty = IntegerType::get(C1->getContext(), 32); // Compare the elements, producing an i1 result or constant expr. for (unsigned i = 0, e = C1->getType()->getVectorNumElements(); i != e;++i){ Constant *C1E = ConstantExpr::getExtractElement(C1, ConstantInt::get(Ty, i)); Constant *C2E = ConstantExpr::getExtractElement(C2, ConstantInt::get(Ty, i)); ResElts.push_back(ConstantExpr::getCompare(pred, C1E, C2E)); } return ConstantVector::get(ResElts); } if (C1->getType()->isFloatingPointTy() && // Only call evaluateFCmpRelation if we have a constant expr to avoid // infinite recursive loop (isa(C1) || isa(C2))) { int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. switch (evaluateFCmpRelation(C1, C2)) { default: llvm_unreachable("Unknown relation!"); case FCmpInst::FCMP_UNO: case FCmpInst::FCMP_ORD: case FCmpInst::FCMP_UEQ: case FCmpInst::FCMP_UNE: case FCmpInst::FCMP_ULT: case FCmpInst::FCMP_UGT: case FCmpInst::FCMP_ULE: case FCmpInst::FCMP_UGE: case FCmpInst::FCMP_TRUE: case FCmpInst::FCMP_FALSE: case FCmpInst::BAD_FCMP_PREDICATE: break; // Couldn't determine anything about these constants. case FCmpInst::FCMP_OEQ: // We know that C1 == C2 Result = (pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE || pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); break; case FCmpInst::FCMP_OLT: // We know that C1 < C2 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT || pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE); break; case FCmpInst::FCMP_OGT: // We know that C1 > C2 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT || pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); break; case FCmpInst::FCMP_OLE: // We know that C1 <= C2 // We can only partially decide this relation. if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) Result = 0; else if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) Result = 1; break; case FCmpInst::FCMP_OGE: // We known that C1 >= C2 // We can only partially decide this relation. if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) Result = 0; else if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) Result = 1; break; case FCmpInst::FCMP_ONE: // We know that C1 != C2 // We can only partially decide this relation. if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ) Result = 0; else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE) Result = 1; break; } // If we evaluated the result, return it now. if (Result != -1) return ConstantInt::get(ResultTy, Result); } else { // Evaluate the relation between the two constants, per the predicate. int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. switch (evaluateICmpRelation(C1, C2, CmpInst::isSigned((CmpInst::Predicate)pred))) { default: llvm_unreachable("Unknown relational!"); case ICmpInst::BAD_ICMP_PREDICATE: break; // Couldn't determine anything about these constants. case ICmpInst::ICMP_EQ: // We know the constants are equal! // If we know the constants are equal, we can decide the result of this // computation precisely. Result = ICmpInst::isTrueWhenEqual((ICmpInst::Predicate)pred); break; case ICmpInst::ICMP_ULT: switch (pred) { case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE: Result = 1; break; case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE: Result = 0; break; } break; case ICmpInst::ICMP_SLT: switch (pred) { case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE: Result = 1; break; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE: Result = 0; break; } break; case ICmpInst::ICMP_UGT: switch (pred) { case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE: Result = 1; break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE: Result = 0; break; } break; case ICmpInst::ICMP_SGT: switch (pred) { case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE: Result = 1; break; case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE: Result = 0; break; } break; case ICmpInst::ICMP_ULE: if (pred == ICmpInst::ICMP_UGT) Result = 0; if (pred == ICmpInst::ICMP_ULT || pred == ICmpInst::ICMP_ULE) Result = 1; break; case ICmpInst::ICMP_SLE: if (pred == ICmpInst::ICMP_SGT) Result = 0; if (pred == ICmpInst::ICMP_SLT || pred == ICmpInst::ICMP_SLE) Result = 1; break; case ICmpInst::ICMP_UGE: if (pred == ICmpInst::ICMP_ULT) Result = 0; if (pred == ICmpInst::ICMP_UGT || pred == ICmpInst::ICMP_UGE) Result = 1; break; case ICmpInst::ICMP_SGE: if (pred == ICmpInst::ICMP_SLT) Result = 0; if (pred == ICmpInst::ICMP_SGT || pred == ICmpInst::ICMP_SGE) Result = 1; break; case ICmpInst::ICMP_NE: if (pred == ICmpInst::ICMP_EQ) Result = 0; if (pred == ICmpInst::ICMP_NE) Result = 1; break; } // If we evaluated the result, return it now. if (Result != -1) return ConstantInt::get(ResultTy, Result); // If the right hand side is a bitcast, try using its inverse to simplify // it by moving it to the left hand side. We can't do this if it would turn // a vector compare into a scalar compare or visa versa. if (ConstantExpr *CE2 = dyn_cast(C2)) { Constant *CE2Op0 = CE2->getOperand(0); if (CE2->getOpcode() == Instruction::BitCast && CE2->getType()->isVectorTy() == CE2Op0->getType()->isVectorTy()) { Constant *Inverse = ConstantExpr::getBitCast(C1, CE2Op0->getType()); return ConstantExpr::getICmp(pred, Inverse, CE2Op0); } } // If the left hand side is an extension, try eliminating it. if (ConstantExpr *CE1 = dyn_cast(C1)) { if ((CE1->getOpcode() == Instruction::SExt && ICmpInst::isSigned((ICmpInst::Predicate)pred)) || (CE1->getOpcode() == Instruction::ZExt && !ICmpInst::isSigned((ICmpInst::Predicate)pred))){ Constant *CE1Op0 = CE1->getOperand(0); Constant *CE1Inverse = ConstantExpr::getTrunc(CE1, CE1Op0->getType()); if (CE1Inverse == CE1Op0) { // Check whether we can safely truncate the right hand side. Constant *C2Inverse = ConstantExpr::getTrunc(C2, CE1Op0->getType()); if (ConstantExpr::getCast(CE1->getOpcode(), C2Inverse, C2->getType()) == C2) return ConstantExpr::getICmp(pred, CE1Inverse, C2Inverse); } } } if ((!isa(C1) && isa(C2)) || (C1->isNullValue() && !C2->isNullValue())) { // If C2 is a constant expr and C1 isn't, flip them around and fold the // other way if possible. // Also, if C1 is null and C2 isn't, flip them around. pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred); return ConstantExpr::getICmp(pred, C2, C1); } } return nullptr; } /// Test whether the given sequence of *normalized* indices is "inbounds". template static bool isInBoundsIndices(ArrayRef Idxs) { // No indices means nothing that could be out of bounds. if (Idxs.empty()) return true; // If the first index is zero, it's in bounds. if (cast(Idxs[0])->isNullValue()) return true; // If the first index is one and all the rest are zero, it's in bounds, // by the one-past-the-end rule. - if (!cast(Idxs[0])->isOne()) - return false; + if (auto *CI = dyn_cast(Idxs[0])) { + if (!CI->isOne()) + return false; + } else { + auto *CV = cast(Idxs[0]); + CI = dyn_cast_or_null(CV->getSplatValue()); + if (!CI || !CI->isOne()) + return false; + } + for (unsigned i = 1, e = Idxs.size(); i != e; ++i) if (!cast(Idxs[i])->isNullValue()) return false; return true; } /// Test whether a given ConstantInt is in-range for a SequentialType. static bool isIndexInRangeOfArrayType(uint64_t NumElements, const ConstantInt *CI) { // We cannot bounds check the index if it doesn't fit in an int64_t. if (CI->getValue().getActiveBits() > 64) return false; // A negative index or an index past the end of our sequential type is // considered out-of-range. int64_t IndexVal = CI->getSExtValue(); if (IndexVal < 0 || (NumElements > 0 && (uint64_t)IndexVal >= NumElements)) return false; // Otherwise, it is in-range. return true; } Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C, bool InBounds, Optional InRangeIndex, ArrayRef Idxs) { if (Idxs.empty()) return C; - if (isa(C)) { - Type *GEPTy = GetElementPtrInst::getGEPReturnType( - C, makeArrayRef((Value * const *)Idxs.data(), Idxs.size())); + Type *GEPTy = GetElementPtrInst::getGEPReturnType( + C, makeArrayRef((Value *const *)Idxs.data(), Idxs.size())); + + if (isa(C)) return UndefValue::get(GEPTy); - } Constant *Idx0 = cast(Idxs[0]); if (Idxs.size() == 1 && (Idx0->isNullValue() || isa(Idx0))) - return C; + return GEPTy->isVectorTy() && !C->getType()->isVectorTy() + ? ConstantVector::getSplat( + cast(GEPTy)->getNumElements(), C) + : C; if (C->isNullValue()) { bool isNull = true; for (unsigned i = 0, e = Idxs.size(); i != e; ++i) if (!isa(Idxs[i]) && !cast(Idxs[i])->isNullValue()) { isNull = false; break; } if (isNull) { PointerType *PtrTy = cast(C->getType()->getScalarType()); Type *Ty = GetElementPtrInst::getIndexedType(PointeeTy, Idxs); assert(Ty && "Invalid indices for GEP!"); Type *OrigGEPTy = PointerType::get(Ty, PtrTy->getAddressSpace()); Type *GEPTy = PointerType::get(Ty, PtrTy->getAddressSpace()); if (VectorType *VT = dyn_cast(C->getType())) GEPTy = VectorType::get(OrigGEPTy, VT->getNumElements()); // The GEP returns a vector of pointers when one of more of // its arguments is a vector. for (unsigned i = 0, e = Idxs.size(); i != e; ++i) { if (auto *VT = dyn_cast(Idxs[i]->getType())) { GEPTy = VectorType::get(OrigGEPTy, VT->getNumElements()); break; } } return Constant::getNullValue(GEPTy); } } if (ConstantExpr *CE = dyn_cast(C)) { // Combine Indices - If the source pointer to this getelementptr instruction // is a getelementptr instruction, combine the indices of the two // getelementptr instructions into a single instruction. // if (CE->getOpcode() == Instruction::GetElementPtr) { gep_type_iterator LastI = gep_type_end(CE); for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); I != E; ++I) LastI = I; // We cannot combine indices if doing so would take us outside of an // array or vector. Doing otherwise could trick us if we evaluated such a // GEP as part of a load. // // e.g. Consider if the original GEP was: // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c, // i32 0, i32 0, i64 0) // // If we then tried to offset it by '8' to get to the third element, // an i8, we should *not* get: // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c, // i32 0, i32 0, i64 8) // // This GEP tries to index array element '8 which runs out-of-bounds. // Subsequent evaluation would get confused and produce erroneous results. // // The following prohibits such a GEP from being formed by checking to see // if the index is in-range with respect to an array. // TODO: This code may be extended to handle vectors as well. bool PerformFold = false; if (Idx0->isNullValue()) PerformFold = true; else if (LastI.isSequential()) if (ConstantInt *CI = dyn_cast(Idx0)) PerformFold = (!LastI.isBoundedSequential() || isIndexInRangeOfArrayType( LastI.getSequentialNumElements(), CI)) && !CE->getOperand(CE->getNumOperands() - 1) ->getType() ->isVectorTy(); if (PerformFold) { SmallVector NewIndices; NewIndices.reserve(Idxs.size() + CE->getNumOperands()); NewIndices.append(CE->op_begin() + 1, CE->op_end() - 1); // Add the last index of the source with the first index of the new GEP. // Make sure to handle the case when they are actually different types. Constant *Combined = CE->getOperand(CE->getNumOperands()-1); // Otherwise it must be an array. if (!Idx0->isNullValue()) { Type *IdxTy = Combined->getType(); if (IdxTy != Idx0->getType()) { unsigned CommonExtendedWidth = std::max(IdxTy->getIntegerBitWidth(), Idx0->getType()->getIntegerBitWidth()); CommonExtendedWidth = std::max(CommonExtendedWidth, 64U); Type *CommonTy = Type::getIntNTy(IdxTy->getContext(), CommonExtendedWidth); Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, CommonTy); Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined, CommonTy); Combined = ConstantExpr::get(Instruction::Add, C1, C2); } else { Combined = ConstantExpr::get(Instruction::Add, Idx0, Combined); } } NewIndices.push_back(Combined); NewIndices.append(Idxs.begin() + 1, Idxs.end()); // The combined GEP normally inherits its index inrange attribute from // the inner GEP, but if the inner GEP's last index was adjusted by the // outer GEP, any inbounds attribute on that index is invalidated. Optional IRIndex = cast(CE)->getInRangeIndex(); if (IRIndex && *IRIndex == CE->getNumOperands() - 2 && !Idx0->isNullValue()) IRIndex = None; return ConstantExpr::getGetElementPtr( cast(CE)->getSourceElementType(), CE->getOperand(0), NewIndices, InBounds && cast(CE)->isInBounds(), IRIndex); } } // Attempt to fold casts to the same type away. For example, folding: // // i32* getelementptr ([2 x i32]* bitcast ([3 x i32]* %X to [2 x i32]*), // i64 0, i64 0) // into: // // i32* getelementptr ([3 x i32]* %X, i64 0, i64 0) // // Don't fold if the cast is changing address spaces. if (CE->isCast() && Idxs.size() > 1 && Idx0->isNullValue()) { PointerType *SrcPtrTy = dyn_cast(CE->getOperand(0)->getType()); PointerType *DstPtrTy = dyn_cast(CE->getType()); if (SrcPtrTy && DstPtrTy) { ArrayType *SrcArrayTy = dyn_cast(SrcPtrTy->getElementType()); ArrayType *DstArrayTy = dyn_cast(DstPtrTy->getElementType()); if (SrcArrayTy && DstArrayTy && SrcArrayTy->getElementType() == DstArrayTy->getElementType() && SrcPtrTy->getAddressSpace() == DstPtrTy->getAddressSpace()) return ConstantExpr::getGetElementPtr(SrcArrayTy, (Constant *)CE->getOperand(0), Idxs, InBounds, InRangeIndex); } } } // Check to see if any array indices are not within the corresponding // notional array or vector bounds. If so, try to determine if they can be // factored out into preceding dimensions. SmallVector NewIdxs; Type *Ty = PointeeTy; Type *Prev = C->getType(); bool Unknown = !isa(Idxs[0]) && !isa(Idxs[0]); for (unsigned i = 1, e = Idxs.size(); i != e; Prev = Ty, Ty = cast(Ty)->getTypeAtIndex(Idxs[i]), ++i) { if (!isa(Idxs[i]) && !isa(Idxs[i])) { // We don't know if it's in range or not. Unknown = true; continue; } if (!isa(Idxs[i - 1]) && !isa(Idxs[i - 1])) // Skip if the type of the previous index is not supported. continue; if (InRangeIndex && i == *InRangeIndex + 1) { // If an index is marked inrange, we cannot apply this canonicalization to // the following index, as that will cause the inrange index to point to // the wrong element. continue; } if (isa(Ty)) { // The verify makes sure that GEPs into a struct are in range. continue; } auto *STy = cast(Ty); if (isa(STy)) { // There can be awkward padding in after a non-power of two vector. Unknown = true; continue; } if (ConstantInt *CI = dyn_cast(Idxs[i])) { if (isIndexInRangeOfArrayType(STy->getNumElements(), CI)) // It's in range, skip to the next index. continue; if (CI->getSExtValue() < 0) { // It's out of range and negative, don't try to factor it. Unknown = true; continue; } } else { auto *CV = cast(Idxs[i]); bool InRange = true; for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { auto *CI = cast(CV->getElementAsConstant(I)); InRange &= isIndexInRangeOfArrayType(STy->getNumElements(), CI); if (CI->getSExtValue() < 0) { Unknown = true; break; } } if (InRange || Unknown) // It's in range, skip to the next index. // It's out of range and negative, don't try to factor it. continue; } if (isa(Prev)) { // It's out of range, but the prior dimension is a struct // so we can't do anything about it. Unknown = true; continue; } // It's out of range, but we can factor it into the prior // dimension. NewIdxs.resize(Idxs.size()); // Determine the number of elements in our sequential type. uint64_t NumElements = STy->getArrayNumElements(); // Expand the current index or the previous index to a vector from a scalar // if necessary. Constant *CurrIdx = cast(Idxs[i]); auto *PrevIdx = NewIdxs[i - 1] ? NewIdxs[i - 1] : cast(Idxs[i - 1]); bool IsCurrIdxVector = CurrIdx->getType()->isVectorTy(); bool IsPrevIdxVector = PrevIdx->getType()->isVectorTy(); bool UseVector = IsCurrIdxVector || IsPrevIdxVector; if (!IsCurrIdxVector && IsPrevIdxVector) CurrIdx = ConstantDataVector::getSplat( PrevIdx->getType()->getVectorNumElements(), CurrIdx); if (!IsPrevIdxVector && IsCurrIdxVector) PrevIdx = ConstantDataVector::getSplat( CurrIdx->getType()->getVectorNumElements(), PrevIdx); Constant *Factor = ConstantInt::get(CurrIdx->getType()->getScalarType(), NumElements); if (UseVector) Factor = ConstantDataVector::getSplat( IsPrevIdxVector ? PrevIdx->getType()->getVectorNumElements() : CurrIdx->getType()->getVectorNumElements(), Factor); NewIdxs[i] = ConstantExpr::getSRem(CurrIdx, Factor); Constant *Div = ConstantExpr::getSDiv(CurrIdx, Factor); unsigned CommonExtendedWidth = std::max(PrevIdx->getType()->getScalarSizeInBits(), Div->getType()->getScalarSizeInBits()); CommonExtendedWidth = std::max(CommonExtendedWidth, 64U); // Before adding, extend both operands to i64 to avoid // overflow trouble. Type *ExtendedTy = Type::getIntNTy(Div->getContext(), CommonExtendedWidth); if (UseVector) ExtendedTy = VectorType::get( ExtendedTy, IsPrevIdxVector ? PrevIdx->getType()->getVectorNumElements() : CurrIdx->getType()->getVectorNumElements()); if (!PrevIdx->getType()->isIntOrIntVectorTy(CommonExtendedWidth)) PrevIdx = ConstantExpr::getSExt(PrevIdx, ExtendedTy); if (!Div->getType()->isIntOrIntVectorTy(CommonExtendedWidth)) Div = ConstantExpr::getSExt(Div, ExtendedTy); NewIdxs[i - 1] = ConstantExpr::getAdd(PrevIdx, Div); } // If we did any factoring, start over with the adjusted indices. if (!NewIdxs.empty()) { for (unsigned i = 0, e = Idxs.size(); i != e; ++i) if (!NewIdxs[i]) NewIdxs[i] = cast(Idxs[i]); return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds, InRangeIndex); } // If all indices are known integers and normalized, we can do a simple // check for the "inbounds" property. if (!Unknown && !InBounds) if (auto *GV = dyn_cast(C)) if (!GV->hasExternalWeakLinkage() && isInBoundsIndices(Idxs)) return ConstantExpr::getGetElementPtr(PointeeTy, C, Idxs, /*InBounds=*/true, InRangeIndex); return nullptr; }