contrib/llvm/include/llvm/Analysis/InstructionSimplify.h

   1 //===-- InstructionSimplify.h - Fold instrs into simpler forms --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares routines for folding instructions into simpler forms
  11 // that do not require creating new instructions.  This does constant folding
  12 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
  13 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
  14 // ("and i32 %x, %x" -> "%x").  If the simplification is also an instruction
  15 // then it dominates the original instruction.
  16 //
  17 // These routines implicitly resolve undef uses. The easiest way to be safe when
  18 // using these routines to obtain simplified values for existing instructions is
  19 // to always replace all uses of the instructions with the resulting simplified
  20 // values. This will prevent other code from seeing the same undef uses and
  21 // resolving them to different values.
  22 //
  23 // These routines are designed to tolerate moderately incomplete IR, such as
  24 // instructions that are not connected to basic blocks yet. However, they do
  25 // require that all the IR that they encounter be valid. In particular, they
  26 // require that all non-constant values be defined in the same function, and the
  27 // same call context of that function (and not split between caller and callee
  28 // contexts of a directly recursive call, for example).
  29 //
  30 //===----------------------------------------------------------------------===//
  31
  32 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
  33 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
  34
  35 #include "llvm/IR/User.h"
  36
  37 namespace llvm {
  38 class Function;
  39 template <typename T, typename... TArgs> class AnalysisManager;
  40 template <class T> class ArrayRef;
  41 class AssumptionCache;
  42 class DominatorTree;
  43 class Instruction;
  44 class DataLayout;
  45 class FastMathFlags;
  46 struct LoopStandardAnalysisResults;
  47 class OptimizationRemarkEmitter;
  48 class Pass;
  49 class TargetLibraryInfo;
  50 class Type;
  51 class Value;
  52
  53 struct SimplifyQuery {
  54   const DataLayout &DL;
  55   const TargetLibraryInfo *TLI = nullptr;
  56   const DominatorTree *DT = nullptr;
  57   AssumptionCache *AC = nullptr;
  58   const Instruction *CxtI = nullptr;
  59
  60   SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
  61       : DL(DL), CxtI(CXTI) {}
  62
  63   SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI,
  64                 const DominatorTree *DT = nullptr,
  65                 AssumptionCache *AC = nullptr,
  66                 const Instruction *CXTI = nullptr)
  67       : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI) {}
  68   SimplifyQuery getWithInstruction(Instruction *I) const {
  69     SimplifyQuery Copy(*this);
  70     Copy.CxtI = I;
  71     return Copy;
  72   }
  73   };
  74
  75   // NOTE: the explicit multiple argument versions of these functions are
  76   // deprecated.
  77   // Please use the SimplifyQuery versions in new code.
  78
  79   /// Given operands for an Add, fold the result or return null.
  80   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  81                        const SimplifyQuery &Q);
  82
  83   /// Given operands for a Sub, fold the result or return null.
  84   Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  85                          const SimplifyQuery &Q);
  86
  87   /// Given operands for an FAdd, fold the result or return null.
  88   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  89                           const SimplifyQuery &Q);
  90
  91   /// Given operands for an FSub, fold the result or return null.
  92   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  93                           const SimplifyQuery &Q);
  94
  95   /// Given operands for an FMul, fold the result or return null.
  96   Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  97                           const SimplifyQuery &Q);
  98
  99   /// Given operands for a Mul, fold the result or return null.
 100   Value *SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 101
 102   /// Given operands for an SDiv, fold the result or return null.
 103   Value *SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 104
 105   /// Given operands for a UDiv, fold the result or return null.
 106   Value *SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 107
 108   /// Given operands for an FDiv, fold the result or return null.
 109   Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 110                           const SimplifyQuery &Q);
 111
 112   /// Given operands for an SRem, fold the result or return null.
 113   Value *SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 114
 115   /// Given operands for a URem, fold the result or return null.
 116   Value *SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 117
 118   /// Given operands for an FRem, fold the result or return null.
 119   Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 120                           const SimplifyQuery &Q);
 121
 122   /// Given operands for a Shl, fold the result or return null.
 123   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 124                          const SimplifyQuery &Q);
 125
 126   /// Given operands for a LShr, fold the result or return null.
 127   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
 128                           const SimplifyQuery &Q);
 129
 130   /// Given operands for a AShr, fold the result or return nulll.
 131   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
 132                           const SimplifyQuery &Q);
 133
 134   /// Given operands for an And, fold the result or return null.
 135   Value *SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 136
 137   /// Given operands for an Or, fold the result or return null.
 138   Value *SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 139
 140   /// Given operands for an Xor, fold the result or return null.
 141   Value *SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 142
 143   /// Given operands for an ICmpInst, fold the result or return null.
 144   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 145                           const SimplifyQuery &Q);
 146
 147   /// Given operands for an FCmpInst, fold the result or return null.
 148   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 149                           FastMathFlags FMF, const SimplifyQuery &Q);
 150
 151   /// Given operands for a SelectInst, fold the result or return null.
 152   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
 153                             const SimplifyQuery &Q);
 154
 155   /// Given operands for a GetElementPtrInst, fold the result or return null.
 156   Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
 157                          const SimplifyQuery &Q);
 158
 159   /// Given operands for an InsertValueInst, fold the result or return null.
 160   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
 161                                  ArrayRef<unsigned> Idxs,
 162                                  const SimplifyQuery &Q);
 163
 164   /// Given operands for an ExtractValueInst, fold the result or return null.
 165   Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
 166                                   const SimplifyQuery &Q);
 167
 168   /// Given operands for an ExtractElementInst, fold the result or return null.
 169   Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
 170                                     const SimplifyQuery &Q);
 171
 172   /// Given operands for a CastInst, fold the result or return null.
 173   Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
 174                           const SimplifyQuery &Q);
 175
 176   /// Given operands for a ShuffleVectorInst, fold the result or return null.
 177   Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
 178                                    Type *RetTy, const SimplifyQuery &Q);
 179
 180   //=== Helper functions for higher up the class hierarchy.
 181
 182
 183   /// Given operands for a CmpInst, fold the result or return null.
 184   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 185                          const SimplifyQuery &Q);
 186
 187   /// Given operands for a BinaryOperator, fold the result or return null.
 188   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 189                        const SimplifyQuery &Q);
 190
 191   /// Given operands for an FP BinaryOperator, fold the result or return null.
 192   /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
 193   /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
 194   Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 195                          FastMathFlags FMF, const SimplifyQuery &Q);
 196
 197   /// Given a function and iterators over arguments, fold the result or return
 198   /// null.
 199   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
 200                       User::op_iterator ArgEnd, const SimplifyQuery &Q);
 201
 202   /// Given a function and set of arguments, fold the result or return null.
 203   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, const SimplifyQuery &Q);
 204
 205   /// See if we can compute a simplified version of this instruction. If not,
 206   /// return null.
 207   Value *SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
 208                              OptimizationRemarkEmitter *ORE = nullptr);
 209
 210   /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
 211   ///
 212   /// This first performs a normal RAUW of I with SimpleV. It then recursively
 213   /// attempts to simplify those users updated by the operation. The 'I'
 214   /// instruction must not be equal to the simplified value 'SimpleV'.
 215   ///
 216   /// The function returns true if any simplifications were performed.
 217   bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
 218                                      const TargetLibraryInfo *TLI = nullptr,
 219                                      const DominatorTree *DT = nullptr,
 220                                      AssumptionCache *AC = nullptr);
 221
 222   /// Recursively attempt to simplify an instruction.
 223   ///
 224   /// This routine uses SimplifyInstruction to simplify 'I', and if successful
 225   /// replaces uses of 'I' with the simplified value. It then recurses on each
 226   /// of the users impacted. It returns true if any simplifications were
 227   /// performed.
 228   bool recursivelySimplifyInstruction(Instruction *I,
 229                                       const TargetLibraryInfo *TLI = nullptr,
 230                                       const DominatorTree *DT = nullptr,
 231                                       AssumptionCache *AC = nullptr);
 232   // These helper functions return a SimplifyQuery structure that contains as
 233   // many of the optional analysis we use as are currently valid.  This is the
 234   // strongly preferred way of constructing SimplifyQuery in passes.
 235   const SimplifyQuery getBestSimplifyQuery(Pass &, Function &);
 236   template <class T, class... TArgs>
 237   const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &,
 238                                            Function &);
 239   const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &,
 240                                            const DataLayout &);
 241 } // end namespace llvm
 242
 243 #endif
 244