LLVM  10.0.0svn
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 
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.
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,
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
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.)
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).
71  Loop *getNonVersionedLoop() { return NonVersionedLoop; }
72 
73  /// Sets the runtime alias checks for versioning the loop.
74  void setAliasChecks(
76 
77  /// Sets the runtime SCEV checks for versioning the loop.
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.
86 
87  /// Set up the aliasing scopes based on the memchecks. This needs to
88  /// be called before the first call to annotateInstWithNoAlias.
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.
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.
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.
133  PtrToGroup;
134 
135  /// The alias scope corresponding to a pointer checking group.
137  GroupToScope;
138 
139  /// The list of alias scopes that a pointer checking group can't alias.
141  GroupToNonAliasingScopeList;
142 
143  /// Analyses used.
144  const LoopAccessInfo &LAI;
145  LoopInfo *LI;
146  DominatorTree *DT;
147  ScalarEvolution *SE;
148 };
149 }
150 
151 #endif
static bool Check(DecodeStatus &Out, DecodeStatus In)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The main scalar evolution driver.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:120
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 setAliasChecks(SmallVector< RuntimePointerChecking::PointerCheck, 4 > Checks)
Sets the runtime alias checks for versioning the loop.
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:509
#define I(x, y, z)
Definition: MD5.cpp:58
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.