1 //===- LoopVersioning.h - Utility to version a loop -------------*- 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 a utility class to perform loop versioning. The versioned 10 // loop speculates that otherwise may-aliasing memory accesses don't overlap and 11 // emits checks to prove this. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H 16 #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H 17 18 #include "llvm/IR/PassManager.h" 19 #include "llvm/Transforms/Utils/LoopUtils.h" 20 #include "llvm/Transforms/Utils/ValueMapper.h" 21 22 namespace llvm { 23 24 class Loop; 25 class SCEVPredicate; 26 class ScalarEvolution; 27 class LoopAccessInfo; 28 class LoopInfo; 29 struct RuntimeCheckingPtrGroup; 30 typedef std::pair<const RuntimeCheckingPtrGroup *, 31 const RuntimeCheckingPtrGroup *> 32 RuntimePointerCheck; 33 34 template <typename T> class ArrayRef; 35 36 /// This class emits a version of the loop where run-time checks ensure 37 /// that may-alias pointers can't overlap. 38 /// 39 /// It currently only supports single-exit loops and assumes that the loop 40 /// already has a preheader. 41 class LoopVersioning { 42 public: 43 /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input. 44 /// It uses runtime check provided by the user. If \p UseLAIChecks is true, 45 /// we will retain the default checks made by LAI. Otherwise, construct an 46 /// object having no checks and we expect the user to add them. 47 LoopVersioning(const LoopAccessInfo &LAI, 48 ArrayRef<RuntimePointerCheck> Checks, Loop *L, LoopInfo *LI, 49 DominatorTree *DT, ScalarEvolution *SE); 50 51 /// Performs the CFG manipulation part of versioning the loop including 52 /// the DominatorTree and LoopInfo updates. 53 /// 54 /// The loop that was used to construct the class will be the "versioned" loop 55 /// i.e. the loop that will receive control if all the memchecks pass. 56 /// 57 /// This allows the loop transform pass to operate on the same loop regardless 58 /// of whether versioning was necessary or not: 59 /// 60 /// for each loop L: 61 /// analyze L 62 /// if versioning is necessary version L 63 /// transform L versionLoop()64 void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); } 65 66 /// Same but if the client has already precomputed the set of values 67 /// used outside the loop, this API will allows passing that. 68 void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside); 69 70 /// Returns the versioned loop. Control flows here if pointers in the 71 /// loop don't alias (i.e. all memchecks passed). (This loop is actually the 72 /// same as the original loop that we got constructed with.) getVersionedLoop()73 Loop *getVersionedLoop() { return VersionedLoop; } 74 75 /// Returns the fall-back loop. Control flows here if pointers in the 76 /// loop may alias (i.e. one of the memchecks failed). getNonVersionedLoop()77 Loop *getNonVersionedLoop() { return NonVersionedLoop; } 78 79 /// Annotate memory instructions in the versioned loop with no-alias 80 /// metadata based on the memchecks issued. 81 /// 82 /// This is just wrapper that calls prepareNoAliasMetadata and 83 /// annotateInstWithNoAlias on the instructions of the versioned loop. 84 void annotateLoopWithNoAlias(); 85 86 /// Set up the aliasing scopes based on the memchecks. This needs to 87 /// be called before the first call to annotateInstWithNoAlias. 88 void prepareNoAliasMetadata(); 89 90 /// Add the noalias annotations to \p VersionedInst. 91 /// 92 /// \p OrigInst is the instruction corresponding to \p VersionedInst in the 93 /// original loop. Initialize the aliasing scopes with 94 /// prepareNoAliasMetadata once before this can be called. 95 void annotateInstWithNoAlias(Instruction *VersionedInst, 96 const Instruction *OrigInst); 97 98 private: 99 /// Adds the necessary PHI nodes for the versioned loops based on the 100 /// loop-defined values used outside of the loop. 101 /// 102 /// This needs to be called after versionLoop if there are defs in the loop 103 /// that are used outside the loop. 104 void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); 105 106 /// Add the noalias annotations to \p I. Initialize the aliasing 107 /// scopes with prepareNoAliasMetadata once before this can be called. annotateInstWithNoAlias(Instruction * I)108 void annotateInstWithNoAlias(Instruction *I) { 109 annotateInstWithNoAlias(I, I); 110 } 111 112 /// The original loop. This becomes the "versioned" one. I.e., 113 /// control flows here if pointers in the loop don't alias. 114 Loop *VersionedLoop; 115 /// The fall-back loop. I.e. control flows here if pointers in the 116 /// loop may alias (memchecks failed). 117 Loop *NonVersionedLoop = nullptr; 118 119 /// This maps the instructions from VersionedLoop to their counterpart 120 /// in NonVersionedLoop. 121 ValueToValueMapTy VMap; 122 123 /// The set of alias checks that we are versioning for. 124 SmallVector<RuntimePointerCheck, 4> AliasChecks; 125 126 /// The set of SCEV checks that we are versioning for. 127 const SCEVPredicate &Preds; 128 129 /// Maps a pointer to the pointer checking group that the pointer 130 /// belongs to. 131 DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup; 132 133 /// The alias scope corresponding to a pointer checking group. 134 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope; 135 136 /// The list of alias scopes that a pointer checking group can't alias. 137 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> 138 GroupToNonAliasingScopeList; 139 140 /// Analyses used. 141 const LoopAccessInfo &LAI; 142 LoopInfo *LI; 143 DominatorTree *DT; 144 ScalarEvolution *SE; 145 }; 146 147 /// Expose LoopVersioning as a pass. Currently this is only used for 148 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing 149 /// array accesses from the loop. 150 class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> { 151 public: 152 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 153 }; 154 } 155 156 #endif 157