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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
| //===- Codegen/IRBuilder.h - The IR builder used by Polly -*- 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
//
//===----------------------------------------------------------------------===//
//
// The Polly IRBuilder file contains Polly specific extensions for the IRBuilder
// that are used e.g. to emit the llvm.loop.parallel metadata.
//
//===----------------------------------------------------------------------===//
#ifndef POLLY_CODEGEN_IRBUILDER_H
#define POLLY_CODEGEN_IRBUILDER_H
#include "llvm/ADT/MapVector.h"
#include "llvm/IR/IRBuilder.h"
namespace llvm {
class Loop;
class SCEV;
class ScalarEvolution;
} // namespace llvm
namespace polly {
class Scop;
/// Helper class to annotate newly generated SCoPs with metadata.
///
/// The annotations are twofold:
/// 1) Loops are stored in a stack-like structure in the order they are
/// constructed and the LoopID metadata node is added to the backedge.
/// Contained memory instructions and loop headers are annotated according
/// to all parallel surrounding loops.
/// 2) The new SCoP is assumed alias free (either due to the result of
/// AliasAnalysis queries or runtime alias checks). We annotate therefore
/// all memory instruction with alias scopes to indicate that fact to
/// later optimizations.
/// These alias scopes live in a new alias domain only used in this SCoP.
/// Each base pointer has its own alias scope and is annotated to not
/// alias with any access to different base pointers.
class ScopAnnotator {
public:
ScopAnnotator();
/// Build all alias scopes for the given SCoP.
void buildAliasScopes(Scop &S);
/// Add a new loop @p L which is parallel if @p IsParallel is true.
void pushLoop(llvm::Loop *L, bool IsParallel);
/// Remove the last added loop.
void popLoop(bool isParallel);
/// Annotate the new instruction @p I for all parallel loops.
void annotate(llvm::Instruction *I);
/// Annotate the loop latch @p B wrt. @p L.
void annotateLoopLatch(llvm::BranchInst *B, llvm::Loop *L, bool IsParallel,
bool IsLoopVectorizerDisabled) const;
/// Add alternative alias based pointers
///
/// When annotating instructions with alias scope metadata, the right metadata
/// is identified through the base pointer of the memory access. In some cases
/// (e.g. OpenMP code generation), the base pointer of the memory accesses is
/// not the original base pointer, but was changed when passing the original
/// base pointer over a function boundary. This function allows to provide a
/// map that maps from these new base pointers to the original base pointers
/// to allow the ScopAnnotator to still find the right alias scop annotations.
///
/// @param NewMap A map from new base pointers to original base pointers.
void addAlternativeAliasBases(
llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
llvm::AssertingVH<llvm::Value>> &NewMap) {
AlternativeAliasBases.insert(NewMap.begin(), NewMap.end());
}
/// Delete the set of alternative alias bases
void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); }
/// Add inter iteration alias-free base pointer @p BasePtr.
void addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr);
private:
/// Annotate with the second level alias metadata
///
/// Annotate the instruction @p I with the second level alias metadata
/// to distinguish the individual non-aliasing accesses that have inter
/// iteration alias-free base pointers.
///
/// @param I The instruction to be annotated.
/// @param BasePtr The base pointer of @p I.
void annotateSecondLevel(llvm::Instruction *I, llvm::Value *BasePtr);
/// The ScalarEvolution analysis we use to find base pointers.
llvm::ScalarEvolution *SE;
/// All loops currently under construction.
llvm::SmallVector<llvm::Loop *, 8> ActiveLoops;
/// Metadata pointing to parallel loops currently under construction.
llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops;
/// The alias scope domain for the current SCoP.
llvm::MDNode *AliasScopeDomain;
/// A map from base pointers to its alias scope.
llvm::MapVector<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> AliasScopeMap;
/// A map from base pointers to an alias scope list of other pointers.
llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *>
OtherAliasScopeListMap;
/// A map from pointers to second level alias scopes.
llvm::DenseMap<const llvm::SCEV *, llvm::MDNode *> SecondLevelAliasScopeMap;
/// A map from pointers to second level alias scope list of other pointers.
llvm::DenseMap<const llvm::SCEV *, llvm::MDNode *>
SecondLevelOtherAliasScopeListMap;
/// Inter iteration alias-free base pointers.
llvm::SmallPtrSet<llvm::Value *, 4> InterIterationAliasFreeBasePtrs;
llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>>
AlternativeAliasBases;
};
/// Add Polly specifics when running IRBuilder.
///
/// This is used to add additional items such as e.g. the llvm.loop.parallel
/// metadata.
class IRInserter : protected llvm::IRBuilderDefaultInserter {
public:
IRInserter() = default;
IRInserter(class ScopAnnotator &A) : Annotator(&A) {}
protected:
void InsertHelper(llvm::Instruction *I, const llvm::Twine &Name,
llvm::BasicBlock *BB,
llvm::BasicBlock::iterator InsertPt) const {
llvm::IRBuilderDefaultInserter::InsertHelper(I, Name, BB, InsertPt);
if (Annotator)
Annotator->annotate(I);
}
private:
class ScopAnnotator *Annotator = nullptr;
};
// TODO: We should not name instructions in NDEBUG builds.
//
// We currently always name instructions, as the polly test suite currently
// matches for certain names.
typedef llvm::IRBuilder<llvm::ConstantFolder, IRInserter> PollyIRBuilder;
/// Return an IR builder pointed before the @p BB terminator.
static inline PollyIRBuilder createPollyIRBuilder(llvm::BasicBlock *BB,
ScopAnnotator &LA) {
PollyIRBuilder Builder(BB->getContext(), llvm::ConstantFolder(),
polly::IRInserter(LA));
Builder.SetInsertPoint(BB->getTerminator());
return Builder;
}
} // namespace polly
#endif
|