Coverage Report

Created: 2017-08-18 19:41

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