include/llvm/Analysis/ScalarEvolutionExpander.h

   1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- 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 defines the classes used to generate code from scalar expressions.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
  14 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
  15
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/DenseSet.h"
  18 #include "llvm/ADT/Optional.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
  21 #include "llvm/Analysis/TargetFolder.h"
  22 #include "llvm/IR/IRBuilder.h"
  23 #include "llvm/IR/ValueHandle.h"
  24
  25 namespace llvm {
  26   class TargetTransformInfo;
  27
  28   /// Return true if the given expression is safe to expand in the sense that
  29   /// all materialized values are safe to speculate anywhere their operands are
  30   /// defined.
  31   bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
  32
  33   /// Return true if the given expression is safe to expand in the sense that
  34   /// all materialized values are defined and safe to speculate at the specified
  35   /// location and their operands are defined at this location.
  36   bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
  37                         ScalarEvolution &SE);
  38
  39   /// This class uses information about analyze scalars to rewrite expressions
  40   /// in canonical form.
  41   ///
  42   /// Clients should create an instance of this class when rewriting is needed,
  43   /// and destroy it when finished to allow the release of the associated
  44   /// memory.
  45   class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
  46     ScalarEvolution &SE;
  47     const DataLayout &DL;
  48
  49     // New instructions receive a name to identify them with the current pass.
  50     const char* IVName;
  51
  52     // InsertedExpressions caches Values for reuse, so must track RAUW.
  53     DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>>
  54         InsertedExpressions;
  55
  56     // InsertedValues only flags inserted instructions so needs no RAUW.
  57     DenseSet<AssertingVH<Value>> InsertedValues;
  58     DenseSet<AssertingVH<Value>> InsertedPostIncValues;
  59
  60     /// A memoization of the "relevant" loop for a given SCEV.
  61     DenseMap<const SCEV *, const Loop *> RelevantLoops;
  62
  63     /// Addrecs referring to any of the given loops are expanded in post-inc
  64     /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
  65     /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
  66     /// phi starting at 1. This is only supported in non-canonical mode.
  67     PostIncLoopSet PostIncLoops;
  68
  69     /// When this is non-null, addrecs expanded in the loop it indicates should
  70     /// be inserted with increments at IVIncInsertPos.
  71     const Loop *IVIncInsertLoop;
  72
  73     /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
  74     /// increment at this position.
  75     Instruction *IVIncInsertPos;
  76
  77     /// Phis that complete an IV chain. Reuse
  78     DenseSet<AssertingVH<PHINode>> ChainedPhis;
  79
  80     /// When true, expressions are expanded in "canonical" form. In particular,
  81     /// addrecs are expanded as arithmetic based on a canonical induction
  82     /// variable. When false, expression are expanded in a more literal form.
  83     bool CanonicalMode;
  84
  85     /// When invoked from LSR, the expander is in "strength reduction" mode. The
  86     /// only difference is that phi's are only reused if they are already in
  87     /// "expanded" form.
  88     bool LSRMode;
  89
  90     typedef IRBuilder<TargetFolder> BuilderType;
  91     BuilderType Builder;
  92
  93     // RAII object that stores the current insertion point and restores it when
  94     // the object is destroyed. This includes the debug location.  Duplicated
  95     // from InsertPointGuard to add SetInsertPoint() which is used to updated
  96     // InsertPointGuards stack when insert points are moved during SCEV
  97     // expansion.
  98     class SCEVInsertPointGuard {
  99       IRBuilderBase &Builder;
 100       AssertingVH<BasicBlock> Block;
 101       BasicBlock::iterator Point;
 102       DebugLoc DbgLoc;
 103       SCEVExpander *SE;
 104
 105       SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
 106       SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
 107
 108     public:
 109       SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
 110           : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
 111             DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
 112         SE->InsertPointGuards.push_back(this);
 113       }
 114
 115       ~SCEVInsertPointGuard() {
 116         // These guards should always created/destroyed in FIFO order since they
 117         // are used to guard lexically scoped blocks of code in
 118         // ScalarEvolutionExpander.
 119         assert(SE->InsertPointGuards.back() == this);
 120         SE->InsertPointGuards.pop_back();
 121         Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
 122         Builder.SetCurrentDebugLocation(DbgLoc);
 123       }
 124
 125       BasicBlock::iterator GetInsertPoint() const { return Point; }
 126       void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
 127     };
 128
 129     /// Stack of pointers to saved insert points, used to keep insert points
 130     /// consistent when instructions are moved.
 131     SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
 132
 133 #ifndef NDEBUG
 134     const char *DebugType;
 135 #endif
 136
 137     friend struct SCEVVisitor<SCEVExpander, Value*>;
 138
 139   public:
 140     /// Construct a SCEVExpander in "canonical" mode.
 141     explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
 142                           const char *name)
 143         : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
 144           IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
 145           Builder(se.getContext(), TargetFolder(DL)) {
 146 #ifndef NDEBUG
 147       DebugType = "";
 148 #endif
 149     }
 150
 151     ~SCEVExpander() {
 152       // Make sure the insert point guard stack is consistent.
 153       assert(InsertPointGuards.empty());
 154     }
 155
 156 #ifndef NDEBUG
 157     void setDebugType(const char* s) { DebugType = s; }
 158 #endif
 159
 160     /// Erase the contents of the InsertedExpressions map so that users trying
 161     /// to expand the same expression into multiple BasicBlocks or different
 162     /// places within the same BasicBlock can do so.
 163     void clear() {
 164       InsertedExpressions.clear();
 165       InsertedValues.clear();
 166       InsertedPostIncValues.clear();
 167       ChainedPhis.clear();
 168     }
 169
 170     /// Return true for expressions that may incur non-trivial cost to evaluate
 171     /// at runtime.
 172     ///
 173     /// At is an optional parameter which specifies point in code where user is
 174     /// going to expand this expression. Sometimes this knowledge can lead to a
 175     /// more accurate cost estimation.
 176     bool isHighCostExpansion(const SCEV *Expr, Loop *L,
 177                              const Instruction *At = nullptr) {
 178       SmallPtrSet<const SCEV *, 8> Processed;
 179       return isHighCostExpansionHelper(Expr, L, At, Processed);
 180     }
 181
 182     /// This method returns the canonical induction variable of the specified
 183     /// type for the specified loop (inserting one if there is none).  A
 184     /// canonical induction variable starts at zero and steps by one on each
 185     /// iteration.
 186     PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
 187
 188     /// Return the induction variable increment's IV operand.
 189     Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos,
 190                                  bool allowScale);
 191
 192     /// Utility for hoisting an IV increment.
 193     bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
 194
 195     /// replace congruent phis with their most canonical representative. Return
 196     /// the number of phis eliminated.
 197     unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
 198                                  SmallVectorImpl<WeakTrackingVH> &DeadInsts,
 199                                  const TargetTransformInfo *TTI = nullptr);
 200
 201     /// Insert code to directly compute the specified SCEV expression into the
 202     /// program.  The inserted code is inserted into the specified block.
 203     Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
 204
 205     /// Insert code to directly compute the specified SCEV expression into the
 206     /// program.  The inserted code is inserted into the SCEVExpander's current
 207     /// insertion point. If a type is specified, the result will be expanded to
 208     /// have that type, with a cast if necessary.
 209     Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
 210
 211
 212     /// Generates a code sequence that evaluates this predicate.  The inserted
 213     /// instructions will be at position \p Loc.  The result will be of type i1
 214     /// and will have a value of 0 when the predicate is false and 1 otherwise.
 215     Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
 216
 217     /// A specialized variant of expandCodeForPredicate, handling the case when
 218     /// we are expanding code for a SCEVEqualPredicate.
 219     Value *expandEqualPredicate(const SCEVEqualPredicate *Pred,
 220                                 Instruction *Loc);
 221
 222     /// Generates code that evaluates if the \p AR expression will overflow.
 223     Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
 224                                  bool Signed);
 225
 226     /// A specialized variant of expandCodeForPredicate, handling the case when
 227     /// we are expanding code for a SCEVWrapPredicate.
 228     Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc);
 229
 230     /// A specialized variant of expandCodeForPredicate, handling the case when
 231     /// we are expanding code for a SCEVUnionPredicate.
 232     Value *expandUnionPredicate(const SCEVUnionPredicate *Pred,
 233                                 Instruction *Loc);
 234
 235     /// Set the current IV increment loop and position.
 236     void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
 237       assert(!CanonicalMode &&
 238              "IV increment positions are not supported in CanonicalMode");
 239       IVIncInsertLoop = L;
 240       IVIncInsertPos = Pos;
 241     }
 242
 243     /// Enable post-inc expansion for addrecs referring to the given
 244     /// loops. Post-inc expansion is only supported in non-canonical mode.
 245     void setPostInc(const PostIncLoopSet &L) {
 246       assert(!CanonicalMode &&
 247              "Post-inc expansion is not supported in CanonicalMode");
 248       PostIncLoops = L;
 249     }
 250
 251     /// Disable all post-inc expansion.
 252     void clearPostInc() {
 253       PostIncLoops.clear();
 254
 255       // When we change the post-inc loop set, cached expansions may no
 256       // longer be valid.
 257       InsertedPostIncValues.clear();
 258     }
 259
 260     /// Disable the behavior of expanding expressions in canonical form rather
 261     /// than in a more literal form. Non-canonical mode is useful for late
 262     /// optimization passes.
 263     void disableCanonicalMode() { CanonicalMode = false; }
 264
 265     void enableLSRMode() { LSRMode = true; }
 266
 267     /// Set the current insertion point. This is useful if multiple calls to
 268     /// expandCodeFor() are going to be made with the same insert point and the
 269     /// insert point may be moved during one of the expansions (e.g. if the
 270     /// insert point is not a block terminator).
 271     void setInsertPoint(Instruction *IP) {
 272       assert(IP);
 273       Builder.SetInsertPoint(IP);
 274     }
 275
 276     /// Clear the current insertion point. This is useful if the instruction
 277     /// that had been serving as the insertion point may have been deleted.
 278     void clearInsertPoint() { Builder.ClearInsertionPoint(); }
 279
 280     /// Set location information used by debugging information.
 281     void SetCurrentDebugLocation(DebugLoc L) {
 282       Builder.SetCurrentDebugLocation(std::move(L));
 283     }
 284
 285     /// Get location information used by debugging information.
 286     const DebugLoc &getCurrentDebugLocation() const {
 287       return Builder.getCurrentDebugLocation();
 288     }
 289
 290     /// Return true if the specified instruction was inserted by the code
 291     /// rewriter.  If so, the client should not modify the instruction.
 292     bool isInsertedInstruction(Instruction *I) const {
 293       return InsertedValues.count(I) || InsertedPostIncValues.count(I);
 294     }
 295
 296     void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
 297
 298     /// Try to find existing LLVM IR value for S available at the point At.
 299     Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
 300                                      Loop *L);
 301
 302     /// Try to find the ValueOffsetPair for S. The function is mainly used to
 303     /// check whether S can be expanded cheaply.  If this returns a non-None
 304     /// value, we know we can codegen the `ValueOffsetPair` into a suitable
 305     /// expansion identical with S so that S can be expanded cheaply.
 306     ///
 307     /// L is a hint which tells in which loop to look for the suitable value.
 308     /// On success return value which is equivalent to the expanded S at point
 309     /// At. Return nullptr if value was not found.
 310     ///
 311     /// Note that this function does not perform an exhaustive search. I.e if it
 312     /// didn't find any value it does not mean that there is no such value.
 313     ///
 314     Optional<ScalarEvolution::ValueOffsetPair>
 315     getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
 316
 317   private:
 318     LLVMContext &getContext() const { return SE.getContext(); }
 319
 320     /// Recursive helper function for isHighCostExpansion.
 321     bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
 322                                    const Instruction *At,
 323                                    SmallPtrSetImpl<const SCEV *> &Processed);
 324
 325     /// Insert the specified binary operator, doing a small amount of work to
 326     /// avoid inserting an obviously redundant operation, and hoisting to an
 327     /// outer loop when the opportunity is there and it is safe.
 328     Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
 329                        SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
 330
 331     /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
 332     /// cast if a suitable one exists, moving an existing cast if a suitable one
 333     /// exists but isn't in the right place, or creating a new one.
 334     Value *ReuseOrCreateCast(Value *V, Type *Ty,
 335                              Instruction::CastOps Op,
 336                              BasicBlock::iterator IP);
 337
 338     /// Insert a cast of V to the specified type, which must be possible with a
 339     /// noop cast, doing what we can to share the casts.
 340     Value *InsertNoopCastOfTo(Value *V, Type *Ty);
 341
 342     /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
 343     /// ptrtoint+arithmetic+inttoptr.
 344     Value *expandAddToGEP(const SCEV *const *op_begin,
 345                           const SCEV *const *op_end,
 346                           PointerType *PTy, Type *Ty, Value *V);
 347     Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
 348
 349     /// Find a previous Value in ExprValueMap for expand.
 350     ScalarEvolution::ValueOffsetPair
 351     FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
 352
 353     Value *expand(const SCEV *S);
 354
 355     /// Determine the most "relevant" loop for the given SCEV.
 356     const Loop *getRelevantLoop(const SCEV *);
 357
 358     Value *visitConstant(const SCEVConstant *S) {
 359       return S->getValue();
 360     }
 361
 362     Value *visitTruncateExpr(const SCEVTruncateExpr *S);
 363
 364     Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
 365
 366     Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
 367
 368     Value *visitAddExpr(const SCEVAddExpr *S);
 369
 370     Value *visitMulExpr(const SCEVMulExpr *S);
 371
 372     Value *visitUDivExpr(const SCEVUDivExpr *S);
 373
 374     Value *visitAddRecExpr(const SCEVAddRecExpr *S);
 375
 376     Value *visitSMaxExpr(const SCEVSMaxExpr *S);
 377
 378     Value *visitUMaxExpr(const SCEVUMaxExpr *S);
 379
 380     Value *visitSMinExpr(const SCEVSMinExpr *S);
 381
 382     Value *visitUMinExpr(const SCEVUMinExpr *S);
 383
 384     Value *visitUnknown(const SCEVUnknown *S) {
 385       return S->getValue();
 386     }
 387
 388     void rememberInstruction(Value *I);
 389
 390     bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 391
 392     bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 393
 394     Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
 395     PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
 396                                        const Loop *L,
 397                                        Type *ExpandTy,
 398                                        Type *IntTy,
 399                                        Type *&TruncTy,
 400                                        bool &InvertStep);
 401     Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
 402                        Type *ExpandTy, Type *IntTy, bool useSubtract);
 403
 404     void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
 405                         Instruction *Pos, PHINode *LoopPhi);
 406
 407     void fixupInsertPoints(Instruction *I);
 408   };
 409 }
 410
 411 #endif