Coverage Report

Created: 2019-04-21 19:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/CodeGen/IRBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ PollyIRBuilder.cpp --------------------------------------------===//
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
// The Polly IRBuilder file contains Polly specific extensions for the IRBuilder
10
// that are used e.g. to emit the llvm.loop.parallel metadata.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/CodeGen/IRBuilder.h"
15
#include "polly/ScopInfo.h"
16
#include "polly/Support/ScopHelper.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/IR/Metadata.h"
19
20
using namespace llvm;
21
using namespace polly;
22
23
static const int MaxArraysInAliasScops = 10;
24
25
/// Get a self referencing id metadata node.
26
///
27
/// The MDNode looks like this (if arg0/arg1 are not null):
28
///
29
///    '!n = metadata !{metadata !n, arg0, arg1}'
30
///
31
/// @return The self referencing id metadata node.
32
static MDNode *getID(LLVMContext &Ctx, Metadata *arg0 = nullptr,
33
850
                     Metadata *arg1 = nullptr) {
34
850
  MDNode *ID;
35
850
  SmallVector<Metadata *, 3> Args;
36
850
  // Use a temporary node to safely create a unique pointer for the first arg.
37
850
  auto TempNode = MDNode::getTemporary(Ctx, None);
38
850
  // Reserve operand 0 for loop id self reference.
39
850
  Args.push_back(TempNode.get());
40
850
41
850
  if (arg0)
42
820
    Args.push_back(arg0);
43
850
  if (arg1)
44
514
    Args.push_back(arg1);
45
850
46
850
  ID = MDNode::get(Ctx, Args);
47
850
  ID->replaceOperandWith(0, ID);
48
850
  return ID;
49
850
}
50
51
304
ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
52
53
304
void ScopAnnotator::buildAliasScopes(Scop &S) {
54
304
  SE = S.getSE();
55
304
56
304
  LLVMContext &Ctx = SE->getContext();
57
304
  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
58
304
59
304
  AliasScopeMap.clear();
60
304
  OtherAliasScopeListMap.clear();
61
304
62
304
  // We are only interested in arrays, but no scalar references. Scalars should
63
304
  // be handled easily by basicaa.
64
304
  SmallVector<ScopArrayInfo *, 10> Arrays;
65
304
  for (ScopArrayInfo *Array : S.arrays())
66
650
    if (Array->isArrayKind())
67
500
      Arrays.push_back(Array);
68
304
69
304
  // The construction of alias scopes is quadratic in the number of arrays
70
304
  // involved. In case of too many arrays, skip the construction of alias
71
304
  // information to avoid quadratic increases in compile time and code size.
72
304
  if (Arrays.size() > MaxArraysInAliasScops)
73
2
    return;
74
302
75
302
  std::string AliasScopeStr = "polly.alias.scope.";
76
478
  for (const ScopArrayInfo *Array : Arrays) {
77
478
    assert(Array->getBasePtr() && "Base pointer must be present");
78
478
    AliasScopeMap[Array->getBasePtr()] =
79
478
        getID(Ctx, AliasScopeDomain,
80
478
              MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
81
478
  }
82
302
83
478
  for (const ScopArrayInfo *Array : Arrays) {
84
478
    MDNode *AliasScopeList = MDNode::get(Ctx, {});
85
1.14k
    for (const auto &AliasScopePair : AliasScopeMap) {
86
1.14k
      if (Array->getBasePtr() == AliasScopePair.first)
87
478
        continue;
88
662
89
662
      Metadata *Args = {AliasScopePair.second};
90
662
      AliasScopeList =
91
662
          MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
92
662
    }
93
478
94
478
    OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
95
478
  }
96
302
}
97
98
282
void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
99
282
100
282
  ActiveLoops.push_back(L);
101
282
  if (!IsParallel)
102
252
    return;
103
30
104
30
  BasicBlock *Header = L->getHeader();
105
30
  MDNode *Id = getID(Header->getContext());
106
30
  assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
107
30
  assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
108
30
  MDNode *Ids = ParallelLoops.empty()
109
30
                    ? 
Id29
110
30
                    : 
MDNode::concatenate(ParallelLoops.back(), Id)1
;
111
30
  ParallelLoops.push_back(Ids);
112
30
}
113
114
282
void ScopAnnotator::popLoop(bool IsParallel) {
115
282
  ActiveLoops.pop_back();
116
282
  if (!IsParallel)
117
252
    return;
118
30
119
30
  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
120
30
  ParallelLoops.pop_back();
121
30
}
122
123
void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
124
282
                                      bool IsLoopVectorizerDisabled) const {
125
282
  MDNode *MData = nullptr;
126
282
127
282
  if (IsLoopVectorizerDisabled) {
128
2
    SmallVector<Metadata *, 3> Args;
129
2
    LLVMContext &Ctx = SE->getContext();
130
2
    Args.push_back(MDString::get(Ctx, "llvm.loop.vectorize.enable"));
131
2
    auto *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
132
2
    Args.push_back(ValueAsMetadata::get(FalseValue));
133
2
    MData = MDNode::concatenate(MData, getID(Ctx, MDNode::get(Ctx, Args)));
134
2
  }
135
282
136
282
  if (IsParallel) {
137
30
    assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
138
30
    MDNode *Ids = ParallelLoops.back();
139
30
    MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
140
30
    MData = MDNode::concatenate(MData, Id);
141
30
  }
142
282
143
282
  B->setMetadata("llvm.loop", MData);
144
282
}
145
146
/// Get the pointer operand
147
///
148
/// @param Inst The instruction to be analyzed.
149
/// @return the pointer operand in case @p Inst is a memory access
150
///         instruction and nullptr otherwise.
151
1.74k
static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
152
1.74k
  auto MemInst = MemAccInst::dyn_cast(Inst);
