Coverage Report

Created: 2017-10-03 07:32

/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
29.4k
                              Value *Val, bool Virtual) {
36
29.4k
  assert(!isa<StoreInst>(Val) && "a StoreInst cannot be used");
37
29.4k
38
29.4k
  if (isa<BasicBlock>(Val))
39
661
    return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
40
28.7k
41
28.7k
  
if (28.7k
isa<llvm::Constant>(Val) || 28.7k
isa<MetadataAsValue>(Val)21.6k
)
42
7.16k
    return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr);
43
21.6k
44
21.6k
  // Is the value synthesizable? If the user has been pruned
45
21.6k
  // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
46
21.6k
  // We assume synthesizable which practically should have the same effect.
47
21.6k
  auto *SE = S->getSE();
48
21.6k
  if (
SE->isSCEVable(Val->getType())21.6k
) {
49
19.1k
    auto *ScevExpr = SE->getSCEVAtScope(Val, UserScope);
50
19.1k
    if (
!UserStmt || 19.1k
canSynthesize(Val, *UserStmt->getParent(), SE, UserScope)19.1k
)
51
16.3k
      return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr);
52
5.23k
  }
53
5.23k
54
5.23k
  // FIXME: Inconsistency between lookupInvariantEquivClass and
55
5.23k
  // getRequiredInvariantLoads. Querying one of them should be enough.
56
5.23k
  auto &RIL = S->getRequiredInvariantLoads();
57
5.23k
  if (
S->lookupInvariantEquivClass(Val) || 5.23k
RIL.count(dyn_cast<LoadInst>(Val))5.18k
)
58
47
    return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr);
59
5.18k
60
5.18k
  // ReadOnly uses may have MemoryAccesses that we want to associate with the
61
5.18k
  // use. This is why we look for a MemoryAccess here already.
62
5.18k
  MemoryAccess *InputMA = nullptr;
63
5.18k
  if (
UserStmt && 5.18k
Virtual5.18k
)
64
1.30k
    InputMA = UserStmt->lookupValueReadOf(Val);
65
5.18k
66
5.18k
  // Uses are read-only if they have been defined before the SCoP, i.e., they
67
5.18k
  // cannot be written to inside the SCoP. Arguments are defined before any
68
5.18k
  // instructions, hence also before the SCoP. If the user has been pruned
69
5.18k
  // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
70
5.18k
  // neither an intra- nor an inter-use.
71
5.18k
  if (
!UserStmt || 5.18k
isa<Argument>(Val)5.18k
)
72
78
    return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
73
5.11k
74
5.11k
  auto Inst = cast<Instruction>(Val);
75
5.11k
  if (!S->contains(Inst))
76
18
    return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
77
5.09k
78
5.09k
  // A use is inter-statement if either it is defined in another statement, or
79
5.09k
  // there is a MemoryAccess that reads its value that has been written by
80
5.09k
  // another statement.
81
5.09k
  
if (5.09k
InputMA || 5.09k
(!Virtual && 4.89k
UserStmt != S->getStmtFor(Inst)3.81k
))
82
482
    return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA);
83
4.61k
84
4.61k
  return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr);
