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