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