85
4.61k
}
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
) {
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
) {
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
) {
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
188
static bool isRoot(const Instruction *Inst) {
154
188
  // The store is handled by its MemoryAccess. The load must be reached from the
155
188
  // roots in order to be marked as used.
156
188
  if (
isa<LoadInst>(Inst) || 188
isa<StoreInst>(Inst)143
)
157
157
    return false;
158
31
159
31
  // Terminator instructions (in region statements) are required for control
160
31
  // flow.
161
31
  
if (31
isa<TerminatorInst>(Inst)31
)
162
0
    return true;
163
31
164
31
  // Writes to memory must be honored.
165
31
  
if (31
Inst->mayWriteToMemory()31
)
166
0
    return true;
167
31
168
31
  return false;
169
31
}
170
171
/// Return true for MemoryAccesses that cannot be removed because it represents
172
/// an llvm::Value that is used after the SCoP.
173
8
static bool isEscaping(MemoryAccess *MA) {
174
8
  assert(MA->isOriginalValueKind());
175
8
  Scop *S = MA->getStatement()->getParent();
176
8
  return S->isEscaping(cast<Instruction>(MA->getAccessValue()));
177
8
}
178
179
/// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
180
static void
181
addInstructionRoots(ScopStmt *Stmt,
182
61
                    SmallVectorImpl<VirtualInstruction> &RootInsts) {
183
61
  if (
!Stmt->isBlockStmt()61
) {
184
9
    // In region statements the terminator statement and all statements that
185
9
    // are not in the entry block cannot be eliminated and consequently must
186
9
    // be roots.
187
9
    RootInsts.emplace_back(Stmt,
188
9
                           Stmt->getRegion()->getEntry()->getTerminator());
189
9
    for (BasicBlock *BB : Stmt->getRegion()->blocks())
190
25
      
if (25
Stmt->getRegion()->getEntry() != BB25
)
191
16
        for (Instruction &Inst : *BB)
192
26
          RootInsts.emplace_back(Stmt, &Inst);
193
9
    return;
194
9
  }
195
52
196
52
  for (Instruction *Inst : Stmt->getInstructions())
197
188
    
if (188
isRoot(Inst)188
)
198
0
      RootInsts.emplace_back(Stmt, Inst);
199
61
}
200
201
/// Add non-removable memory accesses in @p Stmt to @p RootInsts.
202
///
203
/// @param Local If true, all writes are assumed to escape. markAndSweep
204
/// algorithms can use this to be applicable to a single ScopStmt only without
205
/// the risk of removing definitions required by other statements.
206
///              If false, only writes for SCoP-escaping values are roots.  This
207
///              is global mode, where such writes must be marked by theirs uses
208
///              in order to be reachable.
209
static void addAccessRoots(ScopStmt *Stmt,
210
                           SmallVectorImpl<MemoryAccess *> &RootAccs,
211
61
                           bool Local) {
212
196
  for (auto *MA : *Stmt) {
213
196
    if (!MA->isWrite())
214
77
      continue;
215
119
216
119
    // Writes to arrays are always used.
217
119
    
if (119
MA->isLatestArrayKind()119
)
218
108
      RootAccs.push_back(MA);
219
119
220
119
    // Values are roots if they are escaping.
221
11
    else 
if (11
MA->isLatestValueKind()11
) {
222
8
      if (
Local || 8
isEscaping(MA)8
)
223
3
        RootAccs.push_back(MA);
224
8
    }
225
11
226
11
    // Exit phis are, by definition, escaping.
227
3
    else 
if (3
MA->isLatestExitPHIKind()3
)
228
0
      RootAccs.push_back(MA);
229
3
230
3
    // phi writes are only roots if we are not visiting the statement
231
3
    // containing the PHINode.
232
3
    else 
if (3
Local && 3
MA->isLatestPHIKind()0
)
233
0
      RootAccs.push_back(MA);
234
196
  }
235
61
}
236
237
/// Determine all instruction and access roots.
238
static void addRoots(ScopStmt *Stmt,
239
                     SmallVectorImpl<VirtualInstruction> &RootInsts,
240
61
                     SmallVectorImpl<MemoryAccess *> &RootAccs, bool Local) {
241
61
  addInstructionRoots(Stmt, RootInsts);
242
61
  addAccessRoots(Stmt, RootAccs, Local);
243
61
}
244
245
/// Mark accesses and instructions as used if they are reachable from a root,
246
/// walking the operand trees.
247
///
248
/// @param S              The SCoP to walk.
249
/// @param LI             The LoopInfo Analysis.
250
/// @param RootInsts      List of root instructions.
251
/// @param RootAccs       List of root accesses.
252
/// @param UsesInsts[out] Receives all reachable instructions, including the
253
/// roots.
254
/// @param UsedAccs[out]  Receives all reachable accesses, including the roots.
255
/// @param OnlyLocal      If non-nullptr, restricts walking to a single
256
/// statement.
257
static void walkReachable(Scop *S, LoopInfo *LI,
258
                          ArrayRef<VirtualInstruction> RootInsts,
259
                          ArrayRef<MemoryAccess *> RootAccs,
260
                          DenseSet<VirtualInstruction> &UsedInsts,
261
                          DenseSet<MemoryAccess *> &UsedAccs,
262
41
                          ScopStmt *OnlyLocal = nullptr) {
263
41
  UsedInsts.clear();
264
41
  UsedAccs.clear();
265
41
266
41
  SmallVector<VirtualInstruction, 32> WorklistInsts;
267
41
  SmallVector<MemoryAccess *, 32> WorklistAccs;
268
41
269
41
  WorklistInsts.append(RootInsts.begin(), RootInsts.end());
270
41
  WorklistAccs.append(RootAccs.begin(), RootAccs.end());
271
41
272
467
  auto AddToWorklist = [&](VirtualUse VUse) {
273
467
    switch (VUse.getKind()) {
274
276
    case VirtualUse::Block:
275
276
    case VirtualUse::Constant:
276
276
    case VirtualUse::Synthesizable:
277
276
    case VirtualUse::Hoisted:
278
276
      break;
279
2
    case VirtualUse::ReadOnly:
280
2
      // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
281
2
      // enabled.
282
2
      if (!VUse.getMemoryAccess())
283
0
        break;
284
2
      
LLVM_FALLTHROUGH2
;
285
15
    case VirtualUse::Inter:
286
15
      assert(VUse.getMemoryAccess());
287
15
      WorklistAccs.push_back(VUse.getMemoryAccess());
288
15
      break;
289
176
    case VirtualUse::Intra:
290
176
      WorklistInsts.emplace_back(VUse.getUser(),
291
176
                                 cast<Instruction>(VUse.getValue()));
292
176
      break;
293
467
    }
294
467
  };
295
41
296
354
  while (
true354
) {
297
354
    // We have two worklists to process: Only when the MemoryAccess worklist is
298
354
    // empty, we process the instruction worklist.
299
354
300
642
    while (
!WorklistAccs.empty()642
) {
301
288
      auto *Acc = WorklistAccs.pop_back_val();
302
288
303
288
      ScopStmt *Stmt = Acc->getStatement();
304
288
      if (
OnlyLocal && 288
Stmt != OnlyLocal0
)
305
0
        continue;
306
288
307
288
      auto Inserted = UsedAccs.insert(Acc);
308
288
      if (!Inserted.second)
309
110
        continue;
310
178
311
178
      
if (178
Acc->isRead()178
) {
312
58
        const ScopArrayInfo *SAI = Acc->getScopArrayInfo();
313
58
314
58
        if (
Acc->isOriginalValueKind()58
) {
315
11
          MemoryAccess *DefAcc = S->getValueDef(SAI);
316
11
317
11
          // Accesses to read-only values do not have a definition.
318
11
          if (DefAcc)
319
7
            WorklistAccs.push_back(S->getValueDef(SAI));
320
11
        }
321
58
322
58
        if (
Acc->isOriginalAnyPHIKind()58
) {
323
6
          auto IncomingMAs = S->getPHIIncomings(SAI);
324
6
          WorklistAccs.append(IncomingMAs.begin(), IncomingMAs.end());
325
6
        }
326
58
      }
327
178
328
178
      if (
Acc->isWrite()178
) {
329
120
        if (Acc->isOriginalValueKind() ||
330
120
            
(Acc->isOriginalArrayKind() && 109
Acc->getAccessValue()102
)) {
331
113
          Loop *Scope = Stmt->getSurroundingLoop();
332
113
          VirtualUse VUse =
333
113
              VirtualUse::create(S, Stmt, Scope, Acc->getAccessValue(), true);
334
113
          AddToWorklist(VUse);
335
113
        }
336
120
337
120
        if (
Acc->isOriginalAnyPHIKind()120
) {
338
8
          for (auto Incoming : Acc->getIncoming()) {
339
8
            VirtualUse VUse = VirtualUse::create(
340
8
                S, Stmt, LI->getLoopFor(Incoming.first), Incoming.second, true);
341
8
            AddToWorklist(VUse);
342
8
          }
343
7
        }
344
120
345
120
        if (Acc->isOriginalArrayKind())
346
102
          WorklistInsts.emplace_back(Stmt, Acc->getAccessInstruction());
347
120
      }
348
288
    }
349
354
350
354
    // If both worklists are empty, stop walking.
351
354
    if (WorklistInsts.empty())
352
41
      break;
353
313
354
313
    VirtualInstruction VInst = WorklistInsts.pop_back_val();
355
313
    ScopStmt *Stmt = VInst.getStmt();
356
313
    Instruction *Inst = VInst.getInstruction();
357
313
358
313
    // Do not process statements other than the local.
359
313
    if (
OnlyLocal && 313
Stmt != OnlyLocal0
)
360
0
      continue;
361
313
362
313
    auto InsertResult = UsedInsts.insert(VInst);
363
313
    if (!InsertResult.second)
364
113
      continue;
365
200
366
200
    // Add all operands to the worklists.
367
200
    PHINode *PHI = dyn_cast<PHINode>(Inst);
368
200
    if (
PHI && 200
PHI->getParent() == Stmt->getEntryBlock()8
) {
369
6
      if (MemoryAccess *PHIRead = Stmt->lookupPHIReadOf(PHI))
370
6
        WorklistAccs.push_back(PHIRead);
371
200
    } else {
372
194
      for (VirtualUse VUse : VInst.operands())
373
346
        AddToWorklist(VUse);
374
194
    }
375
200
376
200
    // If there is an array access, also add its MemoryAccesses to the worklist.
377
200
    const MemoryAccessList *Accs = Stmt->lookupArrayAccessesFor(Inst);
378
200
    if (!Accs)
379
57
      continue;
380
143
381
143
    for (MemoryAccess *Acc : *Accs)
382
143
      WorklistAccs.push_back(Acc);
383
354
  }
384
41
}
385
386
void polly::markReachable(Scop *S, LoopInfo *LI,
387
                          DenseSet<VirtualInstruction> &UsedInsts,
388
                          DenseSet<MemoryAccess *> &UsedAccs,
389
41
                          ScopStmt *OnlyLocal) {
390
41
  SmallVector<VirtualInstruction, 32> RootInsts;
391
41
  SmallVector<MemoryAccess *, 32> RootAccs;
392
41
393
41
  if (
OnlyLocal41
) {
394
0
    addRoots(OnlyLocal, RootInsts, RootAccs, true);
395
41
  } else {
396
41
    for (auto &Stmt : *S)
397
61
      addRoots(&Stmt, RootInsts, RootAccs, false);
398
41
  }
399
41
400
41
  walkReachable(S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal);
401
41
}