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