diff options
Diffstat (limited to 'Source/JavaScriptCore/b3/air/AirAllocateStack.cpp')
| -rw-r--r-- | Source/JavaScriptCore/b3/air/AirAllocateStack.cpp | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp b/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp new file mode 100644 index 000000000..de9297f26 --- /dev/null +++ b/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp @@ -0,0 +1,308 @@ +/* + * Copyright (C) 2015-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. + */ + +#include "config.h" +#include "AirAllocateStack.h" + +#if ENABLE(B3_JIT) + +#include "AirArgInlines.h" +#include "AirCode.h" +#include "AirInsertionSet.h" +#include "AirInstInlines.h" +#include "AirLiveness.h" +#include "AirPhaseScope.h" +#include "StackAlignment.h" +#include <wtf/ListDump.h> + +namespace JSC { namespace B3 { namespace Air { + +namespace { + +const bool verbose = false; + +bool attemptAssignment( + StackSlot* slot, intptr_t offsetFromFP, const Vector<StackSlot*>& otherSlots) +{ + if (verbose) + dataLog("Attempting to assign ", pointerDump(slot), " to ", offsetFromFP, " with interference ", pointerListDump(otherSlots), "\n"); + + // Need to align it to the slot's desired alignment. + offsetFromFP = -WTF::roundUpToMultipleOf(slot->alignment(), -offsetFromFP); + + for (StackSlot* otherSlot : otherSlots) { + if (!otherSlot->offsetFromFP()) + continue; + bool overlap = WTF::rangesOverlap( + offsetFromFP, + offsetFromFP + static_cast<intptr_t>(slot->byteSize()), + otherSlot->offsetFromFP(), + otherSlot->offsetFromFP() + static_cast<intptr_t>(otherSlot->byteSize())); + if (overlap) + return false; + } + + if (verbose) + dataLog("Assigned ", pointerDump(slot), " to ", offsetFromFP, "\n"); + slot->setOffsetFromFP(offsetFromFP); + return true; +} + +void assign(StackSlot* slot, const Vector<StackSlot*>& otherSlots) +{ + if (verbose) + dataLog("Attempting to assign ", pointerDump(slot), " with interference ", pointerListDump(otherSlots), "\n"); + + if (attemptAssignment(slot, -static_cast<intptr_t>(slot->byteSize()), otherSlots)) + return; + + for (StackSlot* otherSlot : otherSlots) { + if (!otherSlot->offsetFromFP()) + continue; + bool didAssign = attemptAssignment( + slot, otherSlot->offsetFromFP() - static_cast<intptr_t>(slot->byteSize()), otherSlots); + if (didAssign) + return; + } + + RELEASE_ASSERT_NOT_REACHED(); +} + +} // anonymous namespace + +void allocateStack(Code& code) +{ + PhaseScope phaseScope(code, "allocateStack"); + + // 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. + ASSERT(!code.frameSize()); + Vector<StackSlot*> assignedEscapedStackSlots; + Vector<StackSlot*> escapedStackSlotsWorklist; + for (StackSlot* slot : code.stackSlots()) { + if (slot->isLocked()) { + if (slot->offsetFromFP()) + assignedEscapedStackSlots.append(slot); + else + escapedStackSlotsWorklist.append(slot); + } else { + // It would be super strange to have an unlocked stack slot that has an offset already. + ASSERT(!slot->offsetFromFP()); + } + } + // This is a fairly expensive loop, but it's OK because we'll usually only have a handful of + // escaped stack slots. + while (!escapedStackSlotsWorklist.isEmpty()) { + StackSlot* slot = escapedStackSlotsWorklist.takeLast(); + assign(slot, assignedEscapedStackSlots); + assignedEscapedStackSlots.append(slot); + } + + // Now we handle the spill slots. + StackSlotLiveness liveness(code); + IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size()); + Vector<StackSlot*> slots; + + for (BasicBlock* block : code) { + StackSlotLiveness::LocalCalc localCalc(liveness, block); + + auto interfere = [&] (unsigned instIndex) { + if (verbose) + dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n"); + + Inst::forEachDef<Arg>( + block->get(instIndex), block->get(instIndex + 1), + [&] (Arg& arg, Arg::Role, Arg::Type, Arg::Width) { + if (!arg.isStack()) + return; + StackSlot* slot = arg.stackSlot(); + if (slot->kind() != StackSlotKind::Spill) + return; + + for (StackSlot* otherSlot : localCalc.live()) { + interference[slot].add(otherSlot); + interference[otherSlot].add(slot); + } + }); + }; + + for (unsigned instIndex = block->size(); instIndex--;) { + if (verbose) + dataLog("Analyzing: ", block->at(instIndex), "\n"); + + // 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. + Inst& inst = block->at(instIndex); + if (!inst.hasNonArgEffects()) { + bool ok = true; + inst.forEachArg( + [&] (Arg& arg, Arg::Role role, Arg::Type, Arg::Width) { + if (Arg::isEarlyDef(role)) { + ok = false; + return; + } + if (!Arg::isLateDef(role)) + return; + if (!arg.isStack()) { + ok = false; + return; + } + StackSlot* slot = arg.stackSlot(); + if (slot->kind() != StackSlotKind::Spill) { + ok = false; + return; + } + + if (localCalc.isLive(slot)) { + ok = false; + return; + } + }); + if (ok) + inst = Inst(); + } + + interfere(instIndex); + localCalc.execute(instIndex); + } + interfere(-1); + + block->insts().removeAllMatching( + [&] (const Inst& inst) -> bool { + return !inst; + }); + } + + if (verbose) { + for (StackSlot* slot : code.stackSlots()) + dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n"); + } + + // 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. + Vector<StackSlot*> otherSlots = assignedEscapedStackSlots; + for (StackSlot* slot : code.stackSlots()) { + if (slot->offsetFromFP()) { + // Already assigned an offset. + continue; + } + + HashSet<StackSlot*>& interferingSlots = interference[slot]; + otherSlots.resize(assignedEscapedStackSlots.size()); + otherSlots.resize(assignedEscapedStackSlots.size() + interferingSlots.size()); + unsigned nextIndex = assignedEscapedStackSlots.size(); + for (StackSlot* otherSlot : interferingSlots) + otherSlots[nextIndex++] = otherSlot; + + assign(slot, otherSlots); + } + + // Figure out how much stack we're using for stack slots. + unsigned frameSizeForStackSlots = 0; + for (StackSlot* slot : code.stackSlots()) { + frameSizeForStackSlots = std::max( + frameSizeForStackSlots, + static_cast<unsigned>(-slot->offsetFromFP())); + } + + frameSizeForStackSlots = WTF::roundUpToMultipleOf(stackAlignmentBytes(), frameSizeForStackSlots); + + // Now we need to deduce how much argument area we need. + for (BasicBlock* block : code) { + for (Inst& inst : *block) { + for (Arg& arg : 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 + ASSERT(arg.offset() >= 0); + code.requestCallArgAreaSizeInBytes(arg.offset() + 8); + } + } + } + } + + code.setFrameSize(frameSizeForStackSlots + code.callArgAreaSizeInBytes()); + + // Finally, transform the code to use Addr's instead of StackSlot's. 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 + + InsertionSet insertionSet(code); + for (BasicBlock* block : code) { + for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) { + Inst& inst = block->at(instIndex); + inst.forEachArg( + [&] (Arg& arg, Arg::Role role, Arg::Type, Arg::Width width) { + auto stackAddr = [&] (int32_t offset) -> Arg { + return Arg::stackAddr(offset, code.frameSize(), width); + }; + + switch (arg.kind()) { + case Arg::Stack: { + StackSlot* slot = arg.stackSlot(); + if (Arg::isZDef(role) + && slot->kind() == StackSlotKind::Spill + && 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. + RELEASE_ASSERT(slot->byteSize() == 8); + RELEASE_ASSERT(width == Arg::Width32); + + RELEASE_ASSERT(isValidForm(StoreZero32, Arg::Stack)); + insertionSet.insert( + instIndex + 1, StoreZero32, inst.origin, + stackAddr(arg.offset() + 4 + slot->offsetFromFP())); + } + arg = stackAddr(arg.offset() + slot->offsetFromFP()); + break; + } + case Arg::CallArg: + arg = stackAddr(arg.offset() - code.frameSize()); + break; + default: + break; + } + } + ); + } + insertionSet.execute(block); + } +} + +} } } // namespace JSC::B3::Air + +#endif // ENABLE(B3_JIT) + + |