1 //===-- InstructionSimplify.h - Fold instrs into simpler forms --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file declares routines for folding instructions into simpler forms 10 // that do not require creating new instructions. This does constant folding 11 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 12 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value 13 // ("and i32 %x, %x" -> "%x"). If the simplification is also an instruction 14 // then it dominates the original instruction. 15 // 16 // These routines implicitly resolve undef uses. The easiest way to be safe when 17 // using these routines to obtain simplified values for existing instructions is 18 // to always replace all uses of the instructions with the resulting simplified 19 // values. This will prevent other code from seeing the same undef uses and 20 // resolving them to different values. 21 // 22 // They require that all the IR that they encounter be valid and inserted into a 23 // parent function. 24 // 25 // Additionally, these routines can't simplify to the instructions that are not 26 // def-reachable, meaning we can't just scan the basic block for instructions 27 // to simplify to. 28 // 29 //===----------------------------------------------------------------------===// 30 31 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H 32 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H 33 34 #include "llvm/IR/PatternMatch.h" 35 36 namespace llvm { 37 38 template <typename T, typename... TArgs> class AnalysisManager; 39 template <class T> class ArrayRef; 40 class AssumptionCache; 41 class BinaryOperator; 42 class CallBase; 43 class DataLayout; 44 class DominatorTree; 45 class Function; 46 class Instruction; 47 struct LoopStandardAnalysisResults; 48 class MDNode; 49 class Pass; 50 template <class T, unsigned n> class SmallSetVector; 51 class TargetLibraryInfo; 52 class Type; 53 class Value; 54 55 /// InstrInfoQuery provides an interface to query additional information for 56 /// instructions like metadata or keywords like nsw, which provides conservative 57 /// results if the users specified it is safe to use. 58 struct InstrInfoQuery { 59 InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {} 60 InstrInfoQuery() = default; 61 bool UseInstrInfo = true; 62 63 MDNode *getMetadata(const Instruction *I, unsigned KindID) const { 64 if (UseInstrInfo) 65 return I->getMetadata(KindID); 66 return nullptr; 67 } 68 69 template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const { 70 if (UseInstrInfo) 71 return Op->hasNoUnsignedWrap(); 72 return false; 73 } 74 75 template <class InstT> bool hasNoSignedWrap(const InstT *Op) const { 76 if (UseInstrInfo) 77 return Op->hasNoSignedWrap(); 78 return false; 79 } 80 81 bool isExact(const BinaryOperator *Op) const { 82 if (UseInstrInfo && isa<PossiblyExactOperator>(Op)) 83 return cast<PossiblyExactOperator>(Op)->isExact(); 84 return false; 85 } 86 87 template <class InstT> bool hasNoSignedZeros(const InstT *Op) const { 88 if (UseInstrInfo) 89 return Op->hasNoSignedZeros(); 90 return false; 91 } 92 }; 93 94 struct SimplifyQuery { 95 const DataLayout &DL; 96 const TargetLibraryInfo *TLI = nullptr; 97 const DominatorTree *DT = nullptr; 98 AssumptionCache *AC = nullptr; 99 const Instruction *CxtI = nullptr; 100 101 // Wrapper to query additional information for instructions like metadata or 102 // keywords like nsw, which provides conservative results if those cannot 103 // be safely used. 104 const InstrInfoQuery IIQ; 105 106 /// Controls whether simplifications are allowed to constrain the range of 107 /// possible values for uses of undef. If it is false, simplifications are not 108 /// allowed to assume a particular value for a use of undef for example. 109 bool CanUseUndef = true; 110 111 SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr) 112 : DL(DL), CxtI(CXTI) {} 113 114 SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI, 115 const DominatorTree *DT = nullptr, 116 AssumptionCache *AC = nullptr, 117 const Instruction *CXTI = nullptr, bool UseInstrInfo = true, 118 bool CanUseUndef = true) 119 : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo), 120 CanUseUndef(CanUseUndef) {} 121 SimplifyQuery getWithInstruction(Instruction *I) const { 122 SimplifyQuery Copy(*this); 123 Copy.CxtI = I; 124 return Copy; 125 } 126 SimplifyQuery getWithoutUndef() const { 127 SimplifyQuery Copy(*this); 128 Copy.CanUseUndef = false; 129 return Copy; 130 } 131 132 /// If CanUseUndef is true, returns whether \p V is undef. 133 /// Otherwise always return false. 134 bool isUndefValue(Value *V) const { 135 if (!CanUseUndef) 136 return false; 137 138 using namespace PatternMatch; 139 return match(V, m_Undef()); 140 } 141 }; 142 143 // NOTE: the explicit multiple argument versions of these functions are 144 // deprecated. 145 // Please use the SimplifyQuery versions in new code. 146 147 /// Given operands for an Add, fold the result or return null. 148 Value *simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, 149 const SimplifyQuery &Q); 150 151 /// Given operands for a Sub, fold the result or return null. 152 Value *simplifySubInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, 153 const SimplifyQuery &Q); 154 155 /// Given operands for a Mul, fold the result or return null. 156 Value *simplifyMulInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, 157 const SimplifyQuery &Q); 158 159 /// Given operands for an SDiv, fold the result or return null. 160 Value *simplifySDivInst(Value *LHS, Value *RHS, bool IsExact, 161 const SimplifyQuery &Q); 162 163 /// Given operands for a UDiv, fold the result or return null. 164 Value *simplifyUDivInst(Value *LHS, Value *RHS, bool IsExact, 165 const SimplifyQuery &Q); 166 167 /// Given operands for an SRem, fold the result or return null. 168 Value *simplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 169 170 /// Given operands for a URem, fold the result or return null. 171 Value *simplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 172 173 /// Given operand for an FNeg, fold the result or return null. 174 Value *simplifyFNegInst(Value *Op, FastMathFlags FMF, const SimplifyQuery &Q); 175 176 177 /// Given operands for an FAdd, fold the result or return null. 178 Value * 179 simplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, 180 const SimplifyQuery &Q, 181 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 182 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 183 184 /// Given operands for an FSub, fold the result or return null. 185 Value * 186 simplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, 187 const SimplifyQuery &Q, 188 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 189 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 190 191 /// Given operands for an FMul, fold the result or return null. 192 Value * 193 simplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF, 194 const SimplifyQuery &Q, 195 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 196 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 197 198 /// Given operands for the multiplication of a FMA, fold the result or return 199 /// null. In contrast to simplifyFMulInst, this function will not perform 200 /// simplifications whose unrounded results differ when rounded to the argument 201 /// type. 202 Value *simplifyFMAFMul(Value *LHS, Value *RHS, FastMathFlags FMF, 203 const SimplifyQuery &Q, 204 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 205 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 206 207 /// Given operands for an FDiv, fold the result or return null. 208 Value * 209 simplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, 210 const SimplifyQuery &Q, 211 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 212 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 213 214 /// Given operands for an FRem, fold the result or return null. 215 Value * 216 simplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF, 217 const SimplifyQuery &Q, 218 fp::ExceptionBehavior ExBehavior = fp::ebIgnore, 219 RoundingMode Rounding = RoundingMode::NearestTiesToEven); 220 221 /// Given operands for a Shl, fold the result or return null. 222 Value *simplifyShlInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW, 223 const SimplifyQuery &Q); 224 225 /// Given operands for a LShr, fold the result or return null. 226 Value *simplifyLShrInst(Value *Op0, Value *Op1, bool IsExact, 227 const SimplifyQuery &Q); 228 229 /// Given operands for a AShr, fold the result or return nulll. 230 Value *simplifyAShrInst(Value *Op0, Value *Op1, bool IsExact, 231 const SimplifyQuery &Q); 232 233 /// Given operands for an And, fold the result or return null. 234 Value *simplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 235 236 /// Given operands for an Or, fold the result or return null. 237 Value *simplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 238 239 /// Given operands for an Xor, fold the result or return null. 240 Value *simplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 241 242 /// Given operands for an ICmpInst, fold the result or return null. 243 Value *simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 244 const SimplifyQuery &Q); 245 246 /// Given operands for an FCmpInst, fold the result or return null. 247 Value *simplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 248 FastMathFlags FMF, const SimplifyQuery &Q); 249 250 /// Given operands for a SelectInst, fold the result or return null. 251 Value *simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 252 const SimplifyQuery &Q); 253 254 /// Given operands for a GetElementPtrInst, fold the result or return null. 255 Value *simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef<Value *> Indices, 256 bool InBounds, const SimplifyQuery &Q); 257 258 /// Given operands for an InsertValueInst, fold the result or return null. 259 Value *simplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, 260 const SimplifyQuery &Q); 261 262 /// Given operands for an InsertElement, fold the result or return null. 263 Value *simplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx, 264 const SimplifyQuery &Q); 265 266 /// Given operands for an ExtractValueInst, fold the result or return null. 267 Value *simplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs, 268 const SimplifyQuery &Q); 269 270 /// Given operands for an ExtractElementInst, fold the result or return null. 271 Value *simplifyExtractElementInst(Value *Vec, Value *Idx, 272 const SimplifyQuery &Q); 273 274 /// Given operands for a CastInst, fold the result or return null. 275 Value *simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, 276 const SimplifyQuery &Q); 277 278 /// Given operands for a ShuffleVectorInst, fold the result or return null. 279 /// See class ShuffleVectorInst for a description of the mask representation. 280 Value *simplifyShuffleVectorInst(Value *Op0, Value *Op1, ArrayRef<int> Mask, 281 Type *RetTy, const SimplifyQuery &Q); 282 283 //=== Helper functions for higher up the class hierarchy. 284 285 /// Given operands for a CmpInst, fold the result or return null. 286 Value *simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 287 const SimplifyQuery &Q); 288 289 /// Given operand for a UnaryOperator, fold the result or return null. 290 Value *simplifyUnOp(unsigned Opcode, Value *Op, const SimplifyQuery &Q); 291 292 /// Given operand for a UnaryOperator, fold the result or return null. 293 /// Try to use FastMathFlags when folding the result. 294 Value *simplifyUnOp(unsigned Opcode, Value *Op, FastMathFlags FMF, 295 const SimplifyQuery &Q); 296 297 /// Given operands for a BinaryOperator, fold the result or return null. 298 Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 299 const SimplifyQuery &Q); 300 301 /// Given operands for a BinaryOperator, fold the result or return null. 302 /// Try to use FastMathFlags when folding the result. 303 Value *simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, FastMathFlags FMF, 304 const SimplifyQuery &Q); 305 306 /// Given a callsite, callee, and arguments, fold the result or return null. 307 Value *simplifyCall(CallBase *Call, Value *Callee, ArrayRef<Value *> Args, 308 const SimplifyQuery &Q); 309 310 /// Given a constrained FP intrinsic call, tries to compute its simplified 311 /// version. Returns a simplified result or null. 312 /// 313 /// This function provides an additional contract: it guarantees that if 314 /// simplification succeeds that the intrinsic is side effect free. As a result, 315 /// successful simplification can be used to delete the intrinsic not just 316 /// replace its result. 317 Value *simplifyConstrainedFPCall(CallBase *Call, const SimplifyQuery &Q); 318 319 /// Given an operand for a Freeze, see if we can fold the result. 320 /// If not, this returns null. 321 Value *simplifyFreezeInst(Value *Op, const SimplifyQuery &Q); 322 323 /// Given a load instruction and its pointer operand, fold the result or return 324 /// null. 325 Value *simplifyLoadInst(LoadInst *LI, Value *PtrOp, const SimplifyQuery &Q); 326 327 /// See if we can compute a simplified version of this instruction. If not, 328 /// return null. 329 Value *simplifyInstruction(Instruction *I, const SimplifyQuery &Q); 330 331 /// Like \p simplifyInstruction but the operands of \p I are replaced with 332 /// \p NewOps. Returns a simplified value, or null if none was found. 333 Value * 334 simplifyInstructionWithOperands(Instruction *I, ArrayRef<Value *> NewOps, 335 const SimplifyQuery &Q); 336 337 /// See if V simplifies when its operand Op is replaced with RepOp. If not, 338 /// return null. 339 /// AllowRefinement specifies whether the simplification can be a refinement 340 /// (e.g. 0 instead of poison), or whether it needs to be strictly identical. 341 /// Op and RepOp can be assumed to not be poison when determining refinement. 342 Value *simplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, 343 const SimplifyQuery &Q, bool AllowRefinement); 344 345 /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively. 346 /// 347 /// This first performs a normal RAUW of I with SimpleV. It then recursively 348 /// attempts to simplify those users updated by the operation. The 'I' 349 /// instruction must not be equal to the simplified value 'SimpleV'. 350 /// If UnsimplifiedUsers is provided, instructions that could not be simplified 351 /// are added to it. 352 /// 353 /// The function returns true if any simplifications were performed. 354 bool replaceAndRecursivelySimplify( 355 Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI = nullptr, 356 const DominatorTree *DT = nullptr, AssumptionCache *AC = nullptr, 357 SmallSetVector<Instruction *, 8> *UnsimplifiedUsers = nullptr); 358 359 // These helper functions return a SimplifyQuery structure that contains as 360 // many of the optional analysis we use as are currently valid. This is the 361 // strongly preferred way of constructing SimplifyQuery in passes. 362 const SimplifyQuery getBestSimplifyQuery(Pass &, Function &); 363 template <class T, class... TArgs> 364 const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &, 365 Function &); 366 const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &, 367 const DataLayout &); 368 } // end namespace llvm 369 370 #endif 371