Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ |
| 18 | #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ |
| 19 | |
| 20 | #include "arch/instruction_set.h" |
| 21 | #include "base/arena_containers.h" |
| 22 | #include "base/arena_object.h" |
| 23 | #include "base/macros.h" |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 24 | #include "register_allocator.h" |
| 25 | |
| 26 | namespace art { |
| 27 | |
| 28 | class CodeGenerator; |
| 29 | class HBasicBlock; |
| 30 | class HGraph; |
| 31 | class HInstruction; |
| 32 | class HParallelMove; |
| 33 | class Location; |
| 34 | class SsaLivenessAnalysis; |
| 35 | class InterferenceNode; |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 36 | struct CoalesceOpportunity; |
| 37 | enum class CoalesceKind; |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 38 | |
| 39 | /** |
| 40 | * A graph coloring register allocator. |
| 41 | * |
| 42 | * The algorithm proceeds as follows: |
| 43 | * (1) Build an interference graph, where nodes represent live intervals, and edges represent |
| 44 | * interferences between two intervals. Coloring this graph with k colors is isomorphic to |
| 45 | * finding a valid register assignment with k registers. |
| 46 | * (2) To color the graph, first prune all nodes with degree less than k, since these nodes are |
| 47 | * guaranteed a color. (No matter how we color their adjacent nodes, we can give them a |
| 48 | * different color.) As we prune nodes from the graph, more nodes may drop below degree k, |
| 49 | * enabling further pruning. The key is to maintain the pruning order in a stack, so that we |
| 50 | * can color the nodes in the reverse order. |
| 51 | * When there are no more nodes with degree less than k, we start pruning alternate nodes based |
| 52 | * on heuristics. Since these nodes are not guaranteed a color, we are careful to |
| 53 | * prioritize nodes that require a register. We also prioritize short intervals, because |
| 54 | * short intervals cannot be split very much if coloring fails (see below). "Prioritizing" |
| 55 | * a node amounts to pruning it later, since it will have fewer interferences if we prune other |
| 56 | * nodes first. |
| 57 | * (3) We color nodes in the reverse order in which we pruned them. If we cannot assign |
| 58 | * a node a color, we do one of two things: |
| 59 | * - If the node requires a register, we consider the current coloring attempt a failure. |
| 60 | * However, we split the node's live interval in order to make the interference graph |
| 61 | * sparser, so that future coloring attempts may succeed. |
| 62 | * - If the node does not require a register, we simply assign it a location on the stack. |
| 63 | * |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 64 | * If iterative move coalescing is enabled, the algorithm also attempts to conservatively |
| 65 | * combine nodes in the graph that would prefer to have the same color. (For example, the output |
| 66 | * of a phi instruction would prefer to have the same register as at least one of its inputs.) |
| 67 | * There are several additional steps involved with this: |
| 68 | * - We look for coalesce opportunities by examining each live interval, a step similar to that |
| 69 | * used by linear scan when looking for register hints. |
| 70 | * - When pruning the graph, we maintain a worklist of coalesce opportunities, as well as a worklist |
| 71 | * of low degree nodes that have associated coalesce opportunities. Only when we run out of |
| 72 | * coalesce opportunities do we start pruning coalesce-associated nodes. |
| 73 | * - When pruning a node, if any nodes transition from high degree to low degree, we add |
| 74 | * associated coalesce opportunities to the worklist, since these opportunities may now succeed. |
| 75 | * - Whether two nodes can be combined is decided by two different heuristics--one used when |
| 76 | * coalescing uncolored nodes, and one used for coalescing an uncolored node with a colored node. |
| 77 | * It is vital that we only combine two nodes if the node that remains is guaranteed to receive |
| 78 | * a color. This is because additionally spilling is more costly than failing to coalesce. |
| 79 | * - Even if nodes are not coalesced while pruning, we keep the coalesce opportunities around |
| 80 | * to be used as last-chance register hints when coloring. If nothing else, we try to use |
| 81 | * caller-save registers before callee-save registers. |
| 82 | * |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 83 | * A good reference for graph coloring register allocation is |
| 84 | * "Modern Compiler Implementation in Java" (Andrew W. Appel, 2nd Edition). |
| 85 | */ |
| 86 | class RegisterAllocatorGraphColor : public RegisterAllocator { |
| 87 | public: |
| 88 | RegisterAllocatorGraphColor(ArenaAllocator* allocator, |
| 89 | CodeGenerator* codegen, |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 90 | const SsaLivenessAnalysis& analysis, |
| 91 | bool iterative_move_coalescing = true); |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 92 | ~RegisterAllocatorGraphColor() OVERRIDE {} |
| 93 | |
| 94 | void AllocateRegisters() OVERRIDE; |
| 95 | |
| 96 | bool Validate(bool log_fatal_on_failure); |
| 97 | |
| 98 | private: |
| 99 | // Collect all intervals and prepare for register allocation. |
| 100 | void ProcessInstructions(); |
| 101 | void ProcessInstruction(HInstruction* instruction); |
| 102 | |
| 103 | // If any inputs require specific registers, block those registers |
| 104 | // at the position of this instruction. |
| 105 | void CheckForFixedInputs(HInstruction* instruction); |
| 106 | |
| 107 | // If the output of an instruction requires a specific register, split |
| 108 | // the interval and assign the register to the first part. |
| 109 | void CheckForFixedOutput(HInstruction* instruction); |
| 110 | |
| 111 | // Add all applicable safepoints to a live interval. |
| 112 | // Currently depends on instruction processing order. |
| 113 | void AddSafepointsFor(HInstruction* instruction); |
| 114 | |
| 115 | // Collect all live intervals associated with the temporary locations |
| 116 | // needed by an instruction. |
| 117 | void CheckForTempLiveIntervals(HInstruction* instruction); |
| 118 | |
| 119 | // If a safe point is needed, add a synthesized interval to later record |
| 120 | // the number of live registers at this point. |
| 121 | void CheckForSafepoint(HInstruction* instruction); |
| 122 | |
| 123 | // Split an interval, but only if `position` is inside of `interval`. |
| 124 | // Return either the new interval, or the original interval if not split. |
| 125 | static LiveInterval* TrySplit(LiveInterval* interval, size_t position); |
| 126 | |
| 127 | // To ensure every graph can be colored, split live intervals |
| 128 | // at their register defs and uses. This creates short intervals with low |
| 129 | // degree in the interference graph, which are prioritized during graph |
| 130 | // coloring. |
| 131 | void SplitAtRegisterUses(LiveInterval* interval); |
| 132 | |
| 133 | // If the given instruction is a catch phi, give it a spill slot. |
| 134 | void AllocateSpillSlotForCatchPhi(HInstruction* instruction); |
| 135 | |
| 136 | // Ensure that the given register cannot be allocated for a given range. |
| 137 | void BlockRegister(Location location, size_t start, size_t end); |
| 138 | void BlockRegisters(size_t start, size_t end, bool caller_save_only = false); |
| 139 | |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 140 | bool IsCallerSave(size_t reg, bool processing_core_regs); |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 141 | |
Matthew Gharrity | b6722ff | 2016-08-12 19:07:11 -0700 | [diff] [blame] | 142 | // Assigns stack slots to a list of intervals, ensuring that interfering intervals are not |
| 143 | // assigned the same stack slot. |
| 144 | void ColorSpillSlots(ArenaVector<LiveInterval*>* nodes, |
| 145 | size_t* num_stack_slots_used); |
| 146 | |
| 147 | // Provide stack slots to nodes that need them. |
| 148 | void AllocateSpillSlots(const ArenaVector<InterferenceNode*>& nodes); |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 149 | |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 150 | // Whether iterative move coalescing should be performed. Iterative move coalescing |
| 151 | // improves code quality, but increases compile time. |
| 152 | const bool iterative_move_coalescing_; |
| 153 | |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 154 | // Live intervals, split by kind (core and floating point). |
| 155 | // These should not contain high intervals, as those are represented by |
| 156 | // the corresponding low interval throughout register allocation. |
| 157 | ArenaVector<LiveInterval*> core_intervals_; |
| 158 | ArenaVector<LiveInterval*> fp_intervals_; |
| 159 | |
| 160 | // Intervals for temporaries, saved for special handling in the resolution phase. |
| 161 | ArenaVector<LiveInterval*> temp_intervals_; |
| 162 | |
| 163 | // Safepoints, saved for special handling while processing instructions. |
| 164 | ArenaVector<HInstruction*> safepoints_; |
| 165 | |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 166 | // Interference nodes representing specific registers. These are "pre-colored" nodes |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 167 | // in the interference graph. |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 168 | ArenaVector<InterferenceNode*> physical_core_nodes_; |
| 169 | ArenaVector<InterferenceNode*> physical_fp_nodes_; |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 170 | |
| 171 | // Allocated stack slot counters. |
Matthew Gharrity | b6722ff | 2016-08-12 19:07:11 -0700 | [diff] [blame] | 172 | size_t num_int_spill_slots_; |
| 173 | size_t num_double_spill_slots_; |
| 174 | size_t num_float_spill_slots_; |
| 175 | size_t num_long_spill_slots_; |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 176 | size_t catch_phi_spill_slot_counter_; |
| 177 | |
| 178 | // Number of stack slots needed for the pointer to the current method. |
| 179 | // This is 1 for 32-bit architectures, and 2 for 64-bit architectures. |
| 180 | const size_t reserved_art_method_slots_; |
| 181 | |
| 182 | // Number of stack slots needed for outgoing arguments. |
| 183 | const size_t reserved_out_slots_; |
| 184 | |
Matthew Gharrity | 2ccae4a | 2016-08-12 16:10:45 +0000 | [diff] [blame] | 185 | friend class ColoringIteration; |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 186 | |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 187 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGraphColor); |
| 188 | }; |
| 189 | |
| 190 | } // namespace art |
| 191 | |
| 192 | #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ |