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 /// Returns a pair containing the alias_scope and noalias metadata nodes for 87 /// \p OrigInst, if they exists. 88 std::pair<MDNode *, MDNode *> 89 getNoAliasMetadataFor(const Instruction *OrigInst) const; 90 91 /// Set up the aliasing scopes based on the memchecks. This needs to 92 /// be called before the first call to annotateInstWithNoAlias. 93 void prepareNoAliasMetadata(); 94 95 /// Add the noalias annotations to \p VersionedInst. 96 /// 97 /// \p OrigInst is the instruction corresponding to \p VersionedInst in the 98 /// original loop. Initialize the aliasing scopes with 99 /// prepareNoAliasMetadata once before this can be called. 100 void annotateInstWithNoAlias(Instruction *VersionedInst, 101 const Instruction *OrigInst); 102 103 private: 104 /// Adds the necessary PHI nodes for the versioned loops based on the 105 /// loop-defined values used outside of the loop. 106 /// 107 /// This needs to be called after versionLoop if there are defs in the loop 108 /// that are used outside the loop. 109 void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); 110 111 /// Add the noalias annotations to \p I. Initialize the aliasing 112 /// scopes with prepareNoAliasMetadata once before this can be called. annotateInstWithNoAlias(Instruction * I)113 void annotateInstWithNoAlias(Instruction *I) { 114 annotateInstWithNoAlias(I, I); 115 } 116 117 /// The original loop. This becomes the "versioned" one. I.e., 118 /// control flows here if pointers in the loop don't alias. 119 Loop *VersionedLoop; 120 /// The fall-back loop. I.e. control flows here if pointers in the 121 /// loop may alias (memchecks failed). 122 Loop *NonVersionedLoop = nullptr; 123 124 /// This maps the instructions from VersionedLoop to their counterpart 125 /// in NonVersionedLoop. 126 ValueToValueMapTy VMap; 127 128 /// The set of alias checks that we are versioning for. 129 SmallVector<RuntimePointerCheck, 4> AliasChecks; 130 131 /// The set of SCEV checks that we are versioning for. 132 const SCEVPredicate &Preds; 133 134 /// Maps a pointer to the pointer checking group that the pointer 135 /// belongs to. 136 DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup; 137 138 /// The alias scope corresponding to a pointer checking group. 139 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope; 140 141 /// The list of alias scopes that a pointer checking group can't alias. 142 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> 143 GroupToNonAliasingScopeList; 144 145 /// Analyses used. 146 const LoopAccessInfo &LAI; 147 LoopInfo *LI; 148 DominatorTree *DT; 149 ScalarEvolution *SE; 150 }; 151 152 /// Expose LoopVersioning as a pass. Currently this is only used for 153 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing 154 /// array accesses from the loop. 155 class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> { 156 public: 157 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 158 }; 159 } 160 161 #endif 162