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