Coverage Report

Created: 2017-11-21 16:49

/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
276
                     Metadata *arg1 = nullptr) {
36
276
  MDNode *ID;
37
276
  SmallVector<Metadata *, 3> Args;
38
276
  // Use a temporary node to safely create a unique pointer for the first arg.
39
276
  auto TempNode = MDNode::getTemporary(Ctx, None);
40
276
  // Reserve operand 0 for loop id self reference.
41
276
  Args.push_back(TempNode.get());
42
276
43
276
  if (arg0)
44
272
    Args.push_back(arg0);
45
276
  if (arg1)
46
179
    Args.push_back(arg1);
47
276
48
276
  ID = MDNode::get(Ctx, Args);
49
276
  ID->replaceOperandWith(0, ID);
50
276
  return ID;
51
276
}
52
53
92
ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
54
55
92
void ScopAnnotator::buildAliasScopes(Scop &S) {
56
92
  SE = S.getSE();
57
92
58
92
  LLVMContext &Ctx = SE->getContext();
59
92
  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
60
92
61
92
  AliasScopeMap.clear();
62
92
  OtherAliasScopeListMap.clear();
63
92
64
92
  // We are only interested in arrays, but no scalar references. Scalars should
65
92
  // be handled easily by basicaa.
66
92
  SmallVector<ScopArrayInfo *, 10> Arrays;
67
92
  for (ScopArrayInfo *Array : S.arrays())
68
188
    if (Array->isArrayKind())
69
147
      Arrays.push_back(Array);
70
92
71
92
  // The construction of alias scopes is quadratic in the number of arrays
72
92
  // involved. In case of too many arrays, skip the construction of alias
73
92
  // information to avoid quadratic increases in compile time and code size.
74
92
  if (Arrays.size() > MaxArraysInAliasScops)
75
0
    return;
76
92
77
92
  std::string AliasScopeStr = "polly.alias.scope.";
78
147
  for (const ScopArrayInfo *Array : Arrays) {
79
147
    assert(Array->getBasePtr() && "Base pointer must be present");
80
147
    AliasScopeMap[Array->getBasePtr()] =
81
147
        getID(Ctx, AliasScopeDomain,
82
147
              MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
83
147
  }
84
92
85
147
  for (const ScopArrayInfo *Array : Arrays) {
86
147
    MDNode *AliasScopeList = MDNode::get(Ctx, {});
87
323
    for (const auto &AliasScopePair : AliasScopeMap) {
88
323
      if (Array->getBasePtr() == AliasScopePair.first)
89
147
        continue;
90
176
91
176
      Metadata *Args = {AliasScopePair.second};
92
176
      AliasScopeList =
93
176
          MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
94
176
    }
95
147
96
147
    OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
97
147
  }
98
92
}
99
100
76
void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
101
76
102
76
  ActiveLoops.push_back(L);
103
76
  if (!IsParallel)
104
72
    return;
105
4
106
4
  BasicBlock *Header = L->getHeader();
107
4
  MDNode *Id = getID(Header->getContext());
108
4
  assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
109
4
  assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
110
4
  MDNode *Ids = ParallelLoops.empty()
111
4
                    ? Id
112
4
                    : 
MDNode::concatenate(ParallelLoops.back(), Id)0
;
113
76
  ParallelLoops.push_back(Ids);
114
76
}
115
116
76
void ScopAnnotator::popLoop(bool IsParallel) {
117
76
  ActiveLoops.pop_back();
118
76
  if (!IsParallel)
119
72
    return;
120
4
121
4
  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
122
4
  ParallelLoops.pop_back();
123
4
}
124
125
void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
126
76
                                      bool IsLoopVectorizerDisabled) const {
127
76
  MDNode *MData = nullptr;
128
76
129
76
  if (IsLoopVectorizerDisabled) {
130
1
    SmallVector<Metadata *, 3> Args;
131
1
    LLVMContext &Ctx = SE->getContext();
132
1
    Args.push_back(MDString::get(Ctx, "llvm.loop.vectorize.enable"));
133
1
    auto *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
134
1
    Args.push_back(ValueAsMetadata::get(FalseValue));
135
1
    MData = MDNode::concatenate(MData, getID(Ctx, MDNode::get(Ctx, Args)));
136
1
  }
137
76
138
76
  if (IsParallel) {
139
4
    assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
140
4
    MDNode *Ids = ParallelLoops.back();
141
4
    MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
142
4
    MData = MDNode::concatenate(MData, Id);
143
4
  }
144
76
145
76
  B->setMetadata("llvm.loop", MData);
146
76
}
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
621
static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
154
621
  auto MemInst = MemAccInst::dyn_cast(Inst);
