LLVM 19.0.0git
Go to the documentation of this file.
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
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.
18#include "llvm/IR/PassManager.h"
22namespace llvm {
24class Loop;
25class SCEVPredicate;
26class ScalarEvolution;
27class LoopAccessInfo;
28class LoopInfo;
29struct RuntimeCheckingPtrGroup;
30typedef std::pair<const RuntimeCheckingPtrGroup *,
31 const RuntimeCheckingPtrGroup *>
34template <typename T> class ArrayRef;
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.
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
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);
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.)
73 Loop *getVersionedLoop() { return VersionedLoop; }
75 /// Returns the fall-back loop. Control flows here if pointers in the
76 /// loop may alias (i.e. one of the memchecks failed).
77 Loop *getNonVersionedLoop() { return NonVersionedLoop; }
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.
86 /// Set up the aliasing scopes based on the memchecks. This needs to
87 /// be called before the first call to annotateInstWithNoAlias.
90 /// Add the noalias annotations to \p VersionedInst.
91 ///
92 /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
93 /// original loop. Initialize the aliasing scopes with
94 /// prepareNoAliasMetadata once before this can be called.
95 void annotateInstWithNoAlias(Instruction *VersionedInst,
96 const Instruction *OrigInst);
99 /// Adds the necessary PHI nodes for the versioned loops based on the
100 /// loop-defined values used outside of the loop.
101 ///
102 /// This needs to be called after versionLoop if there are defs in the loop
103 /// that are used outside the loop.
104 void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
106 /// Add the noalias annotations to \p I. Initialize the aliasing
107 /// scopes with prepareNoAliasMetadata once before this can be called.
110 }
112 /// The original loop. This becomes the "versioned" one. I.e.,
113 /// control flows here if pointers in the loop don't alias.
114 Loop *VersionedLoop;
115 /// The fall-back loop. I.e. control flows here if pointers in the
116 /// loop may alias (memchecks failed).
117 Loop *NonVersionedLoop = nullptr;
119 /// This maps the instructions from VersionedLoop to their counterpart
120 /// in NonVersionedLoop.
123 /// The set of alias checks that we are versioning for.
124 SmallVector<RuntimePointerCheck, 4> AliasChecks;
126 /// The set of SCEV checks that we are versioning for.
127 const SCEVPredicate &Preds;
129 /// Maps a pointer to the pointer checking group that the pointer
130 /// belongs to.
131 DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;
133 /// The alias scope corresponding to a pointer checking group.
134 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
136 /// The list of alias scopes that a pointer checking group can't alias.
137 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
138 GroupToNonAliasingScopeList;
140 /// Analyses used.
141 const LoopAccessInfo &LAI;
142 LoopInfo *LI;
143 DominatorTree *DT;
144 ScalarEvolution *SE;
147/// Expose LoopVersioning as a pass. Currently this is only used for
148/// unit-testing. It adds all memchecks necessary to remove all may-aliasing
149/// array accesses from the loop.
150class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> {
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Drive the analysis of memory accesses in the loop.
Expose LoopVersioning as a pass.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
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...
Loop * getNonVersionedLoop()
Returns the fall-back loop.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
The main scalar evolution driver.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:123
ArrayRef(const T &OneElt) -> ArrayRef< T >
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74