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