/*
|
* Copyright (C) 2016 The Android Open Source Project
|
*
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
* you may not use this file except in compliance with the License.
|
* You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing, software
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
* See the License for the specific language governing permissions and
|
* limitations under the License.
|
*/
|
|
#ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_
|
#define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_
|
|
#include "arch/instruction_set.h"
|
#include "base/arena_object.h"
|
#include "base/array_ref.h"
|
#include "base/macros.h"
|
#include "base/scoped_arena_containers.h"
|
#include "register_allocator.h"
|
|
namespace art {
|
|
class CodeGenerator;
|
class HBasicBlock;
|
class HGraph;
|
class HInstruction;
|
class HParallelMove;
|
class Location;
|
class SsaLivenessAnalysis;
|
class InterferenceNode;
|
struct CoalesceOpportunity;
|
enum class CoalesceKind;
|
|
/**
|
* A graph coloring register allocator.
|
*
|
* The algorithm proceeds as follows:
|
* (1) Build an interference graph, where nodes represent live intervals, and edges represent
|
* interferences between two intervals. Coloring this graph with k colors is isomorphic to
|
* finding a valid register assignment with k registers.
|
* (2) To color the graph, first prune all nodes with degree less than k, since these nodes are
|
* guaranteed a color. (No matter how we color their adjacent nodes, we can give them a
|
* different color.) As we prune nodes from the graph, more nodes may drop below degree k,
|
* enabling further pruning. The key is to maintain the pruning order in a stack, so that we
|
* can color the nodes in the reverse order.
|
* When there are no more nodes with degree less than k, we start pruning alternate nodes based
|
* on heuristics. Since these nodes are not guaranteed a color, we are careful to
|
* prioritize nodes that require a register. We also prioritize short intervals, because
|
* short intervals cannot be split very much if coloring fails (see below). "Prioritizing"
|
* a node amounts to pruning it later, since it will have fewer interferences if we prune other
|
* nodes first.
|
* (3) We color nodes in the reverse order in which we pruned them. If we cannot assign
|
* a node a color, we do one of two things:
|
* - If the node requires a register, we consider the current coloring attempt a failure.
|
* However, we split the node's live interval in order to make the interference graph
|
* sparser, so that future coloring attempts may succeed.
|
* - If the node does not require a register, we simply assign it a location on the stack.
|
*
|
* If iterative move coalescing is enabled, the algorithm also attempts to conservatively
|
* combine nodes in the graph that would prefer to have the same color. (For example, the output
|
* of a phi instruction would prefer to have the same register as at least one of its inputs.)
|
* There are several additional steps involved with this:
|
* - We look for coalesce opportunities by examining each live interval, a step similar to that
|
* used by linear scan when looking for register hints.
|
* - When pruning the graph, we maintain a worklist of coalesce opportunities, as well as a worklist
|
* of low degree nodes that have associated coalesce opportunities. Only when we run out of
|
* coalesce opportunities do we start pruning coalesce-associated nodes.
|
* - When pruning a node, if any nodes transition from high degree to low degree, we add
|
* associated coalesce opportunities to the worklist, since these opportunities may now succeed.
|
* - Whether two nodes can be combined is decided by two different heuristics--one used when
|
* coalescing uncolored nodes, and one used for coalescing an uncolored node with a colored node.
|
* It is vital that we only combine two nodes if the node that remains is guaranteed to receive
|
* a color. This is because additionally spilling is more costly than failing to coalesce.
|
* - Even if nodes are not coalesced while pruning, we keep the coalesce opportunities around
|
* to be used as last-chance register hints when coloring. If nothing else, we try to use
|
* caller-save registers before callee-save registers.
|
*
|
* A good reference for graph coloring register allocation is
|
* "Modern Compiler Implementation in Java" (Andrew W. Appel, 2nd Edition).
|
*/
|
class RegisterAllocatorGraphColor : public RegisterAllocator {
|
public:
|
RegisterAllocatorGraphColor(ScopedArenaAllocator* allocator,
|
CodeGenerator* codegen,
|
const SsaLivenessAnalysis& analysis,
|
bool iterative_move_coalescing = true);
|
~RegisterAllocatorGraphColor() override;
|
|
void AllocateRegisters() override;
|
|
bool Validate(bool log_fatal_on_failure) override;
|
|
private:
|
// Collect all intervals and prepare for register allocation.
|
void ProcessInstructions();
|
void ProcessInstruction(HInstruction* instruction);
|
|
// If any inputs require specific registers, block those registers
|
// at the position of this instruction.
|
void CheckForFixedInputs(HInstruction* instruction);
|
|
// If the output of an instruction requires a specific register, split
|
// the interval and assign the register to the first part.
|
void CheckForFixedOutput(HInstruction* instruction);
|
|
// Add all applicable safepoints to a live interval.
|
// Currently depends on instruction processing order.
|
void AddSafepointsFor(HInstruction* instruction);
|
|
// Collect all live intervals associated with the temporary locations
|
// needed by an instruction.
|
void CheckForTempLiveIntervals(HInstruction* instruction);
|
|
// If a safe point is needed, add a synthesized interval to later record
|
// the number of live registers at this point.
|
void CheckForSafepoint(HInstruction* instruction);
|
|
// Split an interval, but only if `position` is inside of `interval`.
|
// Return either the new interval, or the original interval if not split.
|
static LiveInterval* TrySplit(LiveInterval* interval, size_t position);
|
|
// To ensure every graph can be colored, split live intervals
|
// at their register defs and uses. This creates short intervals with low
|
// degree in the interference graph, which are prioritized during graph
|
// coloring.
|
void SplitAtRegisterUses(LiveInterval* interval);
|
|
// If the given instruction is a catch phi, give it a spill slot.
|
void AllocateSpillSlotForCatchPhi(HInstruction* instruction);
|
|
// Ensure that the given register cannot be allocated for a given range.
|
void BlockRegister(Location location, size_t start, size_t end);
|
void BlockRegisters(size_t start, size_t end, bool caller_save_only = false);
|
|
bool IsCallerSave(size_t reg, bool processing_core_regs);
|
|
// Assigns stack slots to a list of intervals, ensuring that interfering intervals are not
|
// assigned the same stack slot.
|
void ColorSpillSlots(ArrayRef<LiveInterval* const> nodes, /* out */ size_t* num_stack_slots_used);
|
|
// Provide stack slots to nodes that need them.
|
void AllocateSpillSlots(ArrayRef<InterferenceNode* const> nodes);
|
|
// Whether iterative move coalescing should be performed. Iterative move coalescing
|
// improves code quality, but increases compile time.
|
const bool iterative_move_coalescing_;
|
|
// Live intervals, split by kind (core and floating point).
|
// These should not contain high intervals, as those are represented by
|
// the corresponding low interval throughout register allocation.
|
ScopedArenaVector<LiveInterval*> core_intervals_;
|
ScopedArenaVector<LiveInterval*> fp_intervals_;
|
|
// Intervals for temporaries, saved for special handling in the resolution phase.
|
ScopedArenaVector<LiveInterval*> temp_intervals_;
|
|
// Safepoints, saved for special handling while processing instructions.
|
ScopedArenaVector<HInstruction*> safepoints_;
|
|
// Interference nodes representing specific registers. These are "pre-colored" nodes
|
// in the interference graph.
|
ScopedArenaVector<InterferenceNode*> physical_core_nodes_;
|
ScopedArenaVector<InterferenceNode*> physical_fp_nodes_;
|
|
// Allocated stack slot counters.
|
size_t num_int_spill_slots_;
|
size_t num_double_spill_slots_;
|
size_t num_float_spill_slots_;
|
size_t num_long_spill_slots_;
|
size_t catch_phi_spill_slot_counter_;
|
|
// Number of stack slots needed for the pointer to the current method.
|
// This is 1 for 32-bit architectures, and 2 for 64-bit architectures.
|
const size_t reserved_art_method_slots_;
|
|
// Number of stack slots needed for outgoing arguments.
|
const size_t reserved_out_slots_;
|
|
friend class ColoringIteration;
|
|
DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGraphColor);
|
};
|
|
} // namespace art
|
|
#endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_
|
