Coverage Report

Created: 2019-02-21 13:17

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