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