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