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