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"