blob: 1a4aa271b1d9107306a8a104c3439b0a8c6d8717 (
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
|
#include "slang-ir-reachability.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;
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::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);
}
}
|
