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