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