1 /*

     2  * Copyright 2005-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 class DebugInfoCache;

    26 class FpuStackAllocator;

    27 class IRScopeDebugInfo;

    28 class Interval;

    29 class IntervalWalker;

    30 class LIRGenerator;

    31 class LinearScan;

    32 class MoveResolver;

    33 class Range;

    34 

    35 define_array(IntervalArray, Interval*)

    36 define_stack(IntervalList, IntervalArray)

    37 

    38 define_array(IntervalsArray, IntervalList*)

    39 define_stack(IntervalsList, IntervalsArray)

    40 

    41 define_array(OopMapArray, OopMap*)

    42 define_stack(OopMapList, OopMapArray)

    43 

    44 define_array(ScopeValueArray, ScopeValue*)

    45 

    46 define_array(LIR_OpListArray, LIR_OpList*);

    47 define_stack(LIR_OpListStack, LIR_OpListArray);

    48 

    49 

    50 enum IntervalUseKind {

    51   // priority of use kinds must be ascending

    52   noUse = 0,

    53   loopEndMarker = 1,

    54   shouldHaveRegister = 2,

    55   mustHaveRegister = 3,

    56 

    57   firstValidKind = 1,

    58   lastValidKind = 3

    59 };

    60 define_array(UseKindArray, IntervalUseKind)

    61 define_stack(UseKindStack, UseKindArray)

    62 

    63 

    64 enum IntervalKind {

    65   fixedKind = 0,  // interval pre-colored by LIR_Generator

    66   anyKind   = 1,  // no register/memory allocated by LIR_Generator

    67   nofKinds,

    68   firstKind = fixedKind

    69 };

    70 

    71 

    72 // during linear scan an interval is in one of four states in

    73 enum IntervalState {

    74   unhandledState = 0, // unhandled state (not processed yet)

    75   activeState   = 1,  // life and is in a physical register

    76   inactiveState = 2,  // in a life time hole and is in a physical register

    77   handledState  = 3,  // spilled or not life again

    78   invalidState = -1

    79 };

    80 

    81 

    82 enum IntervalSpillState {

    83   noDefinitionFound,  // starting state of calculation: no definition found yet

    84   oneDefinitionFound, // one definition has already been found.

    85                       // Note: two consecutive definitions are treated as one (e.g. consecutive move and add because of two-operand LIR form)

    86                       // the position of this definition is stored in _definition_pos

    87   oneMoveInserted,    // one spill move has already been inserted.

    88   storeAtDefinition,  // the interval should be stored immediately after its definition because otherwise

    89                       // there would be multiple redundant stores

    90   startInMemory,      // the interval starts in memory (e.g. method parameter), so a store is never necessary

    91   noOptimization      // the interval has more then one definition (e.g. resulting from phi moves), so stores to memory are not optimized

    92 };

    93 

    94 

    95 #define for_each_interval_kind(kind) \

    96   for (IntervalKind kind = firstKind; kind < nofKinds; kind = (IntervalKind)(kind + 1))

    97 

    98 #define for_each_visitor_mode(mode) \

    99   for (LIR_OpVisitState::OprMode mode = LIR_OpVisitState::firstMode; mode < LIR_OpVisitState::numModes; mode = (LIR_OpVisitState::OprMode)(mode + 1))

   100 

   101 

   102 class LinearScan : public CompilationResourceObj {

   103   // declare classes used by LinearScan as friends because they

   104   // need a wide variety of functions declared here

   105   //

   106   // Only the small interface to the rest of the compiler is public

   107   friend class Interval;

   108   friend class IntervalWalker;

   109   friend class LinearScanWalker;

   110   friend class FpuStackAllocator;

   111   friend class MoveResolver;

   112   friend class LinearScanStatistic;

   113   friend class LinearScanTimers;

   114   friend class RegisterVerifier;

   115 

   116  public:

   117   enum {

   118     any_reg = -1,

   119     nof_cpu_regs = pd_nof_cpu_regs_linearscan,

   120     nof_fpu_regs = pd_nof_fpu_regs_linearscan,

   121     nof_xmm_regs = pd_nof_xmm_regs_linearscan,

   122     nof_regs = nof_cpu_regs + nof_fpu_regs + nof_xmm_regs

   123   };

   124 

   125  private:

   126   Compilation*              _compilation;

   127   IR*                       _ir;

   128   LIRGenerator*             _gen;

   129   FrameMap*                 _frame_map;

   130 

   131   BlockList                 _cached_blocks;     // cached list with all blocks in linear-scan order (only correct if original list keeps unchanged)

   132   int                       _num_virtual_regs;  // number of virtual registers (without new registers introduced because of splitting intervals)

   133   bool                      _has_fpu_registers; // true if this method uses any floating point registers (and so fpu stack allocation is necessary)

   134   int                       _num_calls;         // total number of calls in this method

   135   int                       _max_spills;        // number of stack slots used for intervals allocated to memory

   136   int                       _unused_spill_slot; // unused spill slot for a single-word value because of alignment of a double-word value

   137 

   138   IntervalList              _intervals;         // mapping from register number to interval

   139   IntervalList*             _new_intervals_from_allocation; // list with all intervals created during allocation when an existing interval is split

   140   IntervalArray*            _sorted_intervals;  // intervals sorted by Interval::from()

   141 

   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   BitMap                    _has_info;          // bit set for each LIR_Op id that has a CodeEmitInfo

   145   BitMap                    _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 IA32

   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 

   345   int append_scope_value_for_constant(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values);

   346   int append_scope_value_for_operand(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values);

   347   int append_scope_value(int op_id, Value value, GrowableArray<ScopeValue*>* scope_values);

   348 

   349   IRScopeDebugInfo* compute_debug_info_for_scope(int op_id, IRScope* cur_scope, ValueStack* cur_state, ValueStack* innermost_state, int cur_bci, int stack_end, int locks_end);

   350   void compute_debug_info(CodeEmitInfo* info, int op_id);

   351 

   352   void assign_reg_num(LIR_OpList* instructions, IntervalWalker* iw);

   353   void assign_reg_num();

   354 

   355 

   356   // Phase 8: fpu stack allocation

   357   // (Used only on x86 when fpu operands are present)

   358   void allocate_fpu_stack();

   359 

   360 

   361   // helper functions for printing state

   362 #ifndef PRODUCT

   363   static void print_bitmap(BitMap& bitmap);

   364   void        print_intervals(const char* label);

   365   void        print_lir(int level, const char* label, bool hir_valid = true);

   366 #endif

   367 

   368 #ifdef ASSERT

   369   // verification functions for allocation

   370   // (check that all intervals have a correct register and that no registers are overwritten)

   371   void verify();

   372   void verify_intervals();

   373   void verify_no_oops_in_fixed_intervals();

   374   void verify_constants();

   375   void verify_registers();

   376 #endif

   377 

   378  public:

   379   // creation

   380   LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map);

   381 

   382   // main entry function: perform linear scan register allocation

   383   void             do_linear_scan();

   384 

   385   // accessors used by Compilation

   386   int         max_spills()  const { return _max_spills; }

   387   int         num_calls() const   { assert(_num_calls >= 0, "not set"); return _num_calls; }

   388 

   389   // entry functions for printing

   390 #ifndef PRODUCT

   391   static void print_statistics();

   392   static void print_timers(double total);

   393 #endif

   394 };

   395 

   396 

   397 // Helper class for ordering moves that are inserted at the same position in the LIR

   398 // When moves between registers are inserted, it is important that the moves are

   399 // ordered such that no register is overwritten. So moves from register to stack

   400 // are processed prior to moves from stack to register. When moves have circular

   401 // dependencies, a temporary stack slot is used to break the circle.

   402 // The same logic is used in the LinearScanWalker and in LinearScan during resolve_data_flow

   403 // and therefore factored out in a separate class

   404 class MoveResolver: public StackObj {

   405  private:

   406   LinearScan*      _allocator;

   407 

   408   LIR_List*        _insert_list;

   409   int              _insert_idx;

   410   LIR_InsertionBuffer _insertion_buffer; // buffer where moves are inserted

   411 

   412   IntervalList     _mapping_from;

   413   LIR_OprList      _mapping_from_opr;

   414   IntervalList     _mapping_to;

   415   bool             _multiple_reads_allowed;

   416   int              _register_blocked[LinearScan::nof_regs];

   417 

   418   int  register_blocked(int reg)                    { assert(reg >= 0 && reg < LinearScan::nof_regs, "out of bounds"); return _register_blocked[reg]; }

   419   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; }

   420 

   421   void block_registers(Interval* it);

   422   void unblock_registers(Interval* it);

   423   bool save_to_process_move(Interval* from, Interval* to);

   424 

   425   void create_insertion_buffer(LIR_List* list);

   426   void append_insertion_buffer();

   427   void insert_move(Interval* from_interval, Interval* to_interval);

   428   void insert_move(LIR_Opr from_opr, Interval* to_interval);

   429 

   430   DEBUG_ONLY(void verify_before_resolve();)

   431   void resolve_mappings();

   432  public:

   433   MoveResolver(LinearScan* allocator);

   434 

   435   DEBUG_ONLY(void check_empty();)

   436   void set_multiple_reads_allowed() { _multiple_reads_allowed = true; }

   437   void set_insert_position(LIR_List* insert_list, int insert_idx);

   438   void move_insert_position(LIR_List* insert_list, int insert_idx);

   439   void add_mapping(Interval* from, Interval* to);

   440   void add_mapping(LIR_Opr from, Interval* to);

   441   void resolve_and_append_moves();

   442 

   443   LinearScan* allocator()   { return _allocator; }

   444   bool has_mappings()       { return _mapping_from.length() > 0; }

   445 };

   446 

   447 

   448 class Range : public CompilationResourceObj {

   449   friend class Interval;

   450 

   451  private:

   452   static Range*    _end;       // sentinel (from == to == max_jint)

   453 

   454   int              _from;      // from (inclusive)

   455   int              _to;        // to (exclusive)

   456   Range*           _next;      // linear list of Ranges

   457 

   458   // used only by class Interval, so hide them

   459   bool             intersects(Range* r) const    { return intersects_at(r) != -1; }

   460   int              intersects_at(Range* r) const;

   461 

   462  public:

   463   Range(int from, int to, Range* next);

   464 

   465   static void      initialize();

   466   static Range*    end()                         { return _end; }

   467 

   468   int              from() const                  { return _from; }

   469   int              to()   const                  { return _to; }

   470   Range*           next() const                  { return _next; }

   471   void             set_from(int from)            { _from = from; }

   472   void             set_to(int to)                { _to = to; }

   473   void             set_next(Range* next)         { _next = next; }

   474 

   475   // for testing

   476   void             print(outputStream* out = tty) const PRODUCT_RETURN;

   477 };

   478 

   479 

   480 // Interval is an ordered list of disjoint ranges.

   481 

   482 // For pre-colored double word LIR_Oprs, one interval is created for

   483 // the low word register and one is created for the hi word register.

   484 // On Intel for FPU double registers only one interval is created.  At

   485 // all times assigned_reg contains the reg. number of the physical

   486 // register.

   487 

   488 // For LIR_Opr in virtual registers a single interval can represent

   489 // single and double word values.  When a physical register is

   490 // assigned to the interval, assigned_reg contains the

   491 // phys. reg. number and for double word values assigned_regHi the

   492 // phys. reg. number of the hi word if there is any.  For spilled

   493 // intervals assigned_reg contains the stack index.  assigned_regHi is

   494 // always -1.

   495 

   496 class Interval : public CompilationResourceObj {

   497  private:

   498   static Interval* _end;          // sentinel (interval with only range Range::end())

   499 

   500   int              _reg_num;

   501   BasicType        _type;         // valid only for virtual registers

   502   Range*           _first;        // sorted list of Ranges

   503   intStack         _use_pos_and_kinds; // sorted list of use-positions and their according use-kinds

   504 

   505   Range*           _current;      // interval iteration: the current Range

   506   Interval*        _next;         // interval iteration: sorted list of Intervals (ends with sentinel)

   507   IntervalState    _state;        // interval iteration: to which set belongs this interval

   508 

   509 

   510   int              _assigned_reg;

   511   int              _assigned_regHi;

   512 

   513   int              _cached_to;    // cached value: to of last range (-1: not cached)

   514   LIR_Opr          _cached_opr;

   515   VMReg            _cached_vm_reg;

   516 

   517   Interval*        _split_parent;           // the original interval where this interval is derived from

   518   IntervalList     _split_children;         // list of all intervals that are split off from this interval (only available for split parents)

   519   Interval*        _current_split_child;    // the current split child that has been active or inactive last (always stored in split parents)

   520 

   521   int              _canonical_spill_slot;   // the stack slot where all split parts of this interval are spilled to (always stored in split parents)

   522   bool             _insert_move_when_activated; // true if move is inserted between _current_split_child and this interval when interval gets active the first time

   523   IntervalSpillState _spill_state;          // for spill move optimization

   524   int              _spill_definition_pos;   // position where the interval is defined (if defined only once)

   525   Interval*        _register_hint;          // this interval should be in the same register as the hint interval

   526 

   527   int              calc_to();

   528   Interval*        new_split_child();

   529  public:

   530   Interval(int reg_num);

   531 

   532   static void      initialize();

   533   static Interval* end()                         { return _end; }

   534 

   535   // accessors

   536   int              reg_num() const               { return _reg_num; }

   537   void             set_reg_num(int r)            { assert(_reg_num == -1, "cannot change reg_num"); _reg_num = r; }

   538   BasicType        type() const                  { assert(_reg_num == -1 || _reg_num >= LIR_OprDesc::vreg_base, "cannot access type for fixed interval"); return _type; }

   539   void             set_type(BasicType type)      { assert(_reg_num < LIR_OprDesc::vreg_base || _type == T_ILLEGAL || _type == type, "overwriting existing type"); _type = type; }

   540 

   541   Range*           first() const                 { return _first; }

   542   int              from() const                  { return _first->from(); }

   543   int              to()                          { if (_cached_to == -1) _cached_to = calc_to(); assert(_cached_to == calc_to(), "invalid cached value"); return _cached_to; }

   544   int              num_use_positions() const     { return _use_pos_and_kinds.length() / 2; }

   545 

   546   Interval*        next() const                  { return _next; }

   547   Interval**       next_addr()                   { return &_next; }

   548   void             set_next(Interval* next)      { _next = next; }

   549 

   550   int              assigned_reg() const          { return _assigned_reg; }

   551   int              assigned_regHi() const        { return _assigned_regHi; }

   552   void             assign_reg(int reg)           { _assigned_reg = reg; _assigned_regHi = LinearScan::any_reg; }

   553   void             assign_reg(int reg,int regHi) { _assigned_reg = reg; _assigned_regHi = regHi; }

   554 

   555   Interval*        register_hint(bool search_split_child = true) const; // calculation needed

   556   void             set_register_hint(Interval* i) { _register_hint = i; }

   557 

   558   int              state() const                 { return _state; }

   559   void             set_state(IntervalState s)    { _state = s; }

   560 

   561   // access to split parent and split children

   562   bool             is_split_parent() const       { return _split_parent == this; }

   563   bool             is_split_child() const        { return _split_parent != this; }

   564   Interval*        split_parent() const          { assert(_split_parent->is_split_parent(), "must be"); return _split_parent; }

   565   Interval*        split_child_at_op_id(int op_id, LIR_OpVisitState::OprMode mode);

   566   Interval*        split_child_before_op_id(int op_id);

   567   bool             split_child_covers(int op_id, LIR_OpVisitState::OprMode mode);

   568   DEBUG_ONLY(void  check_split_children();)

   569 

   570   // information stored in split parent, but available for all children

   571   int              canonical_spill_slot() const            { return split_parent()->_canonical_spill_slot; }

   572   void             set_canonical_spill_slot(int slot)      { assert(split_parent()->_canonical_spill_slot == -1, "overwriting existing value"); split_parent()->_canonical_spill_slot = slot; }

   573   Interval*        current_split_child() const             { return split_parent()->_current_split_child; }

   574   void             make_current_split_child()              { split_parent()->_current_split_child = this; }

   575 

   576   bool             insert_move_when_activated() const      { return _insert_move_when_activated; }

   577   void             set_insert_move_when_activated(bool b)  { _insert_move_when_activated = b; }

   578 

   579   // for spill optimization

   580   IntervalSpillState spill_state() const         { return split_parent()->_spill_state; }

   581   int              spill_definition_pos() const  { return split_parent()->_spill_definition_pos; }

   582   void             set_spill_state(IntervalSpillState state) {  assert(state >= spill_state(), "state cannot decrease"); split_parent()->_spill_state = state; }

   583   void             set_spill_definition_pos(int pos) { assert(spill_definition_pos() == -1, "cannot set the position twice"); split_parent()->_spill_definition_pos = pos; }

   584   // returns true if this interval has a shadow copy on the stack that is always correct

   585   bool             always_in_memory() const      { return split_parent()->_spill_state == storeAtDefinition || split_parent()->_spill_state == startInMemory; }

   586 

   587   // caching of values that take time to compute and are used multiple times

   588   LIR_Opr          cached_opr() const            { return _cached_opr; }

   589   VMReg            cached_vm_reg() const         { return _cached_vm_reg; }

   590   void             set_cached_opr(LIR_Opr opr)   { _cached_opr = opr; }

   591   void             set_cached_vm_reg(VMReg reg)  { _cached_vm_reg = reg; }

   592 

   593   // access to use positions

   594   int    first_usage(IntervalUseKind min_use_kind) const;           // id of the first operation requiring this interval in a register

   595   int    next_usage(IntervalUseKind min_use_kind, int from) const;  // id of next usage seen from the given position

   596   int    next_usage_exact(IntervalUseKind exact_use_kind, int from) const;

   597   int    previous_usage(IntervalUseKind min_use_kind, int from) const;

   598 

   599   // manipulating intervals

   600   void   add_use_pos(int pos, IntervalUseKind use_kind);

   601   void   add_range(int from, int to);

   602   Interval* split(int split_pos);

   603   Interval* split_from_start(int split_pos);

   604   void remove_first_use_pos()                    { _use_pos_and_kinds.truncate(_use_pos_and_kinds.length() - 2); }

   605 

   606   // test intersection

   607   bool   covers(int op_id, LIR_OpVisitState::OprMode mode) const;

   608   bool   has_hole_between(int from, int to);

   609   bool   intersects(Interval* i) const           { return _first->intersects(i->_first); }

   610   int    intersects_at(Interval* i) const        { return _first->intersects_at(i->_first); }

   611 

   612   // range iteration

   613   void   rewind_range()                          { _current = _first; }

   614   void   next_range()                            { assert(this != _end, "not allowed on sentinel"); _current = _current->next(); }

   615   int    current_from() const                    { return _current->from(); }

   616   int    current_to() const                      { return _current->to(); }

   617   bool   current_at_end() const                  { return _current == Range::end(); }

   618   bool   current_intersects(Interval* it)        { return _current->intersects(it->_current); };

   619   int    current_intersects_at(Interval* it)     { return _current->intersects_at(it->_current); };

   620 

   621   // printing

   622   void print(outputStream* out = tty) const      PRODUCT_RETURN;

   623 };

   624 

   625 

   626 class IntervalWalker : public CompilationResourceObj {

   627  protected:

   628   Compilation*     _compilation;

   629   LinearScan*      _allocator;

   630 

   631   Interval*        _unhandled_first[nofKinds];  // sorted list of intervals, not life before the current position

   632   Interval*        _active_first   [nofKinds];  // sorted list of intervals, life at the current position

   633   Interval*        _inactive_first [nofKinds];  // sorted list of intervals, intervals in a life time hole at the current position

   634 

   635   Interval*        _current;                     // the current interval coming from unhandled list

   636   int              _current_position;            // the current position (intercept point through the intervals)

   637   IntervalKind     _current_kind;                // and whether it is fixed_kind or any_kind.

   638 

   639 

   640   Compilation*     compilation() const               { return _compilation; }

   641   LinearScan*      allocator() const                 { return _allocator; }

   642 

   643   // unified bailout support

   644   void             bailout(const char* msg) const    { compilation()->bailout(msg); }

   645   bool             bailed_out() const                { return compilation()->bailed_out(); }

   646 

   647   void check_bounds(IntervalKind kind) { assert(kind >= fixedKind && kind <= anyKind, "invalid interval_kind"); }

   648 

   649   Interval** unhandled_first_addr(IntervalKind kind) { check_bounds(kind); return &_unhandled_first[kind]; }

   650   Interval** active_first_addr(IntervalKind kind)    { check_bounds(kind); return &_active_first[kind]; }

   651   Interval** inactive_first_addr(IntervalKind kind)  { check_bounds(kind); return &_inactive_first[kind]; }

   652 

   653   void append_unsorted(Interval** first, Interval* interval);

   654   void append_sorted(Interval** first, Interval* interval);

   655   void append_to_unhandled(Interval** list, Interval* interval);

   656 

   657   bool remove_from_list(Interval** list, Interval* i);

   658   void remove_from_list(Interval* i);

   659 

   660   void next_interval();

   661   Interval*        current() const               { return _current; }

   662   IntervalKind     current_kind() const          { return _current_kind; }

   663 

   664   void walk_to(IntervalState state, int from);

   665 

   666   // activate_current() is called when an unhandled interval becomes active (in current(), current_kind()).

   667   // Return false if current() should not be moved the the active interval list.

   668   // It is safe to append current to any interval list but the unhandled list.

   669   virtual bool activate_current() { return true; }

   670 

   671   // interval_moved() is called whenever an interval moves from one interval list to another.

   672   // In the implementation of this method it is prohibited to move the interval to any list.

   673   virtual void interval_moved(Interval* interval, IntervalKind kind, IntervalState from, IntervalState to);

   674 

   675  public:

   676   IntervalWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first);

   677 

   678   Interval* unhandled_first(IntervalKind kind)   { check_bounds(kind); return _unhandled_first[kind]; }

   679   Interval* active_first(IntervalKind kind)      { check_bounds(kind); return _active_first[kind]; }

   680   Interval* inactive_first(IntervalKind kind)    { check_bounds(kind); return _inactive_first[kind]; }

   681 

   682   // active contains the intervals that are live after the lir_op

   683   void walk_to(int lir_op_id);

   684   // active contains the intervals that are live before the lir_op

   685   void walk_before(int lir_op_id)  { walk_to(lir_op_id-1); }

   686   // walk through all intervals

   687   void walk()                      { walk_to(max_jint); }

   688 

   689   int current_position()           { return _current_position; }

   690 };

   691 

   692 

   693 // The actual linear scan register allocator

   694 class LinearScanWalker : public IntervalWalker {

   695   enum {

   696     any_reg = LinearScan::any_reg

   697   };

   698 

   699  private:

   700   int              _first_reg;       // the reg. number of the first phys. register

   701   int              _last_reg;        // the reg. nmber of the last phys. register

   702   int              _num_phys_regs;   // required by current interval

   703   bool             _adjacent_regs;   // have lo/hi words of phys. regs be adjacent

   704 

   705   int              _use_pos[LinearScan::nof_regs];

   706   int              _block_pos[LinearScan::nof_regs];

   707   IntervalList*    _spill_intervals[LinearScan::nof_regs];

   708 

   709   MoveResolver     _move_resolver;   // for ordering spill moves

   710 

   711   // accessors mapped to same functions in class LinearScan

   712   int         block_count() const      { return allocator()->block_count(); }

   713   BlockBegin* block_at(int idx) const  { return allocator()->block_at(idx); }

   714   BlockBegin* block_of_op_with_id(int op_id) const { return allocator()->block_of_op_with_id(op_id); }

   715 

   716   void init_use_lists(bool only_process_use_pos);

   717   void exclude_from_use(int reg);

   718   void exclude_from_use(Interval* i);

   719   void set_use_pos(int reg, Interval* i, int use_pos, bool only_process_use_pos);

   720   void set_use_pos(Interval* i, int use_pos, bool only_process_use_pos);

   721   void set_block_pos(int reg, Interval* i, int block_pos);

   722   void set_block_pos(Interval* i, int block_pos);

   723 

   724   void free_exclude_active_fixed();

   725   void free_exclude_active_any();

   726   void free_collect_inactive_fixed(Interval* cur);

   727   void free_collect_inactive_any(Interval* cur);

   728   void free_collect_unhandled(IntervalKind kind, Interval* cur);

   729   void spill_exclude_active_fixed();

   730   void spill_block_unhandled_fixed(Interval* cur);

   731   void spill_block_inactive_fixed(Interval* cur);

   732   void spill_collect_active_any();

   733   void spill_collect_inactive_any(Interval* cur);

   734 

   735   void insert_move(int op_id, Interval* src_it, Interval* dst_it);

   736   int  find_optimal_split_pos(BlockBegin* min_block, BlockBegin* max_block, int max_split_pos);

   737   int  find_optimal_split_pos(Interval* it, int min_split_pos, int max_split_pos, bool do_loop_optimization);

   738   void split_before_usage(Interval* it, int min_split_pos, int max_split_pos);

   739   void split_for_spilling(Interval* it);

   740   void split_stack_interval(Interval* it);

   741   void split_when_partial_register_available(Interval* it, int register_available_until);

   742   void split_and_spill_interval(Interval* it);

   743 

   744   int  find_free_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split);

   745   int  find_free_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split);

   746   bool alloc_free_reg(Interval* cur);

   747 

   748   int  find_locked_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split);

   749   int  find_locked_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split);

   750   void split_and_spill_intersecting_intervals(int reg, int regHi);

   751   void alloc_locked_reg(Interval* cur);

   752 

   753   bool no_allocation_possible(Interval* cur);

   754   void update_phys_reg_range(bool requires_cpu_register);

   755   void init_vars_for_alloc(Interval* cur);

   756   bool pd_init_regs_for_alloc(Interval* cur);

   757 

   758   void combine_spilled_intervals(Interval* cur);

   759   bool is_move(LIR_Op* op, Interval* from, Interval* to);

   760 

   761   bool activate_current();

   762 

   763  public:

   764   LinearScanWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first);

   765 

   766   // must be called when all intervals are allocated

   767   void             finish_allocation()           { _move_resolver.resolve_and_append_moves(); }

   768 };

   769 

   770 

   771 

   772 /*

   773 When a block has more than one predecessor, and all predecessors end with

   774 the same sequence of move-instructions, than this moves can be placed once

   775 at the beginning of the block instead of multiple times in the predecessors.

   776 

   777 Similarly, when a block has more than one successor, then equal sequences of

   778 moves at the beginning of the successors can be placed once at the end of

   779 the block. But because the moves must be inserted before all branch

   780 instructions, this works only when there is exactly one conditional branch

   781 at the end of the block (because the moves must be inserted before all

   782 branches, but after all compares).

   783 

   784 This optimization affects all kind of moves (reg->reg, reg->stack and

   785 stack->reg). Because this optimization works best when a block contains only

   786 few moves, it has a huge impact on the number of blocks that are totally

   787 empty.

   788 */

   789 class EdgeMoveOptimizer : public StackObj {

   790  private:

   791   // the class maintains a list with all lir-instruction-list of the

   792   // successors (predecessors) and the current index into the lir-lists

   793   LIR_OpListStack _edge_instructions;

   794   intStack        _edge_instructions_idx;

   795 

   796   void init_instructions();

   797   void append_instructions(LIR_OpList* instructions, int instructions_idx);

   798   LIR_Op* instruction_at(int edge);

   799   void remove_cur_instruction(int edge, bool decrement_index);

   800 

   801   bool operations_different(LIR_Op* op1, LIR_Op* op2);

   802 

   803   void optimize_moves_at_block_end(BlockBegin* cur);

   804   void optimize_moves_at_block_begin(BlockBegin* cur);

   805 

   806   EdgeMoveOptimizer();

   807 

   808  public:

   809   static void optimize(BlockList* code);

   810 };

   811 

   812 

   813 

   814 class ControlFlowOptimizer : public StackObj {

   815  private:

   816   BlockList _original_preds;

   817 

   818   enum {

   819     ShortLoopSize = 5

   820   };

   821   void reorder_short_loop(BlockList* code, BlockBegin* header_block, int header_idx);

   822   void reorder_short_loops(BlockList* code);

   823 

   824   bool can_delete_block(BlockBegin* cur);

   825   void substitute_branch_target(BlockBegin* cur, BlockBegin* target_from, BlockBegin* target_to);

   826   void delete_empty_blocks(BlockList* code);

   827 

   828   void delete_unnecessary_jumps(BlockList* code);

   829   void delete_jumps_to_return(BlockList* code);

   830 

   831   DEBUG_ONLY(void verify(BlockList* code);)

   832 

   833   ControlFlowOptimizer();

   834  public:

   835   static void optimize(BlockList* code);

   836 };

   837 

   838 

   839 #ifndef PRODUCT

   840 

   841 // Helper class for collecting statistics of LinearScan

   842 class LinearScanStatistic : public StackObj {

   843  public:

   844   enum Counter {

   845     // general counters

   846     counter_method,

   847     counter_fpu_method,

   848     counter_loop_method,

   849     counter_exception_method,

   850     counter_loop,

   851     counter_block,

   852     counter_loop_block,

   853     counter_exception_block,

   854     counter_interval,

   855     counter_fixed_interval,

   856     counter_range,

   857     counter_fixed_range,

   858     counter_use_pos,

   859     counter_fixed_use_pos,

   860     counter_spill_slots,

   861     blank_line_1,

   862 

   863     // counter for classes of lir instructions

   864     counter_instruction,

   865     counter_label,

   866     counter_entry,

   867     counter_return,

   868     counter_call,

   869     counter_move,

   870     counter_cmp,

   871     counter_cond_branch,

   872     counter_uncond_branch,

   873     counter_stub_branch,

   874     counter_alu,

   875     counter_alloc,

   876     counter_sync,

   877     counter_throw,

   878     counter_unwind,

   879     counter_typecheck,

   880     counter_fpu_stack,

   881     counter_misc_inst,

   882     counter_other_inst,

   883     blank_line_2,

   884 

   885     // counter for different types of moves

   886     counter_move_total,

   887     counter_move_reg_reg,

   888     counter_move_reg_stack,

   889     counter_move_stack_reg,

   890     counter_move_stack_stack,

   891     counter_move_reg_mem,

   892     counter_move_mem_reg,

   893     counter_move_const_any,

   894 

   895     number_of_counters,

   896     invalid_counter = -1

   897   };

   898 

   899  private:

   900   int _counters_sum[number_of_counters];

   901   int _counters_max[number_of_counters];

   902 

   903   void inc_counter(Counter idx, int value = 1) { _counters_sum[idx] += value; }

   904 

   905   const char* counter_name(int counter_idx);

   906   Counter base_counter(int counter_idx);

   907 

   908   void sum_up(LinearScanStatistic &method_statistic);

   909   void collect(LinearScan* allocator);

   910 

   911  public:

   912   LinearScanStatistic();

   913   void print(const char* title);

   914   static void compute(LinearScan* allocator, LinearScanStatistic &global_statistic);

   915 };

   916 

   917 

   918 // Helper class for collecting compilation time of LinearScan

   919 class LinearScanTimers : public StackObj {

   920  public:

   921   enum Timer {

   922     timer_do_nothing,

   923     timer_number_instructions,

   924     timer_compute_local_live_sets,

   925     timer_compute_global_live_sets,

   926     timer_build_intervals,

   927     timer_sort_intervals_before,

   928     timer_allocate_registers,

   929     timer_resolve_data_flow,

   930     timer_sort_intervals_after,

   931     timer_eliminate_spill_moves,

   932     timer_assign_reg_num,

   933     timer_allocate_fpu_stack,

   934     timer_optimize_lir,

   935 

   936     number_of_timers

   937   };

   938 

   939  private:

   940   elapsedTimer _timers[number_of_timers];

   941   const char*  timer_name(int idx);

   942 

   943  public:

   944   LinearScanTimers();

   945 

   946   void begin_method();                     // called for each method when register allocation starts

   947   void end_method(LinearScan* allocator);  // called for each method when register allocation completed

   948   void print(double total_time);           // called before termination of VM to print global summary

   949 

   950   elapsedTimer* timer(int idx) { return &(_timers[idx]); }

   951 };

   952 

   953 

   954 #endif // ifndef PRODUCT

   955 

   956 

   957 // Pick up platform-dependent implementation details

   958 # include "incls/_c1_LinearScan_pd.hpp.incl"