1//===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===//
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
7//===----------------------------------------------------------------------===//
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.
13//===----------------------------------------------------------------------===//
15#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
16#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
36/// This class emits a version of the loop where run-time checks ensure
37/// that may-alias pointers can't overlap.
39/// It currently only supports single-exit loops and assumes that the loop
40/// already has a preheader.
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.
51 /// Performs the CFG manipulation part of versioning the loop including
52 /// the DominatorTree and LoopInfo updates.
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.
57 /// This allows the loop transform pass to operate on the same loop regardless
58 /// of whether versioning was necessary or not:
62 /// if versioning is necessary version L
66 /// Same but if the client has already precomputed the set of values
67 /// used outside the loop, this API will allows passing that.
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.)
75 /// Returns the fall-back loop. Control flows here if pointers in the
76 /// loop may alias (i.e. one of the memchecks failed).
79 /// Annotate memory instructions in the versioned loop with no-alias
80 /// metadata based on the memchecks issued.
82 /// This is just wrapper that calls prepareNoAliasMetadata and
83 /// annotateInstWithNoAlias on the instructions of the versioned loop.
86 /// Returns a pair containing the alias_scope and noalias metadata nodes for
87 /// \p OrigInst, if they exists.
88 std::pair<MDNode *, MDNode *>
91 /// Set up the aliasing scopes based on the memchecks. This needs to
92 /// be called before the first call to annotateInstWithNoAlias.
95 /// Add the noalias annotations to \p VersionedInst.
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.
104 /// Adds the necessary PHI nodes for the versioned loops based on the
105 /// loop-defined values used outside of the loop.
107 /// This needs to be called after versionLoop if there are defs in the loop
108 /// that are used outside the loop.
111 /// Add the noalias annotations to \p I. Initialize the aliasing
112 /// scopes with prepareNoAliasMetadata once before this can be called.
117 /// The original loop. This becomes the "versioned" one. I.e.,
118 /// control flows here if pointers in the loop don't alias.
120 /// The fall-back loop. I.e. control flows here if pointers in the
121 /// loop may alias (memchecks failed).
122 Loop *NonVersionedLoop =
nullptr;
124 /// This maps the instructions from VersionedLoop to their counterpart
125 /// in NonVersionedLoop.
128 /// The set of alias checks that we are versioning for.
129 SmallVector<RuntimePointerCheck, 4> AliasChecks;
131 /// The set of SCEV checks that we are versioning for.
132 const SCEVPredicate &Preds;
134 /// Maps a pointer to the pointer checking group that the pointer
136 DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;
138 /// The alias scope corresponding to a pointer checking group.
139 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
141 /// The list of alias scopes that a pointer checking group can't alias.
142 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
143 GroupToNonAliasingScopeList;
146 const LoopAccessInfo &LAI;
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.
This header defines various interfaces for pass management in LLVM.
FunctionAnalysisManager FAM
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Drive the analysis of memory accesses in the loop.
Expose LoopVersioning as a pass.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
Loop * getVersionedLoop()
Returns the versioned loop.
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
std::pair< MDNode *, MDNode * > getNoAliasMetadataFor(const Instruction *OrigInst) const
Returns a pair containing the alias_scope and noalias metadata nodes for OrigInst,...
LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
Loop * getNonVersionedLoop()
Returns the fall-back loop.
Represents a single loop in the control flow graph.
A set of analyses that are preserved following a run of a transformation pass.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
The main scalar evolution driver.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is an optimization pass for GlobalISel generic memory operations.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
LLVM_ABI SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
A CRTP mix-in to automatically provide informational APIs needed for passes.