Line data Source code
1 : //===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines a utility class to perform loop versioning. The versioned
11 : // loop speculates that otherwise may-aliasing memory accesses don't overlap and
12 : // emits checks to prove this.
13 : //
14 : //===----------------------------------------------------------------------===//
15 :
16 : #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
17 : #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
18 :
19 : #include "llvm/Analysis/LoopAccessAnalysis.h"
20 : #include "llvm/Analysis/ScalarEvolution.h"
21 : #include "llvm/Transforms/Utils/LoopUtils.h"
22 : #include "llvm/Transforms/Utils/ValueMapper.h"
23 :
24 : namespace llvm {
25 :
26 : class Loop;
27 : class LoopAccessInfo;
28 : class LoopInfo;
29 : class ScalarEvolution;
30 :
31 : /// This class emits a version of the loop where run-time checks ensure
32 : /// that may-alias pointers can't overlap.
33 : ///
34 : /// It currently only supports single-exit loops and assumes that the loop
35 : /// already has a preheader.
36 : class LoopVersioning {
37 : public:
38 : /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
39 : /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
40 : /// we will retain the default checks made by LAI. Otherwise, construct an
41 : /// object having no checks and we expect the user to add them.
42 : LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
43 : DominatorTree *DT, ScalarEvolution *SE,
44 : bool UseLAIChecks = true);
45 :
46 : /// Performs the CFG manipulation part of versioning the loop including
47 : /// the DominatorTree and LoopInfo updates.
48 : ///
49 : /// The loop that was used to construct the class will be the "versioned" loop
50 : /// i.e. the loop that will receive control if all the memchecks pass.
51 : ///
52 : /// This allows the loop transform pass to operate on the same loop regardless
53 : /// of whether versioning was necessary or not:
54 : ///
55 : /// for each loop L:
56 : /// analyze L
57 : /// if versioning is necessary version L
58 : /// transform L
59 29 : void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
60 :
61 : /// Same but if the client has already precomputed the set of values
62 : /// used outside the loop, this API will allows passing that.
63 : void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
64 :
65 : /// Returns the versioned loop. Control flows here if pointers in the
66 : /// loop don't alias (i.e. all memchecks passed). (This loop is actually the
67 : /// same as the original loop that we got constructed with.)
68 0 : Loop *getVersionedLoop() { return VersionedLoop; }
69 :
70 : /// Returns the fall-back loop. Control flows here if pointers in the
71 : /// loop may alias (i.e. one of the memchecks failed).
72 0 : Loop *getNonVersionedLoop() { return NonVersionedLoop; }
73 :
74 : /// Sets the runtime alias checks for versioning the loop.
75 : void setAliasChecks(
76 : SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
77 :
78 : /// Sets the runtime SCEV checks for versioning the loop.
79 : void setSCEVChecks(SCEVUnionPredicate Check);
80 :
81 : /// Annotate memory instructions in the versioned loop with no-alias
82 : /// metadata based on the memchecks issued.
83 : ///
84 : /// This is just wrapper that calls prepareNoAliasMetadata and
85 : /// annotateInstWithNoAlias on the instructions of the versioned loop.
86 : void annotateLoopWithNoAlias();
87 :
88 : /// Set up the aliasing scopes based on the memchecks. This needs to
89 : /// be called before the first call to annotateInstWithNoAlias.
90 : void prepareNoAliasMetadata();
91 :
92 : /// Add the noalias annotations to \p VersionedInst.
93 : ///
94 : /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
95 : /// original loop. Initialize the aliasing scopes with
96 : /// prepareNoAliasMetadata once before this can be called.
97 : void annotateInstWithNoAlias(Instruction *VersionedInst,
98 : const Instruction *OrigInst);
99 :
100 : private:
101 : /// Adds the necessary PHI nodes for the versioned loops based on the
102 : /// loop-defined values used outside of the loop.
103 : ///
104 : /// This needs to be called after versionLoop if there are defs in the loop
105 : /// that are used outside the loop.
106 : void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
107 :
108 : /// Add the noalias annotations to \p I. Initialize the aliasing
109 : /// scopes with prepareNoAliasMetadata once before this can be called.
110 : void annotateInstWithNoAlias(Instruction *I) {
111 113 : annotateInstWithNoAlias(I, I);
112 : }
113 :
114 : /// The original loop. This becomes the "versioned" one. I.e.,
115 : /// control flows here if pointers in the loop don't alias.
116 : Loop *VersionedLoop;
117 : /// The fall-back loop. I.e. control flows here if pointers in the
118 : /// loop may alias (memchecks failed).
119 : Loop *NonVersionedLoop;
120 :
121 : /// This maps the instructions from VersionedLoop to their counterpart
122 : /// in NonVersionedLoop.
123 : ValueToValueMapTy VMap;
124 :
125 : /// The set of alias checks that we are versioning for.
126 : SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
127 :
128 : /// The set of SCEV checks that we are versioning for.
129 : SCEVUnionPredicate Preds;
130 :
131 : /// Maps a pointer to the pointer checking group that the pointer
132 : /// belongs to.
133 : DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *>
134 : PtrToGroup;
135 :
136 : /// The alias scope corresponding to a pointer checking group.
137 : DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
138 : GroupToScope;
139 :
140 : /// The list of alias scopes that a pointer checking group can't alias.
141 : DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
142 : GroupToNonAliasingScopeList;
143 :
144 : /// Analyses used.
145 : const LoopAccessInfo &LAI;
146 : LoopInfo *LI;
147 : DominatorTree *DT;
148 : ScalarEvolution *SE;
149 : };
150 : }
151 :
152 : #endif
|
