Coverage Report

Created: 2017-06-28 17:40

/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
876
                     Metadata *arg1 = nullptr) {
35
876
  MDNode *ID;
36
876
  SmallVector<Metadata *, 3> Args;
37
876
  // Use a temporary node to safely create a unique pointer for the first arg.
38
876
  auto TempNode = MDNode::getTemporary(Ctx, None);
39
876
  // Reserve operand 0 for loop id self reference.
40
876
  Args.push_back(TempNode.get());
41
876
42
876
  if (arg0)
43
860
    Args.push_back(arg0);
44
876
  if (arg1)
45
580
    Args.push_back(arg1);
46
876
47
876
  ID = MDNode::get(Ctx, Args);
48
876
  ID->replaceOperandWith(0, ID);
49
876
  return ID;
50
876
}
51
52
280
ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
53
54
280
void ScopAnnotator::buildAliasScopes(Scop &S) {
55
280
  SE = S.getSE();
56
280
57
280
  LLVMContext &Ctx = SE->getContext();
58
280
  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
59
280
60
280
  AliasScopeMap.clear();
61
280
  OtherAliasScopeListMap.clear();
62
280
63
280
  // The construction of alias scopes is quadratic in the number of arrays
64
280
  // involved. In case of too many arrays, skip the construction of alias
65
280
  // information to avoid quadratic increases in compile time and code size.
66
280
  if (std::distance(S.array_begin(), S.array_end()) > MaxArraysInAliasScops)
67
2
    return;
68
280
69
278
  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
278
77
576
  for (const ScopArrayInfo *Array : S.arrays()) {
78
576
    MDNode *AliasScopeList = MDNode::get(Ctx, {});
79
1.65k
    for (const auto &AliasScopePair : AliasScopeMap) {
80
1.65k
      if (Array->getBasePtr() == AliasScopePair.first)
81
576
        continue;
82
1.65k
83
1.08k
      Metadata *Args = {AliasScopePair.second};
84
1.08k
      AliasScopeList =
85
1.08k
          MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
86
1.08k
    }
87
576
88
576
    OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
89
576
  }
90
278
}
91
92
227
void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
93
227
94
227
  ActiveLoops.push_back(L);
95
227
  if (!IsParallel)
96
211
    return;
97
227
98
16
  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
16
}
107
108
227
void ScopAnnotator::popLoop(bool IsParallel) {
109
227
  ActiveLoops.pop_back();
110
227
  if (!IsParallel)
111
211
    return;
112
227
113
16
  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
114
16
  ParallelLoops.pop_back();
115
16
}
116
117
void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
118
227
                                      bool IsParallel) const {
119
227
  if (!IsParallel)
120
211
    return;
121
227
122
16
  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
16
}
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.46k
static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
134
1.46k
  auto MemInst = MemAccInst::dyn_cast(Inst);
135
1.46k
  if (!MemInst)
136
0
    return nullptr;
137
1.46k
138
1.46k
  return MemInst.getPointerOperand();
139
1.46k
}
140
141
void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
142
8
                                        llvm::Value *BasePtr) {
143
8
  auto *Ptr = getMemAccInstPointerOperand(Inst);
144
8
  if (!Ptr)
145
0
    return;
146
8
  auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(Ptr);
147
8
  auto SecondLevelOtherAliasScopeList =
148
8
      SecondLevelOtherAliasScopeListMap.lookup(Ptr);
149
8
  if (
!SecondLevelAliasScope8
)
{4
150
4
    auto AliasScope = AliasScopeMap.lookup(BasePtr);
151
4
    if (!AliasScope)
152
0
      return;
153
4
    LLVMContext &Ctx = SE->getContext();
154
4
    SecondLevelAliasScope = getID(
155
4
        Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
156
4
    SecondLevelAliasScopeMap[Ptr] = SecondLevelAliasScope;
157
4
    Metadata *Args = {SecondLevelAliasScope};
158
4
    auto SecondLevelBasePtrAliasScopeList =
159
4
        SecondLevelAliasScopeMap.lookup(BasePtr);
160
4
    SecondLevelAliasScopeMap[BasePtr] = MDNode::concatenate(
161
4
        SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
162
4
    auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
163
4
    SecondLevelOtherAliasScopeList = MDNode::concatenate(
164
4
        OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
165
4
    SecondLevelOtherAliasScopeListMap[Ptr] = SecondLevelOtherAliasScopeList;
166
4
  }
167
8
  Inst->setMetadata("alias.scope", SecondLevelAliasScope);
168
8
  Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
169
8
}
170
171
7.96k
void ScopAnnotator::annotate(Instruction *Inst) {
172
7.96k
  if (!Inst->mayReadOrWriteMemory())
173
6.51k
    return;
174
7.96k
175
1.45k
  
if (1.45k
!ParallelLoops.empty()1.45k
)
176
43
    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
177
1.45k
178
1.45k
  // TODO: Use the ScopArrayInfo once available here.
179
1.45k
  if (!AliasScopeDomain)
180
0
    return;
181
1.45k
182
1.45k
  auto *Ptr = getMemAccInstPointerOperand(Inst);
183
1.45k
  if (!Ptr)
184
146
    return;
185
1.45k
186
1.31k
  auto *PtrSCEV = SE->getSCEV(Ptr);
187
1.31k
  auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
188
1.31k
  auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
189
1.31k
190
1.31k
  if (!SU)
191
1
    return;
192
1.31k
193
1.31k
  auto *BasePtr = SU->getValue();
194
1.31k
195
1.31k
  if (!BasePtr)
196
0
    return;
197
1.31k
198
1.31k
  auto AliasScope = AliasScopeMap.lookup(BasePtr);
199
1.31k
200
1.31k
  if (
!AliasScope1.31k
)
{688
201
688
    BasePtr = AlternativeAliasBases.lookup(BasePtr);
202
688
    if (!BasePtr)
203
615
      return;
204
688
205
73
    AliasScope = AliasScopeMap.lookup(BasePtr);
206
73
    if (!AliasScope)
207
14
      return;
208
73
  }
209
1.31k
210
683
  assert(OtherAliasScopeListMap.count(BasePtr) &&
211
683
         "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
212
683
  auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
213
683
214
683
  if (
InterIterationAliasFreeBasePtrs.count(BasePtr)683
)
{8
215
8
    annotateSecondLevel(Inst, BasePtr);
216
8
    return;
217
8
  }
218
683
219
675
  Inst->setMetadata("alias.scope", AliasScope);
220
675
  Inst->setMetadata("noalias", OtherAliasScopeList);
221
675
}
222
223
1
void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
224
1
  if (!BasePtr)
225
0
    return;
226
1
227
1
  InterIterationAliasFreeBasePtrs.insert(BasePtr);
228
1
}