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