Coverage Report

Created: 2018-06-19 22:08

/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
810
                     Metadata *arg1 = nullptr) {
36
810
  MDNode *ID;
37
810
  SmallVector<Metadata *, 3> Args;
38
810
  // Use a temporary node to safely create a unique pointer for the first arg.
39
810
  auto TempNode = MDNode::getTemporary(Ctx, None);
40
810
  // Reserve operand 0 for loop id self reference.
41
810
  Args.push_back(TempNode.get());
42
810
43
810
  if (arg0)
44
793
    Args.push_back(arg0);
45
810
  if (arg1)
46
499
    Args.push_back(arg1);
47
810
48
810
  ID = MDNode::get(Ctx, Args);
49
810
  ID->replaceOperandWith(0, ID);
50
810
  return ID;
51
810
}
52
53
292
ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
54
55
292
void ScopAnnotator::buildAliasScopes(Scop &S) {
56
292
  SE = S.getSE();
57
292
58
292
  LLVMContext &Ctx = SE->getContext();
59
292
  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
60
292
61
292
  AliasScopeMap.clear();
62
292
  OtherAliasScopeListMap.clear();
63
292
64
292
  // We are only interested in arrays, but no scalar references. Scalars should
65
292
  // be handled easily by basicaa.
66
292
  SmallVector<ScopArrayInfo *, 10> Arrays;
67
292
  for (ScopArrayInfo *Array : S.arrays())
68
632
    if (Array->isArrayKind())
69
485
      Arrays.push_back(Array);
70
292
71
292
  // The construction of alias scopes is quadratic in the number of arrays
72
292
  // involved. In case of too many arrays, skip the construction of alias
73
292
  // information to avoid quadratic increases in compile time and code size.
74
292
  if (Arrays.size() > MaxArraysInAliasScops)
75
2
    return;
76
290
77
290
  std::string AliasScopeStr = "polly.alias.scope.";
78
463
  for (const ScopArrayInfo *Array : Arrays) {
79
463
    assert(Array->getBasePtr() && "Base pointer must be present");
80
463
    AliasScopeMap[Array->getBasePtr()] =
81
463
        getID(Ctx, AliasScopeDomain,
82
463
              MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
83
463
  }
84
290
85
463
  for (const ScopArrayInfo *Array : Arrays) {
86
463
    MDNode *AliasScopeList = MDNode::get(Ctx, {});
87
1.11k
    for (const auto &AliasScopePair : AliasScopeMap) {
88
1.11k
      if (Array->getBasePtr() == AliasScopePair.first)
89
463
        continue;
90
656
91
656
      Metadata *Args = {AliasScopePair.second};
92
656
      AliasScopeList =
93
656
          MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
94
656
    }
95
463
96
463
    OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
97
463
  }
98
290
}
99
100
251
void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
101
251
102
251
  ActiveLoops.push_back(L);
103
251
  if (!IsParallel)
104
234
    return;
105
17
106
17
  BasicBlock *Header = L->getHeader();
107
17
  MDNode *Id = getID(Header->getContext());
108
17
  assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
109
17
  assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
110
17
  MDNode *Ids = ParallelLoops.empty()
111
17
                    ? 
Id16
112
17
                    : 
MDNode::concatenate(ParallelLoops.back(), Id)1
;
113
17
  ParallelLoops.push_back(Ids);
114
17
}
115
116
251
void ScopAnnotator::popLoop(bool IsParallel) {
117
251
  ActiveLoops.pop_back();
118
251
  if (!IsParallel)
119
234
    return;
120
17
121
17
  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
122
17
  ParallelLoops.pop_back();
123
17
}
124
125
void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
126
251
                                      bool IsLoopVectorizerDisabled) const {
127
251
  MDNode *MData = nullptr;
128
251
129
251
  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
251
138
251
  if (IsParallel) {
139
17
    assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
140
17
    MDNode *Ids = ParallelLoops.back();
141
17
    MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
142
17
    MData = MDNode::concatenate(MData, Id);
143
17
  }
144
251
145
251
  B->setMetadata("llvm.loop", MData);
146
251
}
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.59k
static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
154
1.59k
  auto MemInst = MemAccInst::dyn_cast(Inst);
155
1.59k
  if (!MemInst)
156
0
    return nullptr;
157
1.59k
158
1.59k
  return MemInst.getPointerOperand();
159
1.59k
}
160
161
void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
162
72
                                        llvm::Value *BasePtr) {
163
72
  auto *PtrSCEV = SE->getSCEV(getMemAccInstPointerOperand(Inst));
164
72
  auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
165
72
166
72
  if (!PtrSCEV)
167
0
    return;
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
9.08k
void ScopAnnotator::annotate(Instruction *Inst) {
194
9.08k
  if (!Inst->mayReadOrWriteMemory())
195
7.40k
    return;
196
1.68k
197
1.68k
  if (!ParallelLoops.empty())
198
45
    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
199
1.68k
200
1.68k
  // TODO: Use the ScopArrayInfo once available here.
201
1.68k
  if (!AliasScopeDomain)
202
0
    return;
203
1.68k
204
1.68k
  // Do not apply annotations on memory operations that take more than one
205
1.68k
  // pointer. It would be ambiguous to which pointer the annotation applies.
206
1.68k
  // FIXME: How can we specify annotations for all pointer arguments?
207
1.68k
  if (isa<CallInst>(Inst) && 
!isa<MemSetInst>(Inst)162
)
208
161
    return;
209
1.52k
210
1.52k
  auto *Ptr = getMemAccInstPointerOperand(Inst);
211
1.52k
  if (!Ptr)
212
0
    return;
213
1.52k
214
1.52k
  auto *PtrSCEV = SE->getSCEV(Ptr);
215
1.52k
  auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
216
1.52k
  auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
217
1.52k
218
1.52k
  if (!SU)
219
0
    return;
220
1.52k
221
1.52k
  auto *BasePtr = SU->getValue();
222
1.52k
223
1.52k
  if (!BasePtr)
224
0
    return;
225
1.52k
226
1.52k
  auto AliasScope = AliasScopeMap.lookup(BasePtr);
227
1.52k
228
1.52k
  if (!AliasScope) {
229
695
    BasePtr = AlternativeAliasBases.lookup(BasePtr);
230
695
    if (!BasePtr)
231
622
      return;
232
73
233
73
    AliasScope = AliasScopeMap.lookup(BasePtr);
234
73
    if (!AliasScope)
235
15
      return;
236
883
  }
237
883
238
883
  assert(OtherAliasScopeListMap.count(BasePtr) &&
239
883
         "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
240
883
  auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
241
883
242
883
  if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
243
72
    annotateSecondLevel(Inst, BasePtr);
244
72
    return;
245
72
  }
246
811
247
811
  Inst->setMetadata("alias.scope", AliasScope);
248
811
  Inst->setMetadata("noalias", OtherAliasScopeList);
249
811
}
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
}