Tue, 08 Aug 2017 15:57:29 +0800
merge
1 /*
2 * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 /*
26 * This file has been modified by Loongson Technology in 2015. These
27 * modifications are Copyright (c) 2015 Loongson Technology, and are made
28 * available on the same license terms set forth above.
29 */
31 #ifndef SHARE_VM_C1_C1_LINEARSCAN_HPP
32 #define SHARE_VM_C1_C1_LINEARSCAN_HPP
34 #include "c1/c1_FpuStackSim.hpp"
35 #include "c1/c1_FrameMap.hpp"
36 #include "c1/c1_IR.hpp"
37 #include "c1/c1_Instruction.hpp"
38 #include "c1/c1_LIR.hpp"
39 #include "c1/c1_LIRGenerator.hpp"
41 class DebugInfoCache;
42 class FpuStackAllocator;
43 class IRScopeDebugInfo;
44 class Interval;
45 class IntervalWalker;
46 class LIRGenerator;
47 class LinearScan;
48 class MoveResolver;
49 class Range;
51 define_array(IntervalArray, Interval*)
52 define_stack(IntervalList, IntervalArray)
54 define_array(IntervalsArray, IntervalList*)
55 define_stack(IntervalsList, IntervalsArray)
57 define_array(OopMapArray, OopMap*)
58 define_stack(OopMapList, OopMapArray)
60 define_array(ScopeValueArray, ScopeValue*)
62 define_array(LIR_OpListArray, LIR_OpList*);
63 define_stack(LIR_OpListStack, LIR_OpListArray);
66 enum IntervalUseKind {
67 // priority of use kinds must be ascending
68 noUse = 0,
69 loopEndMarker = 1,
70 shouldHaveRegister = 2,
71 mustHaveRegister = 3,
73 firstValidKind = 1,
74 lastValidKind = 3
75 };
76 define_array(UseKindArray, IntervalUseKind)
77 define_stack(UseKindStack, UseKindArray)
80 enum IntervalKind {
81 fixedKind = 0, // interval pre-colored by LIR_Generator
82 anyKind = 1, // no register/memory allocated by LIR_Generator
83 nofKinds,
84 firstKind = fixedKind
85 };
88 // during linear scan an interval is in one of four states in
89 enum IntervalState {
90 unhandledState = 0, // unhandled state (not processed yet)
91 activeState = 1, // life and is in a physical register
92 inactiveState = 2, // in a life time hole and is in a physical register
93 handledState = 3, // spilled or not life again
94 invalidState = -1
95 };
98 enum IntervalSpillState {
99 noDefinitionFound, // starting state of calculation: no definition found yet
100 oneDefinitionFound, // one definition has already been found.
101 // Note: two consecutive definitions are treated as one (e.g. consecutive move and add because of two-operand LIR form)
102 // the position of this definition is stored in _definition_pos
103 oneMoveInserted, // one spill move has already been inserted.
104 storeAtDefinition, // the interval should be stored immediately after its definition because otherwise
105 // there would be multiple redundant stores
106 startInMemory, // the interval starts in memory (e.g. method parameter), so a store is never necessary
107 noOptimization // the interval has more then one definition (e.g. resulting from phi moves), so stores to memory are not optimized
108 };
111 #define for_each_interval_kind(kind) \
112 for (IntervalKind kind = firstKind; kind < nofKinds; kind = (IntervalKind)(kind + 1))
114 #define for_each_visitor_mode(mode) \
115 for (LIR_OpVisitState::OprMode mode = LIR_OpVisitState::firstMode; mode < LIR_OpVisitState::numModes; mode = (LIR_OpVisitState::OprMode)(mode + 1))
118 class LinearScan : public CompilationResourceObj {
119 // declare classes used by LinearScan as friends because they
120 // need a wide variety of functions declared here
121 //
122 // Only the small interface to the rest of the compiler is public
123 friend class Interval;
124 friend class IntervalWalker;
125 friend class LinearScanWalker;
126 friend class FpuStackAllocator;
127 friend class MoveResolver;
128 friend class LinearScanStatistic;
129 friend class LinearScanTimers;
130 friend class RegisterVerifier;
132 public:
133 enum {
134 any_reg = -1,
135 nof_cpu_regs = pd_nof_cpu_regs_linearscan,
136 nof_fpu_regs = pd_nof_fpu_regs_linearscan,
137 nof_xmm_regs = pd_nof_xmm_regs_linearscan,
138 nof_regs = nof_cpu_regs + nof_fpu_regs + nof_xmm_regs
139 };
141 private:
142 Compilation* _compilation;
143 IR* _ir;
144 LIRGenerator* _gen;
145 FrameMap* _frame_map;
147 BlockList _cached_blocks; // cached list with all blocks in linear-scan order (only correct if original list keeps unchanged)
148 int _num_virtual_regs; // number of virtual registers (without new registers introduced because of splitting intervals)
149 bool _has_fpu_registers; // true if this method uses any floating point registers (and so fpu stack allocation is necessary)
150 int _num_calls; // total number of calls in this method
151 int _max_spills; // number of stack slots used for intervals allocated to memory
152 int _unused_spill_slot; // unused spill slot for a single-word value because of alignment of a double-word value
154 IntervalList _intervals; // mapping from register number to interval
155 IntervalList* _new_intervals_from_allocation; // list with all intervals created during allocation when an existing interval is split
156 IntervalArray* _sorted_intervals; // intervals sorted by Interval::from()
157 bool _needs_full_resort; // set to true if an Interval::from() is changed and _sorted_intervals must be resorted
159 LIR_OpArray _lir_ops; // mapping from LIR_Op id to LIR_Op node
160 BlockBeginArray _block_of_op; // mapping from LIR_Op id to the BlockBegin containing this instruction
161 BitMap _has_info; // bit set for each LIR_Op id that has a CodeEmitInfo
162 BitMap _has_call; // bit set for each LIR_Op id that destroys all caller save registers
163 BitMap2D _interval_in_loop; // bit set for each virtual register that is contained in each loop
165 // cached debug info to prevent multiple creation of same object
166 // TODO: cached scope values for registers could be static
167 ScopeValueArray _scope_value_cache;
169 static ConstantOopWriteValue* _oop_null_scope_value;
170 static ConstantIntValue* _int_m1_scope_value;
171 static ConstantIntValue* _int_0_scope_value;
172 static ConstantIntValue* _int_1_scope_value;
173 static ConstantIntValue* _int_2_scope_value;
175 // accessors
176 IR* ir() const { return _ir; }
177 Compilation* compilation() const { return _compilation; }
178 LIRGenerator* gen() const { return _gen; }
179 FrameMap* frame_map() const { return _frame_map; }
181 // unified bailout support
182 void bailout(const char* msg) const { compilation()->bailout(msg); }
183 bool bailed_out() const { return compilation()->bailed_out(); }
185 // access to block list (sorted in linear scan order)
186 int block_count() const { assert(_cached_blocks.length() == ir()->linear_scan_order()->length(), "invalid cached block list"); return _cached_blocks.length(); }
187 BlockBegin* block_at(int idx) const { assert(_cached_blocks.at(idx) == ir()->linear_scan_order()->at(idx), "invalid cached block list"); return _cached_blocks.at(idx); }
189 int num_virtual_regs() const { return _num_virtual_regs; }
190 // size of live_in and live_out sets of BasicBlocks (BitMap needs rounded size for iteration)
191 int live_set_size() const { return round_to(_num_virtual_regs, BitsPerWord); }
192 bool has_fpu_registers() const { return _has_fpu_registers; }
193 int num_loops() const { return ir()->num_loops(); }
194 bool is_interval_in_loop(int interval, int loop) const { return _interval_in_loop.at(interval, loop); }
196 // handling of fpu stack allocation (platform dependent, needed for debug information generation)
197 #ifdef X86
198 FpuStackAllocator* _fpu_stack_allocator;
199 bool use_fpu_stack_allocation() const { return UseSSE < 2 && has_fpu_registers(); }
200 #else
201 bool use_fpu_stack_allocation() const { return false; }
202 #endif
205 // access to interval list
206 int interval_count() const { return _intervals.length(); }
207 Interval* interval_at(int reg_num) const { return _intervals.at(reg_num); }
209 IntervalList* new_intervals_from_allocation() const { return _new_intervals_from_allocation; }
211 // access to LIR_Ops and Blocks indexed by op_id
212 int max_lir_op_id() const { assert(_lir_ops.length() > 0, "no operations"); return (_lir_ops.length() - 1) << 1; }
213 LIR_Op* lir_op_with_id(int op_id) const { assert(op_id >= 0 && op_id <= max_lir_op_id() && op_id % 2 == 0, "op_id out of range or not even"); return _lir_ops.at(op_id >> 1); }
214 BlockBegin* block_of_op_with_id(int op_id) const { assert(_block_of_op.length() > 0 && op_id >= 0 && op_id <= max_lir_op_id() + 1, "op_id out of range"); return _block_of_op.at(op_id >> 1); }
216 bool is_block_begin(int op_id) { return op_id == 0 || block_of_op_with_id(op_id) != block_of_op_with_id(op_id - 1); }
217 bool covers_block_begin(int op_id_1, int op_id_2) { return block_of_op_with_id(op_id_1) != block_of_op_with_id(op_id_2); }
219 bool has_call(int op_id) { assert(op_id % 2 == 0, "must be even"); return _has_call.at(op_id >> 1); }
220 bool has_info(int op_id) { assert(op_id % 2 == 0, "must be even"); return _has_info.at(op_id >> 1); }
223 // functions for converting LIR-Operands to register numbers
224 static bool is_valid_reg_num(int reg_num) { return reg_num >= 0; }
225 static int reg_num(LIR_Opr opr);
226 static int reg_numHi(LIR_Opr opr);
228 // functions for classification of intervals
229 static bool is_precolored_interval(const Interval* i);
230 static bool is_virtual_interval(const Interval* i);
232 static bool is_precolored_cpu_interval(const Interval* i);
233 static bool is_virtual_cpu_interval(const Interval* i);
234 static bool is_precolored_fpu_interval(const Interval* i);
235 static bool is_virtual_fpu_interval(const Interval* i);
237 static bool is_in_fpu_register(const Interval* i);
238 static bool is_oop_interval(const Interval* i);
241 // General helper functions
242 int allocate_spill_slot(bool double_word);
243 void assign_spill_slot(Interval* it);
244 void propagate_spill_slots();
246 Interval* create_interval(int reg_num);
247 void append_interval(Interval* it);
248 void copy_register_flags(Interval* from, Interval* to);
250 // platform dependent functions
251 static bool is_processed_reg_num(int reg_num);
252 static int num_physical_regs(BasicType type);
253 static bool requires_adjacent_regs(BasicType type);
254 static bool is_caller_save(int assigned_reg);
256 // spill move optimization: eliminate moves from register to stack if
257 // stack slot is known to be correct
258 void change_spill_definition_pos(Interval* interval, int def_pos);
259 void change_spill_state(Interval* interval, int spill_pos);
260 static bool must_store_at_definition(const Interval* i);
261 void eliminate_spill_moves();
263 // Phase 1: number all instructions in all blocks
264 void number_instructions();
266 // Phase 2: compute local live sets separately for each block
267 // (sets live_gen and live_kill for each block)
268 //
269 // helper methods used by compute_local_live_sets()
270 void set_live_gen_kill(Value value, LIR_Op* op, BitMap& live_gen, BitMap& live_kill);
272 void compute_local_live_sets();
274 // Phase 3: perform a backward dataflow analysis to compute global live sets
275 // (sets live_in and live_out for each block)
276 void compute_global_live_sets();
279 // Phase 4: build intervals
280 // (fills the list _intervals)
281 //
282 // helper methods used by build_intervals()
283 void add_use (Value value, int from, int to, IntervalUseKind use_kind);
285 void add_def (LIR_Opr opr, int def_pos, IntervalUseKind use_kind);
286 void add_use (LIR_Opr opr, int from, int to, IntervalUseKind use_kind);
287 void add_temp(LIR_Opr opr, int temp_pos, IntervalUseKind use_kind);
289 void add_def (int reg_num, int def_pos, IntervalUseKind use_kind, BasicType type);
290 void add_use (int reg_num, int from, int to, IntervalUseKind use_kind, BasicType type);
291 void add_temp(int reg_num, int temp_pos, IntervalUseKind use_kind, BasicType type);
293 // Add platform dependent kills for particular LIR ops. Can be used
294 // to add platform dependent behaviour for some operations.
295 void pd_add_temps(LIR_Op* op);
297 IntervalUseKind use_kind_of_output_operand(LIR_Op* op, LIR_Opr opr);
298 IntervalUseKind use_kind_of_input_operand(LIR_Op* op, LIR_Opr opr);
299 void handle_method_arguments(LIR_Op* op);
300 void handle_doubleword_moves(LIR_Op* op);
301 void add_register_hints(LIR_Op* op);
303 void build_intervals();
306 // Phase 5: actual register allocation
307 // (Uses LinearScanWalker)
308 //
309 // helper functions for building a sorted list of intervals
310 NOT_PRODUCT(bool is_sorted(IntervalArray* intervals);)
311 static int interval_cmp(Interval** a, Interval** b);
312 void add_to_list(Interval** first, Interval** prev, Interval* interval);
313 void create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i));
315 void sort_intervals_before_allocation();
316 void sort_intervals_after_allocation();
317 void allocate_registers();
320 // Phase 6: resolve data flow
321 // (insert moves at edges between blocks if intervals have been split)
322 //
323 // helper functions for resolve_data_flow()
324 Interval* split_child_at_op_id(Interval* interval, int op_id, LIR_OpVisitState::OprMode mode);
325 Interval* interval_at_block_begin(BlockBegin* block, int reg_num);
326 Interval* interval_at_block_end(BlockBegin* block, int reg_num);
327 Interval* interval_at_op_id(int reg_num, int op_id);
328 void resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver);
329 void resolve_find_insert_pos(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver);
330 void resolve_data_flow();
332 void resolve_exception_entry(BlockBegin* block, int reg_num, MoveResolver &move_resolver);
333 void resolve_exception_entry(BlockBegin* block, MoveResolver &move_resolver);
334 void resolve_exception_edge(XHandler* handler, int throwing_op_id, int reg_num, Phi* phi, MoveResolver &move_resolver);
335 void resolve_exception_edge(XHandler* handler, int throwing_op_id, MoveResolver &move_resolver);
336 void resolve_exception_handlers();
338 // Phase 7: assign register numbers back to LIR
339 // (includes computation of debug information and oop maps)
340 //
341 // helper functions for assign_reg_num()
342 VMReg vm_reg_for_interval(Interval* interval);
343 VMReg vm_reg_for_operand(LIR_Opr opr);
345 static LIR_Opr operand_for_interval(Interval* interval);
346 static LIR_Opr calc_operand_for_interval(const Interval* interval);
347 LIR_Opr canonical_spill_opr(Interval* interval);
349 LIR_Opr color_lir_opr(LIR_Opr opr, int id, LIR_OpVisitState::OprMode);
351 // methods used for oop map computation
352 IntervalWalker* init_compute_oop_maps();
353 OopMap* compute_oop_map(IntervalWalker* iw, LIR_Op* op, CodeEmitInfo* info, bool is_call_site);
354 void compute_oop_map(IntervalWalker* iw, const LIR_OpVisitState &visitor, LIR_Op* op);
356 // methods used for debug information computation
357 void init_compute_debug_info();
359 MonitorValue* location_for_monitor_index(int monitor_index);
360 LocationValue* location_for_name(int name, Location::Type loc_type);
361 void set_oop(OopMap* map, VMReg name) {
362 if (map->legal_vm_reg_name(name)) {
363 map->set_oop(name);
364 } else {
365 bailout("illegal oopMap register name");
366 }
367 }
369 int append_scope_value_for_constant(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values);
370 int append_scope_value_for_operand(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values);
371 int append_scope_value(int op_id, Value value, GrowableArray<ScopeValue*>* scope_values);
373 IRScopeDebugInfo* compute_debug_info_for_scope(int op_id, IRScope* cur_scope, ValueStack* cur_state, ValueStack* innermost_state);
374 void compute_debug_info(CodeEmitInfo* info, int op_id);
376 void assign_reg_num(LIR_OpList* instructions, IntervalWalker* iw);
377 void assign_reg_num();
380 // Phase 8: fpu stack allocation
381 // (Used only on x86 when fpu operands are present)
382 void allocate_fpu_stack();
385 // helper functions for printing state
386 #ifndef PRODUCT
387 static void print_bitmap(BitMap& bitmap);
388 void print_intervals(const char* label);
389 void print_lir(int level, const char* label, bool hir_valid = true);
390 #endif
392 #ifdef ASSERT
393 // verification functions for allocation
394 // (check that all intervals have a correct register and that no registers are overwritten)
395 void verify();
396 void verify_intervals();
397 void verify_no_oops_in_fixed_intervals();
398 void verify_constants();
399 void verify_registers();
400 #endif
402 public:
403 // creation
404 LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map);
406 // main entry function: perform linear scan register allocation
407 void do_linear_scan();
409 // accessors used by Compilation
410 int max_spills() const { return _max_spills; }
411 int num_calls() const { assert(_num_calls >= 0, "not set"); return _num_calls; }
413 // entry functions for printing
414 #ifndef PRODUCT
415 static void print_statistics();
416 static void print_timers(double total);
417 #endif
418 };
421 // Helper class for ordering moves that are inserted at the same position in the LIR
422 // When moves between registers are inserted, it is important that the moves are
423 // ordered such that no register is overwritten. So moves from register to stack
424 // are processed prior to moves from stack to register. When moves have circular
425 // dependencies, a temporary stack slot is used to break the circle.
426 // The same logic is used in the LinearScanWalker and in LinearScan during resolve_data_flow
427 // and therefore factored out in a separate class
428 class MoveResolver: public StackObj {
429 private:
430 LinearScan* _allocator;
432 LIR_List* _insert_list;
433 int _insert_idx;
434 LIR_InsertionBuffer _insertion_buffer; // buffer where moves are inserted
436 IntervalList _mapping_from;
437 LIR_OprList _mapping_from_opr;
438 IntervalList _mapping_to;
439 bool _multiple_reads_allowed;
440 int _register_blocked[LinearScan::nof_regs];
442 int register_blocked(int reg) { assert(reg >= 0 && reg < LinearScan::nof_regs, "out of bounds"); return _register_blocked[reg]; }
443 void set_register_blocked(int reg, int direction) { assert(reg >= 0 && reg < LinearScan::nof_regs, "out of bounds"); assert(direction == 1 || direction == -1, "out of bounds"); _register_blocked[reg] += direction; }
445 void block_registers(Interval* it);
446 void unblock_registers(Interval* it);
447 bool save_to_process_move(Interval* from, Interval* to);
449 void create_insertion_buffer(LIR_List* list);
450 void append_insertion_buffer();
451 void insert_move(Interval* from_interval, Interval* to_interval);
452 void insert_move(LIR_Opr from_opr, Interval* to_interval);
454 DEBUG_ONLY(void verify_before_resolve();)
455 void resolve_mappings();
456 public:
457 MoveResolver(LinearScan* allocator);
459 DEBUG_ONLY(void check_empty();)
460 void set_multiple_reads_allowed() { _multiple_reads_allowed = true; }
461 void set_insert_position(LIR_List* insert_list, int insert_idx);
462 void move_insert_position(LIR_List* insert_list, int insert_idx);
463 void add_mapping(Interval* from, Interval* to);
464 void add_mapping(LIR_Opr from, Interval* to);
465 void resolve_and_append_moves();
467 LinearScan* allocator() { return _allocator; }
468 bool has_mappings() { return _mapping_from.length() > 0; }
469 };
472 class Range : public CompilationResourceObj {
473 friend class Interval;
475 private:
476 static Range* _end; // sentinel (from == to == max_jint)
478 int _from; // from (inclusive)
479 int _to; // to (exclusive)
480 Range* _next; // linear list of Ranges
482 // used only by class Interval, so hide them
483 bool intersects(Range* r) const { return intersects_at(r) != -1; }
484 int intersects_at(Range* r) const;
486 public:
487 Range(int from, int to, Range* next);
489 static void initialize(Arena* arena);
490 static Range* end() { return _end; }
492 int from() const { return _from; }
493 int to() const { return _to; }
494 Range* next() const { return _next; }
495 void set_from(int from) { _from = from; }
496 void set_to(int to) { _to = to; }
497 void set_next(Range* next) { _next = next; }
499 // for testing
500 void print(outputStream* out = tty) const PRODUCT_RETURN;
501 };
504 // Interval is an ordered list of disjoint ranges.
506 // For pre-colored double word LIR_Oprs, one interval is created for
507 // the low word register and one is created for the hi word register.
508 // On Intel for FPU double registers only one interval is created. At
509 // all times assigned_reg contains the reg. number of the physical
510 // register.
512 // For LIR_Opr in virtual registers a single interval can represent
513 // single and double word values. When a physical register is
514 // assigned to the interval, assigned_reg contains the
515 // phys. reg. number and for double word values assigned_regHi the
516 // phys. reg. number of the hi word if there is any. For spilled
517 // intervals assigned_reg contains the stack index. assigned_regHi is
518 // always -1.
520 class Interval : public CompilationResourceObj {
521 private:
522 static Interval* _end; // sentinel (interval with only range Range::end())
524 int _reg_num;
525 BasicType _type; // valid only for virtual registers
526 Range* _first; // sorted list of Ranges
527 intStack _use_pos_and_kinds; // sorted list of use-positions and their according use-kinds
529 Range* _current; // interval iteration: the current Range
530 Interval* _next; // interval iteration: sorted list of Intervals (ends with sentinel)
531 IntervalState _state; // interval iteration: to which set belongs this interval
534 int _assigned_reg;
535 int _assigned_regHi;
537 int _cached_to; // cached value: to of last range (-1: not cached)
538 LIR_Opr _cached_opr;
539 VMReg _cached_vm_reg;
541 Interval* _split_parent; // the original interval where this interval is derived from
542 IntervalList _split_children; // list of all intervals that are split off from this interval (only available for split parents)
543 Interval* _current_split_child; // the current split child that has been active or inactive last (always stored in split parents)
545 int _canonical_spill_slot; // the stack slot where all split parts of this interval are spilled to (always stored in split parents)
546 bool _insert_move_when_activated; // true if move is inserted between _current_split_child and this interval when interval gets active the first time
547 IntervalSpillState _spill_state; // for spill move optimization
548 int _spill_definition_pos; // position where the interval is defined (if defined only once)
549 Interval* _register_hint; // this interval should be in the same register as the hint interval
551 int calc_to();
552 Interval* new_split_child();
553 public:
554 Interval(int reg_num);
556 static void initialize(Arena* arena);
557 static Interval* end() { return _end; }
559 // accessors
560 int reg_num() const { return _reg_num; }
561 void set_reg_num(int r) { assert(_reg_num == -1, "cannot change reg_num"); _reg_num = r; }
562 BasicType type() const { assert(_reg_num == -1 || _reg_num >= LIR_OprDesc::vreg_base, "cannot access type for fixed interval"); return _type; }
563 void set_type(BasicType type) { assert(_reg_num < LIR_OprDesc::vreg_base || _type == T_ILLEGAL || _type == type, "overwriting existing type"); _type = type; }
565 Range* first() const { return _first; }
566 int from() const { return _first->from(); }
567 int to() { if (_cached_to == -1) _cached_to = calc_to(); assert(_cached_to == calc_to(), "invalid cached value"); return _cached_to; }
568 int num_use_positions() const { return _use_pos_and_kinds.length() / 2; }
570 Interval* next() const { return _next; }
571 Interval** next_addr() { return &_next; }
572 void set_next(Interval* next) { _next = next; }
574 int assigned_reg() const { return _assigned_reg; }
575 int assigned_regHi() const { return _assigned_regHi; }
576 void assign_reg(int reg) { _assigned_reg = reg; _assigned_regHi = LinearScan::any_reg; }
577 void assign_reg(int reg,int regHi) { _assigned_reg = reg; _assigned_regHi = regHi; }
579 Interval* register_hint(bool search_split_child = true) const; // calculation needed
580 void set_register_hint(Interval* i) { _register_hint = i; }
582 int state() const { return _state; }
583 void set_state(IntervalState s) { _state = s; }
585 // access to split parent and split children
586 bool is_split_parent() const { return _split_parent == this; }
587 bool is_split_child() const { return _split_parent != this; }
588 Interval* split_parent() const { assert(_split_parent->is_split_parent(), "must be"); return _split_parent; }
589 Interval* split_child_at_op_id(int op_id, LIR_OpVisitState::OprMode mode);
590 Interval* split_child_before_op_id(int op_id);
591 bool split_child_covers(int op_id, LIR_OpVisitState::OprMode mode);
592 DEBUG_ONLY(void check_split_children();)
594 // information stored in split parent, but available for all children
595 int canonical_spill_slot() const { return split_parent()->_canonical_spill_slot; }
596 void set_canonical_spill_slot(int slot) { assert(split_parent()->_canonical_spill_slot == -1, "overwriting existing value"); split_parent()->_canonical_spill_slot = slot; }
597 Interval* current_split_child() const { return split_parent()->_current_split_child; }
598 void make_current_split_child() { split_parent()->_current_split_child = this; }
600 bool insert_move_when_activated() const { return _insert_move_when_activated; }
601 void set_insert_move_when_activated(bool b) { _insert_move_when_activated = b; }
603 // for spill optimization
604 IntervalSpillState spill_state() const { return split_parent()->_spill_state; }
605 int spill_definition_pos() const { return split_parent()->_spill_definition_pos; }
606 void set_spill_state(IntervalSpillState state) { assert(state >= spill_state(), "state cannot decrease"); split_parent()->_spill_state = state; }
607 void set_spill_definition_pos(int pos) { assert(spill_definition_pos() == -1, "cannot set the position twice"); split_parent()->_spill_definition_pos = pos; }
608 // returns true if this interval has a shadow copy on the stack that is always correct
609 bool always_in_memory() const { return split_parent()->_spill_state == storeAtDefinition || split_parent()->_spill_state == startInMemory; }
611 // caching of values that take time to compute and are used multiple times
612 LIR_Opr cached_opr() const { return _cached_opr; }
613 VMReg cached_vm_reg() const { return _cached_vm_reg; }
614 void set_cached_opr(LIR_Opr opr) { _cached_opr = opr; }
615 void set_cached_vm_reg(VMReg reg) { _cached_vm_reg = reg; }
617 // access to use positions
618 int first_usage(IntervalUseKind min_use_kind) const; // id of the first operation requiring this interval in a register
619 int next_usage(IntervalUseKind min_use_kind, int from) const; // id of next usage seen from the given position
620 int next_usage_exact(IntervalUseKind exact_use_kind, int from) const;
621 int previous_usage(IntervalUseKind min_use_kind, int from) const;
623 // manipulating intervals
624 void add_use_pos(int pos, IntervalUseKind use_kind);
625 void add_range(int from, int to);
626 Interval* split(int split_pos);
627 Interval* split_from_start(int split_pos);
628 void remove_first_use_pos() { _use_pos_and_kinds.truncate(_use_pos_and_kinds.length() - 2); }
630 // test intersection
631 bool covers(int op_id, LIR_OpVisitState::OprMode mode) const;
632 bool has_hole_between(int from, int to);
633 bool intersects(Interval* i) const { return _first->intersects(i->_first); }
634 int intersects_at(Interval* i) const { return _first->intersects_at(i->_first); }
636 // range iteration
637 void rewind_range() { _current = _first; }
638 void next_range() { assert(this != _end, "not allowed on sentinel"); _current = _current->next(); }
639 int current_from() const { return _current->from(); }
640 int current_to() const { return _current->to(); }
641 bool current_at_end() const { return _current == Range::end(); }
642 bool current_intersects(Interval* it) { return _current->intersects(it->_current); };
643 int current_intersects_at(Interval* it) { return _current->intersects_at(it->_current); };
645 // printing
646 void print(outputStream* out = tty) const PRODUCT_RETURN;
647 };
650 class IntervalWalker : public CompilationResourceObj {
651 protected:
652 Compilation* _compilation;
653 LinearScan* _allocator;
655 Interval* _unhandled_first[nofKinds]; // sorted list of intervals, not life before the current position
656 Interval* _active_first [nofKinds]; // sorted list of intervals, life at the current position
657 Interval* _inactive_first [nofKinds]; // sorted list of intervals, intervals in a life time hole at the current position
659 Interval* _current; // the current interval coming from unhandled list
660 int _current_position; // the current position (intercept point through the intervals)
661 IntervalKind _current_kind; // and whether it is fixed_kind or any_kind.
664 Compilation* compilation() const { return _compilation; }
665 LinearScan* allocator() const { return _allocator; }
667 // unified bailout support
668 void bailout(const char* msg) const { compilation()->bailout(msg); }
669 bool bailed_out() const { return compilation()->bailed_out(); }
671 void check_bounds(IntervalKind kind) { assert(kind >= fixedKind && kind <= anyKind, "invalid interval_kind"); }
673 Interval** unhandled_first_addr(IntervalKind kind) { check_bounds(kind); return &_unhandled_first[kind]; }
674 Interval** active_first_addr(IntervalKind kind) { check_bounds(kind); return &_active_first[kind]; }
675 Interval** inactive_first_addr(IntervalKind kind) { check_bounds(kind); return &_inactive_first[kind]; }
677 void append_unsorted(Interval** first, Interval* interval);
678 void append_sorted(Interval** first, Interval* interval);
679 void append_to_unhandled(Interval** list, Interval* interval);
681 bool remove_from_list(Interval** list, Interval* i);
682 void remove_from_list(Interval* i);
684 void next_interval();
685 Interval* current() const { return _current; }
686 IntervalKind current_kind() const { return _current_kind; }
688 void walk_to(IntervalState state, int from);
690 // activate_current() is called when an unhandled interval becomes active (in current(), current_kind()).
691 // Return false if current() should not be moved the the active interval list.
692 // It is safe to append current to any interval list but the unhandled list.
693 virtual bool activate_current() { return true; }
695 // interval_moved() is called whenever an interval moves from one interval list to another.
696 // In the implementation of this method it is prohibited to move the interval to any list.
697 virtual void interval_moved(Interval* interval, IntervalKind kind, IntervalState from, IntervalState to);
699 public:
700 IntervalWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first);
702 Interval* unhandled_first(IntervalKind kind) { check_bounds(kind); return _unhandled_first[kind]; }
703 Interval* active_first(IntervalKind kind) { check_bounds(kind); return _active_first[kind]; }
704 Interval* inactive_first(IntervalKind kind) { check_bounds(kind); return _inactive_first[kind]; }
706 // active contains the intervals that are live after the lir_op
707 void walk_to(int lir_op_id);
708 // active contains the intervals that are live before the lir_op
709 void walk_before(int lir_op_id) { walk_to(lir_op_id-1); }
710 // walk through all intervals
711 void walk() { walk_to(max_jint); }
713 int current_position() { return _current_position; }
714 };
717 // The actual linear scan register allocator
718 class LinearScanWalker : public IntervalWalker {
719 enum {
720 any_reg = LinearScan::any_reg
721 };
723 private:
724 int _first_reg; // the reg. number of the first phys. register
725 int _last_reg; // the reg. nmber of the last phys. register
726 int _num_phys_regs; // required by current interval
727 bool _adjacent_regs; // have lo/hi words of phys. regs be adjacent
729 int _use_pos[LinearScan::nof_regs];
730 int _block_pos[LinearScan::nof_regs];
731 IntervalList* _spill_intervals[LinearScan::nof_regs];
733 MoveResolver _move_resolver; // for ordering spill moves
735 // accessors mapped to same functions in class LinearScan
736 int block_count() const { return allocator()->block_count(); }
737 BlockBegin* block_at(int idx) const { return allocator()->block_at(idx); }
738 BlockBegin* block_of_op_with_id(int op_id) const { return allocator()->block_of_op_with_id(op_id); }
740 void init_use_lists(bool only_process_use_pos);
741 void exclude_from_use(int reg);
742 void exclude_from_use(Interval* i);
743 void set_use_pos(int reg, Interval* i, int use_pos, bool only_process_use_pos);
744 void set_use_pos(Interval* i, int use_pos, bool only_process_use_pos);
745 void set_block_pos(int reg, Interval* i, int block_pos);
746 void set_block_pos(Interval* i, int block_pos);
748 void free_exclude_active_fixed();
749 void free_exclude_active_any();
750 void free_collect_inactive_fixed(Interval* cur);
751 void free_collect_inactive_any(Interval* cur);
752 void free_collect_unhandled(IntervalKind kind, Interval* cur);
753 void spill_exclude_active_fixed();
754 void spill_block_unhandled_fixed(Interval* cur);
755 void spill_block_inactive_fixed(Interval* cur);
756 void spill_collect_active_any();
757 void spill_collect_inactive_any(Interval* cur);
759 void insert_move(int op_id, Interval* src_it, Interval* dst_it);
760 int find_optimal_split_pos(BlockBegin* min_block, BlockBegin* max_block, int max_split_pos);
761 int find_optimal_split_pos(Interval* it, int min_split_pos, int max_split_pos, bool do_loop_optimization);
762 void split_before_usage(Interval* it, int min_split_pos, int max_split_pos);
763 void split_for_spilling(Interval* it);
764 void split_stack_interval(Interval* it);
765 void split_when_partial_register_available(Interval* it, int register_available_until);
766 void split_and_spill_interval(Interval* it);
768 int find_free_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split);
769 int find_free_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split);
770 bool alloc_free_reg(Interval* cur);
772 int find_locked_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split);
773 int find_locked_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split);
774 void split_and_spill_intersecting_intervals(int reg, int regHi);
775 void alloc_locked_reg(Interval* cur);
777 bool no_allocation_possible(Interval* cur);
778 void update_phys_reg_range(bool requires_cpu_register);
779 void init_vars_for_alloc(Interval* cur);
780 bool pd_init_regs_for_alloc(Interval* cur);
782 void combine_spilled_intervals(Interval* cur);
783 bool is_move(LIR_Op* op, Interval* from, Interval* to);
785 bool activate_current();
787 public:
788 LinearScanWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first);
790 // must be called when all intervals are allocated
791 void finish_allocation() { _move_resolver.resolve_and_append_moves(); }
792 };
796 /*
797 When a block has more than one predecessor, and all predecessors end with
798 the same sequence of move-instructions, than this moves can be placed once
799 at the beginning of the block instead of multiple times in the predecessors.
801 Similarly, when a block has more than one successor, then equal sequences of
802 moves at the beginning of the successors can be placed once at the end of
803 the block. But because the moves must be inserted before all branch
804 instructions, this works only when there is exactly one conditional branch
805 at the end of the block (because the moves must be inserted before all
806 branches, but after all compares).
808 This optimization affects all kind of moves (reg->reg, reg->stack and
809 stack->reg). Because this optimization works best when a block contains only
810 few moves, it has a huge impact on the number of blocks that are totally
811 empty.
812 */
813 class EdgeMoveOptimizer : public StackObj {
814 private:
815 // the class maintains a list with all lir-instruction-list of the
816 // successors (predecessors) and the current index into the lir-lists
817 LIR_OpListStack _edge_instructions;
818 intStack _edge_instructions_idx;
820 void init_instructions();
821 void append_instructions(LIR_OpList* instructions, int instructions_idx);
822 LIR_Op* instruction_at(int edge);
823 void remove_cur_instruction(int edge, bool decrement_index);
825 bool operations_different(LIR_Op* op1, LIR_Op* op2);
827 void optimize_moves_at_block_end(BlockBegin* cur);
828 void optimize_moves_at_block_begin(BlockBegin* cur);
830 EdgeMoveOptimizer();
832 public:
833 static void optimize(BlockList* code);
834 };
838 class ControlFlowOptimizer : public StackObj {
839 private:
840 BlockList _original_preds;
842 enum {
843 ShortLoopSize = 5
844 };
845 void reorder_short_loop(BlockList* code, BlockBegin* header_block, int header_idx);
846 void reorder_short_loops(BlockList* code);
848 bool can_delete_block(BlockBegin* cur);
849 void substitute_branch_target(BlockBegin* cur, BlockBegin* target_from, BlockBegin* target_to);
850 void delete_empty_blocks(BlockList* code);
852 void delete_unnecessary_jumps(BlockList* code);
853 void delete_jumps_to_return(BlockList* code);
855 DEBUG_ONLY(void verify(BlockList* code);)
857 ControlFlowOptimizer();
858 public:
859 static void optimize(BlockList* code);
860 };
863 #ifndef PRODUCT
865 // Helper class for collecting statistics of LinearScan
866 class LinearScanStatistic : public StackObj {
867 public:
868 enum Counter {
869 // general counters
870 counter_method,
871 counter_fpu_method,
872 counter_loop_method,
873 counter_exception_method,
874 counter_loop,
875 counter_block,
876 counter_loop_block,
877 counter_exception_block,
878 counter_interval,
879 counter_fixed_interval,
880 counter_range,
881 counter_fixed_range,
882 counter_use_pos,
883 counter_fixed_use_pos,
884 counter_spill_slots,
885 blank_line_1,
887 // counter for classes of lir instructions
888 counter_instruction,
889 counter_label,
890 counter_entry,
891 counter_return,
892 counter_call,
893 counter_move,
894 counter_cmp,
895 counter_cond_branch,
896 counter_uncond_branch,
897 counter_stub_branch,
898 counter_alu,
899 counter_alloc,
900 counter_sync,
901 counter_throw,
902 counter_unwind,
903 counter_typecheck,
904 counter_fpu_stack,
905 counter_misc_inst,
906 counter_other_inst,
907 blank_line_2,
909 // counter for different types of moves
910 counter_move_total,
911 counter_move_reg_reg,
912 counter_move_reg_stack,
913 counter_move_stack_reg,
914 counter_move_stack_stack,
915 counter_move_reg_mem,
916 counter_move_mem_reg,
917 counter_move_const_any,
919 number_of_counters,
920 invalid_counter = -1
921 };
923 private:
924 int _counters_sum[number_of_counters];
925 int _counters_max[number_of_counters];
927 void inc_counter(Counter idx, int value = 1) { _counters_sum[idx] += value; }
929 const char* counter_name(int counter_idx);
930 Counter base_counter(int counter_idx);
932 void sum_up(LinearScanStatistic &method_statistic);
933 void collect(LinearScan* allocator);
935 public:
936 LinearScanStatistic();
937 void print(const char* title);
938 static void compute(LinearScan* allocator, LinearScanStatistic &global_statistic);
939 };
942 // Helper class for collecting compilation time of LinearScan
943 class LinearScanTimers : public StackObj {
944 public:
945 enum Timer {
946 timer_do_nothing,
947 timer_number_instructions,
948 timer_compute_local_live_sets,
949 timer_compute_global_live_sets,
950 timer_build_intervals,
951 timer_sort_intervals_before,
952 timer_allocate_registers,
953 timer_resolve_data_flow,
954 timer_sort_intervals_after,
955 timer_eliminate_spill_moves,
956 timer_assign_reg_num,
957 timer_allocate_fpu_stack,
958 timer_optimize_lir,
960 number_of_timers
961 };
963 private:
964 elapsedTimer _timers[number_of_timers];
965 const char* timer_name(int idx);
967 public:
968 LinearScanTimers();
970 void begin_method(); // called for each method when register allocation starts
971 void end_method(LinearScan* allocator); // called for each method when register allocation completed
972 void print(double total_time); // called before termination of VM to print global summary
974 elapsedTimer* timer(int idx) { return &(_timers[idx]); }
975 };
978 #endif // ifndef PRODUCT
981 // Pick up platform-dependent implementation details
982 #ifdef TARGET_ARCH_x86
983 # include "c1_LinearScan_x86.hpp"
984 #endif
985 #ifdef TARGET_ARCH_mips
986 # include "c1_LinearScan_mips.hpp"
987 #endif
988 #ifdef TARGET_ARCH_sparc
989 # include "c1_LinearScan_sparc.hpp"
990 #endif
991 #ifdef TARGET_ARCH_arm
992 # include "c1_LinearScan_arm.hpp"
993 #endif
994 #ifdef TARGET_ARCH_ppc
995 # include "c1_LinearScan_ppc.hpp"
996 #endif
999 #endif // SHARE_VM_C1_C1_LINEARSCAN_HPP