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