5171922250f5f4bfea04e7d46ad682ad906e3839
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirGenerate.cpp
1 /*
2  * Copyright (C) 2015-2016 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 "AirAllocateStack.h"
32 #include "AirCode.h"
33 #include "AirDumpAsJS.h"
34 #include "AirEliminateDeadCode.h"
35 #include "AirFixObviousSpills.h"
36 #include "AirFixPartialRegisterStalls.h"
37 #include "AirGenerationContext.h"
38 #include "AirHandleCalleeSaves.h"
39 #include "AirIteratedRegisterCoalescing.h"
40 #include "AirLogRegisterPressure.h"
41 #include "AirLowerAfterRegAlloc.h"
42 #include "AirLowerMacros.h"
43 #include "AirOpcodeUtils.h"
44 #include "AirOptimizeBlockOrder.h"
45 #include "AirReportUsedRegisters.h"
46 #include "AirSimplifyCFG.h"
47 #include "AirSpillEverything.h"
48 #include "AirValidate.h"
49 #include "B3Common.h"
50 #include "B3IndexMap.h"
51 #include "B3Procedure.h"
52 #include "B3TimingScope.h"
53 #include "B3ValueInlines.h"
54 #include "CCallHelpers.h"
55 #include "DisallowMacroScratchRegisterUsage.h"
56 #include "LinkBuffer.h"
57
58 namespace JSC { namespace B3 { namespace Air {
59
60 void prepareForGeneration(Code& code)
61 {
62     TimingScope timingScope("Air::prepareForGeneration");
63     
64     // We don't expect the incoming code to have predecessors computed.
65     code.resetReachability();
66     
67     if (shouldValidateIR())
68         validate(code);
69
70     // If we're doing super verbose dumping, the phase scope of any phase will already do a dump.
71     if (shouldDumpIR(AirMode) && !shouldDumpIRAtEachPhase(AirMode)) {
72         dataLog("Initial air:\n");
73         dataLog(code);
74     }
75
76     lowerMacros(code);
77
78     // This is where we run our optimizations and transformations.
79     // FIXME: Add Air optimizations.
80     // https://bugs.webkit.org/show_bug.cgi?id=150456
81     
82     eliminateDeadCode(code);
83
84     // Register allocation for all the Tmps that do not have a corresponding machine register.
85     // After this phase, every Tmp has a reg.
86     //
87     // For debugging, you can use spillEverything() to put everything to the stack between each Inst.
88     if (Options::airSpillsEverything())
89         spillEverything(code);
90     else
91         iteratedRegisterCoalescing(code);
92
93     if (Options::logAirRegisterPressure()) {
94         dataLog("Register pressure after register allocation:\n");
95         logRegisterPressure(code);
96     }
97
98     // This replaces uses of spill slots with registers or constants if possible. It does this by
99     // minimizing the amount that we perturb the already-chosen register allocation. It may extend
100     // the live ranges of registers though.
101     fixObviousSpills(code);
102
103     lowerAfterRegAlloc(code);
104
105     // Prior to this point the prologue and epilogue is implicit. This makes it explicit. It also
106     // does things like identify which callee-saves we're using and saves them.
107     handleCalleeSaves(code);
108     
109     if (Options::dumpAirAsJSBeforeAllocateStack()) {
110         dataLog("Dumping Air as JS before allocateStack:\n");
111         dumpAsJS(code, WTF::dataFile());
112         dataLog("Air hash: ", code.jsHash(), "\n");
113     }
114
115     // This turns all Stack and CallArg Args into Addr args that use the frame pointer. It does
116     // this by first-fit allocating stack slots. It should be pretty darn close to optimal, so we
117     // shouldn't have to worry about this very much.
118     allocateStack(code);
119     
120     if (Options::dumpAirAfterAllocateStack()) {
121         dataLog("Dumping Air after allocateStack:\n");
122         dataLog(code);
123         dataLog("Air hash: ", code.jsHash(), "\n");
124     }
125
126     // If we coalesced moves then we can unbreak critical edges. This is the main reason for this
127     // phase.
128     simplifyCFG(code);
129
130     // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high
131     // frequency successor is also the fall-through target.
132     optimizeBlockOrder(code);
133
134     // This is needed to satisfy a requirement of B3::StackmapValue.
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     if (shouldValidateIR())
144         validate(code);
145
146     // Do a final dump of Air. Note that we have to do this even if we are doing per-phase dumping,
147     // since the final generation is not a phase.
148     if (shouldDumpIR(AirMode)) {
149         dataLog("Air after ", code.lastPhaseName(), ", before generation:\n");
150         dataLog(code);
151     }
152 }
153
154 void generate(Code& code, CCallHelpers& jit)
155 {
156     TimingScope timingScope("Air::generate");
157
158     DisallowMacroScratchRegisterUsage disallowScratch(jit);
159
160     // And now, we generate code.
161     jit.emitFunctionPrologue();
162     if (code.frameSize())
163         jit.addPtr(CCallHelpers::TrustedImm32(-code.frameSize()), MacroAssembler::stackPointerRegister);
164
165     auto argFor = [&] (const RegisterAtOffset& entry) -> CCallHelpers::Address {
166         return CCallHelpers::Address(GPRInfo::callFrameRegister, entry.offset());
167     };
168     
169     for (const RegisterAtOffset& entry : code.calleeSaveRegisters()) {
170         if (entry.reg().isGPR())
171             jit.storePtr(entry.reg().gpr(), argFor(entry));
172         else
173             jit.storeDouble(entry.reg().fpr(), argFor(entry));
174     }
175
176     GenerationContext context;
177     context.code = &code;
178     context.blockLabels.resize(code.size());
179     for (BasicBlock* block : code) {
180         if (block)
181             context.blockLabels[block] = Box<CCallHelpers::Label>::create();
182     }
183     IndexMap<BasicBlock, CCallHelpers::JumpList> blockJumps(code.size());
184
185     auto link = [&] (CCallHelpers::Jump jump, BasicBlock* target) {
186         if (context.blockLabels[target]->isSet()) {
187             jump.linkTo(*context.blockLabels[target], &jit);
188             return;
189         }
190
191         blockJumps[target].append(jump);
192     };
193
194     PCToOriginMap& pcToOriginMap = code.proc().pcToOriginMap();
195     auto addItem = [&] (Inst& inst) {
196         if (!inst.origin) {
197             pcToOriginMap.appendItem(jit.label(), Origin());
198             return;
199         }
200         pcToOriginMap.appendItem(jit.label(), inst.origin->origin());
201     };
202
203     for (BasicBlock* block : code) {
204         context.currentBlock = block;
205         context.indexInBlock = UINT_MAX;
206         blockJumps[block].link(&jit);
207         CCallHelpers::Label label = jit.label();
208         *context.blockLabels[block] = label;
209         ASSERT(block->size() >= 1);
210         for (unsigned i = 0; i < block->size() - 1; ++i) {
211             context.indexInBlock = i;
212             Inst& inst = block->at(i);
213             addItem(inst);
214             CCallHelpers::Jump jump = inst.generate(jit, context);
215             ASSERT_UNUSED(jump, !jump.isSet());
216         }
217
218         context.indexInBlock = block->size() - 1;
219         
220         if (block->last().opcode == Jump
221             && block->successorBlock(0) == code.findNextBlock(block))
222             continue;
223
224         addItem(block->last());
225
226         if (isReturn(block->last().opcode)) {
227             // We currently don't represent the full prologue/epilogue in Air, so we need to
228             // have this override.
229             if (code.frameSize()) {
230                 for (const RegisterAtOffset& entry : code.calleeSaveRegisters()) {
231                     if (entry.reg().isGPR())
232                         jit.loadPtr(argFor(entry), entry.reg().gpr());
233                     else
234                         jit.loadDouble(argFor(entry), entry.reg().fpr());
235                 }
236                 jit.emitFunctionEpilogue();
237             } else
238                 jit.emitFunctionEpilogueWithEmptyFrame();
239             jit.ret();
240             addItem(block->last());
241             continue;
242         }
243
244         CCallHelpers::Jump jump = block->last().generate(jit, context);
245         // The jump won't be set for patchpoints. It won't be set for Oops because then it won't have
246         // any successors.
247         if (jump.isSet()) {
248             switch (block->numSuccessors()) {
249             case 1:
250                 link(jump, block->successorBlock(0));
251                 break;
252             case 2:
253                 link(jump, block->successorBlock(0));
254                 if (block->successorBlock(1) != code.findNextBlock(block))
255                     link(jit.jump(), block->successorBlock(1));
256                 break;
257             default:
258                 RELEASE_ASSERT_NOT_REACHED();
259                 break;
260             }
261         }
262         addItem(block->last());
263     }
264     
265     context.currentBlock = nullptr;
266     context.indexInBlock = UINT_MAX;
267
268     pcToOriginMap.appendItem(jit.label(), Origin());
269     // FIXME: Make late paths have Origins: https://bugs.webkit.org/show_bug.cgi?id=153689
270     for (auto& latePath : context.latePaths)
271         latePath->run(jit, context);
272     pcToOriginMap.appendItem(jit.label(), Origin());
273 }
274
275 } } } // namespace JSC::B3::Air
276
277 #endif // ENABLE(B3_JIT)