Coverage Report

Created: 2019-02-15 18:59

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