Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Support/VirtualInstruction.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
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
// Tools for determining which instructions are within a statement and the
11
// nature of their operands.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "polly/Support/VirtualInstruction.h"
16
#include "polly/Support/SCEVValidator.h"
17
18
using namespace polly;
19
using namespace llvm;
20
21
VirtualUse VirtualUse ::create(Scop *S, const Use &U, LoopInfo *LI,
22
0
                               bool Virtual) {
23
0
  auto *UserBB = getUseBlock(U);
24
0
  Instruction *UI = dyn_cast<Instruction>(U.getUser());
25
0
  ScopStmt *UserStmt = nullptr;
26
0
  if (PHINode *PHI = dyn_cast<PHINode>(UI))
27
0
    UserStmt = S->getLastStmtFor(PHI->getIncomingBlock(U));
28
0
  else
29
0
    UserStmt = S->getStmtFor(UI);
30
0
  auto *UserScope = LI->getLoopFor(UserBB);
31
0
  return create(S, UserStmt, UserScope, U.get(), Virtual);
32
0
}
33
34
VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
35
28.3k
                              Value *Val, bool Virtual) {
36
28.3k
  assert(!isa<StoreInst>(Val) && "a StoreInst cannot be used");
37
28.3k
38
28.3k
  if (isa<BasicBlock>(Val))
39
615
    return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
40
28.3k
41
27.7k
  
if (27.7k
isa<llvm::Constant>(Val) || 27.7k
isa<MetadataAsValue>(Val)20.8k
)
42
6.86k
    return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr);
43
27.7k
44
27.7k
  // Is the value synthesizable? If the user has been pruned
45
27.7k
  // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
46
27.7k
  // We assume synthesizable which practically should have the same effect.
47
27.7k
  auto *SE = S->getSE();
48
20.8k
  if (
SE->isSCEVable(Val->getType())20.8k
)
{18.5k
49
18.5k
    auto *ScevExpr = SE->getSCEVAtScope(Val, UserScope);
50
18.5k
    if (
!UserStmt || 18.5k
canSynthesize(Val, *UserStmt->getParent(), SE, UserScope)18.5k
)
51
15.7k
      return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr);
52
20.8k
  }
53
20.8k
54
20.8k
  // FIXME: Inconsistency between lookupInvariantEquivClass and
55
20.8k
  // getRequiredInvariantLoads. Querying one of them should be enough.
56
20.8k
  auto &RIL = S->getRequiredInvariantLoads();
57
5.03k
  if (
S->lookupInvariantEquivClass(Val) || 5.03k
RIL.count(dyn_cast<LoadInst>(Val))4.99k
)
58
47
    return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr);
59
5.03k
60
5.03k
  // ReadOnly uses may have MemoryAccesses that we want to associate with the
61
5.03k
  // use. This is why we look for a MemoryAccess here already.
62
5.03k
  MemoryAccess *InputMA = nullptr;
63
4.99k
  if (
UserStmt && 4.99k
Virtual4.99k
)
64
1.24k
    InputMA = UserStmt->lookupValueReadOf(Val);
65
4.99k
66
4.99k
  // Uses are read-only if they have been defined before the SCoP, i.e., they
67
4.99k
  // cannot be written to inside the SCoP. Arguments are defined before any
68
4.99k
  // instructions, hence also before the SCoP. If the user has been pruned
69
4.99k
  // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
70
4.99k
  // neither an intra- nor an inter-use.
71
4.99k
  if (
!UserStmt || 4.99k
isa<Argument>(Val)4.99k
)
72
78
    return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
73
4.99k
74
4.99k
  auto Inst = cast<Instruction>(Val);
75
4.91k
  if (!S->contains(Inst))
76
18
    return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
77
4.91k
78
4.91k
  // A use is inter-statement if either it is defined in another statement, or
79
4.91k
  // there is a MemoryAccess that reads its value that has been written by
80
4.91k
  // another statement.
81
4.89k
  
if (4.89k
InputMA || 4.89k
(!Virtual && 4.73k
!UserStmt->represents(Inst->getParent())3.68k
))
82
434
    return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA);
83
4.89k
84
4.46k
  return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr);
