chromium/v8/src/compiler/backend/spill-placer.h

// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_BACKEND_SPILL_PLACER_H_
#define V8_COMPILER_BACKEND_SPILL_PLACER_H_

#include "src/compiler/backend/instruction.h"

namespace v8 {
namespace internal {

namespace compiler {

class LiveRangeFinder;
class TopLevelLiveRange;
class RegisterAllocationData;

// SpillPlacer is an implementation of an algorithm to find optimal spill
// insertion positions, where optimal is defined as:
//
// 1. Spills needed by deferred code don't affect non-deferred code.
// 2. No control-flow path spills the same value more than once in non-deferred
//    blocks.
// 3. Where possible based on #2, control-flow paths through non-deferred code
//    that don't need the value to be on the stack don't execute any spills.
// 4. The fewest number of spill instructions is written to meet these rules.
// 5. Spill instructions are placed as early as possible.
//
// These rules are an attempt to make code paths that don't need to spill faster
// while not increasing code size too much.
//
// Considering just one value at a time for now, the steps are:
//
// 1. If the value is defined in a deferred block, or needs its value to be on
//    the stack during the definition block, emit a move right after the
//    definition and exit.
// 2. Build an array representing the state at each block, where the state can
//    be any of the following:
//    - unmarked (default/initial state)
//    - definition
//    - spill required
//    - spill required in non-deferred successor
//    - spill required in deferred successor
// 3. Mark the block containing the definition.
// 4. Mark as "spill required" all blocks that contain any part of a spilled
//    LiveRange, or any use that requires the value to be on the stack.
// 5. Walk the block list backward, setting the "spill required in successor"
//    values where appropriate. If both deferred and non-deferred successors
//    require a spill, then the result should be "spill required in non-deferred
//    successor".
// 6. Walk the block list forward, updating marked blocks to "spill required" if
//    all of their predecessors agree that a spill is required. Furthermore, if
//    a block is marked as "spill required in non-deferred successor" and any
//    non-deferred predecessor is marked as "spill required", then the current
//    block is updated to "spill required". We must mark these merge points as
//    "spill required" to obey rule #2 above: if we didn't, then there would
//    exist a control-flow path through two different spilled regions.
// 7. Walk the block list backward again, updating blocks to "spill required" if
//    all of their successors agree that a spill is required, or if the current
//    block is deferred and any of its successors require spills. If only some
//    successors of a non-deferred block require spills, then insert spill moves
//    at the beginning of those successors. If we manage to smear the "spill
//    required" value all the way to the definition block, then insert a spill
//    move at the definition instead. (Spilling at the definition implies that
//    we didn't emit any other spill moves, and there is a DCHECK mechanism to
//    ensure that invariant.)
//
// Loop back-edges can be safely ignored in every step. Anything that the loop
// header needs on-stack will be spilled either in the loop header itself or
// sometime before entering the loop, so its back-edge predecessors don't need
// to contain any data about the loop header.
//
// The operations described in those steps are simple Boolean logic, so we can
// easily process a batch of values at the same time as an optimization.
class SpillPlacer { … };

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_BACKEND_SPILL_PLACER_H_