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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include "slang-ir-check-recursion.h"
#include "slang-ir-util.h"
namespace Slang
{
bool checkTypeRecursionImpl(
HashSet<IRInst*>& checkedTypes,
HashSet<IRInst*>& stack,
IRInst* type,
IRInst* field,
DiagnosticSink* sink)
{
auto visitElementType = [&](IRInst* elementType, IRInst* field) -> bool
{
if (!stack.add(elementType))
{
sink->diagnose(field ? field : type, Diagnostics::recursiveType, type);
return false;
}
if (checkedTypes.add(elementType))
checkTypeRecursionImpl(checkedTypes, stack, elementType, field, sink);
stack.remove(elementType);
return true;
};
if (auto arrayType = as<IRArrayTypeBase>(type))
{
return visitElementType(arrayType->getElementType(), field);
}
else if (auto structType = as<IRStructType>(type))
{
for (auto sfield : structType->getFields())
if (!visitElementType(sfield->getFieldType(), sfield))
return false;
}
return true;
}
void checkTypeRecursion(HashSet<IRInst*>& checkedTypes, IRInst* type, DiagnosticSink* sink)
{
HashSet<IRInst*> stack;
if (checkedTypes.add(type))
{
stack.add(type);
checkTypeRecursionImpl(checkedTypes, stack, type, nullptr, sink);
}
}
void checkForRecursiveTypes(IRModule* module, DiagnosticSink* sink)
{
HashSet<IRInst*> checkedTypes;
for (auto globalInst : module->getGlobalInsts())
{
switch (globalInst->getOp())
{
case kIROp_StructType:
{
checkTypeRecursion(checkedTypes, globalInst, sink);
}
break;
default:
break;
}
}
}
bool checkFunctionRecursionImpl(
HashSet<IRFunc*>& checkedFuncs,
HashSet<IRFunc*>& callStack,
IRFunc* func,
DiagnosticSink* sink)
{
for (auto block : func->getBlocks())
{
for (auto inst : block->getChildren())
{
auto callInst = as<IRCall>(inst);
if (!callInst)
continue;
auto callee = as<IRFunc>(callInst->getCallee());
if (!callee)
continue;
if (!callStack.add(callee))
{
sink->diagnose(callInst, Diagnostics::unsupportedRecursion, callee);
return false;
}
if (checkedFuncs.add(callee))
checkFunctionRecursionImpl(checkedFuncs, callStack, callee, sink);
callStack.remove(callee);
}
}
return true;
}
void checkFunctionRecursion(HashSet<IRFunc*>& checkedFuncs, IRFunc* func, DiagnosticSink* sink)
{
HashSet<IRFunc*> callStack;
if (checkedFuncs.add(func))
{
callStack.add(func);
checkFunctionRecursionImpl(checkedFuncs, callStack, func, sink);
}
}
void checkForRecursiveFunctions(TargetRequest* target, IRModule* module, DiagnosticSink* sink)
{
HashSet<IRFunc*> checkedFuncsForRecursionDetection;
for (auto globalInst : module->getGlobalInsts())
{
switch (globalInst->getOp())
{
case kIROp_Func:
if (!isCPUTarget(target))
checkFunctionRecursion(
checkedFuncsForRecursionDetection,
as<IRFunc>(globalInst),
sink);
break;
default:
break;
}
}
}
} // namespace Slang
|
