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