1286425Sdim//===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===// 2286425Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6286425Sdim// 7286425Sdim//===----------------------------------------------------------------------===// 8286425Sdim// 9286425Sdim// This file defines a utility class to perform loop versioning. The versioned 10286425Sdim// loop speculates that otherwise may-aliasing memory accesses don't overlap and 11286425Sdim// emits checks to prove this. 12286425Sdim// 13286425Sdim//===----------------------------------------------------------------------===// 14286425Sdim 15286425Sdim#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H 16286425Sdim#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H 17286425Sdim 18296417Sdim#include "llvm/Analysis/LoopAccessAnalysis.h" 19296417Sdim#include "llvm/Analysis/ScalarEvolution.h" 20321369Sdim#include "llvm/Transforms/Utils/LoopUtils.h" 21286425Sdim#include "llvm/Transforms/Utils/ValueMapper.h" 22286425Sdim 23286425Sdimnamespace llvm { 24286425Sdim 25286425Sdimclass Loop; 26286425Sdimclass LoopAccessInfo; 27286425Sdimclass LoopInfo; 28296417Sdimclass ScalarEvolution; 29286425Sdim 30341825Sdim/// This class emits a version of the loop where run-time checks ensure 31286425Sdim/// that may-alias pointers can't overlap. 32286425Sdim/// 33286425Sdim/// It currently only supports single-exit loops and assumes that the loop 34286425Sdim/// already has a preheader. 35286425Sdimclass LoopVersioning { 36286425Sdimpublic: 37341825Sdim /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input. 38296417Sdim /// It uses runtime check provided by the user. If \p UseLAIChecks is true, 39296417Sdim /// we will retain the default checks made by LAI. Otherwise, construct an 40296417Sdim /// object having no checks and we expect the user to add them. 41286425Sdim LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, 42296417Sdim DominatorTree *DT, ScalarEvolution *SE, 43296417Sdim bool UseLAIChecks = true); 44286425Sdim 45341825Sdim /// Performs the CFG manipulation part of versioning the loop including 46286425Sdim /// the DominatorTree and LoopInfo updates. 47286425Sdim /// 48286425Sdim /// The loop that was used to construct the class will be the "versioned" loop 49286425Sdim /// i.e. the loop that will receive control if all the memchecks pass. 50286425Sdim /// 51286425Sdim /// This allows the loop transform pass to operate on the same loop regardless 52286425Sdim /// of whether versioning was necessary or not: 53286425Sdim /// 54286425Sdim /// for each loop L: 55286425Sdim /// analyze L 56286425Sdim /// if versioning is necessary version L 57286425Sdim /// transform L 58296417Sdim void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); } 59286425Sdim 60341825Sdim /// Same but if the client has already precomputed the set of values 61296417Sdim /// used outside the loop, this API will allows passing that. 62296417Sdim void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside); 63286425Sdim 64341825Sdim /// Returns the versioned loop. Control flows here if pointers in the 65286425Sdim /// loop don't alias (i.e. all memchecks passed). (This loop is actually the 66286425Sdim /// same as the original loop that we got constructed with.) 67286425Sdim Loop *getVersionedLoop() { return VersionedLoop; } 68286425Sdim 69341825Sdim /// Returns the fall-back loop. Control flows here if pointers in the 70286425Sdim /// loop may alias (i.e. one of the memchecks failed). 71286425Sdim Loop *getNonVersionedLoop() { return NonVersionedLoop; } 72286425Sdim 73341825Sdim /// Sets the runtime alias checks for versioning the loop. 74296417Sdim void setAliasChecks( 75309124Sdim SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); 76296417Sdim 77341825Sdim /// Sets the runtime SCEV checks for versioning the loop. 78296417Sdim void setSCEVChecks(SCEVUnionPredicate Check); 79296417Sdim 80341825Sdim /// Annotate memory instructions in the versioned loop with no-alias 81309124Sdim /// metadata based on the memchecks issued. 82309124Sdim /// 83309124Sdim /// This is just wrapper that calls prepareNoAliasMetadata and 84309124Sdim /// annotateInstWithNoAlias on the instructions of the versioned loop. 85309124Sdim void annotateLoopWithNoAlias(); 86309124Sdim 87341825Sdim /// Set up the aliasing scopes based on the memchecks. This needs to 88309124Sdim /// be called before the first call to annotateInstWithNoAlias. 89309124Sdim void prepareNoAliasMetadata(); 90309124Sdim 91341825Sdim /// Add the noalias annotations to \p VersionedInst. 92309124Sdim /// 93309124Sdim /// \p OrigInst is the instruction corresponding to \p VersionedInst in the 94309124Sdim /// original loop. Initialize the aliasing scopes with 95309124Sdim /// prepareNoAliasMetadata once before this can be called. 96309124Sdim void annotateInstWithNoAlias(Instruction *VersionedInst, 97309124Sdim const Instruction *OrigInst); 98309124Sdim 99286425Sdimprivate: 100341825Sdim /// Adds the necessary PHI nodes for the versioned loops based on the 101296417Sdim /// loop-defined values used outside of the loop. 102296417Sdim /// 103296417Sdim /// This needs to be called after versionLoop if there are defs in the loop 104296417Sdim /// that are used outside the loop. 105296417Sdim void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); 106296417Sdim 107341825Sdim /// Add the noalias annotations to \p I. Initialize the aliasing 108309124Sdim /// scopes with prepareNoAliasMetadata once before this can be called. 109309124Sdim void annotateInstWithNoAlias(Instruction *I) { 110309124Sdim annotateInstWithNoAlias(I, I); 111309124Sdim } 112309124Sdim 113341825Sdim /// The original loop. This becomes the "versioned" one. I.e., 114286425Sdim /// control flows here if pointers in the loop don't alias. 115286425Sdim Loop *VersionedLoop; 116341825Sdim /// The fall-back loop. I.e. control flows here if pointers in the 117286425Sdim /// loop may alias (memchecks failed). 118286425Sdim Loop *NonVersionedLoop; 119286425Sdim 120341825Sdim /// This maps the instructions from VersionedLoop to their counterpart 121286425Sdim /// in NonVersionedLoop. 122286425Sdim ValueToValueMapTy VMap; 123286425Sdim 124341825Sdim /// The set of alias checks that we are versioning for. 125296417Sdim SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks; 126296417Sdim 127341825Sdim /// The set of SCEV checks that we are versioning for. 128296417Sdim SCEVUnionPredicate Preds; 129296417Sdim 130341825Sdim /// Maps a pointer to the pointer checking group that the pointer 131309124Sdim /// belongs to. 132309124Sdim DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *> 133309124Sdim PtrToGroup; 134309124Sdim 135341825Sdim /// The alias scope corresponding to a pointer checking group. 136309124Sdim DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> 137309124Sdim GroupToScope; 138309124Sdim 139341825Sdim /// The list of alias scopes that a pointer checking group can't alias. 140309124Sdim DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> 141309124Sdim GroupToNonAliasingScopeList; 142309124Sdim 143341825Sdim /// Analyses used. 144286425Sdim const LoopAccessInfo &LAI; 145286425Sdim LoopInfo *LI; 146286425Sdim DominatorTree *DT; 147296417Sdim ScalarEvolution *SE; 148286425Sdim}; 149286425Sdim} 150286425Sdim 151286425Sdim#endif 152