diff options
Diffstat (limited to 'third_party/webkit/PerformanceTests/ARES-6/Air/allocate_stack.js')
| -rw-r--r-- | third_party/webkit/PerformanceTests/ARES-6/Air/allocate_stack.js | 252 |
1 files changed, 252 insertions, 0 deletions
diff --git a/third_party/webkit/PerformanceTests/ARES-6/Air/allocate_stack.js b/third_party/webkit/PerformanceTests/ARES-6/Air/allocate_stack.js new file mode 100644 index 0000000000..bada197bf1 --- /dev/null +++ b/third_party/webkit/PerformanceTests/ARES-6/Air/allocate_stack.js @@ -0,0 +1,252 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +"use strict"; + +function allocateStack(code) +{ + if (code.frameSize) + throw new Error("Frame size already determined"); + + function attemptAssignment(slot, offsetFromFP, otherSlots) + { + if (offsetFromFP > 0) + throw new Error("Expect negative offset"); + + offsetFromFP = -roundUpToMultipleOf(slot.alignment, -offsetFromFP); + + for (let otherSlot of otherSlots) { + if (!otherSlot.offsetFromFP) + continue; + let overlap = rangesOverlap( + offsetFromFP, + offsetFromFP + slot.byteSize, + otherSlot.offsetFromFP, + otherSlot.offsetFromFP + otherSlot.byteSize); + if (overlap) + return false; + } + + slot.setOffsetFromFP(offsetFromFP); + return true; + } + + function assign(slot, otherSlots) + { + if (attemptAssignment(slot, -slot.byteSize, otherSlots)) + return; + + for (let otherSlot of otherSlots) { + if (!otherSlot.offsetFromFP) + continue; + if (attemptAssignment(slot, otherSlot.offsetFromFP - slot.byteSize, otherSlots)) + return; + } + + throw new Error("Assignment failed"); + } + + // Allocate all of the escaped slots in order. This is kind of a crazy algorithm to allow for + // the possibility of stack slots being assigned frame offsets before we even get here. + let assignedEscapedStackSlots = []; + let escapedStackSlotsWorklist = []; + for (let slot of code.stackSlots) { + if (slot.isLocked) { + if (slot.offsetFromFP) + assignedEscapedStackSlots.push(slot); + else + escapedStackSlotsWorklist.push(slot); + } else { + if (slot.offsetFromFP) + throw new Error("Offset already assigned"); + } + } + + // This is a fairly espensive loop, but it's OK because we'll usually only have a handful of + // escaped stack slots. + while (escapedStackSlotsWorklist.length) { + let slot = escapedStackSlotsWorklist.pop(); + assign(slot, assignedEscapedStackSlots); + assignedEscapedStackSlots.push(slot); + } + + // Now we handle the spill slots. + let liveness = new Liveness(StackSlot, code); + let interference = new Map(); + for (let slot of code.stackSlots) + interference.set(slot, new Set()); + let slots = []; + + for (let block of code) { + let localCalc = liveness.localCalc(block); + + function interfere(instIndex) + { + Inst.forEachDef( + StackSlot, block.get(instIndex), block.get(instIndex + 1), + (slot, role, type, width) => { + if (!slot.isSpill) + return; + + for (let otherSlot of localCalc.liveSet) { + interference.get(slot).add(otherSlot); + interference.get(otherSlot).add(slot); + } + }); + } + + for (let instIndex = block.size; instIndex--;) { + // Kill dead stores. For simplicity we say that a store is killable if it has only late + // defs and those late defs are to things that are dead right now. We only do that + // because that's the only kind of dead stack store we will see here. + let inst = block.at(instIndex); + if (!inst.hasNonArgEffects) { + let ok = true; + inst.forEachArg((arg, role, type, width) => { + if (Arg.isEarlyDef(role)) { + ok = false; + return; + } + if (!Arg.isLateDef(role)) + return; + if (!arg.isStack) { + ok = false; + return; + } + + let slot = arg.stackSlot; + if (!slot.isSpill) { + ok = false; + return; + } + + if (localCalc.liveSet.has(slot)) { + ok = false; + return; + } + }); + if (ok) + inst.clear(); + } + + interfere(instIndex); + localCalc.execute(instIndex); + } + interfere(-1); + + removeAllMatching(block.insts, inst => inst.opcode == Nop); + } + + // Now we assign stack locations. At its heart this algorithm is just first-fit. For each + // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no + // overlap with other StackSlots that this overlaps with. + for (let slot of code.stackSlots) { + if (slot.offsetFromFP) + continue; + + assign(slot, assignedEscapedStackSlots.concat(Array.from(interference.get(slot)))); + } + + // Figure out how much stack we're using for stack slots. + let frameSizeForStackSlots = 0; + for (let slot of code.stackSlots) { + frameSizeForStackSlots = Math.max( + frameSizeForStackSlots, + -slot.offsetFromFP); + } + + frameSizeForStackSlots = roundUpToMultipleOf(stackAlignmentBytes, frameSizeForStackSlots); + + // No we need to deduce how much argument area we need. + for (let block of code) { + for (let inst of block) { + for (let arg of inst.args) { + if (arg.isCallArg) { + // For now, we assume that we use 8 bytes of the call arg. But that's not + // such an awesome assumption. + // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150454 + if (arg.offset < 0) + throw new Error("Did not expect negative offset for callArg"); + code.requestCallArgAreaSize(arg.offset + 8); + } + } + } + } + + code.setFrameSize(frameSizeForStackSlots + code.callArgAreaSize); + + // Finally transform the code to use Addrs instead of StackSlots. This is a lossless + // transformation since we can search the StackSlots array to figure out which StackSlot any + // offset-from-FP refers to. + + // FIXME: This may produce addresses that aren't valid if we end up with a ginormous stack frame. + // We would have to scavenge for temporaries if this happened. Fortunately, this case will be + // extremely rare so we can do crazy things when it arises. + // https://bugs.webkit.org/show_bug.cgi?id=152530 + + let insertionSet = new InsertionSet(); + for (let block of code) { + for (let instIndex = 0; instIndex < block.size; ++instIndex) { + let inst = block.at(instIndex); + inst.forEachArg((arg, role, type, width) => { + function stackAddr(offset) + { + return Arg.createStackAddr(offset, code.frameSize, width); + } + + switch (arg.kind) { + case Arg.Stack: { + let slot = arg.stackSlot; + if (Arg.isZDef(role) + && slot.isSpill + && slot.byteSize > Arg.bytes(width)) { + // Currently we only handle this simple case because it's the only one + // that arises: ZDef's are only 32-bit right now. So, when we hit these + // assertions it means that we need to implement those other kinds of + // zero fills. + if (slot.byteSize != 8) { + throw new Error( + `Bad spill slot size for ZDef: ${slot.byteSize}, width is ${width}`); + } + if (width != 32) + throw new Error("Bad width for ZDef"); + + insertionSet.insert( + instIndex + 1, + new Inst( + StoreZero32, + [stackAddr(arg.offset + 4 + slot.offsetFromFP)])); + } + return stackAddr(arg.offset + slot.offsetFromFP); + } + case Arg.CallArg: + return stackAddr(arg.offset - code.frameSize); + default: + break; + } + }); + } + insertionSet.execute(block.insts); + } +} |