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