Coverage Report

Created: 2018-10-23 03:11

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