5ba671654c603ea6a6f8a70007290c01c2816095
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirSpillEverything.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 "AirSpillEverything.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirCode.h"
32 #include "AirFixSpillSlotZDef.h"
33 #include "AirInsertionSet.h"
34 #include "AirInstInlines.h"
35 #include "AirLiveness.h"
36 #include "AirPhaseScope.h"
37 #include "AirRegisterPriority.h"
38 #include "B3IndexMap.h"
39
40 namespace JSC { namespace B3 { namespace Air {
41
42 void spillEverything(Code& code)
43 {
44     PhaseScope phaseScope(code, "spillEverything");
45
46     // We want to know the set of registers used at every point in every basic block.
47     IndexMap<BasicBlock, Vector<RegisterSet>> usedRegisters(code.size());
48     GPLiveness gpLiveness(code);
49     FPLiveness fpLiveness(code);
50     for (BasicBlock* block : code) {
51         GPLiveness::LocalCalc gpLocalCalc(gpLiveness, block);
52         FPLiveness::LocalCalc fpLocalCalc(fpLiveness, block);
53
54         usedRegisters[block].resize(block->size() + 1);
55
56         auto setUsedRegisters = [&] (unsigned index) {
57             RegisterSet& registerSet = usedRegisters[block][index];
58             for (Tmp tmp : gpLocalCalc.live()) {
59                 if (tmp.isReg())
60                     registerSet.set(tmp.reg());
61             }
62             for (Tmp tmp : fpLocalCalc.live()) {
63                 if (tmp.isReg())
64                     registerSet.set(tmp.reg());
65             }
66
67             // Gotta account for dead assignments to registers. These may happen because the input
68             // code is suboptimal.
69             Inst::forEachDefWithExtraClobberedRegs<Tmp>(
70                 block->get(index - 1), block->get(index),
71                 [&] (const Tmp& tmp, Arg::Role, Arg::Type, Arg::Width) {
72                     if (tmp.isReg())
73                         registerSet.set(tmp.reg());
74                 });
75         };
76
77         for (unsigned instIndex = block->size(); instIndex--;) {
78             setUsedRegisters(instIndex + 1);
79             gpLocalCalc.execute(instIndex);
80             fpLocalCalc.execute(instIndex);
81         }
82         setUsedRegisters(0);
83     }
84
85     // Allocate a stack slot for each tmp.
86     Vector<StackSlot*> allStackSlots[Arg::numTypes];
87     unsigned newStackSlotThreshold = code.stackSlots().size();
88     for (unsigned typeIndex = 0; typeIndex < Arg::numTypes; ++typeIndex) {
89         Vector<StackSlot*>& stackSlots = allStackSlots[typeIndex];
90         Arg::Type type = static_cast<Arg::Type>(typeIndex);
91         stackSlots.resize(code.numTmps(type));
92         for (unsigned tmpIndex = code.numTmps(type); tmpIndex--;)
93             stackSlots[tmpIndex] = code.addStackSlot(8, StackSlotKind::Anonymous);
94     }
95
96     InsertionSet insertionSet(code);
97     for (BasicBlock* block : code) {
98         for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
99             RegisterSet& setBefore = usedRegisters[block][instIndex];
100             RegisterSet& setAfter = usedRegisters[block][instIndex + 1];
101             Inst& inst = block->at(instIndex);
102
103             // First try to spill directly.
104             for (unsigned i = 0; i < inst.args.size(); ++i) {
105                 Arg& arg = inst.args[i];
106
107                 if (arg.isTmp()) {
108                     if (arg.isReg())
109                         continue;
110
111                     if (inst.admitsStack(i)) {
112                         StackSlot* stackSlot = allStackSlots[arg.type()][arg.tmpIndex()];
113                         arg = Arg::stack(stackSlot);
114                         continue;
115                     }
116                 }
117             }
118
119             // Now fall back on spilling using separate Move's to load/store the tmp.
120             inst.forEachTmp(
121                 [&] (Tmp& tmp, Arg::Role role, Arg::Type type, Arg::Width) {
122                     if (tmp.isReg())
123                         return;
124                     
125                     StackSlot* stackSlot = allStackSlots[type][tmp.tmpIndex()];
126                     Arg arg = Arg::stack(stackSlot);
127
128                     // Need to figure out a register to use. How we do that depends on the role.
129                     Reg chosenReg;
130                     switch (role) {
131                     case Arg::Use:
132                     case Arg::ColdUse:
133                     case Arg::EarlyDef:
134                         for (Reg reg : regsInPriorityOrder(type)) {
135                             if (!setBefore.get(reg)) {
136                                 setBefore.set(reg);
137                                 chosenReg = reg;
138                                 break;
139                             }
140                         }
141                         break;
142                     case Arg::Def:
143                     case Arg::ZDef:
144                         for (Reg reg : regsInPriorityOrder(type)) {
145                             if (!setAfter.get(reg)) {
146                                 setAfter.set(reg);
147                                 chosenReg = reg;
148                                 break;
149                             }
150                         }
151                         break;
152                     case Arg::UseDef:
153                     case Arg::UseZDef:
154                     case Arg::LateUse:
155                     case Arg::LateColdUse:
156                     case Arg::Scratch:
157                         for (Reg reg : regsInPriorityOrder(type)) {
158                             if (!setBefore.get(reg) && !setAfter.get(reg)) {
159                                 setAfter.set(reg);
160                                 setBefore.set(reg);
161                                 chosenReg = reg;
162                                 break;
163                             }
164                         }
165                         break;
166                     case Arg::UseAddr:
167                         // We will never UseAddr a Tmp, that doesn't make sense.
168                         RELEASE_ASSERT_NOT_REACHED();
169                         break;
170                     }
171                     RELEASE_ASSERT(chosenReg);
172
173                     tmp = Tmp(chosenReg);
174
175                     Opcode move = type == Arg::GP ? Move : MoveDouble;
176
177                     if (Arg::isAnyUse(role) && role != Arg::Scratch)
178                         insertionSet.insert(instIndex, move, inst.origin, arg, tmp);
179                     if (Arg::isAnyDef(role))
180                         insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
181                 });
182         }
183         insertionSet.execute(block);
184     }
185
186     fixSpillSlotZDef(
187         code,
188         [&] (StackSlot* stackSlot) -> bool {
189             return stackSlot->index() >= newStackSlotThreshold;
190         });
191 }
192
193 } } } // namespace JSC::B3::Air
194
195 #endif // ENABLE(B3_JIT)