LLVM  12.0.0git
LoopVersioning.h
Go to the documentation of this file.
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 
21 
22 namespace llvm {
23 
24 class Loop;
25 class LoopAccessInfo;
26 class LoopInfo;
27 class ScalarEvolution;
28 struct RuntimeCheckingPtrGroup;
29 typedef std::pair<const RuntimeCheckingPtrGroup *,
30  const RuntimeCheckingPtrGroup *>
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.
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, Loop *L, LoopInfo *LI,
48  bool UseLAIChecks = true);
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
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.)
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).
76  Loop *getNonVersionedLoop() { return NonVersionedLoop; }
77 
78  /// Sets the runtime alias checks for versioning the loop.
80 
81  /// Sets the runtime SCEV checks for versioning the loop.
83 
84  /// Annotate memory instructions in the versioned loop with no-alias
85  /// metadata based on the memchecks issued.
86  ///
87  /// This is just wrapper that calls prepareNoAliasMetadata and
88  /// annotateInstWithNoAlias on the instructions of the versioned loop.
90 
91  /// Set up the aliasing scopes based on the memchecks. This needs to
92  /// be called before the first call to annotateInstWithNoAlias.
94 
95  /// Add the noalias annotations to \p VersionedInst.
96  ///
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.
100  void annotateInstWithNoAlias(Instruction *VersionedInst,
101  const Instruction *OrigInst);
102 
103 private:
104  /// Adds the necessary PHI nodes for the versioned loops based on the
105  /// loop-defined values used outside of the loop.
106  ///
107  /// This needs to be called after versionLoop if there are defs in the loop
108  /// that are used outside the loop.
109  void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
110 
111  /// Add the noalias annotations to \p I. Initialize the aliasing
112  /// scopes with prepareNoAliasMetadata once before this can be called.
115  }
116 
117  /// The original loop. This becomes the "versioned" one. I.e.,
118  /// control flows here if pointers in the loop don't alias.
119  Loop *VersionedLoop;
120  /// The fall-back loop. I.e. control flows here if pointers in the
121  /// loop may alias (memchecks failed).
122  Loop *NonVersionedLoop;
123 
124  /// This maps the instructions from VersionedLoop to their counterpart
125  /// in NonVersionedLoop.
126  ValueToValueMapTy VMap;
127 
128  /// The set of alias checks that we are versioning for.
130 
131  /// The set of SCEV checks that we are versioning for.
132  SCEVUnionPredicate Preds;
133 
134  /// Maps a pointer to the pointer checking group that the pointer
135  /// belongs to.
137 
138  /// The alias scope corresponding to a pointer checking group.
140 
141  /// The list of alias scopes that a pointer checking group can't alias.
143  GroupToNonAliasingScopeList;
144 
145  /// Analyses used.
146  const LoopAccessInfo &LAI;
147  LoopInfo *LI;
148  DominatorTree *DT;
149  ScalarEvolution *SE;
150 };
151 }
152 
153 #endif
static bool Check(DecodeStatus &Out, DecodeStatus In)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The main scalar evolution driver.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:136
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Loop * getVersionedLoop()
Returns the versioned loop.
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
void setSCEVChecks(SCEVUnionPredicate Check)
Sets the runtime SCEV checks for versioning the loop.
Drive the analysis of memory accesses in the loop.
This class emits a version of the loop where run-time checks ensure that may-alias pointers can&#39;t ove...
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
#define I(x, y, z)
Definition: MD5.cpp:59
void setAliasChecks(ArrayRef< RuntimePointerCheck > Checks)
Sets the runtime alias checks for versioning the loop.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Loop * getNonVersionedLoop()
Returns the fall-back loop.
LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE, bool UseLAIChecks=true)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.