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_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H 14 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/Optional.h" 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 22 #include "llvm/Analysis/ScalarEvolutionNormalization.h" 23 #include "llvm/Analysis/TargetFolder.h" 24 #include "llvm/Analysis/TargetTransformInfo.h" 25 #include "llvm/IR/IRBuilder.h" 26 #include "llvm/IR/ValueHandle.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Support/InstructionCost.h" 29 30 namespace llvm { 31 extern cl::opt<unsigned> SCEVCheapExpansionBudget; 32 33 /// Return true if the given expression is safe to expand in the sense that 34 /// all materialized values are safe to speculate anywhere their operands are 35 /// defined. 36 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); 37 38 /// Return true if the given expression is safe to expand in the sense that 39 /// all materialized values are defined and safe to speculate at the specified 40 /// location and their operands are defined at this location. 41 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, 42 ScalarEvolution &SE); 43 44 /// struct for holding enough information to help calculate the cost of the 45 /// given SCEV when expanded into IR. 46 struct SCEVOperand { SCEVOperandSCEVOperand47 explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) : 48 ParentOpcode(Opc), OperandIdx(Idx), S(S) { } 49 /// LLVM instruction opcode that uses the operand. 50 unsigned ParentOpcode; 51 /// The use index of an expanded instruction. 52 int OperandIdx; 53 /// The SCEV operand to be costed. 54 const SCEV* S; 55 }; 56 57 /// This class uses information about analyze scalars to rewrite expressions 58 /// in canonical form. 59 /// 60 /// Clients should create an instance of this class when rewriting is needed, 61 /// and destroy it when finished to allow the release of the associated 62 /// memory. 63 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> { 64 ScalarEvolution &SE; 65 const DataLayout &DL; 66 67 // New instructions receive a name to identify them with the current pass. 68 const char *IVName; 69 70 /// Indicates whether LCSSA phis should be created for inserted values. 71 bool PreserveLCSSA; 72 73 // InsertedExpressions caches Values for reuse, so must track RAUW. 74 DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>> 75 InsertedExpressions; 76 77 // InsertedValues only flags inserted instructions so needs no RAUW. 78 DenseSet<AssertingVH<Value>> InsertedValues; 79 DenseSet<AssertingVH<Value>> InsertedPostIncValues; 80 81 /// Keep track of the existing IR values re-used during expansion. 82 /// FIXME: Ideally re-used instructions would not be added to 83 /// InsertedValues/InsertedPostIncValues. 84 SmallPtrSet<Value *, 16> ReusedValues; 85 86 /// A memoization of the "relevant" loop for a given SCEV. 87 DenseMap<const SCEV *, const Loop *> RelevantLoops; 88 89 /// Addrecs referring to any of the given loops are expanded in post-inc 90 /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add 91 /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new 92 /// phi starting at 1. This is only supported in non-canonical mode. 93 PostIncLoopSet PostIncLoops; 94 95 /// When this is non-null, addrecs expanded in the loop it indicates should 96 /// be inserted with increments at IVIncInsertPos. 97 const Loop *IVIncInsertLoop; 98 99 /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV 100 /// increment at this position. 101 Instruction *IVIncInsertPos; 102 103 /// Phis that complete an IV chain. Reuse 104 DenseSet<AssertingVH<PHINode>> ChainedPhis; 105 106 /// When true, SCEVExpander tries to expand expressions in "canonical" form. 107 /// When false, expressions are expanded in a more literal form. 108 /// 109 /// In "canonical" form addrecs are expanded as arithmetic based on a 110 /// canonical induction variable. Note that CanonicalMode doesn't guarantee 111 /// that all expressions are expanded in "canonical" form. For some 112 /// expressions literal mode can be preferred. 113 bool CanonicalMode; 114 115 /// When invoked from LSR, the expander is in "strength reduction" mode. The 116 /// only difference is that phi's are only reused if they are already in 117 /// "expanded" form. 118 bool LSRMode; 119 120 typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderType; 121 BuilderType Builder; 122 123 // RAII object that stores the current insertion point and restores it when 124 // the object is destroyed. This includes the debug location. Duplicated 125 // from InsertPointGuard to add SetInsertPoint() which is used to updated 126 // InsertPointGuards stack when insert points are moved during SCEV 127 // expansion. 128 class SCEVInsertPointGuard { 129 IRBuilderBase &Builder; 130 AssertingVH<BasicBlock> Block; 131 BasicBlock::iterator Point; 132 DebugLoc DbgLoc; 133 SCEVExpander *SE; 134 135 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete; 136 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete; 137 138 public: SCEVInsertPointGuard(IRBuilderBase & B,SCEVExpander * SE)139 SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE) 140 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()), 141 DbgLoc(B.getCurrentDebugLocation()), SE(SE) { 142 SE->InsertPointGuards.push_back(this); 143 } 144 ~SCEVInsertPointGuard()145 ~SCEVInsertPointGuard() { 146 // These guards should always created/destroyed in FIFO order since they 147 // are used to guard lexically scoped blocks of code in 148 // ScalarEvolutionExpander. 149 assert(SE->InsertPointGuards.back() == this); 150 SE->InsertPointGuards.pop_back(); 151 Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point)); 152 Builder.SetCurrentDebugLocation(DbgLoc); 153 } 154 GetInsertPoint()155 BasicBlock::iterator GetInsertPoint() const { return Point; } SetInsertPoint(BasicBlock::iterator I)156 void SetInsertPoint(BasicBlock::iterator I) { Point = I; } 157 }; 158 159 /// Stack of pointers to saved insert points, used to keep insert points 160 /// consistent when instructions are moved. 161 SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards; 162 163 #ifndef NDEBUG 164 const char *DebugType; 165 #endif 166 167 friend struct SCEVVisitor<SCEVExpander, Value *>; 168 169 public: 170 /// Construct a SCEVExpander in "canonical" mode. 171 explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL, 172 const char *name, bool PreserveLCSSA = true) 173 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA), 174 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true), 175 LSRMode(false), 176 Builder(se.getContext(), TargetFolder(DL), 177 IRBuilderCallbackInserter( 178 [this](Instruction *I) { rememberInstruction(I); })) { 179 #ifndef NDEBUG 180 DebugType = ""; 181 #endif 182 } 183 184 ~SCEVExpander() { 185 // Make sure the insert point guard stack is consistent. 186 assert(InsertPointGuards.empty()); 187 } 188 189 #ifndef NDEBUG 190 void setDebugType(const char *s) { DebugType = s; } 191 #endif 192 193 /// Erase the contents of the InsertedExpressions map so that users trying 194 /// to expand the same expression into multiple BasicBlocks or different 195 /// places within the same BasicBlock can do so. 196 void clear() { 197 InsertedExpressions.clear(); 198 InsertedValues.clear(); 199 InsertedPostIncValues.clear(); 200 ReusedValues.clear(); 201 ChainedPhis.clear(); 202 } 203 204 ScalarEvolution *getSE() { return &SE; } 205 206 /// Return a vector containing all instructions inserted during expansion. 207 SmallVector<Instruction *, 32> getAllInsertedInstructions() const { 208 SmallVector<Instruction *, 32> Result; 209 for (auto &VH : InsertedValues) { 210 Value *V = VH; 211 if (ReusedValues.contains(V)) 212 continue; 213 if (auto *Inst = dyn_cast<Instruction>(V)) 214 Result.push_back(Inst); 215 } 216 for (auto &VH : InsertedPostIncValues) { 217 Value *V = VH; 218 if (ReusedValues.contains(V)) 219 continue; 220 if (auto *Inst = dyn_cast<Instruction>(V)) 221 Result.push_back(Inst); 222 } 223 224 return Result; 225 } 226 227 /// Return true for expressions that can't be evaluated at runtime 228 /// within given \b Budget. 229 /// 230 /// At is a parameter which specifies point in code where user is going to 231 /// expand this expression. Sometimes this knowledge can lead to 232 /// a less pessimistic cost estimation. 233 bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, 234 const TargetTransformInfo *TTI, 235 const Instruction *At) { 236 assert(TTI && "This function requires TTI to be provided."); 237 assert(At && "This function requires At instruction to be provided."); 238 if (!TTI) // In assert-less builds, avoid crashing 239 return true; // by always claiming to be high-cost. 240 SmallVector<SCEVOperand, 8> Worklist; 241 SmallPtrSet<const SCEV *, 8> Processed; 242 InstructionCost Cost = 0; 243 unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic; 244 Worklist.emplace_back(-1, -1, Expr); 245 while (!Worklist.empty()) { 246 const SCEVOperand WorkItem = Worklist.pop_back_val(); 247 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI, 248 Processed, Worklist)) 249 return true; 250 } 251 assert(Cost <= ScaledBudget && "Should have returned from inner loop."); 252 return false; 253 } 254 255 /// Return the induction variable increment's IV operand. 256 Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, 257 bool allowScale); 258 259 /// Utility for hoisting an IV increment. 260 bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); 261 262 /// replace congruent phis with their most canonical representative. Return 263 /// the number of phis eliminated. 264 unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, 265 SmallVectorImpl<WeakTrackingVH> &DeadInsts, 266 const TargetTransformInfo *TTI = nullptr); 267 268 /// Insert code to directly compute the specified SCEV expression into the 269 /// program. The code is inserted into the specified block. 270 Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) { 271 return expandCodeForImpl(SH, Ty, I, true); 272 } 273 274 /// Insert code to directly compute the specified SCEV expression into the 275 /// program. The code is inserted into the SCEVExpander's current 276 /// insertion point. If a type is specified, the result will be expanded to 277 /// have that type, with a cast if necessary. 278 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) { 279 return expandCodeForImpl(SH, Ty, true); 280 } 281 282 /// Generates a code sequence that evaluates this predicate. The inserted 283 /// instructions will be at position \p Loc. The result will be of type i1 284 /// and will have a value of 0 when the predicate is false and 1 otherwise. 285 Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc); 286 287 /// A specialized variant of expandCodeForPredicate, handling the case when 288 /// we are expanding code for a SCEVEqualPredicate. 289 Value *expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc); 290 291 /// Generates code that evaluates if the \p AR expression will overflow. 292 Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, 293 bool Signed); 294 295 /// A specialized variant of expandCodeForPredicate, handling the case when 296 /// we are expanding code for a SCEVWrapPredicate. 297 Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc); 298 299 /// A specialized variant of expandCodeForPredicate, handling the case when 300 /// we are expanding code for a SCEVUnionPredicate. 301 Value *expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc); 302 303 /// Set the current IV increment loop and position. 304 void setIVIncInsertPos(const Loop *L, Instruction *Pos) { 305 assert(!CanonicalMode && 306 "IV increment positions are not supported in CanonicalMode"); 307 IVIncInsertLoop = L; 308 IVIncInsertPos = Pos; 309 } 310 311 /// Enable post-inc expansion for addrecs referring to the given 312 /// loops. Post-inc expansion is only supported in non-canonical mode. 313 void setPostInc(const PostIncLoopSet &L) { 314 assert(!CanonicalMode && 315 "Post-inc expansion is not supported in CanonicalMode"); 316 PostIncLoops = L; 317 } 318 319 /// Disable all post-inc expansion. 320 void clearPostInc() { 321 PostIncLoops.clear(); 322 323 // When we change the post-inc loop set, cached expansions may no 324 // longer be valid. 325 InsertedPostIncValues.clear(); 326 } 327 328 /// Disable the behavior of expanding expressions in canonical form rather 329 /// than in a more literal form. Non-canonical mode is useful for late 330 /// optimization passes. 331 void disableCanonicalMode() { CanonicalMode = false; } 332 333 void enableLSRMode() { LSRMode = true; } 334 335 /// Set the current insertion point. This is useful if multiple calls to 336 /// expandCodeFor() are going to be made with the same insert point and the 337 /// insert point may be moved during one of the expansions (e.g. if the 338 /// insert point is not a block terminator). 339 void setInsertPoint(Instruction *IP) { 340 assert(IP); 341 Builder.SetInsertPoint(IP); 342 } 343 344 /// Clear the current insertion point. This is useful if the instruction 345 /// that had been serving as the insertion point may have been deleted. 346 void clearInsertPoint() { Builder.ClearInsertionPoint(); } 347 348 /// Set location information used by debugging information. 349 void SetCurrentDebugLocation(DebugLoc L) { 350 Builder.SetCurrentDebugLocation(std::move(L)); 351 } 352 353 /// Get location information used by debugging information. 354 DebugLoc getCurrentDebugLocation() const { 355 return Builder.getCurrentDebugLocation(); 356 } 357 358 /// Return true if the specified instruction was inserted by the code 359 /// rewriter. If so, the client should not modify the instruction. Note that 360 /// this also includes instructions re-used during expansion. 361 bool isInsertedInstruction(Instruction *I) const { 362 return InsertedValues.count(I) || InsertedPostIncValues.count(I); 363 } 364 365 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); } 366 367 /// Try to find the ValueOffsetPair for S. The function is mainly used to 368 /// check whether S can be expanded cheaply. If this returns a non-None 369 /// value, we know we can codegen the `ValueOffsetPair` into a suitable 370 /// expansion identical with S so that S can be expanded cheaply. 371 /// 372 /// L is a hint which tells in which loop to look for the suitable value. 373 /// On success return value which is equivalent to the expanded S at point 374 /// At. Return nullptr if value was not found. 375 /// 376 /// Note that this function does not perform an exhaustive search. I.e if it 377 /// didn't find any value it does not mean that there is no such value. 378 /// 379 Optional<ScalarEvolution::ValueOffsetPair> 380 getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L); 381 382 /// Returns a suitable insert point after \p I, that dominates \p 383 /// MustDominate. Skips instructions inserted by the expander. 384 BasicBlock::iterator findInsertPointAfter(Instruction *I, 385 Instruction *MustDominate) const; 386 387 private: 388 LLVMContext &getContext() const { return SE.getContext(); } 389 390 /// Insert code to directly compute the specified SCEV expression into the 391 /// program. The code is inserted into the SCEVExpander's current 392 /// insertion point. If a type is specified, the result will be expanded to 393 /// have that type, with a cast if necessary. If \p Root is true, this 394 /// indicates that \p SH is the top-level expression to expand passed from 395 /// an external client call. 396 Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root); 397 398 /// Insert code to directly compute the specified SCEV expression into the 399 /// program. The code is inserted into the specified block. If \p 400 /// Root is true, this indicates that \p SH is the top-level expression to 401 /// expand passed from an external client call. 402 Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root); 403 404 /// Recursive helper function for isHighCostExpansion. 405 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L, 406 const Instruction &At, InstructionCost &Cost, 407 unsigned Budget, 408 const TargetTransformInfo &TTI, 409 SmallPtrSetImpl<const SCEV *> &Processed, 410 SmallVectorImpl<SCEVOperand> &Worklist); 411 412 /// Insert the specified binary operator, doing a small amount of work to 413 /// avoid inserting an obviously redundant operation, and hoisting to an 414 /// outer loop when the opportunity is there and it is safe. 415 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, 416 SCEV::NoWrapFlags Flags, bool IsSafeToHoist); 417 418 /// We want to cast \p V. What would be the best place for such a cast? 419 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const; 420 421 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing 422 /// cast if a suitable one exists, moving an existing cast if a suitable one 423 /// exists but isn't in the right place, or creating a new one. 424 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op, 425 BasicBlock::iterator IP); 426 427 /// Insert a cast of V to the specified type, which must be possible with a 428 /// noop cast, doing what we can to share the casts. 429 Value *InsertNoopCastOfTo(Value *V, Type *Ty); 430 431 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using 432 /// ptrtoint+arithmetic+inttoptr. 433 Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end, 434 PointerType *PTy, Type *Ty, Value *V); 435 Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V); 436 437 /// Find a previous Value in ExprValueMap for expand. 438 ScalarEvolution::ValueOffsetPair 439 FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt); 440 441 Value *expand(const SCEV *S); 442 443 /// Determine the most "relevant" loop for the given SCEV. 444 const Loop *getRelevantLoop(const SCEV *); 445 446 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } 447 448 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S); 449 450 Value *visitTruncateExpr(const SCEVTruncateExpr *S); 451 452 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); 453 454 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); 455 456 Value *visitAddExpr(const SCEVAddExpr *S); 457 458 Value *visitMulExpr(const SCEVMulExpr *S); 459 460 Value *visitUDivExpr(const SCEVUDivExpr *S); 461 462 Value *visitAddRecExpr(const SCEVAddRecExpr *S); 463 464 Value *visitSMaxExpr(const SCEVSMaxExpr *S); 465 466 Value *visitUMaxExpr(const SCEVUMaxExpr *S); 467 468 Value *visitSMinExpr(const SCEVSMinExpr *S); 469 470 Value *visitUMinExpr(const SCEVUMinExpr *S); 471 472 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } 473 474 void rememberInstruction(Value *I); 475 476 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); 477 478 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); 479 480 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); 481 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, 482 const Loop *L, Type *ExpandTy, Type *IntTy, 483 Type *&TruncTy, bool &InvertStep); 484 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy, 485 Type *IntTy, bool useSubtract); 486 487 void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, 488 Instruction *Pos, PHINode *LoopPhi); 489 490 void fixupInsertPoints(Instruction *I); 491 492 /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new 493 /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User. 494 /// If no PHIs have been created, return the unchanged operand \p OpIdx. 495 Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx); 496 }; 497 498 /// Helper to remove instructions inserted during SCEV expansion, unless they 499 /// are marked as used. 500 class SCEVExpanderCleaner { 501 SCEVExpander &Expander; 502 503 DominatorTree &DT; 504 505 /// Indicates whether the result of the expansion is used. If false, the 506 /// instructions added during expansion are removed. 507 bool ResultUsed; 508 509 public: 510 SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT) 511 : Expander(Expander), DT(DT), ResultUsed(false) {} 512 513 ~SCEVExpanderCleaner() { cleanup(); } 514 515 /// Indicate that the result of the expansion is used. 516 void markResultUsed() { ResultUsed = true; } 517 518 void cleanup(); 519 }; 520 } // namespace llvm 521 522 #endif 523