8e33c7fe204c84e0598056f52918607f61609595
[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 "AirEliminateDeadCode.h"
34 #include "AirFixPartialRegisterStalls.h"
35 #include "AirGenerationContext.h"
36 #include "AirHandleCalleeSaves.h"
37 #include "AirIteratedRegisterCoalescing.h"
38 #include "AirLowerAfterRegAlloc.h"
39 #include "AirLowerMacros.h"
40 #include "AirOpcodeUtils.h"
41 #include "AirOptimizeBlockOrder.h"
42 #include "AirReportUsedRegisters.h"
43 #include "AirSimplifyCFG.h"
44 #include "AirSpillEverything.h"
45 #include "AirValidate.h"
46 #include "B3Common.h"
47 #include "B3IndexMap.h"
48 #include "B3TimingScope.h"
49 #include "CCallHelpers.h"
50 #include "DisallowMacroScratchRegisterUsage.h"
51
52 namespace JSC { namespace B3 { namespace Air {
53
54 void prepareForGeneration(Code& code)
55 {
56     TimingScope timingScope("Air::prepareForGeneration");
57     
58     // We don't expect the incoming code to have predecessors computed.
59     code.resetReachability();
60     
61     if (shouldValidateIR())
62         validate(code);
63
64     // If we're doing super verbose dumping, the phase scope of any phase will already do a dump.
65     if (shouldDumpIR() && !shouldDumpIRAtEachPhase()) {
66         dataLog("Initial air:\n");
67         dataLog(code);
68     }
69
70     lowerMacros(code);
71
72     // This is where we run our optimizations and transformations.
73     // FIXME: Add Air optimizations.
74     // https://bugs.webkit.org/show_bug.cgi?id=150456
75     
76     eliminateDeadCode(code);
77
78     // Register allocation for all the Tmps that do not have a corresponding machine register.
79     // After this phase, every Tmp has a reg.
80     //
81     // For debugging, you can use spillEverything() to put everything to the stack between each Inst.
82     if (Options::airSpillsEverything())
83         spillEverything(code);
84     else
85         iteratedRegisterCoalescing(code);
86
87     lowerAfterRegAlloc(code);
88
89     // Prior to this point the prologue and epilogue is implicit. This makes it explicit. It also
90     // does things like identify which callee-saves we're using and saves them.
91     handleCalleeSaves(code);
92
93     // This turns all Stack and CallArg Args into Addr args that use the frame pointer. It does
94     // this by first-fit allocating stack slots. It should be pretty darn close to optimal, so we
95     // shouldn't have to worry about this very much.
96     allocateStack(code);
97
98     // If we coalesced moves then we can unbreak critical edges. This is the main reason for this
99     // phase.
100     simplifyCFG(code);
101
102     // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high
103     // frequency successor is also the fall-through target.
104     optimizeBlockOrder(code);
105
106     // Attempt to remove false dependencies between instructions created by partial register changes.
107     // This must be executed as late as possible as it depends on the instructions order and register use.
108     fixPartialRegisterStalls(code);
109
110     // This is needed to satisfy a requirement of B3::StackmapValue.
111     reportUsedRegisters(code);
112
113     if (shouldValidateIR())
114         validate(code);
115
116     // Do a final dump of Air. Note that we have to do this even if we are doing per-phase dumping,
117     // since the final generation is not a phase.
118     if (shouldDumpIR()) {
119         dataLog("Air after ", code.lastPhaseName(), ", before generation:\n");
120         dataLog(code);
121     }
122 }
123
124 void generate(Code& code, CCallHelpers& jit)
125 {
126     TimingScope timingScope("Air::generate");
127
128     DisallowMacroScratchRegisterUsage disallowScratch(jit);
129
130     // And now, we generate code.
131     jit.emitFunctionPrologue();
132     if (code.frameSize())
133         jit.addPtr(CCallHelpers::TrustedImm32(-code.frameSize()), MacroAssembler::stackPointerRegister);
134
135     GenerationContext context;
136     context.code = &code;
137     IndexMap<BasicBlock, CCallHelpers::Label> blockLabels(code.size());
138     IndexMap<BasicBlock, CCallHelpers::JumpList> blockJumps(code.size());
139
140     auto link = [&] (CCallHelpers::Jump jump, BasicBlock* target) {
141         if (blockLabels[target].isSet()) {
142             jump.linkTo(blockLabels[target], &jit);
143             return;
144         }
145
146         blockJumps[target].append(jump);
147     };
148
149     for (BasicBlock* block : code) {
150         blockJumps[block].link(&jit);
151         blockLabels[block] = jit.label();
152         ASSERT(block->size() >= 1);
153         for (unsigned i = 0; i < block->size() - 1; ++i) {
154             CCallHelpers::Jump jump = block->at(i).generate(jit, context);
155             ASSERT_UNUSED(jump, !jump.isSet());
156         }
157
158         if (block->last().opcode == Jump
159             && block->successorBlock(0) == code.findNextBlock(block))
160             continue;
161
162         if (isReturn(block->last().opcode)) {
163             // We currently don't represent the full prologue/epilogue in Air, so we need to
164             // have this override.
165             if (code.frameSize())
166                 jit.emitFunctionEpilogue();
167             else
168                 jit.emitFunctionEpilogueWithEmptyFrame();
169             jit.ret();
170             continue;
171         }
172
173         CCallHelpers::Jump jump = block->last().generate(jit, context);
174         switch (block->numSuccessors()) {
175         case 0:
176             ASSERT(!jump.isSet());
177             break;
178         case 1:
179             link(jump, block->successorBlock(0));
180             break;
181         case 2:
182             link(jump, block->successorBlock(0));
183             if (block->successorBlock(1) != code.findNextBlock(block))
184                 link(jit.jump(), block->successorBlock(1));
185             break;
186         default:
187             RELEASE_ASSERT_NOT_REACHED();
188             break;
189         }
190     }
191
192     for (auto& latePath : context.latePaths)
193         latePath->run(jit, context);
194 }
195
196 } } } // namespace JSC::B3::Air
197
198 #endif // ENABLE(B3_JIT)