blob: 629e751c80722ae636222b4b4f5a57b3ab1eca82 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include "slang-ir-reachability.h"
#include "slang-ir-insts.h"
#include "slang-ir-util.h"
namespace Slang
{
// Computes whether block1 can reach block2.
// A block is considered not reachable from itself unless there is a backedge in the CFG.
ReachabilityContext::ReachabilityContext(IRGlobalValueWithCode* code)
{
int id = 0;
for (auto block : code->getBlocks())
{
mapBlockToId[block] = id++;
allBlocks.add(block);
}
sourceBlocks.setCount(allBlocks.getCount());
for (auto& srcBlock : sourceBlocks)
srcBlock.resizeAndClear(allBlocks.getCount());
if (allBlocks.getCount() == 0)
return;
List<IRBlock*> workList;
List<IRBlock*> pendingWorkList;
workList.add(allBlocks[0]);
while (workList.getCount())
{
pendingWorkList.clear();
for (Index i = 0; i < workList.getCount(); i++)
{
auto src = workList[i];
auto srcId = mapBlockToId.getValue(src);
for (auto successor : src->getSuccessors())
{
auto successorId = mapBlockToId.getValue(successor);
auto& blockSet = sourceBlocks[successorId];
bool changed = false;
if (!blockSet.contains(srcId))
{
blockSet.add(srcId);
changed = true;
}
if (!blockSet.contains(sourceBlocks[srcId]))
{
blockSet.unionWith(sourceBlocks[srcId]);
changed = true;
}
if (changed)
pendingWorkList.add(successor);
}
}
workList.swapWith(pendingWorkList);
}
}
bool ReachabilityContext::isInstReachable(IRInst* from, IRInst* to)
{
// If inst1 and inst2 are in the same block,
// we test if inst2 appears after inst1.
if (getBlock(from) == getBlock(to))
{
for (auto inst = from->getNextInst(); inst; inst = inst->getNextInst())
{
if (inst == to)
return true;
}
}
return isBlockReachable(getBlock(from), getBlock(to));
}
bool ReachabilityContext::isBlockReachable(IRBlock* from, IRBlock* to)
{
if (!from)
return false;
if (!to)
return false;
int* fromId = mapBlockToId.tryGetValue(from);
int* toId = mapBlockToId.tryGetValue(to);
if (!fromId || !toId)
return true;
return sourceBlocks[*toId].contains(*fromId);
}
} // namespace Slang
|
