PerformanceTests/ARES-6/Air/allocate_stack.js - WebKit - Git at Google

 /*
  * 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);
     }
 }
	/*
	* 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);
	}
	}