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
|
#include <algorithm>
#include <limits>
#include "src/cfg/cfg.h"
#include "src/dfa/dfa.h"
#include "src/dfa/tcmd.h"
#include "src/regexp/tag.h"
namespace re2c {
/* We have a binary relation on the set of all tags
* and must construct set decomposition into subsets such that
* all tags in the same subset are equivalent.
*
* This problem is isomorphic to partitioning graph into cliques
* (aka finding the 'clique cover' of a graph).
*
* Finding minimal clique cover in arbitrary graph is NP-complete.
* We build just some cover (not necessarily minimal).
* The algorithm takes quadratic (in the number of tags) time.
*/
tagver_t cfg_t::variable_allocation(const cfg_t &cfg, const bool *interf,
tagver_t *ver2new)
{
const size_t END = static_cast<size_t>(std::numeric_limits<tagver_t>::max());
const size_t nver = static_cast<size_t>(cfg.dfa.maxtagver) + 1;
size_t *next = new size_t[nver]; // list of class members
size_t *repr = new size_t[nver]; // maps tag to class representative
size_t rx, ry, x, y, z;
std::fill(next, next + nver, END);
std::fill(repr, repr + nver, END);
// copy coalescing: for each command X = Y, try to merge X and Y
const cfg_bb_t *b = cfg.bblocks, *e = b + cfg.nbbfall;
for (; b < e; ++b) {
for (const tcmd_t *p = b->cmd; p; p = p->next) {
DASSERT(p->lhs >= 0 && p->rhs >= 0);
x = static_cast<size_t>(p->lhs);
y = static_cast<size_t>(p->rhs);
if (y == TAGVER_ZERO || y == x) continue;
rx = repr[x];
ry = repr[y];
if (rx != END) {
if (ry != END) continue;
for (z = rx; z != END; z = next[z]) {
if (interf[z * nver + y]) break;
}
if (z == END) {
repr[y] = rx;
next[y] = next[rx];
next[rx] = y;
}
} else if (ry != END) {
for (z = ry; z != END; z = next[z]) {
if (interf[z * nver + x]) break;
}
if (z == END) {
repr[x] = ry;
next[x] = next[ry];
next[ry] = x;
}
} else if (!interf[x * nver + y]) {
repr[x] = repr[y] = x;
next[x] = y;
}
}
}
// try to merge equivalence classes left after copy coalescing
for (rx = 0; rx < nver; ++rx) {
if (rx != repr[rx]) continue;
for (ry = rx + 1; ry < nver; ++ry) {
if (ry != repr[ry]) continue;
for (x = rx; x != END; x = next[x]) {
for (y = ry; y != END; y = next[y]) {
if (interf[x * nver + y]) break;
}
if (y != END) break;
}
if (x == END) {
for (y = ry;; y = next[y]) {
repr[y] = rx;
if (next[y] == END) {
next[y] = next[rx];
next[rx] = ry;
break;
}
}
}
}
}
// push each remaining tag to any non-interfering class
for (x = 0; x < nver; ++x) {
if (repr[x] != END) continue;
// try all existing classes
for (rx = 0; rx < nver; ++rx) {
if (rx != repr[rx]) continue;
// check interference with class members
for (y = rx; y != END; y = next[y]) {
if (interf[x * nver + y]) break;
}
// no interference; add to class
if (y == END) {
repr[x] = rx;
next[x] = next[rx];
next[rx] = x;
break;
}
}
// make new equivalence class
if (rx == nver) {
repr[x] = x;
}
}
tagver_t maxver = 0;
rx = 0;
// zero-th variable is artificial, skip if it's the only one in its class
if (next[rx] == END) ++rx;
for (; rx < nver; ++rx) {
if (repr[rx] != rx) continue;
++maxver;
for (x = rx; x != END; x = next[x]) {
ver2new[x] = maxver;
}
}
delete[] next;
delete[] repr;
return maxver;
}
} // namespace re2c
|