85
28.3k
}
86
87
0
void VirtualUse::print(raw_ostream &OS, bool Reproducible) const {
88
0
  OS << "User: [" << User->getBaseName() << "] ";
89
0
  switch (Kind) {
90
0
  case VirtualUse::Constant:
91
0
    OS << "Constant Op:";
92
0
    break;
93
0
  case VirtualUse::Block:
94
0
    OS << "BasicBlock Op:";
95
0
    break;
96
0
  case VirtualUse::Synthesizable:
97
0
    OS << "Synthesizable Op:";
98
0
    break;
99
0
  case VirtualUse::Hoisted:
100
0
    OS << "Hoisted load Op:";
101
0
    break;
102
0
  case VirtualUse::ReadOnly:
103
0
    OS << "Read-Only Op:";
104
0
    break;
105
0
  case VirtualUse::Intra:
106
0
    OS << "Intra Op:";
107
0
    break;
108
0
  case VirtualUse::Inter:
109
0
    OS << "Inter Op:";
110
0
    break;
111
0
  }
112
0
113
0
  
if (0
Val0
)
{0
114
0
    OS << ' ';
115
0
    if (Reproducible)
116
0
      OS << '"' << Val->getName() << '"';
117
0
    else
118
0
      Val->print(OS, true);
119
0
  }
120
0
  if (
ScevExpr0
)
{0
121
0
    OS << ' ';
122
0
    ScevExpr->print(OS);
123
0
  }
124
0
  if (
InputMA && 0
!Reproducible0
)
125
0
    OS << ' ' << InputMA;
126
0
}
127
128
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
129
LLVM_DUMP_METHOD void VirtualUse::dump() const {
130
  print(errs(), false);
131
  errs() << '\n';
132
}
133
#endif
134
135
0
void VirtualInstruction::print(raw_ostream &OS, bool Reproducible) const {
136
0
  if (
!Stmt || 0
!Inst0
)
{0
137
0
    OS << "[null VirtualInstruction]";
138
0
    return;
139
0
  }
140
0
141
0
  OS << "[" << Stmt->getBaseName() << "]";
142
0
  Inst->print(OS, !Reproducible);
143
0
}
144
145
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
146
LLVM_DUMP_METHOD void VirtualInstruction::dump() const {
147
  print(errs(), false);
148
  errs() << '\n';
149
}
150
#endif
151
152
/// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
153
186
static bool isRoot(const Instruction *Inst) {
154
186
  // The store is handled by its MemoryAccess. The load must be reached from the
155
186
  // roots in order to be marked as used.
156
186
  if (
isa<LoadInst>(Inst) || 186
isa<StoreInst>(Inst)141
)
157
156
    return false;
158
186
159
186
  // Terminator instructions (in region statements) are required for control
160
186
  // flow.
161
30
  
if (30
isa<TerminatorInst>(Inst)30
)
162
0
    return true;
163
30
164
30
  // Writes to memory must be honored.
165
30
  
if (30
Inst->mayWriteToMemory()30
)
166
0
    return true;
167
30
168
30
  return false;
169
186
}
170
171
/// Return true for MemoryAccesses that cannot be removed because it represents
172
/// an llvm::Value that is used after the SCoP.
173
7
static bool isEscaping(MemoryAccess *MA) {
174
7
  assert(MA->isOriginalValueKind());
175
7
  Scop *S = MA->getStatement()->getParent();
176
7
  return S->isEscaping(cast<Instruction>(MA->getAccessValue()));
177
7
}
178
179
/// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
180
static void
181
addInstructionRoots(ScopStmt *Stmt,
182
57
                    SmallVectorImpl<VirtualInstruction> &RootInsts) {
183
57
  // For region statements we must keep all instructions because we do not
184
57
  // support removing instructions from region statements.
185
57
  if (
!Stmt->isBlockStmt()57
)
{7
186
7
    for (auto *BB : Stmt->getRegion()->blocks())
187
21
      for (Instruction &Inst : *BB)
188
43
        RootInsts.emplace_back(Stmt, &Inst);
189
7
    return;
190
57
  }
191
57
192
57
  for (Instruction *Inst : Stmt->getInstructions())
193
186
    
if (186
isRoot(Inst)186
)
194
0
      RootInsts.emplace_back(Stmt, Inst);
195
57
}
196
197
/// Add non-removable memory accesses in @p Stmt to @p RootInsts.
198
///
199
/// @param Local If true, all writes are assumed to escape. markAndSweep
200
/// algorithms can use this to be applicable to a single ScopStmt only without
201
/// the risk of removing definitions required by other statements.
202
///              If false, only writes for SCoP-escaping values are roots.  This
203
///              is global mode, where such writes must be marked by theirs uses
204
///              in order to be reachable.
205
static void addAccessRoots(ScopStmt *Stmt,
206
                           SmallVectorImpl<MemoryAccess *> &RootAccs,
207
57
                           bool Local) {
208
189
  for (auto *MA : *Stmt) {
209
189
    if (!MA->isWrite())
210
74
      continue;
211
189
212
189
    // Writes to arrays are always used.
213
115
    
if (115
MA->isLatestArrayKind()115
)
214
105
      RootAccs.push_back(MA);
215
115
216
115
    // Values are roots if they are escaping.
217
10
    else 
if (10
MA->isLatestValueKind()10
)
{7
218
7
      if (
Local || 7
isEscaping(MA)7
)
219
3
        RootAccs.push_back(MA);
220
10
    }
221
10
222
10
    // Exit phis are, by definition, escaping.
223
3
    else 
if (3
MA->isLatestExitPHIKind()3
)
224
0
      RootAccs.push_back(MA);
225
3
226
3
    // phi writes are only roots if we are not visiting the statement
227
3
    // containing the PHINode.
228
3
    else 
if (3
Local && 3
MA->isLatestPHIKind()0
)
229
0
      RootAccs.push_back(MA);
230
115
  }
231
57
}
232
233
/// Determine all instruction and access roots.
234
static void addRoots(ScopStmt *Stmt,
235
                     SmallVectorImpl<VirtualInstruction> &RootInsts,
236
57
                     SmallVectorImpl<MemoryAccess *> &RootAccs, bool Local) {
237
57
  addInstructionRoots(Stmt, RootInsts);
238
57
  addAccessRoots(Stmt, RootAccs, Local);
239
57
}
240
241
/// Mark accesses and instructions as used if they are reachable from a root,
242
/// walking the operand trees.
243
///
244
/// @param S              The SCoP to walk.
245
/// @param LI             The LoopInfo Analysis.
246
/// @param RootInsts      List of root instructions.
247
/// @param RootAccs       List of root accesses.
248
/// @param UsesInsts[out] Receives all reachable instructions, including the
249
/// roots.
250
/// @param UsedAccs[out]  Receives all reachable accesses, including the roots.
251
/// @param OnlyLocal      If non-nullptr, restricts walking to a single
252
/// statement.
253
static void walkReachable(Scop *S, LoopInfo *LI,
254
                          ArrayRef<VirtualInstruction> RootInsts,
255
                          ArrayRef<MemoryAccess *> RootAccs,
256
                          DenseSet<VirtualInstruction> &UsedInsts,
257
                          DenseSet<MemoryAccess *> &UsedAccs,
258
38
                          ScopStmt *OnlyLocal = nullptr) {
259
38
  UsedInsts.clear();
260
38
  UsedAccs.clear();
261
38
262
38
  SmallVector<VirtualInstruction, 32> WorklistInsts;
263
38
  SmallVector<MemoryAccess *, 32> WorklistAccs;
264
38
265
38
  WorklistInsts.append(RootInsts.begin(), RootInsts.end());
266
38
  WorklistAccs.append(RootAccs.begin(), RootAccs.end());
267
38
268
451
  auto AddToWorklist = [&](VirtualUse VUse) {
269
451
    switch (VUse.getKind()) {
270
451
    case VirtualUse::Block:
271
264
    case VirtualUse::Constant:
272
264
    case VirtualUse::Synthesizable:
273
264
    case VirtualUse::Hoisted:
274
264
      break;
275
264
    case VirtualUse::ReadOnly:
276
2
      // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
277
2
      // enabled.
278
2
      if (!VUse.getMemoryAccess())
279
0
        break;
280
2
      
LLVM_FALLTHROUGH2
;2
281
13
    case VirtualUse::Inter:
282
13
      assert(VUse.getMemoryAccess());
283
13
      WorklistAccs.push_back(VUse.getMemoryAccess());
284
13
      break;
285
174
    case VirtualUse::Intra:
286
174
      WorklistInsts.emplace_back(VUse.getUser(),
287
174
                                 cast<Instruction>(VUse.getValue()));
288
451
      break;
289
451
    }
290
451
  };
291
38
292
354
  while (
true354
)
{354
293
354
    // We have two worklists to process: Only when the MemoryAccess worklist is
294
354
    // empty, we process the instruction worklist.
295
354
296
634
    while (
!WorklistAccs.empty()634
)
{280
297
280
      auto *Acc = WorklistAccs.pop_back_val();
298
280
299
280
      ScopStmt *Stmt = Acc->getStatement();
300
280
      if (
OnlyLocal && 280
Stmt != OnlyLocal0
)
301
0
        continue;
302
280
303
280
      auto Inserted = UsedAccs.insert(Acc);
304
280
      if (!Inserted.second)
305
106
        continue;
306
280
307
174
      
if (174
Acc->isRead()174
)
{58
308
58
        const ScopArrayInfo *SAI = Acc->getScopArrayInfo();
309
58
310
58
        if (
Acc->isOriginalValueKind()58
)
{10
311
10
          MemoryAccess *DefAcc = S->getValueDef(SAI);
312
10
313
10
          // Accesses to read-only values do not have a definition.
314
10
          if (DefAcc)
315
6
            WorklistAccs.push_back(S->getValueDef(SAI));
316
58
        }
317
58
318
58
        if (
Acc->isOriginalAnyPHIKind()58
)
{6
319
6
          auto IncomingMAs = S->getPHIIncomings(SAI);
320
6
          WorklistAccs.append(IncomingMAs.begin(), IncomingMAs.end());
321
58
        }
322
174
      }
323
174
324
174
      if (
Acc->isWrite()174
)
{116
325
116
        if (Acc->isOriginalValueKind() ||
326
116
            
(Acc->isOriginalArrayKind() && 106
Acc->getAccessValue()99
))
{109
327
109
          Loop *Scope = Stmt->getSurroundingLoop();
328
109
          VirtualUse VUse =
329
109
              VirtualUse::create(S, Stmt, Scope, Acc->getAccessValue(), true);
330
109
          AddToWorklist(VUse);
331
116
        }
332
116
333
116
        if (
Acc->isOriginalAnyPHIKind()116
)
{7
334
8
          for (auto Incoming : Acc->getIncoming()) {
335
8
            VirtualUse VUse = VirtualUse::create(
336
8
                S, Stmt, LI->getLoopFor(Incoming.first), Incoming.second, true);
337
8
            AddToWorklist(VUse);
338
8
          }
339
116
        }
340
116
341
116
        if (Acc->isOriginalArrayKind())
342
99
          WorklistInsts.emplace_back(Stmt, Acc->getAccessInstruction());
343
174
      }
344
354
    }
345
354
346
354
    // If both worklists are empty, stop walking.
347
354
    if (WorklistInsts.empty())
348
38
      break;
349
354
350
354
    VirtualInstruction VInst = WorklistInsts.pop_back_val();
351
316
    ScopStmt *Stmt = VInst.getStmt();
352
316
    Instruction *Inst = VInst.getInstruction();
353
316
354
316
    // Do not process statements other than the local.
355
316
    if (
OnlyLocal && 316
Stmt != OnlyLocal0
)
356
0
      continue;
357
316
358
316
    auto InsertResult = UsedInsts.insert(VInst);
359
316
    if (!InsertResult.second)
360
122
      continue;
361
316
362
316
    // Add all operands to the worklists.
363
316
    PHINode *PHI = dyn_cast<PHINode>(Inst);
364
194
    if (
PHI && 194
PHI->getParent() == Stmt->getEntryBlock()8
)
{6
365
6
      if (MemoryAccess *PHIRead = Stmt->lookupPHIReadOf(PHI))
366
6
        WorklistAccs.push_back(PHIRead);
367
194
    } else {
368
188
      for (VirtualUse VUse : VInst.operands())
369
334
        AddToWorklist(VUse);
370
194
    }
371
194
372
194
    // If there is an array access, also add its MemoryAccesses to the worklist.
373
194
    const MemoryAccessList *Accs = Stmt->lookupArrayAccessesFor(Inst);
374
194
    if (!Accs)
375
53
      continue;
376
194
377
194
    for (MemoryAccess *Acc : *Accs)
378
141
      WorklistAccs.push_back(Acc);
379
141
  }
380
38
}
381
382
void polly::markReachable(Scop *S, LoopInfo *LI,
383
                          DenseSet<VirtualInstruction> &UsedInsts,
384
                          DenseSet<MemoryAccess *> &UsedAccs,
385
38
                          ScopStmt *OnlyLocal) {
386
38
  SmallVector<VirtualInstruction, 32> RootInsts;
387
38
  SmallVector<MemoryAccess *, 32> RootAccs;
388
38
389
38
  if (
OnlyLocal38
)
{0
390
0
    addRoots(OnlyLocal, RootInsts, RootAccs, true);
391
38
  } else {
392
38
    for (auto &Stmt : *S)
393
57
      addRoots(&Stmt, RootInsts, RootAccs, false);
394
38
  }
395
38
396
38
  walkReachable(S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal);
397
38
}