Coverage Report

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