155
621
  if (!MemInst)
156
0
    return nullptr;
157
621
158
621
  return MemInst.getPointerOperand();
159
621
}
160
161
void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
162
64
                                        llvm::Value *BasePtr) {
163
64
  auto *PtrSCEV = SE->getSCEV(getMemAccInstPointerOperand(Inst));
164
64
  auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
165
64
166
64
  if (!PtrSCEV)
167
0
    return;
168
64
  auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
169
64
  auto SecondLevelOtherAliasScopeList =
170
64
      SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
171
64
  if (!SecondLevelAliasScope) {
172
32
    auto AliasScope = AliasScopeMap.lookup(BasePtr);
173
32
    if (!AliasScope)
174
0
      return;
175
32
    LLVMContext &Ctx = SE->getContext();
176
32
    SecondLevelAliasScope = getID(
177
32
        Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
178
32
    SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
179
32
    Metadata *Args = {SecondLevelAliasScope};
180
32
    auto SecondLevelBasePtrAliasScopeList =
181
32
        SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
182
32
    SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
183
32
        SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
184
32
    auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
185
32
    SecondLevelOtherAliasScopeList = MDNode::concatenate(
186
32
        OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
187
32
    SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
188
32
  }
189
64
  Inst->setMetadata("alias.scope", SecondLevelAliasScope);
190
64
  Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
191
64
}
192
193
3.67k
void ScopAnnotator::annotate(Instruction *Inst) {
194
3.67k
  if (!Inst->mayReadOrWriteMemory())
195
3.11k
    return;
196
557
197
557
  if (!ParallelLoops.empty())
198
7
    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
199
557
200
557
  // TODO: Use the ScopArrayInfo once available here.
201
557
  if (!AliasScopeDomain)
202
0
    return;
203
557
204
557
  auto *Ptr = getMemAccInstPointerOperand(Inst);
205
557
  if (!Ptr)
206
35
    return;
207
522
208
522
  auto *PtrSCEV = SE->getSCEV(Ptr);
209
522
  auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
210
522
  auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
211
522
212
522
  if (!SU)
213
1
    return;
214
521
215
521
  auto *BasePtr = SU->getValue();
216
521
217
521
  if (!BasePtr)
218
0
    return;
219
521
220
521
  auto AliasScope = AliasScopeMap.lookup(BasePtr);
221
521
222
521
  if (!AliasScope) {
223
160
    BasePtr = AlternativeAliasBases.lookup(BasePtr);
224
160
    if (!BasePtr)
225
146
      return;
226
14
227
14
    AliasScope = AliasScopeMap.lookup(BasePtr);
228
14
    if (!AliasScope)
229
1
      return;
230
374
  }
231
374
232
374
  assert(OtherAliasScopeListMap.count(BasePtr) &&
233
374
         "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
234
374
  auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
235
374
236
374
  if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
237
64
    annotateSecondLevel(Inst, BasePtr);
238
64
    return;
239
64
  }
240
310
241
310
  Inst->setMetadata("alias.scope", AliasScope);
242
310
  Inst->setMetadata("noalias", OtherAliasScopeList);
243
310
}
244
245
1
void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
246
1
  if (!BasePtr)
247
0
    return;
248
1
249
1
  InterIterationAliasFreeBasePtrs.insert(BasePtr);
250
1
}