Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
797
                     Metadata *arg1 = nullptr) {
36
797
  MDNode *ID;
37
797
  SmallVector<Metadata *, 3> Args;
38
797
  // Use a temporary node to safely create a unique pointer for the first arg.
39
797
  auto TempNode = MDNode::getTemporary(Ctx, None);
40
797
  // Reserve operand 0 for loop id self reference.
41
797
  Args.push_back(TempNode.get());
42
797
43
797
  if (arg0)
44
781
    Args.push_back(arg0);
45
797
  if (arg1)
46
491
    Args.push_back(arg1);
47
797
48
797
  ID = MDNode::get(Ctx, Args);
49
797
  ID->replaceOperandWith(0, ID);
50
797
  return ID;
51
797
}
52
53
288
ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
54
55
288
void ScopAnnotator::buildAliasScopes(Scop &S) {
56
288
  SE = S.getSE();
57
288
58
288
  LLVMContext &Ctx = SE->getContext();
59
288
  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
60
288
61
288
  AliasScopeMap.clear();
62
288
  OtherAliasScopeListMap.clear();
63
288
64
288
  // We are only interested in arrays, but no scalar references. Scalars should
65
288
  // be handled easily by basicaa.
66
288
  SmallVector<ScopArrayInfo *, 10> Arrays;
67
288
  for (ScopArrayInfo *Array : S.arrays())
68
620
    
if (620
Array->isArrayKind()620
)
69
477
      Arrays.push_back(Array);
70
288
71
288
  // The construction of alias scopes is quadratic in the number of arrays
72
288
  // involved. In case of too many arrays, skip the construction of alias
73
288
  // information to avoid quadratic increases in compile time and code size.
74
288
  if (Arrays.size() > MaxArraysInAliasScops)
75
2
    return;
76
286
77
286
  std::string AliasScopeStr = "polly.alias.scope.";
78
455
  for (const ScopArrayInfo *Array : Arrays) {
79
455
    assert(Array->getBasePtr() && "Base pointer must be present");
80
455
    AliasScopeMap[Array->getBasePtr()] =
81
455
        getID(Ctx, AliasScopeDomain,
82
455
              MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
83
455
  }
84
286
85
455
  for (const ScopArrayInfo *Array : Arrays) {
86
455
    MDNode *AliasScopeList = MDNode::get(Ctx, {});
87
1.10k
    for (const auto &AliasScopePair : AliasScopeMap) {
88
1.10k
      if (Array->getBasePtr() == AliasScopePair.first)
89
455
        continue;
90
648
91
648
      Metadata *Args = {AliasScopePair.second};
92
648
      AliasScopeList =
93
648
          MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
94
648
    }
95
455
96
455
    OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
97
455
  }
98
288
}
99
100
248
void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
101
248
102
248
  ActiveLoops.push_back(L);
103
248
  if (!IsParallel)
104
232
    return;
105
16
106
16
  BasicBlock *Header = L->getHeader();
107
16
  MDNode *Id = getID(Header->getContext());
108
16
  assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
109
16
  assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
110
16
  MDNode *Ids = ParallelLoops.empty()
111
15
                    ? Id
112
1
                    : MDNode::concatenate(ParallelLoops.back(), Id);
113
248
  ParallelLoops.push_back(Ids);
114
248
}
115
116
248
void ScopAnnotator::popLoop(bool IsParallel) {
117
248
  ActiveLoops.pop_back();
118
248
  if (!IsParallel)
119
232
    return;
120
16
121
248
  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
122
16
  ParallelLoops.pop_back();
123
16
}
124
125
void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
126
248
                                      bool IsLoopVectorizerDisabled) const {
127
248
  MDNode *MData = nullptr;
128
248
129
248
  if (
IsLoopVectorizerDisabled248
) {
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
248
138
248
  if (
IsParallel248
) {
139
16
    assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
140
16
    MDNode *Ids = ParallelLoops.back();
141
16
    MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
142
16
    MData = MDNode::concatenate(MData, Id);
143
16
  }
144
248
145
248
  B->setMetadata("llvm.loop", MData);
146
248
}
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.73k
static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
154
1.73k
  auto MemInst = MemAccInst::dyn_cast(Inst);
155
1.73k
  if (!MemInst)
156
0
    return nullptr;
157
1.73k
158
1.73k
  return MemInst.getPointerOperand();
159
1.73k
}
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 (
!SecondLevelAliasScope72
) {
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.18k
void ScopAnnotator::annotate(Instruction *Inst) {
194
9.18k
  if (!Inst->mayReadOrWriteMemory())
195
7.52k
    return;
196
1.66k
197
1.66k
  
if (1.66k
!ParallelLoops.empty()1.66k
)
198
43
    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
199
1.66k
200
1.66k
  // TODO: Use the ScopArrayInfo once available here.
201
1.66k
  if (!AliasScopeDomain)
202
0
    return;
203
1.66k
204
1.66k
  auto *Ptr = getMemAccInstPointerOperand(Inst);
205
1.66k
  if (!Ptr)
206
151
    return;
207
1.51k
208
1.51k
  auto *PtrSCEV = SE->getSCEV(Ptr);
209
1.51k
  auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
210
1.51k
  auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
211
1.51k
212
1.51k
  if (!SU)
213
1
    return;
214
1.51k
215
1.51k
  auto *BasePtr = SU->getValue();
216
1.51k
217
1.51k
  if (!BasePtr)
218
0
    return;
219
1.51k
220
1.51k
  auto AliasScope = AliasScopeMap.lookup(BasePtr);
221
1.51k
222
1.51k
  if (
!AliasScope1.51k
) {
223
683
    BasePtr = AlternativeAliasBases.lookup(BasePtr);
224
683
    if (!BasePtr)
225
610
      return;
226
73
227
73
    AliasScope = AliasScopeMap.lookup(BasePtr);
228
73
    if (!AliasScope)
229
15
      return;
230
886
  }
231
886
232
1.51k
  assert(OtherAliasScopeListMap.count(BasePtr) &&
233
886
         "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
234
886
  auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
235
886
236
886
  if (
InterIterationAliasFreeBasePtrs.count(BasePtr)886
) {
237
72
    annotateSecondLevel(Inst, BasePtr);
238
72
    return;
239
72
  }
240
814
241
814
  Inst->setMetadata("alias.scope", AliasScope);
242
814
  Inst->setMetadata("noalias", OtherAliasScopeList);
243
814
}
244
245
2
void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
246
2
  if (!BasePtr)
247
0
    return;
248
2
249
2
  InterIterationAliasFreeBasePtrs.insert(BasePtr);
250
2
}