Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include "jit/LoopUnroller.h"
8 :
9 : #include "jit/MIRGraph.h"
10 :
11 : using namespace js;
12 : using namespace js::jit;
13 :
14 : using mozilla::ArrayLength;
15 :
16 : namespace {
17 :
18 0 : struct LoopUnroller
19 : {
20 : typedef HashMap<MDefinition*, MDefinition*,
21 : PointerHasher<MDefinition*, 2>, SystemAllocPolicy> DefinitionMap;
22 :
23 0 : explicit LoopUnroller(MIRGraph& graph)
24 0 : : graph(graph), alloc(graph.alloc()),
25 : header(nullptr), backedge(nullptr),
26 : unrolledHeader(nullptr), unrolledBackedge(nullptr),
27 0 : oldPreheader(nullptr), newPreheader(nullptr)
28 0 : {}
29 :
30 : MIRGraph& graph;
31 : TempAllocator& alloc;
32 :
33 : // Header and body of the original loop.
34 : MBasicBlock* header;
35 : MBasicBlock* backedge;
36 :
37 : // Header and body of the unrolled loop.
38 : MBasicBlock* unrolledHeader;
39 : MBasicBlock* unrolledBackedge;
40 :
41 : // Old and new preheaders. The old preheader starts out associated with the
42 : // original loop, but becomes the preheader of the new loop. The new
43 : // preheader will be given to the original loop.
44 : MBasicBlock* oldPreheader;
45 : MBasicBlock* newPreheader;
46 :
47 : // Map terms in the original loop to terms in the current unrolled iteration.
48 : DefinitionMap unrolledDefinitions;
49 :
50 : MDefinition* getReplacementDefinition(MDefinition* def);
51 : MResumePoint* makeReplacementResumePoint(MBasicBlock* block, MResumePoint* rp);
52 : MOZ_MUST_USE bool makeReplacementInstruction(MInstruction* ins);
53 :
54 : MOZ_MUST_USE bool go(LoopIterationBound* bound);
55 : };
56 :
57 : } // namespace
58 :
59 : MDefinition*
60 0 : LoopUnroller::getReplacementDefinition(MDefinition* def)
61 : {
62 0 : if (def->block()->id() < header->id()) {
63 : // The definition is loop invariant.
64 0 : return def;
65 : }
66 :
67 0 : DefinitionMap::Ptr p = unrolledDefinitions.lookup(def);
68 0 : if (!p) {
69 : // After phi analysis (TypeAnalyzer::replaceRedundantPhi) the resume
70 : // point at the start of a block can contain definitions from within
71 : // the block itself.
72 0 : MOZ_ASSERT(def->isConstant());
73 :
74 0 : MConstant* constant = MConstant::Copy(alloc, def->toConstant());
75 0 : oldPreheader->insertBefore(*oldPreheader->begin(), constant);
76 0 : return constant;
77 : }
78 :
79 0 : return p->value();
80 : }
81 :
82 : bool
83 0 : LoopUnroller::makeReplacementInstruction(MInstruction* ins)
84 : {
85 0 : MDefinitionVector inputs(alloc);
86 0 : for (size_t i = 0; i < ins->numOperands(); i++) {
87 0 : MDefinition* old = ins->getOperand(i);
88 0 : MDefinition* replacement = getReplacementDefinition(old);
89 0 : if (!inputs.append(replacement))
90 0 : return false;
91 : }
92 :
93 0 : MInstruction* clone = ins->clone(alloc, inputs);
94 :
95 0 : unrolledBackedge->add(clone);
96 :
97 0 : if (!unrolledDefinitions.putNew(ins, clone))
98 0 : return false;
99 :
100 0 : if (MResumePoint* old = ins->resumePoint()) {
101 0 : MResumePoint* rp = makeReplacementResumePoint(unrolledBackedge, old);
102 0 : if (!rp)
103 0 : return false;
104 0 : clone->setResumePoint(rp);
105 : }
106 :
107 0 : return true;
108 : }
109 :
110 : MResumePoint*
111 0 : LoopUnroller::makeReplacementResumePoint(MBasicBlock* block, MResumePoint* rp)
112 : {
113 0 : MDefinitionVector inputs(alloc);
114 0 : for (size_t i = 0; i < rp->numOperands(); i++) {
115 0 : MDefinition* old = rp->getOperand(i);
116 0 : MDefinition* replacement = old->isUnused() ? old : getReplacementDefinition(old);
117 0 : if (!inputs.append(replacement))
118 0 : return nullptr;
119 : }
120 :
121 0 : MResumePoint* clone = MResumePoint::New(alloc, block, rp, inputs);
122 0 : if (!clone)
123 0 : return nullptr;
124 :
125 0 : return clone;
126 : }
127 :
128 : bool
129 0 : LoopUnroller::go(LoopIterationBound* bound)
130 : {
131 : // For now we always unroll loops the same number of times.
132 : static const size_t UnrollCount = 10;
133 :
134 0 : JitSpew(JitSpew_Unrolling, "Attempting to unroll loop");
135 :
136 0 : header = bound->header;
137 :
138 : // UCE might have determined this isn't actually a loop.
139 0 : if (!header->isLoopHeader())
140 0 : return true;
141 :
142 0 : backedge = header->backedge();
143 0 : oldPreheader = header->loopPredecessor();
144 :
145 0 : MOZ_ASSERT(oldPreheader->numSuccessors() == 1);
146 :
147 : // Only unroll loops with two blocks: an initial one ending with the
148 : // bound's test, and the body ending with the backedge.
149 0 : MTest* test = bound->test;
150 0 : if (header->lastIns() != test)
151 0 : return true;
152 0 : if (test->ifTrue() == backedge) {
153 0 : if (test->ifFalse()->id() <= backedge->id())
154 0 : return true;
155 0 : } else if (test->ifFalse() == backedge) {
156 0 : if (test->ifTrue()->id() <= backedge->id())
157 0 : return true;
158 : } else {
159 0 : return true;
160 : }
161 0 : if (backedge->numPredecessors() != 1 || backedge->numSuccessors() != 1)
162 0 : return true;
163 0 : MOZ_ASSERT(backedge->phisEmpty());
164 :
165 0 : MBasicBlock* bodyBlocks[] = { header, backedge };
166 :
167 : // All instructions in the header and body must be clonable.
168 0 : for (size_t i = 0; i < ArrayLength(bodyBlocks); i++) {
169 0 : MBasicBlock* block = bodyBlocks[i];
170 0 : for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
171 0 : MInstruction* ins = *iter;
172 0 : if (ins->canClone())
173 0 : continue;
174 0 : if (ins->isTest() || ins->isGoto() || ins->isInterruptCheck())
175 0 : continue;
176 : #ifdef JS_JITSPEW
177 0 : JitSpew(JitSpew_Unrolling, "Aborting: can't clone instruction %s", ins->opName());
178 : #endif
179 0 : return true;
180 : }
181 : }
182 :
183 : // Compute the linear inequality we will use for exiting the unrolled loop:
184 : //
185 : // iterationBound - iterationCount - UnrollCount >= 0
186 : //
187 0 : LinearSum remainingIterationsInequality(bound->boundSum);
188 0 : if (!remainingIterationsInequality.add(bound->currentSum, -1))
189 0 : return true;
190 0 : if (!remainingIterationsInequality.add(-int32_t(UnrollCount)))
191 0 : return true;
192 :
193 : // Terms in the inequality need to be either loop invariant or phis from
194 : // the original header.
195 0 : for (size_t i = 0; i < remainingIterationsInequality.numTerms(); i++) {
196 0 : MDefinition* def = remainingIterationsInequality.term(i).term;
197 0 : if (def->isDiscarded())
198 0 : return true;
199 0 : if (def->block()->id() < header->id())
200 0 : continue;
201 0 : if (def->block() == header && def->isPhi())
202 0 : continue;
203 0 : return true;
204 : }
205 :
206 : // OK, we've checked everything, now unroll the loop.
207 :
208 0 : JitSpew(JitSpew_Unrolling, "Unrolling loop");
209 :
210 : // The old preheader will go before the unrolled loop, and the old loop
211 : // will need a new empty preheader.
212 0 : const CompileInfo& info = oldPreheader->info();
213 0 : if (header->trackedPc()) {
214 0 : unrolledHeader =
215 0 : MBasicBlock::New(graph, nullptr, info,
216 0 : oldPreheader, header->trackedSite(), MBasicBlock::LOOP_HEADER);
217 0 : if (!unrolledHeader)
218 0 : return false;
219 0 : unrolledBackedge =
220 0 : MBasicBlock::New(graph, nullptr, info,
221 0 : unrolledHeader, backedge->trackedSite(), MBasicBlock::NORMAL);
222 0 : if (!unrolledBackedge)
223 0 : return false;
224 0 : newPreheader =
225 0 : MBasicBlock::New(graph, nullptr, info,
226 0 : unrolledHeader, oldPreheader->trackedSite(), MBasicBlock::NORMAL);
227 0 : if (!newPreheader)
228 0 : return false;
229 : } else {
230 0 : unrolledHeader = MBasicBlock::New(graph, info, oldPreheader, MBasicBlock::LOOP_HEADER);
231 0 : if (!unrolledHeader)
232 0 : return false;
233 0 : unrolledBackedge = MBasicBlock::New(graph, info, unrolledHeader, MBasicBlock::NORMAL);
234 0 : if (!unrolledBackedge)
235 0 : return false;
236 0 : newPreheader = MBasicBlock::New(graph, info, unrolledHeader, MBasicBlock::NORMAL);
237 0 : if (!newPreheader)
238 0 : return false;
239 : }
240 :
241 0 : unrolledHeader->discardAllResumePoints();
242 0 : unrolledBackedge->discardAllResumePoints();
243 0 : newPreheader->discardAllResumePoints();
244 :
245 : // Insert new blocks at their RPO position, and update block ids.
246 0 : graph.insertBlockAfter(oldPreheader, unrolledHeader);
247 0 : graph.insertBlockAfter(unrolledHeader, unrolledBackedge);
248 0 : graph.insertBlockAfter(unrolledBackedge, newPreheader);
249 0 : graph.renumberBlocksAfter(oldPreheader);
250 :
251 0 : if (!unrolledDefinitions.init())
252 0 : return false;
253 :
254 : // Add phis to the unrolled loop header which correspond to the phis in the
255 : // original loop header.
256 0 : MOZ_ASSERT(header->getPredecessor(0) == oldPreheader);
257 0 : for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
258 0 : MPhi* old = *iter;
259 0 : MOZ_ASSERT(old->numOperands() == 2);
260 0 : MPhi* phi = MPhi::New(alloc);
261 0 : phi->setResultType(old->type());
262 0 : phi->setResultTypeSet(old->resultTypeSet());
263 0 : phi->setRange(old->range());
264 :
265 0 : unrolledHeader->addPhi(phi);
266 :
267 0 : if (!phi->reserveLength(2))
268 0 : return false;
269 :
270 : // Set the first input for the phi for now. We'll set the second after
271 : // finishing the unroll.
272 0 : phi->addInput(old->getOperand(0));
273 :
274 : // The old phi will now take the value produced by the unrolled loop.
275 0 : old->replaceOperand(0, phi);
276 :
277 0 : if (!unrolledDefinitions.putNew(old, phi))
278 0 : return false;
279 : }
280 :
281 : // The loop condition can bail out on e.g. integer overflow, so make a
282 : // resume point based on the initial resume point of the original header.
283 0 : MResumePoint* headerResumePoint = header->entryResumePoint();
284 0 : if (headerResumePoint) {
285 0 : MResumePoint* rp = makeReplacementResumePoint(unrolledHeader, headerResumePoint);
286 0 : if (!rp)
287 0 : return false;
288 0 : unrolledHeader->setEntryResumePoint(rp);
289 :
290 : // Perform an interrupt check at the start of the unrolled loop.
291 0 : unrolledHeader->add(MInterruptCheck::New(alloc));
292 : }
293 :
294 : // Generate code for the test in the unrolled loop.
295 0 : for (size_t i = 0; i < remainingIterationsInequality.numTerms(); i++) {
296 0 : MDefinition* def = remainingIterationsInequality.term(i).term;
297 0 : MDefinition* replacement = getReplacementDefinition(def);
298 0 : remainingIterationsInequality.replaceTerm(i, replacement);
299 : }
300 0 : MCompare* compare = ConvertLinearInequality(alloc, unrolledHeader, remainingIterationsInequality);
301 0 : MTest* unrolledTest = MTest::New(alloc, compare, unrolledBackedge, newPreheader);
302 0 : unrolledHeader->end(unrolledTest);
303 :
304 : // Make an entry resume point for the unrolled body. The unrolled header
305 : // does not have side effects on stack values, even if the original loop
306 : // header does, so use the same resume point as for the unrolled header.
307 0 : if (headerResumePoint) {
308 0 : MResumePoint* rp = makeReplacementResumePoint(unrolledBackedge, headerResumePoint);
309 0 : if (!rp)
310 0 : return false;
311 0 : unrolledBackedge->setEntryResumePoint(rp);
312 : }
313 :
314 : // Make an entry resume point for the new preheader. There are no
315 : // instructions which use this but some other stuff wants one to be here.
316 0 : if (headerResumePoint) {
317 0 : MResumePoint* rp = makeReplacementResumePoint(newPreheader, headerResumePoint);
318 0 : if (!rp)
319 0 : return false;
320 0 : newPreheader->setEntryResumePoint(rp);
321 : }
322 :
323 : // Generate the unrolled code.
324 : MOZ_ASSERT(UnrollCount > 1);
325 0 : size_t unrollIndex = 0;
326 : while (true) {
327 : // Clone the contents of the original loop into the unrolled loop body.
328 0 : for (size_t i = 0; i < ArrayLength(bodyBlocks); i++) {
329 0 : MBasicBlock* block = bodyBlocks[i];
330 0 : for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
331 0 : MInstruction* ins = *iter;
332 0 : if (ins->canClone()) {
333 0 : if (!makeReplacementInstruction(*iter))
334 0 : return false;
335 : } else {
336 : // Control instructions are handled separately.
337 0 : MOZ_ASSERT(ins->isTest() || ins->isGoto() || ins->isInterruptCheck());
338 : }
339 : }
340 : }
341 :
342 : // Compute the value of each loop header phi after the execution of
343 : // this unrolled iteration.
344 0 : MDefinitionVector phiValues(alloc);
345 0 : MOZ_ASSERT(header->getPredecessor(1) == backedge);
346 0 : for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
347 0 : MPhi* old = *iter;
348 0 : MDefinition* oldInput = old->getOperand(1);
349 0 : if (!phiValues.append(getReplacementDefinition(oldInput)))
350 0 : return false;
351 : }
352 :
353 0 : unrolledDefinitions.clear();
354 :
355 0 : if (unrollIndex == UnrollCount - 1) {
356 : // We're at the end of the last unrolled iteration, set the
357 : // backedge input for the unrolled loop phis.
358 0 : size_t phiIndex = 0;
359 0 : for (MPhiIterator iter(unrolledHeader->phisBegin()); iter != unrolledHeader->phisEnd(); iter++) {
360 0 : MPhi* phi = *iter;
361 0 : phi->addInput(phiValues[phiIndex++]);
362 : }
363 0 : MOZ_ASSERT(phiIndex == phiValues.length());
364 0 : break;
365 : }
366 :
367 : // Update the map for the phis in the next iteration.
368 0 : size_t phiIndex = 0;
369 0 : for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
370 0 : MPhi* old = *iter;
371 0 : if (!unrolledDefinitions.putNew(old, phiValues[phiIndex++]))
372 0 : return false;
373 : }
374 0 : MOZ_ASSERT(phiIndex == phiValues.length());
375 :
376 0 : unrollIndex++;
377 0 : }
378 :
379 0 : MGoto* backedgeJump = MGoto::New(alloc, unrolledHeader);
380 0 : unrolledBackedge->end(backedgeJump);
381 :
382 : // Place the old preheader before the unrolled loop.
383 0 : MOZ_ASSERT(oldPreheader->lastIns()->isGoto());
384 0 : oldPreheader->discardLastIns();
385 0 : oldPreheader->end(MGoto::New(alloc, unrolledHeader));
386 :
387 : // Place the new preheader before the original loop.
388 0 : newPreheader->end(MGoto::New(alloc, header));
389 :
390 : // Cleanup the MIR graph.
391 0 : if (!unrolledHeader->addPredecessorWithoutPhis(unrolledBackedge))
392 0 : return false;
393 0 : header->replacePredecessor(oldPreheader, newPreheader);
394 0 : oldPreheader->setSuccessorWithPhis(unrolledHeader, 0);
395 0 : newPreheader->setSuccessorWithPhis(header, 0);
396 0 : unrolledBackedge->setSuccessorWithPhis(unrolledHeader, 1);
397 0 : return true;
398 : }
399 :
400 : bool
401 0 : jit::UnrollLoops(MIRGraph& graph, const LoopIterationBoundVector& bounds)
402 : {
403 0 : if (bounds.empty())
404 0 : return true;
405 :
406 0 : for (size_t i = 0; i < bounds.length(); i++) {
407 0 : LoopUnroller unroller(graph);
408 0 : if (!unroller.go(bounds[i]))
409 0 : return false;
410 : }
411 :
412 : // The MIR graph is valid, but now has several new blocks. Update or
413 : // recompute previous analysis information for the remaining optimization
414 : // passes.
415 0 : ClearDominatorTree(graph);
416 0 : if (!BuildDominatorTree(graph))
417 0 : return false;
418 :
419 0 : return true;
420 : }
|
