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   template<typename T>
  39   class ArrayRef;
  40   class AssumptionCache;
  41   class DominatorTree;
  42   class Instruction;
  43   class DataLayout;
  44   class FastMathFlags;
  45   class OptimizationRemarkEmitter;
  46   class TargetLibraryInfo;
  47   class Type;
  48   class Value;
  49
  50   /// Given operands for an Add, fold the result or return null.
  51   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  52                          const DataLayout &DL,
  53                          const TargetLibraryInfo *TLI = nullptr,
  54                          const DominatorTree *DT = nullptr,
  55                          AssumptionCache *AC = nullptr,
  56                          const Instruction *CxtI = nullptr);
  57
  58   /// Given operands for a Sub, fold the result or return null.
  59   Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  60                          const DataLayout &DL,
  61                          const TargetLibraryInfo *TLI = nullptr,
  62                          const DominatorTree *DT = nullptr,
  63                          AssumptionCache *AC = nullptr,
  64                          const Instruction *CxtI = nullptr);
  65
  66   /// Given operands for an FAdd, fold the result or return null.
  67   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  68                           const DataLayout &DL,
  69                           const TargetLibraryInfo *TLI = nullptr,
  70                           const DominatorTree *DT = nullptr,
  71                           AssumptionCache *AC = nullptr,
  72                           const Instruction *CxtI = nullptr);
  73
  74   /// Given operands for an FSub, fold the result or return null.
  75   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  76                           const DataLayout &DL,
  77                           const TargetLibraryInfo *TLI = nullptr,
  78                           const DominatorTree *DT = nullptr,
  79                           AssumptionCache *AC = nullptr,
  80                           const Instruction *CxtI = nullptr);
  81
  82   /// Given operands for an FMul, fold the result or return null.
  83   Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  84                           const DataLayout &DL,
  85                           const TargetLibraryInfo *TLI = nullptr,
  86                           const DominatorTree *DT = nullptr,
  87                           AssumptionCache *AC = nullptr,
  88                           const Instruction *CxtI = nullptr);
  89
  90   /// Given operands for a Mul, fold the result or return null.
  91   Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout &DL,
  92                          const TargetLibraryInfo *TLI = nullptr,
  93                          const DominatorTree *DT = nullptr,
  94                          AssumptionCache *AC = nullptr,
  95                          const Instruction *CxtI = nullptr);
  96
  97   /// Given operands for an SDiv, fold the result or return null.
  98   Value *SimplifySDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
  99                           const TargetLibraryInfo *TLI = nullptr,
 100                           const DominatorTree *DT = nullptr,
 101                           AssumptionCache *AC = nullptr,
 102                           const Instruction *CxtI = nullptr);
 103
 104   /// Given operands for a UDiv, fold the result or return null.
 105   Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
 106                           const TargetLibraryInfo *TLI = nullptr,
 107                           const DominatorTree *DT = nullptr,
 108                           AssumptionCache *AC = nullptr,
 109                           const Instruction *CxtI = nullptr);
 110
 111   /// Given operands for an FDiv, fold the result or return null.
 112   Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 113                           const DataLayout &DL,
 114                           const TargetLibraryInfo *TLI = nullptr,
 115                           const DominatorTree *DT = nullptr,
 116                           AssumptionCache *AC = nullptr,
 117                           const Instruction *CxtI = nullptr);
 118
 119   /// Given operands for an SRem, fold the result or return null.
 120   Value *SimplifySRemInst(Value *LHS, Value *RHS, const DataLayout &DL,
 121                           const TargetLibraryInfo *TLI = nullptr,
 122                           const DominatorTree *DT = nullptr,
 123                           AssumptionCache *AC = nullptr,
 124                           const Instruction *CxtI = nullptr);
 125
 126   /// Given operands for a URem, fold the result or return null.
 127   Value *SimplifyURemInst(Value *LHS, Value *RHS, const DataLayout &DL,
 128                           const TargetLibraryInfo *TLI = nullptr,
 129                           const DominatorTree *DT = nullptr,
 130                           AssumptionCache *AC = nullptr,
 131                           const Instruction *CxtI = nullptr);
 132
 133   /// Given operands for an FRem, fold the result or return null.
 134   Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 135                           const DataLayout &DL,
 136                           const TargetLibraryInfo *TLI = nullptr,
 137                           const DominatorTree *DT = nullptr,
 138                           AssumptionCache *AC = nullptr,
 139                           const Instruction *CxtI = nullptr);
 140
 141   /// Given operands for a Shl, fold the result or return null.
 142   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 143                          const DataLayout &DL,
 144                          const TargetLibraryInfo *TLI = nullptr,
 145                          const DominatorTree *DT = nullptr,
 146                          AssumptionCache *AC = nullptr,
 147                          const Instruction *CxtI = nullptr);
 148
 149   /// Given operands for a LShr, fold the result or return null.
 150   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
 151                           const DataLayout &DL,
 152                           const TargetLibraryInfo *TLI = nullptr,
 153                           const DominatorTree *DT = nullptr,
 154                           AssumptionCache *AC = nullptr,
 155                           const Instruction *CxtI = nullptr);
 156
 157   /// Given operands for a AShr, fold the result or return nulll.
 158   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
 159                           const DataLayout &DL,
 160                           const TargetLibraryInfo *TLI = nullptr,
 161                           const DominatorTree *DT = nullptr,
 162                           AssumptionCache *AC = nullptr,
 163                           const Instruction *CxtI = nullptr);
 164
 165   /// Given operands for an And, fold the result or return null.
 166   Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout &DL,
 167                          const TargetLibraryInfo *TLI = nullptr,
 168                          const DominatorTree *DT = nullptr,
 169                          AssumptionCache *AC = nullptr,
 170                          const Instruction *CxtI = nullptr);
 171
 172   /// Given operands for an Or, fold the result or return null.
 173   Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout &DL,
 174                         const TargetLibraryInfo *TLI = nullptr,
 175                         const DominatorTree *DT = nullptr,
 176                         AssumptionCache *AC = nullptr,
 177                         const Instruction *CxtI = nullptr);
 178
 179   /// Given operands for an Xor, fold the result or return null.
 180   Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout &DL,
 181                          const TargetLibraryInfo *TLI = nullptr,
 182                          const DominatorTree *DT = nullptr,
 183                          AssumptionCache *AC = nullptr,
 184                          const Instruction *CxtI = nullptr);
 185
 186   /// Given operands for an ICmpInst, fold the result or return null.
 187   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 188                           const DataLayout &DL,
 189                           const TargetLibraryInfo *TLI = nullptr,
 190                           const DominatorTree *DT = nullptr,
 191                           AssumptionCache *AC = nullptr,
 192                           const Instruction *CxtI = nullptr);
 193
 194   /// Given operands for an FCmpInst, fold the result or return null.
 195   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 196                           FastMathFlags FMF, const DataLayout &DL,
 197                           const TargetLibraryInfo *TLI = nullptr,
 198                           const DominatorTree *DT = nullptr,
 199                           AssumptionCache *AC = nullptr,
 200                           const Instruction *CxtI = nullptr);
 201
 202   /// Given operands for a SelectInst, fold the result or return null.
 203   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
 204                             const DataLayout &DL,
 205                             const TargetLibraryInfo *TLI = nullptr,
 206                             const DominatorTree *DT = nullptr,
 207                             AssumptionCache *AC = nullptr,
 208                             const Instruction *CxtI = nullptr);
 209
 210   /// Given operands for a GetElementPtrInst, fold the result or return null.
 211   Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
 212                          const DataLayout &DL,
 213                          const TargetLibraryInfo *TLI = nullptr,
 214                          const DominatorTree *DT = nullptr,
 215                          AssumptionCache *AC = nullptr,
 216                          const Instruction *CxtI = nullptr);
 217
 218   /// Given operands for an InsertValueInst, fold the result or return null.
 219   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
 220                                  ArrayRef<unsigned> Idxs, const DataLayout &DL,
 221                                  const TargetLibraryInfo *TLI = nullptr,
 222                                  const DominatorTree *DT = nullptr,
 223                                  AssumptionCache *AC = nullptr,
 224                                  const Instruction *CxtI = nullptr);
 225
 226   /// Given operands for an ExtractValueInst, fold the result or return null.
 227   Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
 228                                   const DataLayout &DL,
 229                                   const TargetLibraryInfo *TLI = nullptr,
 230                                   const DominatorTree *DT = nullptr,
 231                                   AssumptionCache *AC = nullptr,
 232                                   const Instruction *CxtI = nullptr);
 233
 234   /// Given operands for an ExtractElementInst, fold the result or return null.
 235   Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
 236                                     const DataLayout &DL,
 237                                     const TargetLibraryInfo *TLI = nullptr,
 238                                     const DominatorTree *DT = nullptr,
 239                                     AssumptionCache *AC = nullptr,
 240                                     const Instruction *CxtI = nullptr);
 241
 242   /// Given operands for a CastInst, fold the result or return null.
 243   Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
 244                           const DataLayout &DL,
 245                           const TargetLibraryInfo *TLI = nullptr,
 246                           const DominatorTree *DT = nullptr,
 247                           AssumptionCache *AC = nullptr,
 248                           const Instruction *CxtI = nullptr);
 249
 250   /// Given operands for a ShuffleVectorInst, fold the result or return null.
 251   Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
 252                                    Type *RetTy, const DataLayout &DL,
 253                                    const TargetLibraryInfo *TLI = nullptr,
 254                                    const DominatorTree *DT = nullptr,
 255                                    AssumptionCache *AC = nullptr,
 256                                    const Instruction *CxtI = nullptr);
 257
 258   //=== Helper functions for higher up the class hierarchy.
 259
 260
 261   /// Given operands for a CmpInst, fold the result or return null.
 262   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 263                          const DataLayout &DL,
 264                          const TargetLibraryInfo *TLI = nullptr,
 265                          const DominatorTree *DT = nullptr,
 266                          AssumptionCache *AC = nullptr,
 267                          const Instruction *CxtI = nullptr);
 268
 269   /// Given operands for a BinaryOperator, fold the result or return null.
 270   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 271                        const DataLayout &DL,
 272                        const TargetLibraryInfo *TLI = nullptr,
 273                        const DominatorTree *DT = nullptr,
 274                        AssumptionCache *AC = nullptr,
 275                        const Instruction *CxtI = nullptr);
 276
 277   /// Given operands for an FP BinaryOperator, fold the result or return null.
 278   /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
 279   /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
 280   Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 281                          const FastMathFlags &FMF, const DataLayout &DL,
 282                          const TargetLibraryInfo *TLI = nullptr,
 283                          const DominatorTree *DT = nullptr,
 284                          AssumptionCache *AC = nullptr,
 285                          const Instruction *CxtI = nullptr);
 286
 287   /// Given a function and iterators over arguments, fold the result or return
 288   /// null.
 289   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
 290                       User::op_iterator ArgEnd, const DataLayout &DL,
 291                       const TargetLibraryInfo *TLI = nullptr,
 292                       const DominatorTree *DT = nullptr,
 293                       AssumptionCache *AC = nullptr,
 294                       const Instruction *CxtI = nullptr);
 295
 296   /// Given a function and set of arguments, fold the result or return null.
 297   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, const DataLayout &DL,
 298                       const TargetLibraryInfo *TLI = nullptr,
 299                       const DominatorTree *DT = nullptr,
 300                       AssumptionCache *AC = nullptr,
 301                       const Instruction *CxtI = nullptr);
 302
 303   /// See if we can compute a simplified version of this instruction. If not,
 304   /// return null.
 305   Value *SimplifyInstruction(Instruction *I, const DataLayout &DL,
 306                              const TargetLibraryInfo *TLI = nullptr,
 307                              const DominatorTree *DT = nullptr,
 308                              AssumptionCache *AC = nullptr,
 309                              OptimizationRemarkEmitter *ORE = nullptr);
 310
 311   /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
 312   ///
 313   /// This first performs a normal RAUW of I with SimpleV. It then recursively
 314   /// attempts to simplify those users updated by the operation. The 'I'
 315   /// instruction must not be equal to the simplified value 'SimpleV'.
 316   ///
 317   /// The function returns true if any simplifications were performed.
 318   bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
 319                                      const TargetLibraryInfo *TLI = nullptr,
 320                                      const DominatorTree *DT = nullptr,
 321                                      AssumptionCache *AC = nullptr);
 322
 323   /// Recursively attempt to simplify an instruction.
 324   ///
 325   /// This routine uses SimplifyInstruction to simplify 'I', and if successful
 326   /// replaces uses of 'I' with the simplified value. It then recurses on each
 327   /// of the users impacted. It returns true if any simplifications were
 328   /// performed.
 329   bool recursivelySimplifyInstruction(Instruction *I,
 330                                       const TargetLibraryInfo *TLI = nullptr,
 331                                       const DominatorTree *DT = nullptr,
 332                                       AssumptionCache *AC = nullptr);
 333 } // end namespace llvm
 334
 335 #endif
 336