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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
// slang-ir-autodiff-loop-analysis.h
#pragma once
#include "slang-ir-autodiff-region.h"
#include "slang-ir-autodiff.h"
#include "slang-ir-dominators.h"
#include "slang-ir-insts.h"
#include "slang-ir.h"
namespace Slang
{
struct SimpleRelation
{
enum Type
{
Any, // Target can be anything (all values are possible)
IntegerRelation, // Target satisfies a simple integer equality/inequality
BoolRelation, // Target satisfies boolean equality
Impossible // Target is impossible (has no possible values)
} type;
enum Comparator
{
LessThanEqual,
GreaterThanEqual,
Equal,
NotEqual
} comparator;
IRIntegerValue integerValue;
bool boolValue;
static SimpleRelation integerRelation(Comparator comparator, IRIntegerValue integerValue)
{
return SimpleRelation{IntegerRelation, comparator, integerValue, false};
}
static SimpleRelation boolRelation(bool boolValue)
{
return SimpleRelation{BoolRelation, Equal, 0, boolValue};
}
static SimpleRelation impossibleRelation()
{
return SimpleRelation{Impossible, Equal, 0, false};
}
static SimpleRelation anyRelation() { return SimpleRelation{Any, Equal, 0, false}; }
bool operator==(const SimpleRelation& other) const
{
switch (type)
{
case Any:
return other.type == Any;
case IntegerRelation:
return other.type == IntegerRelation && comparator == other.comparator &&
integerValue == other.integerValue;
case BoolRelation:
return other.type == BoolRelation && boolValue == other.boolValue;
case Impossible:
return other.type == Impossible;
default:
SLANG_UNREACHABLE("Unhandled relation type");
}
}
bool operator!=(const SimpleRelation& other) const { return !(*this == other); }
SimpleRelation negated() const
{
switch (type)
{
case Any:
return SimpleRelation{Impossible, Equal, 0, false};
case Impossible:
return SimpleRelation{Any, Equal, 0, false};
case BoolRelation:
return SimpleRelation{BoolRelation, Equal, 0, !boolValue};
case IntegerRelation:
switch (comparator)
{
case LessThanEqual:
return SimpleRelation{IntegerRelation, GreaterThanEqual, integerValue + 1, false};
case GreaterThanEqual:
return SimpleRelation{IntegerRelation, LessThanEqual, integerValue - 1, false};
case Equal:
return SimpleRelation{IntegerRelation, NotEqual, integerValue, false};
case NotEqual:
return SimpleRelation{IntegerRelation, Equal, integerValue, false};
default:
SLANG_UNREACHABLE("Unhandled comparator");
}
default:
SLANG_UNREACHABLE("Unhandled relation type");
}
}
HashCode64 getHashCode() const
{
HashCode64 code = Slang::getHashCode(int(type));
switch (type)
{
case IntegerRelation:
code = combineHash(code, Slang::getHashCode(comparator));
code = combineHash(code, Slang::getHashCode(integerValue));
break;
case BoolRelation:
code = combineHash(code, Slang::getHashCode(boolValue));
break;
case Impossible:
case Any:
break;
default:
SLANG_UNREACHABLE("Unhandled relation type");
}
return code;
}
};
struct StatementSet
{
// A conjunction of independent statements (a1 ^ a2 ^ a3 ...)
// - One simple relation per inst.
// - The absence of an entry implies that the inst is unconstrained.
// - The presence of any "Impossible" relation indicates that the entire conjunction is always
// false.
//
Dictionary<IRInst*, SimpleRelation> statements;
// Disjunction of a conjunction of statements (a1 ^ a2 ^ a3 ...) with the current conjunction.
void disjunct(StatementSet other);
// Conjunction of a conjunction of statements (a1 ^ a2 ^ a3 ...) with the current conjunction.
void conjunct(StatementSet other);
// Conjunction of a single statement with the current conjunction.
void conjunct(IRInst* inst, SimpleRelation relation);
void set(IRInst* inst, SimpleRelation relation)
{
if (relation.type == SimpleRelation::Any)
{
if (statements.containsKey(inst))
statements.remove(inst);
return;
}
statements[inst] = relation;
}
bool isTriviallyFalse()
{
for (auto& statement : statements)
{
if (statement.second.type == SimpleRelation::Impossible)
return true;
}
return false;
}
bool isTriviallyTrue() { return statements.getCount() == 0; }
};
// Utility functions.
bool isIntegerConstantValue(IRInst* inst);
bool isBoolConstantValue(IRInst* inst);
IRIntegerValue getConstantIntegerValue(IRInst* inst);
bool getConstantBoolValue(IRInst* inst);
bool doesRelationImply(SimpleRelation relationA, SimpleRelation relationB);
// Try to collect a set of implications for any insts visible in a block,
// subject to the set of predicates.
//
StatementSet collectImplications(
RefPtr<IRDominatorTree> domTree,
IRBlock* block,
StatementSet Predicates);
} // namespace Slang
|
