B3 -O1 should not allocateStackByGraphColoring
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirGenerate.cpp
1 /*
2  * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "AirGenerate.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirAllocateRegistersAndStackByLinearScan.h"
32 #include "AirAllocateRegistersByGraphColoring.h"
33 #include "AirAllocateStackByGraphColoring.h"
34 #include "AirCode.h"
35 #include "AirEliminateDeadCode.h"
36 #include "AirFixObviousSpills.h"
37 #include "AirFixPartialRegisterStalls.h"
38 #include "AirGenerationContext.h"
39 #include "AirLogRegisterPressure.h"
40 #include "AirLowerAfterRegAlloc.h"
41 #include "AirLowerEntrySwitch.h"
42 #include "AirLowerMacros.h"
43 #include "AirLowerStackArgs.h"
44 #include "AirOpcodeUtils.h"
45 #include "AirOptimizeBlockOrder.h"
46 #include "AirReportUsedRegisters.h"
47 #include "AirSimplifyCFG.h"
48 #include "AirValidate.h"
49 #include "B3Common.h"
50 #include "B3Procedure.h"
51 #include "B3TimingScope.h"
52 #include "B3ValueInlines.h"
53 #include "CCallHelpers.h"
54 #include "DisallowMacroScratchRegisterUsage.h"
55 #include "LinkBuffer.h"
56 #include <wtf/IndexMap.h>
57
58 namespace JSC { namespace B3 { namespace Air {
59
60 void prepareForGeneration(Code& code)
61 {
62     TimingScope timingScope("Air::prepareForGeneration");
63     
64     // If we're doing super verbose dumping, the phase scope of any phase will already do a dump.
65     if (shouldDumpIR(AirMode) && !shouldDumpIRAtEachPhase(AirMode)) {
66         dataLog("Initial air:\n");
67         dataLog(code);
68     }
69     
70     // We don't expect the incoming code to have predecessors computed.
71     code.resetReachability();
72     
73     if (shouldValidateIR())
74         validate(code);
75
76     simplifyCFG(code);
77
78     lowerMacros(code);
79
80     // This is where we run our optimizations and transformations.
81     // FIXME: Add Air optimizations.
82     // https://bugs.webkit.org/show_bug.cgi?id=150456
83     
84     eliminateDeadCode(code);
85
86     if (code.optLevel() <= 1) {
87         // When we're compiling quickly, we do register and stack allocation in one linear scan
88         // phase. It's fast because it computes liveness only once.
89         allocateRegistersAndStackByLinearScan(code);
90         
91         if (Options::logAirRegisterPressure()) {
92             dataLog("Register pressure after register allocation:\n");
93             logRegisterPressure(code);
94         }
95         
96         // We may still need to do post-allocation lowering. Doing it after both register and
97         // stack allocation is less optimal, but it works fine.
98         lowerAfterRegAlloc(code);
99     } else {
100         // NOTE: B3 -O2 generates code that runs 1.5x-2x faster than code generated by -O1.
101         // Most of this performance benefit is from -O2's graph coloring register allocation
102         // and stack allocation pipeline, which you see below.
103         
104         // Register allocation for all the Tmps that do not have a corresponding machine
105         // register. After this phase, every Tmp has a reg.
106         allocateRegistersByGraphColoring(code);
107         
108         if (Options::logAirRegisterPressure()) {
109             dataLog("Register pressure after register allocation:\n");
110             logRegisterPressure(code);
111         }
112         
113         // This replaces uses of spill slots with registers or constants if possible. It
114         // does this by minimizing the amount that we perturb the already-chosen register
115         // allocation. It may extend the live ranges of registers though.
116         fixObviousSpills(code);
117         
118         lowerAfterRegAlloc(code);
119         
120         // This does first-fit allocation of stack slots using an interference graph plus a
121         // bunch of other optimizations.
122         allocateStackByGraphColoring(code);
123     }
124     
125     // This turns all Stack and CallArg Args into Addr args that use the frame pointer.
126     lowerStackArgs(code);
127     
128     // If we coalesced moves then we can unbreak critical edges. This is the main reason for this
129     // phase.
130     simplifyCFG(code);
131
132     // This is needed to satisfy a requirement of B3::StackmapValue. This also removes dead
133     // code. We can avoid running this when certain optimizations are disabled.
134     if (code.optLevel() >= 2 || code.needsUsedRegisters())
135         reportUsedRegisters(code);
136
137     // Attempt to remove false dependencies between instructions created by partial register changes.
138     // This must be executed as late as possible as it depends on the instructions order and register
139     // use. We _must_ run this after reportUsedRegisters(), since that kills variable assignments
140     // that seem dead. Luckily, this phase does not change register liveness, so that's OK.
141     fixPartialRegisterStalls(code);
142     
143     // Actually create entrypoints.
144     lowerEntrySwitch(code);
145     
146     // The control flow graph can be simplified further after we have lowered EntrySwitch.
147     simplifyCFG(code);
148
149     // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high
150     // frequency successor is also the fall-through target.
151     optimizeBlockOrder(code);
152
153     if (shouldValidateIR())
154         validate(code);
155
156     // Do a final dump of Air. Note that we have to do this even if we are doing per-phase dumping,
157     // since the final generation is not a phase.
158     if (shouldDumpIR(AirMode)) {
159         dataLog("Air after ", code.lastPhaseName(), ", before generation:\n");
160         dataLog(code);
161     }
162 }
163
164 void generate(Code& code, CCallHelpers& jit)
165 {
166     TimingScope timingScope("Air::generate");
167
168     DisallowMacroScratchRegisterUsage disallowScratch(jit);
169
170     auto argFor = [&] (const RegisterAtOffset& entry) -> CCallHelpers::Address {
171         return CCallHelpers::Address(GPRInfo::callFrameRegister, entry.offset());
172     };
173     
174     // And now, we generate code.
175     GenerationContext context;
176     context.code = &code;
177     context.blockLabels.resize(code.size());
178     for (BasicBlock* block : code) {
179         if (block)
180             context.blockLabels[block] = Box<CCallHelpers::Label>::create();
181     }
182     IndexMap<BasicBlock*, CCallHelpers::JumpList> blockJumps(code.size());
183
184     auto link = [&] (CCallHelpers::Jump jump, BasicBlock* target) {
185         if (context.blockLabels[target]->isSet()) {
186             jump.linkTo(*context.blockLabels[target], &jit);
187             return;
188         }
189
190         blockJumps[target].append(jump);
191     };
192
193     PCToOriginMap& pcToOriginMap = code.proc().pcToOriginMap();
194     auto addItem = [&] (Inst& inst) {
195         if (!inst.origin) {
196             pcToOriginMap.appendItem(jit.labelIgnoringWatchpoints(), Origin());
197             return;
198         }
199         pcToOriginMap.appendItem(jit.labelIgnoringWatchpoints(), inst.origin->origin());
200     };
201
202     Disassembler* disassembler = code.disassembler();
203
204     for (BasicBlock* block : code) {
205         context.currentBlock = block;
206         context.indexInBlock = UINT_MAX;
207         blockJumps[block].link(&jit);
208         CCallHelpers::Label label = jit.label();
209         *context.blockLabels[block] = label;
210
211         if (disassembler)
212             disassembler->startBlock(block, jit); 
213
214         if (code.isEntrypoint(block)) {
215             if (disassembler)
216                 disassembler->startEntrypoint(jit); 
217
218             jit.emitFunctionPrologue();
219             if (code.frameSize())
220                 jit.addPtr(CCallHelpers::TrustedImm32(-code.frameSize()), MacroAssembler::stackPointerRegister);
221             
222             for (const RegisterAtOffset& entry : code.calleeSaveRegisterAtOffsetList()) {
223                 if (entry.reg().isGPR())
224                     jit.storePtr(entry.reg().gpr(), argFor(entry));
225                 else
226                     jit.storeDouble(entry.reg().fpr(), argFor(entry));
227             }
228
229             if (disassembler)
230                 disassembler->endEntrypoint(jit); 
231         }
232         
233         ASSERT(block->size() >= 1);
234         for (unsigned i = 0; i < block->size() - 1; ++i) {
235             context.indexInBlock = i;
236             Inst& inst = block->at(i);
237             addItem(inst);
238             auto start = jit.labelIgnoringWatchpoints();
239             CCallHelpers::Jump jump = inst.generate(jit, context);
240             ASSERT_UNUSED(jump, !jump.isSet());
241             auto end = jit.labelIgnoringWatchpoints();
242             if (disassembler)
243                 disassembler->addInst(&inst, start, end);
244         }
245
246         context.indexInBlock = block->size() - 1;
247         
248         if (block->last().kind.opcode == Jump
249             && block->successorBlock(0) == code.findNextBlock(block))
250             continue;
251
252         addItem(block->last());
253
254         if (isReturn(block->last().kind.opcode)) {
255             // We currently don't represent the full prologue/epilogue in Air, so we need to
256             // have this override.
257             auto start = jit.labelIgnoringWatchpoints();
258             if (code.frameSize()) {
259                 for (const RegisterAtOffset& entry : code.calleeSaveRegisterAtOffsetList()) {
260                     if (entry.reg().isGPR())
261                         jit.loadPtr(argFor(entry), entry.reg().gpr());
262                     else
263                         jit.loadDouble(argFor(entry), entry.reg().fpr());
264                 }
265                 jit.emitFunctionEpilogue();
266             } else
267                 jit.emitFunctionEpilogueWithEmptyFrame();
268             jit.ret();
269             addItem(block->last());
270             auto end = jit.labelIgnoringWatchpoints();
271             if (disassembler)
272                 disassembler->addInst(&block->last(), start, end);
273             continue;
274         }
275
276         auto start = jit.labelIgnoringWatchpoints();
277         CCallHelpers::Jump jump = block->last().generate(jit, context);
278         auto end = jit.labelIgnoringWatchpoints();
279         if (disassembler)
280             disassembler->addInst(&block->last(), start, end);
281
282         // The jump won't be set for patchpoints. It won't be set for Oops because then it won't have
283         // any successors.
284         if (jump.isSet()) {
285             switch (block->numSuccessors()) {
286             case 1:
287                 link(jump, block->successorBlock(0));
288                 break;
289             case 2:
290                 link(jump, block->successorBlock(0));
291                 if (block->successorBlock(1) != code.findNextBlock(block))
292                     link(jit.jump(), block->successorBlock(1));
293                 break;
294             default:
295                 RELEASE_ASSERT_NOT_REACHED();
296                 break;
297             }
298         }
299         addItem(block->last());
300     }
301     
302     context.currentBlock = nullptr;
303     context.indexInBlock = UINT_MAX;
304     
305     Vector<CCallHelpers::Label> entrypointLabels(code.numEntrypoints());
306     for (unsigned i = code.numEntrypoints(); i--;)
307         entrypointLabels[i] = *context.blockLabels[code.entrypoint(i).block()];
308     code.setEntrypointLabels(WTFMove(entrypointLabels));
309
310     pcToOriginMap.appendItem(jit.label(), Origin());
311     // FIXME: Make late paths have Origins: https://bugs.webkit.org/show_bug.cgi?id=153689
312     if (disassembler)
313         disassembler->startLatePath(jit);
314
315     for (auto& latePath : context.latePaths)
316         latePath->run(jit, context);
317
318     if (disassembler)
319         disassembler->endLatePath(jit);
320     pcToOriginMap.appendItem(jit.labelIgnoringWatchpoints(), Origin());
321 }
322
323 } } } // namespace JSC::B3::Air
324
325 #endif // ENABLE(B3_JIT)