Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / ARES-6 / Air / allocate_stack.js
1 /*
2  * Copyright (C) 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 "use strict";
26
27 function allocateStack(code)
28 {
29     if (code.frameSize)
30         throw new Error("Frame size already determined");
31     
32     function attemptAssignment(slot, offsetFromFP, otherSlots)
33     {
34         if (offsetFromFP > 0)
35             throw new Error("Expect negative offset");
36         
37         offsetFromFP = -roundUpToMultipleOf(slot.alignment, -offsetFromFP);
38         
39         for (let otherSlot of otherSlots) {
40             if (!otherSlot.offsetFromFP)
41                 continue;
42             let overlap = rangesOverlap(
43                 offsetFromFP,
44                 offsetFromFP + slot.byteSize,
45                 otherSlot.offsetFromFP,
46                 otherSlot.offsetFromFP + otherSlot.byteSize);
47             if (overlap)
48                 return false;
49         }
50         
51         slot.setOffsetFromFP(offsetFromFP);
52         return true;
53     }
54     
55     function assign(slot, otherSlots)
56     {
57         if (attemptAssignment(slot, -slot.byteSize, otherSlots))
58             return;
59         
60         for (let otherSlot of otherSlots) {
61             if (!otherSlot.offsetFromFP)
62                 continue;
63             if (attemptAssignment(slot, otherSlot.offsetFromFP - slot.byteSize, otherSlots))
64                 return;
65         }
66         
67         throw new Error("Assignment failed");
68     }
69     
70     // Allocate all of the escaped slots in order. This is kind of a crazy algorithm to allow for
71     // the possibility of stack slots being assigned frame offsets before we even get here.
72     let assignedEscapedStackSlots = [];
73     let escapedStackSlotsWorklist = [];
74     for (let slot of code.stackSlots) {
75         if (slot.isLocked) {
76             if (slot.offsetFromFP)
77                 assignedEscapedStackSlots.push(slot);
78             else
79                 escapedStackSlotsWorklist.push(slot);
80         } else {
81             if (slot.offsetFromFP)
82                 throw new Error("Offset already assigned");
83         }
84     }
85     
86     // This is a fairly espensive loop, but it's OK because we'll usually only have a handful of
87     // escaped stack slots.
88     while (escapedStackSlotsWorklist.length) {
89         let slot = escapedStackSlotsWorklist.pop();
90         assign(slot, assignedEscapedStackSlots);
91         assignedEscapedStackSlots.push(slot);
92     }
93     
94     // Now we handle the spill slots.
95     let liveness = new Liveness(StackSlot, code);
96     let interference = new Map();
97     for (let slot of code.stackSlots)
98         interference.set(slot, new Set());
99     let slots = [];
100     
101     for (let block of code) {
102         let localCalc = liveness.localCalc(block);
103         
104         function interfere(instIndex)
105         {
106             Inst.forEachDef(
107                 StackSlot, block.get(instIndex), block.get(instIndex + 1),
108                 (slot, role, type, width) => {
109                     if (!slot.isSpill)
110                         return;
111                     
112                     for (let otherSlot of localCalc.liveSet) {
113                         interference.get(slot).add(otherSlot);
114                         interference.get(otherSlot).add(slot);
115                     }
116                 });
117         }
118         
119         for (let instIndex = block.size; instIndex--;) {
120             // Kill dead stores. For simplicity we say that a store is killable if it has only late
121             // defs and those late defs are to things that are dead right now. We only do that
122             // because that's the only kind of dead stack store we will see here.
123             let inst = block.at(instIndex);
124             if (!inst.hasNonArgEffects) {
125                 let ok = true;
126                 inst.forEachArg((arg, role, type, width) => {
127                     if (Arg.isEarlyDef(role)) {
128                         ok = false;
129                         return;
130                     }
131                     if (!Arg.isLateDef(role))
132                         return;
133                     if (!arg.isStack) {
134                         ok = false;
135                         return;
136                     }
137                     
138                     let slot = arg.stackSlot;
139                     if (!slot.isSpill) {
140                         ok = false;
141                         return;
142                     }
143                     
144                     if (localCalc.liveSet.has(slot)) {
145                         ok = false;
146                         return;
147                     }
148                 });
149                 if (ok)
150                     inst.clear();
151             }
152             
153             interfere(instIndex);
154             localCalc.execute(instIndex);
155         }
156         interfere(-1);
157         
158         removeAllMatching(block.insts, inst => inst.opcode == Nop);
159     }
160     
161     // Now we assign stack locations. At its heart this algorithm is just first-fit. For each
162     // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no
163     // overlap with other StackSlots that this overlaps with.
164     for (let slot of code.stackSlots) {
165         if (slot.offsetFromFP)
166             continue;
167         
168         assign(slot, assignedEscapedStackSlots.concat(Array.from(interference.get(slot))));
169     }
170     
171     // Figure out how much stack we're using for stack slots.
172     let frameSizeForStackSlots = 0;
173     for (let slot of code.stackSlots) {
174         frameSizeForStackSlots = Math.max(
175             frameSizeForStackSlots,
176             -slot.offsetFromFP);
177     }
178     
179     frameSizeForStackSlots = roundUpToMultipleOf(stackAlignmentBytes, frameSizeForStackSlots);
180
181     // No we need to deduce how much argument area we need.
182     for (let block of code) {
183         for (let inst of block) {
184             for (let arg of inst.args) {
185                 if (arg.isCallArg) {
186                     // For now, we assume that we use 8 bytes of the call arg. But that's not
187                     // such an awesome assumption.
188                     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150454
189                     if (arg.offset < 0)
190                         throw new Error("Did not expect negative offset for callArg");
191                     code.requestCallArgAreaSize(arg.offset + 8);
192                 }
193             }
194         }
195     }
196     
197     code.setFrameSize(frameSizeForStackSlots + code.callArgAreaSize);
198     
199     // Finally transform the code to use Addrs instead of StackSlots. This is a lossless
200     // transformation since we can search the StackSlots array to figure out which StackSlot any
201     // offset-from-FP refers to.
202
203     // FIXME: This may produce addresses that aren't valid if we end up with a ginormous stack frame.
204     // We would have to scavenge for temporaries if this happened. Fortunately, this case will be
205     // extremely rare so we can do crazy things when it arises.
206     // https://bugs.webkit.org/show_bug.cgi?id=152530
207     
208     let insertionSet = new InsertionSet();
209     for (let block of code) {
210         for (let instIndex = 0; instIndex < block.size; ++instIndex) {
211             let inst = block.at(instIndex);
212             inst.forEachArg((arg, role, type, width) => {
213                 function stackAddr(offset)
214                 {
215                     return Arg.createStackAddr(offset, code.frameSize, width);
216                 }
217                 
218                 switch (arg.kind) {
219                 case Arg.Stack: {
220                     let slot = arg.stackSlot;
221                     if (Arg.isZDef(role)
222                         && slot.isSpill
223                         && slot.byteSize > Arg.bytes(width)) {
224                         // Currently we only handle this simple case because it's the only one
225                         // that arises: ZDef's are only 32-bit right now. So, when we hit these
226                         // assertions it means that we need to implement those other kinds of
227                         // zero fills.
228                         if (slot.byteSize != 8) {
229                             throw new Error(
230                                 `Bad spill slot size for ZDef: ${slot.byteSize}, width is ${width}`);
231                         }
232                         if (width != 32)
233                             throw new Error("Bad width for ZDef");
234                         
235                         insertionSet.insert(
236                             instIndex + 1,
237                             new Inst(
238                                 StoreZero32,
239                                 [stackAddr(arg.offset + 4 + slot.offsetFromFP)]));
240                     }
241                     return stackAddr(arg.offset + slot.offsetFromFP);
242                 }
243                 case Arg.CallArg:
244                     return stackAddr(arg.offset - code.frameSize);
245                 default:
246                     break;
247                 }
248             });
249         }
250         insertionSet.execute(block.insts);
251     }
252 }