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/Instruction.h" 39#include "llvm/IR/Operator.h" 40#include "llvm/IR/PatternMatch.h" 41 42namespace llvm { 43 44template <typename T, typename... TArgs> class AnalysisManager; 45template <class T> class ArrayRef; 46class AssumptionCache; 47class BinaryOperator; 48class CallBase; 49class DataLayout; 50class DominatorTree; 51class Function; 52struct LoopStandardAnalysisResults; 53class MDNode; 54class OptimizationRemarkEmitter; 55class Pass; 56template <class T, unsigned n> class SmallSetVector; 57class TargetLibraryInfo; 58class Type; 59class Value; 60 61/// InstrInfoQuery provides an interface to query additional information for 62/// instructions like metadata or keywords like nsw, which provides conservative 63/// results if the users specified it is safe to use. 64struct InstrInfoQuery { 65 InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {} 66 InstrInfoQuery() : UseInstrInfo(true) {} 67 bool UseInstrInfo = true; 68 69 MDNode *getMetadata(const Instruction *I, unsigned KindID) const { 70 if (UseInstrInfo) 71 return I->getMetadata(KindID); 72 return nullptr; 73 } 74 75 template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const { 76 if (UseInstrInfo) 77 return Op->hasNoUnsignedWrap(); 78 return false; 79 } 80 81 template <class InstT> bool hasNoSignedWrap(const InstT *Op) const { 82 if (UseInstrInfo) 83 return Op->hasNoSignedWrap(); 84 return false; 85 } 86 87 bool isExact(const BinaryOperator *Op) const { 88 if (UseInstrInfo && isa<PossiblyExactOperator>(Op)) 89 return cast<PossiblyExactOperator>(Op)->isExact(); 90 return false; 91 } 92}; 93 94struct 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 operand for an FNeg, fold the result or return null. 148Value *SimplifyFNegInst(Value *Op, FastMathFlags FMF, 149 const SimplifyQuery &Q); 150 151/// Given operands for an Add, fold the result or return null. 152Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, 153 const SimplifyQuery &Q); 154 155/// Given operands for a Sub, fold the result or return null. 156Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, 157 const SimplifyQuery &Q); 158 159/// Given operands for an FAdd, fold the result or return null. 160Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, 161 const SimplifyQuery &Q); 162 163/// Given operands for an FSub, fold the result or return null. 164Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, 165 const SimplifyQuery &Q); 166 167/// Given operands for an FMul, fold the result or return null. 168Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF, 169 const SimplifyQuery &Q); 170 171/// Given operands for the multiplication of a FMA, fold the result or return 172/// null. In contrast to SimplifyFMulInst, this function will not perform 173/// simplifications whose unrounded results differ when rounded to the argument 174/// type. 175Value *SimplifyFMAFMul(Value *LHS, Value *RHS, FastMathFlags FMF, 176 const SimplifyQuery &Q); 177 178/// Given operands for a Mul, fold the result or return null. 179Value *SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 180 181/// Given operands for an SDiv, fold the result or return null. 182Value *SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 183 184/// Given operands for a UDiv, fold the result or return null. 185Value *SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 186 187/// Given operands for an FDiv, fold the result or return null. 188Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, 189 const SimplifyQuery &Q); 190 191/// Given operands for an SRem, fold the result or return null. 192Value *SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 193 194/// Given operands for a URem, fold the result or return null. 195Value *SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 196 197/// Given operands for an FRem, fold the result or return null. 198Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF, 199 const SimplifyQuery &Q); 200 201/// Given operands for a Shl, fold the result or return null. 202Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 203 const SimplifyQuery &Q); 204 205/// Given operands for a LShr, fold the result or return null. 206Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 207 const SimplifyQuery &Q); 208 209/// Given operands for a AShr, fold the result or return nulll. 210Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 211 const SimplifyQuery &Q); 212 213/// Given operands for an And, fold the result or return null. 214Value *SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 215 216/// Given operands for an Or, fold the result or return null. 217Value *SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 218 219/// Given operands for an Xor, fold the result or return null. 220Value *SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q); 221 222/// Given operands for an ICmpInst, fold the result or return null. 223Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 224 const SimplifyQuery &Q); 225 226/// Given operands for an FCmpInst, fold the result or return null. 227Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 228 FastMathFlags FMF, const SimplifyQuery &Q); 229 230/// Given operands for a SelectInst, fold the result or return null. 231Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 232 const SimplifyQuery &Q); 233 234/// Given operands for a GetElementPtrInst, fold the result or return null. 235Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops, 236 const SimplifyQuery &Q); 237 238/// Given operands for an InsertValueInst, fold the result or return null. 239Value *SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, 240 const SimplifyQuery &Q); 241 242/// Given operands for an InsertElement, fold the result or return null. 243Value *SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx, 244 const SimplifyQuery &Q); 245 246/// Given operands for an ExtractValueInst, fold the result or return null. 247Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs, 248 const SimplifyQuery &Q); 249 250/// Given operands for an ExtractElementInst, fold the result or return null. 251Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, 252 const SimplifyQuery &Q); 253 254/// Given operands for a CastInst, fold the result or return null. 255Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, 256 const SimplifyQuery &Q); 257 258/// Given operands for a ShuffleVectorInst, fold the result or return null. 259/// See class ShuffleVectorInst for a description of the mask representation. 260Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, ArrayRef<int> Mask, 261 Type *RetTy, const SimplifyQuery &Q); 262 263//=== Helper functions for higher up the class hierarchy. 264 265/// Given operands for a CmpInst, fold the result or return null. 266Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 267 const SimplifyQuery &Q); 268 269/// Given operand for a UnaryOperator, fold the result or return null. 270Value *SimplifyUnOp(unsigned Opcode, Value *Op, const SimplifyQuery &Q); 271 272/// Given operand for a UnaryOperator, fold the result or return null. 273/// Try to use FastMathFlags when folding the result. 274Value *SimplifyUnOp(unsigned Opcode, Value *Op, FastMathFlags FMF, 275 const SimplifyQuery &Q); 276 277/// Given operands for a BinaryOperator, fold the result or return null. 278Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 279 const SimplifyQuery &Q); 280 281/// Given operands for a BinaryOperator, fold the result or return null. 282/// Try to use FastMathFlags when folding the result. 283Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 284 FastMathFlags FMF, const SimplifyQuery &Q); 285 286/// Given a callsite, fold the result or return null. 287Value *SimplifyCall(CallBase *Call, const SimplifyQuery &Q); 288 289/// Given an operand for a Freeze, see if we can fold the result. 290/// If not, this returns null. 291Value *SimplifyFreezeInst(Value *Op, const SimplifyQuery &Q); 292 293/// See if we can compute a simplified version of this instruction. If not, 294/// return null. 295Value *SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, 296 OptimizationRemarkEmitter *ORE = nullptr); 297 298/// See if V simplifies when its operand Op is replaced with RepOp. If not, 299/// return null. 300/// AllowRefinement specifies whether the simplification can be a refinement 301/// (e.g. 0 instead of poison), or whether it needs to be strictly identical. 302Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, 303 const SimplifyQuery &Q, bool AllowRefinement); 304 305/// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively. 306/// 307/// This first performs a normal RAUW of I with SimpleV. It then recursively 308/// attempts to simplify those users updated by the operation. The 'I' 309/// instruction must not be equal to the simplified value 'SimpleV'. 310/// If UnsimplifiedUsers is provided, instructions that could not be simplified 311/// are added to it. 312/// 313/// The function returns true if any simplifications were performed. 314bool replaceAndRecursivelySimplify( 315 Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI = nullptr, 316 const DominatorTree *DT = nullptr, AssumptionCache *AC = nullptr, 317 SmallSetVector<Instruction *, 8> *UnsimplifiedUsers = nullptr); 318 319// These helper functions return a SimplifyQuery structure that contains as 320// many of the optional analysis we use as are currently valid. This is the 321// strongly preferred way of constructing SimplifyQuery in passes. 322const SimplifyQuery getBestSimplifyQuery(Pass &, Function &); 323template <class T, class... TArgs> 324const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &, 325 Function &); 326const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &, 327 const DataLayout &); 328} // end namespace llvm 329 330#endif 331 332