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