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   struct SimplifyQuery {
  51     const DataLayout &DL;
  52     const TargetLibraryInfo *TLI = nullptr;
  53     const DominatorTree *DT = nullptr;
  54     AssumptionCache *AC = nullptr;
  55     const Instruction *CxtI = nullptr;
  56     SimplifyQuery(const DataLayout &DL) : DL(DL) {}
  57
  58     SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI,
  59                   const DominatorTree *DT, AssumptionCache *AC = nullptr,
  60                   const Instruction *CXTI = nullptr)
  61         : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI) {}
  62     SimplifyQuery getWithInstruction(Instruction *I) const {
  63       SimplifyQuery Copy(*this);
  64       Copy.CxtI = I;
  65       return Copy;
  66     }
  67   };
  68
  69   // NOTE: the explicit multiple argument versions of these functions are
  70   // deprecated.
  71   // Please use the SimplifyQuery versions in new code.
  72
  73   /// Given operands for an Add, fold the result or return null.
  74   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  75                        const SimplifyQuery &Q);
  76   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  77                          const DataLayout &DL,
  78                          const TargetLibraryInfo *TLI = nullptr,
  79                          const DominatorTree *DT = nullptr,
  80                          AssumptionCache *AC = nullptr,
  81                          const Instruction *CxtI = nullptr);
  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   Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
  87                          const DataLayout &DL,
  88                          const TargetLibraryInfo *TLI = nullptr,
  89                          const DominatorTree *DT = nullptr,
  90                          AssumptionCache *AC = nullptr,
  91                          const Instruction *CxtI = nullptr);
  92
  93   /// Given operands for an FAdd, fold the result or return null.
  94   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  95                           const SimplifyQuery &Q);
  96   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
  97                           const DataLayout &DL,
  98                           const TargetLibraryInfo *TLI = nullptr,
  99                           const DominatorTree *DT = nullptr,
 100                           AssumptionCache *AC = nullptr,
 101                           const Instruction *CxtI = nullptr);
 102
 103   /// Given operands for an FSub, fold the result or return null.
 104   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 105                           const SimplifyQuery &Q);
 106   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 107                           const DataLayout &DL,
 108                           const TargetLibraryInfo *TLI = nullptr,
 109                           const DominatorTree *DT = nullptr,
 110                           AssumptionCache *AC = nullptr,
 111                           const Instruction *CxtI = nullptr);
 112
 113   /// Given operands for an FMul, fold the result or return null.
 114   Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 115                           const SimplifyQuery &Q);
 116   Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 117                           const DataLayout &DL,
 118                           const TargetLibraryInfo *TLI = nullptr,
 119                           const DominatorTree *DT = nullptr,
 120                           AssumptionCache *AC = nullptr,
 121                           const Instruction *CxtI = nullptr);
 122
 123   /// Given operands for a Mul, fold the result or return null.
 124   Value *SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 125   Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout &DL,
 126                          const TargetLibraryInfo *TLI = nullptr,
 127                          const DominatorTree *DT = nullptr,
 128                          AssumptionCache *AC = nullptr,
 129                          const Instruction *CxtI = nullptr);
 130
 131   /// Given operands for an SDiv, fold the result or return null.
 132   Value *SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 133   Value *SimplifySDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
 134                           const TargetLibraryInfo *TLI = nullptr,
 135                           const DominatorTree *DT = nullptr,
 136                           AssumptionCache *AC = nullptr,
 137                           const Instruction *CxtI = nullptr);
 138
 139   /// Given operands for a UDiv, fold the result or return null.
 140   Value *SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 141   Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
 142                           const TargetLibraryInfo *TLI = nullptr,
 143                           const DominatorTree *DT = nullptr,
 144                           AssumptionCache *AC = nullptr,
 145                           const Instruction *CxtI = nullptr);
 146
 147   /// Given operands for an FDiv, fold the result or return null.
 148   Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 149                           const SimplifyQuery &Q);
 150   Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 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 an SRem, fold the result or return null.
 158   Value *SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 159   Value *SimplifySRemInst(Value *LHS, Value *RHS, 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 a URem, fold the result or return null.
 166   Value *SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 167   Value *SimplifyURemInst(Value *LHS, Value *RHS, const DataLayout &DL,
 168                           const TargetLibraryInfo *TLI = nullptr,
 169                           const DominatorTree *DT = nullptr,
 170                           AssumptionCache *AC = nullptr,
 171                           const Instruction *CxtI = nullptr);
 172
 173   /// Given operands for an FRem, fold the result or return null.
 174   Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 175                           const SimplifyQuery &Q);
 176   Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
 177                           const DataLayout &DL,
 178                           const TargetLibraryInfo *TLI = nullptr,
 179                           const DominatorTree *DT = nullptr,
 180                           AssumptionCache *AC = nullptr,
 181                           const Instruction *CxtI = nullptr);
 182
 183   /// Given operands for a Shl, fold the result or return null.
 184   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 185                          const SimplifyQuery &Q);
 186   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 187                          const DataLayout &DL,
 188                          const TargetLibraryInfo *TLI = nullptr,
 189                          const DominatorTree *DT = nullptr,
 190                          AssumptionCache *AC = nullptr,
 191                          const Instruction *CxtI = nullptr);
 192
 193   /// Given operands for a LShr, fold the result or return null.
 194   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
 195                           const SimplifyQuery &Q);
 196   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
 197                           const DataLayout &DL,
 198                           const TargetLibraryInfo *TLI = nullptr,
 199                           const DominatorTree *DT = nullptr,
 200                           AssumptionCache *AC = nullptr,
 201                           const Instruction *CxtI = nullptr);
 202
 203   /// Given operands for a AShr, fold the result or return nulll.
 204   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
 205                           const SimplifyQuery &Q);
 206   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
 207                           const DataLayout &DL,
 208                           const TargetLibraryInfo *TLI = nullptr,
 209                           const DominatorTree *DT = nullptr,
 210                           AssumptionCache *AC = nullptr,
 211                           const Instruction *CxtI = nullptr);
 212
 213   /// Given operands for an And, fold the result or return null.
 214   Value *SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 215   Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout &DL,
 216                          const TargetLibraryInfo *TLI = nullptr,
 217                          const DominatorTree *DT = nullptr,
 218                          AssumptionCache *AC = nullptr,
 219                          const Instruction *CxtI = nullptr);
 220
 221   /// Given operands for an Or, fold the result or return null.
 222   Value *SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 223   Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout &DL,
 224                         const TargetLibraryInfo *TLI = nullptr,
 225                         const DominatorTree *DT = nullptr,
 226                         AssumptionCache *AC = nullptr,
 227                         const Instruction *CxtI = nullptr);
 228
 229   /// Given operands for an Xor, fold the result or return null.
 230   Value *SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
 231   Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout &DL,
 232                          const TargetLibraryInfo *TLI = nullptr,
 233                          const DominatorTree *DT = nullptr,
 234                          AssumptionCache *AC = nullptr,
 235                          const Instruction *CxtI = nullptr);
 236
 237   /// Given operands for an ICmpInst, fold the result or return null.
 238   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 239                           const SimplifyQuery &Q);
 240   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 241                           const DataLayout &DL,
 242                           const TargetLibraryInfo *TLI = nullptr,
 243                           const DominatorTree *DT = nullptr,
 244                           AssumptionCache *AC = nullptr,
 245                           const Instruction *CxtI = nullptr);
 246
 247   /// Given operands for an FCmpInst, fold the result or return null.
 248   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 249                           FastMathFlags FMF, const SimplifyQuery &Q);
 250   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 251                           FastMathFlags FMF, const DataLayout &DL,
 252                           const TargetLibraryInfo *TLI = nullptr,
 253                           const DominatorTree *DT = nullptr,
 254                           AssumptionCache *AC = nullptr,
 255                           const Instruction *CxtI = nullptr);
 256
 257   /// Given operands for a SelectInst, fold the result or return null.
 258   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
 259                             const SimplifyQuery &Q);
 260   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
 261                             const DataLayout &DL,
 262                             const TargetLibraryInfo *TLI = nullptr,
 263                             const DominatorTree *DT = nullptr,
 264                             AssumptionCache *AC = nullptr,
 265                             const Instruction *CxtI = nullptr);
 266
 267   /// Given operands for a GetElementPtrInst, fold the result or return null.
 268   Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
 269                          const SimplifyQuery &Q);
 270   Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
 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 InsertValueInst, fold the result or return null.
 278   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
 279                                  ArrayRef<unsigned> Idxs,
 280                                  const SimplifyQuery &Q);
 281   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
 282                                  ArrayRef<unsigned> Idxs, const DataLayout &DL,
 283                                  const TargetLibraryInfo *TLI = nullptr,
 284                                  const DominatorTree *DT = nullptr,
 285                                  AssumptionCache *AC = nullptr,
 286                                  const Instruction *CxtI = nullptr);
 287
 288   /// Given operands for an ExtractValueInst, fold the result or return null.
 289   Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
 290                                   const SimplifyQuery &Q);
 291   Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
 292                                   const DataLayout &DL,
 293                                   const TargetLibraryInfo *TLI = nullptr,
 294                                   const DominatorTree *DT = nullptr,
 295                                   AssumptionCache *AC = nullptr,
 296                                   const Instruction *CxtI = nullptr);
 297
 298   /// Given operands for an ExtractElementInst, fold the result or return null.
 299   Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
 300                                     const SimplifyQuery &Q);
 301   Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
 302                                     const DataLayout &DL,
 303                                     const TargetLibraryInfo *TLI = nullptr,
 304                                     const DominatorTree *DT = nullptr,
 305                                     AssumptionCache *AC = nullptr,
 306                                     const Instruction *CxtI = nullptr);
 307
 308   /// Given operands for a CastInst, fold the result or return null.
 309   Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
 310                           const SimplifyQuery &Q);
 311   Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
 312                           const DataLayout &DL,
 313                           const TargetLibraryInfo *TLI = nullptr,
 314                           const DominatorTree *DT = nullptr,
 315                           AssumptionCache *AC = nullptr,
 316                           const Instruction *CxtI = nullptr);
 317
 318   /// Given operands for a ShuffleVectorInst, fold the result or return null.
 319   Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
 320                                    Type *RetTy, const SimplifyQuery &Q);
 321   Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
 322                                    Type *RetTy, const DataLayout &DL,
 323                                    const TargetLibraryInfo *TLI = nullptr,
 324                                    const DominatorTree *DT = nullptr,
 325                                    AssumptionCache *AC = nullptr,
 326                                    const Instruction *CxtI = nullptr);
 327
 328   //=== Helper functions for higher up the class hierarchy.
 329
 330
 331   /// Given operands for a CmpInst, fold the result or return null.
 332   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 333                          const SimplifyQuery &Q);
 334   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 335                          const DataLayout &DL,
 336                          const TargetLibraryInfo *TLI = nullptr,
 337                          const DominatorTree *DT = nullptr,
 338                          AssumptionCache *AC = nullptr,
 339                          const Instruction *CxtI = nullptr);
 340
 341   /// Given operands for a BinaryOperator, fold the result or return null.
 342   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 343                        const SimplifyQuery &Q);
 344   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 345                        const DataLayout &DL,
 346                        const TargetLibraryInfo *TLI = nullptr,
 347                        const DominatorTree *DT = nullptr,
 348                        AssumptionCache *AC = nullptr,
 349                        const Instruction *CxtI = nullptr);
 350
 351   /// Given operands for an FP BinaryOperator, fold the result or return null.
 352   /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
 353   /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
 354   Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 355                          FastMathFlags FMF, const SimplifyQuery &Q);
 356   Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 357                          FastMathFlags FMF, const DataLayout &DL,
 358                          const TargetLibraryInfo *TLI = nullptr,
 359                          const DominatorTree *DT = nullptr,
 360                          AssumptionCache *AC = nullptr,
 361                          const Instruction *CxtI = nullptr);
 362
 363   /// Given a function and iterators over arguments, fold the result or return
 364   /// null.
 365   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
 366                       User::op_iterator ArgEnd, const SimplifyQuery &Q);
 367   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
 368                       User::op_iterator ArgEnd, const DataLayout &DL,
 369                       const TargetLibraryInfo *TLI = nullptr,
 370                       const DominatorTree *DT = nullptr,
 371                       AssumptionCache *AC = nullptr,
 372                       const Instruction *CxtI = nullptr);
 373
 374   /// Given a function and set of arguments, fold the result or return null.
 375   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, const SimplifyQuery &Q);
 376   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, const DataLayout &DL,
 377                       const TargetLibraryInfo *TLI = nullptr,
 378                       const DominatorTree *DT = nullptr,
 379                       AssumptionCache *AC = nullptr,
 380                       const Instruction *CxtI = nullptr);
 381
 382   /// See if we can compute a simplified version of this instruction. If not,
 383   /// return null.
 384   Value *SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
 385                              OptimizationRemarkEmitter *ORE = nullptr);
 386   Value *SimplifyInstruction(Instruction *I, const DataLayout &DL,
 387                              const TargetLibraryInfo *TLI = nullptr,
 388                              const DominatorTree *DT = nullptr,
 389                              AssumptionCache *AC = nullptr,
 390                              OptimizationRemarkEmitter *ORE = nullptr);
 391
 392   /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
 393   ///
 394   /// This first performs a normal RAUW of I with SimpleV. It then recursively
 395   /// attempts to simplify those users updated by the operation. The 'I'
 396   /// instruction must not be equal to the simplified value 'SimpleV'.
 397   ///
 398   /// The function returns true if any simplifications were performed.
 399   bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
 400                                      const TargetLibraryInfo *TLI = nullptr,
 401                                      const DominatorTree *DT = nullptr,
 402                                      AssumptionCache *AC = nullptr);
 403
 404   /// Recursively attempt to simplify an instruction.
 405   ///
 406   /// This routine uses SimplifyInstruction to simplify 'I', and if successful
 407   /// replaces uses of 'I' with the simplified value. It then recurses on each
 408   /// of the users impacted. It returns true if any simplifications were
 409   /// performed.
 410   bool recursivelySimplifyInstruction(Instruction *I,
 411                                       const TargetLibraryInfo *TLI = nullptr,
 412                                       const DominatorTree *DT = nullptr,
 413                                       AssumptionCache *AC = nullptr);
 414 } // end namespace llvm
 415
 416 #endif
 417