153
1.74k
  if (!MemInst)
154
0
    return nullptr;
155
1.74k
156
1.74k
  return MemInst.getPointerOperand();
157
1.74k
}
158
159
void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
160
72
                                        llvm::Value *BasePtr) {
161
72
  Value *Ptr = getMemAccInstPointerOperand(Inst);
162
72
  if (!Ptr)
163
0
    return;
164
72
165
72
  auto *PtrSCEV = SE->getSCEV(Ptr);
166
72
  auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
167
72
168
72
  auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
169
72
  auto SecondLevelOtherAliasScopeList =
170
72
      SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
171
72
  if (!SecondLevelAliasScope) {
172
36
    auto AliasScope = AliasScopeMap.lookup(BasePtr);
173
36
    if (!AliasScope)
174
0
      return;
175
36
    LLVMContext &Ctx = SE->getContext();
176
36
    SecondLevelAliasScope = getID(
177
36
        Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
178
36
    SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
179
36
    Metadata *Args = {SecondLevelAliasScope};
180
36
    auto SecondLevelBasePtrAliasScopeList =
181
36
        SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
182
36
    SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
183
36
        SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
184
36
    auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
185
36
    SecondLevelOtherAliasScopeList = MDNode::concatenate(
186
36
        OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
187
36
    SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
188
36
  }
189
72
  Inst->setMetadata("alias.scope", SecondLevelAliasScope);
190
72
  Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
191
72
}
192
193
10.2k
void ScopAnnotator::annotate(Instruction *Inst) {
194
10.2k
  if (!Inst->mayReadOrWriteMemory())
195
8.36k
    return;
196
1.88k
197
1.88k
  if (!ParallelLoops.empty())
198
58
    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
199
1.88k
200
1.88k
  // TODO: Use the ScopArrayInfo once available here.
201
1.88k
  if (!AliasScopeDomain)
202
0
    return;
203
1.88k
204
1.88k
  // Do not apply annotations on memory operations that take more than one
205
1.88k
  // pointer. It would be ambiguous to which pointer the annotation applies.
206
1.88k
  // FIXME: How can we specify annotations for all pointer arguments?
207
1.88k
  if (isa<CallInst>(Inst) && 
!isa<MemSetInst>(Inst)219
)
208
218
    return;
209
1.66k
210
1.66k
  auto *Ptr = getMemAccInstPointerOperand(Inst);
211
1.66k
  if (!Ptr)
212
0
    return;
213
1.66k
214
1.66k
  auto *PtrSCEV = SE->getSCEV(Ptr);
215
1.66k
  auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
216
1.66k
  auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
217
1.66k
218
1.66k
  if (!SU)
219
0
    return;
220
1.66k
221
1.66k
  auto *BasePtr = SU->getValue();
222
1.66k
223
1.66k
  if (!BasePtr)
224
0
    return;
225
1.66k
226
1.66k
  auto AliasScope = AliasScopeMap.lookup(BasePtr);
227
1.66k
228
1.66k
  if (!AliasScope) {
229
816
    BasePtr = AlternativeAliasBases.lookup(BasePtr);
230
816
    if (!BasePtr)
231
738
      return;
232
78
233
78
    AliasScope = AliasScopeMap.lookup(BasePtr);
234
78
    if (!AliasScope)
235
17
      return;
236
914
  }
237
914
238
914
  assert(OtherAliasScopeListMap.count(BasePtr) &&
239
914
         "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
240
914
  auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
241
914
242
914
  if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
243
72
    annotateSecondLevel(Inst, BasePtr);
244
72
    return;
245
72
  }
246
842
247
842
  Inst->setMetadata("alias.scope", AliasScope);
248
842
  Inst->setMetadata("noalias", OtherAliasScopeList);
249
842
}
250
251
2
void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
252
2
  if (!BasePtr)
253
0
    return;
254
2
255
2
  InterIterationAliasFreeBasePtrs.insert(BasePtr);
256
2
}