1 | 'use strict';
|
2 |
|
3 | var pipeline = require('json-pipeline');
|
4 | var frontier = require('dominance-frontier');
|
5 | var BitField = require('bitfield.js');
|
6 |
|
7 | function Scheduler(input) {
|
8 | this.input = input;
|
9 | this.output = pipeline.create('dominance');
|
10 |
|
11 |
|
12 | this.blocks = new Array(this.input.nodes.length);
|
13 | for (var i = 0; i < this.blocks.length; i++)
|
14 | this.blocks[i] = null;
|
15 |
|
16 | this.nodes = new Array(this.input.nodes.length);
|
17 | for (var i = 0; i < this.nodes.length; i++)
|
18 | this.nodes[i] = null;
|
19 |
|
20 | this.visited = new BitField(this.input.nodes.length);
|
21 |
|
22 |
|
23 | this.scheduleQueue = [];
|
24 | }
|
25 | module.exports = Scheduler;
|
26 |
|
27 | Scheduler.create = function create(input) {
|
28 | return new Scheduler(input);
|
29 | };
|
30 |
|
31 | Scheduler.prototype.run = function run() {
|
32 |
|
33 | this.constructCFG();
|
34 |
|
35 |
|
36 | frontier.create(this.output).compute();
|
37 |
|
38 |
|
39 | for (var i = 0; i < this.scheduleQueue.length; i++)
|
40 | this.scheduleEarly(this.scheduleQueue[i]);
|
41 |
|
42 | this.visited.wipe();
|
43 |
|
44 | for (var i = 0; i < this.scheduleQueue.length; i++)
|
45 | this.scheduleLate(this.scheduleQueue[i]);
|
46 |
|
47 |
|
48 | for (var i = 0; i < this.input.nodes.length; i++) {
|
49 | var node = this.input.nodes[i];
|
50 |
|
51 |
|
52 | if (this.blocks[node.index] !== null)
|
53 | this.scheduleLate(node);
|
54 | }
|
55 |
|
56 |
|
57 | for (var i = 0; i < this.scheduleQueue.length; i++)
|
58 | this.place(this.scheduleQueue[i]);
|
59 |
|
60 |
|
61 | this.moveControl();
|
62 | this.output.link();
|
63 |
|
64 | return this.output;
|
65 | };
|
66 |
|
67 | Scheduler.prototype.constructCFG = function constructCFG() {
|
68 | var queue = [ this.input.nodes[0] ];
|
69 | var visited = this.visited;
|
70 | while (queue.length !== 0) {
|
71 | var node = queue.pop();
|
72 |
|
73 |
|
74 | if (!visited.set(node.index))
|
75 | continue;
|
76 |
|
77 |
|
78 | var block = this.getBlock(node.index);
|
79 |
|
80 |
|
81 | var last = this.queueControl(block, node);
|
82 |
|
83 |
|
84 | if (last === null)
|
85 | continue;
|
86 |
|
87 |
|
88 | for (var i = 0; i < last.controlUses.length; i += 2) {
|
89 | var child = last.controlUses[i];
|
90 |
|
91 | block.jump(this.getBlock(child.index));
|
92 | queue.push(child);
|
93 | }
|
94 | }
|
95 |
|
96 | return queue;
|
97 | };
|
98 |
|
99 | Scheduler.prototype.getBlock = function getBlock(index) {
|
100 | if (this.blocks[index] !== null)
|
101 | return this.blocks[index];
|
102 |
|
103 | var block = this.output.block();
|
104 | this.blocks[index] = block;
|
105 | return block;
|
106 | };
|
107 |
|
108 | Scheduler.prototype.queueControl = function queueControl(block, node) {
|
109 | var queue = [ node ];
|
110 | var last = null;
|
111 | while (queue.length > 0) {
|
112 | var use = queue.pop();
|
113 |
|
114 | for (var i = 0; i < use.controlUses.length; i += 2) {
|
115 | var subuse = use.controlUses[i];
|
116 | if (subuse.opcode === 'region' || subuse.opcode === 'start')
|
117 | continue;
|
118 | queue.push(subuse);
|
119 | }
|
120 |
|
121 | if (use.opcode === 'region' || use.opcode === 'start')
|
122 | continue;
|
123 |
|
124 | if (use.isControl())
|
125 | last = use;
|
126 |
|
127 |
|
128 | this.scheduleQueue.push(use);
|
129 |
|
130 |
|
131 | this.blocks[use.index] = block;
|
132 | }
|
133 | return last;
|
134 | };
|
135 |
|
136 | Scheduler.prototype.scheduleEarly = function scheduleEarly(node) {
|
137 | var block = this.blocks[node.index];
|
138 |
|
139 |
|
140 | if (block === null)
|
141 | block = this.output.blocks[0];
|
142 |
|
143 | for (var i = 0; i < node.inputs.length; i++) {
|
144 | var input = node.inputs[i];
|
145 | if (this.blocks[input.index] === null)
|
146 | this.scheduleEarly(input);
|
147 |
|
148 | var inputBlock = this.blocks[input.index];
|
149 | if (block.dominates(inputBlock))
|
150 | block = inputBlock;
|
151 | }
|
152 |
|
153 |
|
154 | if (this.blocks[node.index] !== null)
|
155 | return;
|
156 |
|
157 | this.blocks[node.index] = block;
|
158 | };
|
159 |
|
160 | Scheduler.prototype.scheduleLate = function scheduleLate(node) {
|
161 | if (!this.visited.set(node.index))
|
162 | return;
|
163 |
|
164 | for (var i = 0; i < node.uses.length; i += 2) {
|
165 | var use = node.uses[i];
|
166 | var isPinned = use.control.length !== 0;
|
167 | if (isPinned)
|
168 | continue;
|
169 |
|
170 | this.scheduleLate(use);
|
171 | }
|
172 |
|
173 |
|
174 | if (node.control.length !== 0)
|
175 | return;
|
176 |
|
177 |
|
178 | var lca = null;
|
179 | for (var i = 0; i < node.uses.length; i += 2) {
|
180 | var use = node.uses[i];
|
181 | var index = node.uses[i + 1];
|
182 |
|
183 |
|
184 | if (use.opcode === 'ssa:phi') {
|
185 | var controlBlock = this.blocks[use.control[0].index];
|
186 | lca = this.findLCA(lca, controlBlock.predecessors[index]);
|
187 | } else {
|
188 | lca = this.findLCA(lca, this.blocks[use.index]);
|
189 | }
|
190 | }
|
191 |
|
192 |
|
193 | if (lca === null)
|
194 | return;
|
195 |
|
196 | var best = lca;
|
197 | var worst = this.blocks[node.index];
|
198 | while (lca !== worst.parent && lca !== null) {
|
199 | if (lca.loopDepth < best.loopDepth)
|
200 | best = lca;
|
201 | lca = lca.parent;
|
202 | }
|
203 | this.blocks[node.index] = best;
|
204 | };
|
205 |
|
206 | Scheduler.prototype.findLCA = function LCA(lca, block) {
|
207 | if (lca === null)
|
208 | return block;
|
209 |
|
210 |
|
211 | while (lca.dominanceDepth > block.dominanceDepth)
|
212 | lca = lca.parent;
|
213 | while (lca.dominanceDepth < block.dominanceDepth)
|
214 | block = block.parent;
|
215 |
|
216 |
|
217 | while (lca !== block) {
|
218 | lca = lca.parent;
|
219 | block = block.parent;
|
220 | }
|
221 |
|
222 | return lca;
|
223 | };
|
224 |
|
225 | Scheduler.prototype.place = function place(node) {
|
226 |
|
227 | if (this.nodes[node.index] !== null)
|
228 | return;
|
229 |
|
230 | var current = this.output.create(node.opcode);
|
231 | this.nodes[node.index] = current;
|
232 |
|
233 |
|
234 | if (node.opcode !== 'ssa:phi')
|
235 | for (var j = 0; j < node.inputs.length; j++)
|
236 | this.place(node.inputs[j]);
|
237 |
|
238 | var block = this.blocks[node.index];
|
239 | block.add(current);
|
240 |
|
241 |
|
242 |
|
243 | if (node.opcode === 'ssa:phi')
|
244 | for (var j = 0; j < node.inputs.length; j++)
|
245 | this.place(node.inputs[j]);
|
246 |
|
247 |
|
248 | for (var j = 0; j < node.literals.length; j++)
|
249 | current.addLiteral(node.literals[j]);
|
250 |
|
251 | for (var j = 0; j < node.inputs.length; j++)
|
252 | current.addInput(this.nodes[node.inputs[j].index]);
|
253 |
|
254 | if (node.control.length === 0)
|
255 | return;
|
256 |
|
257 | if (node.control.length === 1) {
|
258 | current.setControl(this.getControlNode(node.control[0]));
|
259 | } else if (node.control.length === 2) {
|
260 | current.setControl(this.getControlNode(node.control[0]),
|
261 | this.getControlNode(node.control[1]));
|
262 | }
|
263 | };
|
264 |
|
265 | Scheduler.prototype.getControlNode = function getControlNode(original) {
|
266 | if (original.opcode === 'start' || original.opcode === 'region')
|
267 | return this.blocks[original.index];
|
268 |
|
269 | return this.nodes[original.index];
|
270 | };
|
271 |
|
272 | Scheduler.prototype.moveControl = function moveControl() {
|
273 | for (var i = 0; i < this.output.blocks.length; i++) {
|
274 | var block = this.output.blocks[i];
|
275 |
|
276 | for (var j = block.nodes.length - 1; j >= 0; j--) {
|
277 | var node = block.nodes[j];
|
278 | if (node.opcode !== 'if' &&
|
279 | node.opcode !== 'return' &&
|
280 | node.opcode !== 'jump') {
|
281 | continue;
|
282 | }
|
283 |
|
284 | block.remove(j);
|
285 | block.add(node);
|
286 |
|
287 |
|
288 | break;
|
289 | }
|
290 |
|
291 | block.computeLastControl();
|
292 | }
|
293 | };
|