hotspot/src/share/vm/c1/c1_IR.cpp
changeset 1 489c9b5090e2
child 1547 ebdd95407cd4
equal deleted inserted replaced
0:fd16c54261b3 1:489c9b5090e2
       
     1 /*
       
     2  * Copyright 1999-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 # include "incls/_precompiled.incl"
       
    26 # include "incls/_c1_IR.cpp.incl"
       
    27 
       
    28 
       
    29 // Implementation of XHandlers
       
    30 //
       
    31 // Note: This code could eventually go away if we are
       
    32 //       just using the ciExceptionHandlerStream.
       
    33 
       
    34 XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) {
       
    35   ciExceptionHandlerStream s(method);
       
    36   while (!s.is_done()) {
       
    37     _list.append(new XHandler(s.handler()));
       
    38     s.next();
       
    39   }
       
    40   assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent");
       
    41 }
       
    42 
       
    43 // deep copy of all XHandler contained in list
       
    44 XHandlers::XHandlers(XHandlers* other) :
       
    45   _list(other->length())
       
    46 {
       
    47   for (int i = 0; i < other->length(); i++) {
       
    48     _list.append(new XHandler(other->handler_at(i)));
       
    49   }
       
    50 }
       
    51 
       
    52 // Returns whether a particular exception type can be caught.  Also
       
    53 // returns true if klass is unloaded or any exception handler
       
    54 // classes are unloaded.  type_is_exact indicates whether the throw
       
    55 // is known to be exactly that class or it might throw a subtype.
       
    56 bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const {
       
    57   // the type is unknown so be conservative
       
    58   if (!klass->is_loaded()) {
       
    59     return true;
       
    60   }
       
    61 
       
    62   for (int i = 0; i < length(); i++) {
       
    63     XHandler* handler = handler_at(i);
       
    64     if (handler->is_catch_all()) {
       
    65       // catch of ANY
       
    66       return true;
       
    67     }
       
    68     ciInstanceKlass* handler_klass = handler->catch_klass();
       
    69     // if it's unknown it might be catchable
       
    70     if (!handler_klass->is_loaded()) {
       
    71       return true;
       
    72     }
       
    73     // if the throw type is definitely a subtype of the catch type
       
    74     // then it can be caught.
       
    75     if (klass->is_subtype_of(handler_klass)) {
       
    76       return true;
       
    77     }
       
    78     if (!type_is_exact) {
       
    79       // If the type isn't exactly known then it can also be caught by
       
    80       // catch statements where the inexact type is a subtype of the
       
    81       // catch type.
       
    82       // given: foo extends bar extends Exception
       
    83       // throw bar can be caught by catch foo, catch bar, and catch
       
    84       // Exception, however it can't be caught by any handlers without
       
    85       // bar in its type hierarchy.
       
    86       if (handler_klass->is_subtype_of(klass)) {
       
    87         return true;
       
    88       }
       
    89     }
       
    90   }
       
    91 
       
    92   return false;
       
    93 }
       
    94 
       
    95 
       
    96 bool XHandlers::equals(XHandlers* others) const {
       
    97   if (others == NULL) return false;
       
    98   if (length() != others->length()) return false;
       
    99 
       
   100   for (int i = 0; i < length(); i++) {
       
   101     if (!handler_at(i)->equals(others->handler_at(i))) return false;
       
   102   }
       
   103   return true;
       
   104 }
       
   105 
       
   106 bool XHandler::equals(XHandler* other) const {
       
   107   assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco");
       
   108 
       
   109   if (entry_pco() != other->entry_pco()) return false;
       
   110   if (scope_count() != other->scope_count()) return false;
       
   111   if (_desc != other->_desc) return false;
       
   112 
       
   113   assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal");
       
   114   return true;
       
   115 }
       
   116 
       
   117 
       
   118 // Implementation of IRScope
       
   119 
       
   120 BlockBegin* IRScope::header_block(BlockBegin* entry, BlockBegin::Flag f, ValueStack* state) {
       
   121   if (entry == NULL) return NULL;
       
   122   assert(entry->is_set(f), "entry/flag mismatch");
       
   123   // create header block
       
   124   BlockBegin* h = new BlockBegin(entry->bci());
       
   125   BlockEnd* g = new Goto(entry, false);
       
   126   h->set_next(g, entry->bci());
       
   127   h->set_end(g);
       
   128   h->set(f);
       
   129   // setup header block end state
       
   130   ValueStack* s = state->copy(); // can use copy since stack is empty (=> no phis)
       
   131   assert(s->stack_is_empty(), "must have empty stack at entry point");
       
   132   g->set_state(s);
       
   133   return h;
       
   134 }
       
   135 
       
   136 
       
   137 BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) {
       
   138   GraphBuilder gm(compilation, this);
       
   139   NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats());
       
   140   if (compilation->bailed_out()) return NULL;
       
   141   return gm.start();
       
   142 }
       
   143 
       
   144 
       
   145 IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph)
       
   146 : _callees(2)
       
   147 , _compilation(compilation)
       
   148 , _lock_stack_size(-1)
       
   149 , _requires_phi_function(method->max_locals())
       
   150 {
       
   151   _caller             = caller;
       
   152   _caller_bci         = caller == NULL ? -1 : caller_bci;
       
   153   _caller_state       = NULL; // Must be set later if needed
       
   154   _level              = caller == NULL ?  0 : caller->level() + 1;
       
   155   _method             = method;
       
   156   _xhandlers          = new XHandlers(method);
       
   157   _number_of_locks    = 0;
       
   158   _monitor_pairing_ok = method->has_balanced_monitors();
       
   159   _start              = NULL;
       
   160 
       
   161   if (osr_bci == -1) {
       
   162     _requires_phi_function.clear();
       
   163   } else {
       
   164         // selective creation of phi functions is not possibel in osr-methods
       
   165     _requires_phi_function.set_range(0, method->max_locals());
       
   166   }
       
   167 
       
   168   assert(method->holder()->is_loaded() , "method holder must be loaded");
       
   169 
       
   170   // build graph if monitor pairing is ok
       
   171   if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci);
       
   172 }
       
   173 
       
   174 
       
   175 int IRScope::max_stack() const {
       
   176   int my_max = method()->max_stack();
       
   177   int callee_max = 0;
       
   178   for (int i = 0; i < number_of_callees(); i++) {
       
   179     callee_max = MAX2(callee_max, callee_no(i)->max_stack());
       
   180   }
       
   181   return my_max + callee_max;
       
   182 }
       
   183 
       
   184 
       
   185 void IRScope::compute_lock_stack_size() {
       
   186   if (!InlineMethodsWithExceptionHandlers) {
       
   187     _lock_stack_size = 0;
       
   188     return;
       
   189   }
       
   190 
       
   191   // Figure out whether we have to preserve expression stack elements
       
   192   // for parent scopes, and if so, how many
       
   193   IRScope* cur_scope = this;
       
   194   while (cur_scope != NULL && !cur_scope->xhandlers()->has_handlers()) {
       
   195     cur_scope = cur_scope->caller();
       
   196   }
       
   197   _lock_stack_size = (cur_scope == NULL ? 0 :
       
   198                       (cur_scope->caller_state() == NULL ? 0 :
       
   199                        cur_scope->caller_state()->stack_size()));
       
   200 }
       
   201 
       
   202 int IRScope::top_scope_bci() const {
       
   203   assert(!is_top_scope(), "no correct answer for top scope possible");
       
   204   const IRScope* scope = this;
       
   205   while (!scope->caller()->is_top_scope()) {
       
   206     scope = scope->caller();
       
   207   }
       
   208   return scope->caller_bci();
       
   209 }
       
   210 
       
   211 
       
   212 
       
   213 // Implementation of CodeEmitInfo
       
   214 
       
   215 // Stack must be NON-null
       
   216 CodeEmitInfo::CodeEmitInfo(int bci, ValueStack* stack, XHandlers* exception_handlers)
       
   217   : _scope(stack->scope())
       
   218   , _bci(bci)
       
   219   , _scope_debug_info(NULL)
       
   220   , _oop_map(NULL)
       
   221   , _stack(stack)
       
   222   , _exception_handlers(exception_handlers)
       
   223   , _next(NULL)
       
   224   , _id(-1) {
       
   225   assert(_stack != NULL, "must be non null");
       
   226   assert(_bci == SynchronizationEntryBCI || Bytecodes::is_defined(scope()->method()->java_code_at_bci(_bci)), "make sure bci points at a real bytecode");
       
   227 }
       
   228 
       
   229 
       
   230 CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, bool lock_stack_only)
       
   231   : _scope(info->_scope)
       
   232   , _exception_handlers(NULL)
       
   233   , _bci(info->_bci)
       
   234   , _scope_debug_info(NULL)
       
   235   , _oop_map(NULL) {
       
   236   if (lock_stack_only) {
       
   237     if (info->_stack != NULL) {
       
   238       _stack = info->_stack->copy_locks();
       
   239     } else {
       
   240       _stack = NULL;
       
   241     }
       
   242   } else {
       
   243     _stack = info->_stack;
       
   244   }
       
   245 
       
   246   // deep copy of exception handlers
       
   247   if (info->_exception_handlers != NULL) {
       
   248     _exception_handlers = new XHandlers(info->_exception_handlers);
       
   249   }
       
   250 }
       
   251 
       
   252 
       
   253 void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) {
       
   254   // record the safepoint before recording the debug info for enclosing scopes
       
   255   recorder->add_safepoint(pc_offset, _oop_map->deep_copy());
       
   256   _scope_debug_info->record_debug_info(recorder, pc_offset);
       
   257   recorder->end_safepoint(pc_offset);
       
   258 }
       
   259 
       
   260 
       
   261 void CodeEmitInfo::add_register_oop(LIR_Opr opr) {
       
   262   assert(_oop_map != NULL, "oop map must already exist");
       
   263   assert(opr->is_single_cpu(), "should not call otherwise");
       
   264 
       
   265   int frame_size = frame_map()->framesize();
       
   266   int arg_count = frame_map()->oop_map_arg_count();
       
   267   VMReg name = frame_map()->regname(opr);
       
   268   _oop_map->set_oop(name);
       
   269 }
       
   270 
       
   271 
       
   272 
       
   273 
       
   274 // Implementation of IR
       
   275 
       
   276 IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) :
       
   277     _locals_size(in_WordSize(-1))
       
   278   , _num_loops(0) {
       
   279   // initialize data structures
       
   280   ValueType::initialize();
       
   281   Instruction::initialize();
       
   282   BlockBegin::initialize();
       
   283   GraphBuilder::initialize();
       
   284   // setup IR fields
       
   285   _compilation = compilation;
       
   286   _top_scope   = new IRScope(compilation, NULL, -1, method, osr_bci, true);
       
   287   _code        = NULL;
       
   288 }
       
   289 
       
   290 
       
   291 void IR::optimize() {
       
   292   Optimizer opt(this);
       
   293   if (DoCEE) {
       
   294     opt.eliminate_conditional_expressions();
       
   295 #ifndef PRODUCT
       
   296     if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); }
       
   297     if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); }
       
   298 #endif
       
   299   }
       
   300   if (EliminateBlocks) {
       
   301     opt.eliminate_blocks();
       
   302 #ifndef PRODUCT
       
   303     if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); }
       
   304     if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); }
       
   305 #endif
       
   306   }
       
   307   if (EliminateNullChecks) {
       
   308     opt.eliminate_null_checks();
       
   309 #ifndef PRODUCT
       
   310     if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); }
       
   311     if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); }
       
   312 #endif
       
   313   }
       
   314 }
       
   315 
       
   316 
       
   317 static int sort_pairs(BlockPair** a, BlockPair** b) {
       
   318   if ((*a)->from() == (*b)->from()) {
       
   319     return (*a)->to()->block_id() - (*b)->to()->block_id();
       
   320   } else {
       
   321     return (*a)->from()->block_id() - (*b)->from()->block_id();
       
   322   }
       
   323 }
       
   324 
       
   325 
       
   326 class CriticalEdgeFinder: public BlockClosure {
       
   327   BlockPairList blocks;
       
   328   IR*       _ir;
       
   329 
       
   330  public:
       
   331   CriticalEdgeFinder(IR* ir): _ir(ir) {}
       
   332   void block_do(BlockBegin* bb) {
       
   333     BlockEnd* be = bb->end();
       
   334     int nos = be->number_of_sux();
       
   335     if (nos >= 2) {
       
   336       for (int i = 0; i < nos; i++) {
       
   337         BlockBegin* sux = be->sux_at(i);
       
   338         if (sux->number_of_preds() >= 2) {
       
   339           blocks.append(new BlockPair(bb, sux));
       
   340         }
       
   341       }
       
   342     }
       
   343   }
       
   344 
       
   345   void split_edges() {
       
   346     BlockPair* last_pair = NULL;
       
   347     blocks.sort(sort_pairs);
       
   348     for (int i = 0; i < blocks.length(); i++) {
       
   349       BlockPair* pair = blocks.at(i);
       
   350       if (last_pair != NULL && pair->is_same(last_pair)) continue;
       
   351       BlockBegin* from = pair->from();
       
   352       BlockBegin* to = pair->to();
       
   353       BlockBegin* split = from->insert_block_between(to);
       
   354 #ifndef PRODUCT
       
   355       if ((PrintIR || PrintIR1) && Verbose) {
       
   356         tty->print_cr("Split critical edge B%d -> B%d (new block B%d)",
       
   357                       from->block_id(), to->block_id(), split->block_id());
       
   358       }
       
   359 #endif
       
   360       last_pair = pair;
       
   361     }
       
   362   }
       
   363 };
       
   364 
       
   365 void IR::split_critical_edges() {
       
   366   CriticalEdgeFinder cef(this);
       
   367 
       
   368   iterate_preorder(&cef);
       
   369   cef.split_edges();
       
   370 }
       
   371 
       
   372 
       
   373 class UseCountComputer: public AllStatic {
       
   374  private:
       
   375   static void update_use_count(Value* n) {
       
   376     // Local instructions and Phis for expression stack values at the
       
   377     // start of basic blocks are not added to the instruction list
       
   378     if ((*n)->bci() == -99 && (*n)->as_Local() == NULL &&
       
   379         (*n)->as_Phi() == NULL) {
       
   380       assert(false, "a node was not appended to the graph");
       
   381       Compilation::current_compilation()->bailout("a node was not appended to the graph");
       
   382     }
       
   383     // use n's input if not visited before
       
   384     if (!(*n)->is_pinned() && !(*n)->has_uses()) {
       
   385       // note: a) if the instruction is pinned, it will be handled by compute_use_count
       
   386       //       b) if the instruction has uses, it was touched before
       
   387       //       => in both cases we don't need to update n's values
       
   388       uses_do(n);
       
   389     }
       
   390     // use n
       
   391     (*n)->_use_count++;
       
   392   }
       
   393 
       
   394   static Values* worklist;
       
   395   static int depth;
       
   396   enum {
       
   397     max_recurse_depth = 20
       
   398   };
       
   399 
       
   400   static void uses_do(Value* n) {
       
   401     depth++;
       
   402     if (depth > max_recurse_depth) {
       
   403       // don't allow the traversal to recurse too deeply
       
   404       worklist->push(*n);
       
   405     } else {
       
   406       (*n)->input_values_do(update_use_count);
       
   407       // special handling for some instructions
       
   408       if ((*n)->as_BlockEnd() != NULL) {
       
   409         // note on BlockEnd:
       
   410         //   must 'use' the stack only if the method doesn't
       
   411         //   terminate, however, in those cases stack is empty
       
   412         (*n)->state_values_do(update_use_count);
       
   413       }
       
   414     }
       
   415     depth--;
       
   416   }
       
   417 
       
   418   static void basic_compute_use_count(BlockBegin* b) {
       
   419     depth = 0;
       
   420     // process all pinned nodes as the roots of expression trees
       
   421     for (Instruction* n = b; n != NULL; n = n->next()) {
       
   422       if (n->is_pinned()) uses_do(&n);
       
   423     }
       
   424     assert(depth == 0, "should have counted back down");
       
   425 
       
   426     // now process any unpinned nodes which recursed too deeply
       
   427     while (worklist->length() > 0) {
       
   428       Value t = worklist->pop();
       
   429       if (!t->is_pinned()) {
       
   430         // compute the use count
       
   431         uses_do(&t);
       
   432 
       
   433         // pin the instruction so that LIRGenerator doesn't recurse
       
   434         // too deeply during it's evaluation.
       
   435         t->pin();
       
   436       }
       
   437     }
       
   438     assert(depth == 0, "should have counted back down");
       
   439   }
       
   440 
       
   441  public:
       
   442   static void compute(BlockList* blocks) {
       
   443     worklist = new Values();
       
   444     blocks->blocks_do(basic_compute_use_count);
       
   445     worklist = NULL;
       
   446   }
       
   447 };
       
   448 
       
   449 
       
   450 Values* UseCountComputer::worklist = NULL;
       
   451 int UseCountComputer::depth = 0;
       
   452 
       
   453 // helper macro for short definition of trace-output inside code
       
   454 #ifndef PRODUCT
       
   455   #define TRACE_LINEAR_SCAN(level, code)       \
       
   456     if (TraceLinearScanLevel >= level) {       \
       
   457       code;                                    \
       
   458     }
       
   459 #else
       
   460   #define TRACE_LINEAR_SCAN(level, code)
       
   461 #endif
       
   462 
       
   463 class ComputeLinearScanOrder : public StackObj {
       
   464  private:
       
   465   int        _max_block_id;        // the highest block_id of a block
       
   466   int        _num_blocks;          // total number of blocks (smaller than _max_block_id)
       
   467   int        _num_loops;           // total number of loops
       
   468   bool       _iterative_dominators;// method requires iterative computation of dominatiors
       
   469 
       
   470   BlockList* _linear_scan_order;   // the resulting list of blocks in correct order
       
   471 
       
   472   BitMap     _visited_blocks;      // used for recursive processing of blocks
       
   473   BitMap     _active_blocks;       // used for recursive processing of blocks
       
   474   BitMap     _dominator_blocks;    // temproary BitMap used for computation of dominator
       
   475   intArray   _forward_branches;    // number of incoming forward branches for each block
       
   476   BlockList  _loop_end_blocks;     // list of all loop end blocks collected during count_edges
       
   477   BitMap2D   _loop_map;            // two-dimensional bit set: a bit is set if a block is contained in a loop
       
   478   BlockList  _work_list;           // temporary list (used in mark_loops and compute_order)
       
   479 
       
   480   // accessors for _visited_blocks and _active_blocks
       
   481   void init_visited()                     { _active_blocks.clear(); _visited_blocks.clear(); }
       
   482   bool is_visited(BlockBegin* b) const    { return _visited_blocks.at(b->block_id()); }
       
   483   bool is_active(BlockBegin* b) const     { return _active_blocks.at(b->block_id()); }
       
   484   void set_visited(BlockBegin* b)         { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); }
       
   485   void set_active(BlockBegin* b)          { assert(!is_active(b), "already set");  _active_blocks.set_bit(b->block_id()); }
       
   486   void clear_active(BlockBegin* b)        { assert(is_active(b), "not already");   _active_blocks.clear_bit(b->block_id()); }
       
   487 
       
   488   // accessors for _forward_branches
       
   489   void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); }
       
   490   int  dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); }
       
   491 
       
   492   // accessors for _loop_map
       
   493   bool is_block_in_loop   (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); }
       
   494   void set_block_in_loop  (int loop_idx, BlockBegin* b)       { _loop_map.set_bit(loop_idx, b->block_id()); }
       
   495   void clear_block_in_loop(int loop_idx, int block_id)        { _loop_map.clear_bit(loop_idx, block_id); }
       
   496 
       
   497   // count edges between blocks
       
   498   void count_edges(BlockBegin* cur, BlockBegin* parent);
       
   499 
       
   500   // loop detection
       
   501   void mark_loops();
       
   502   void clear_non_natural_loops(BlockBegin* start_block);
       
   503   void assign_loop_depth(BlockBegin* start_block);
       
   504 
       
   505   // computation of final block order
       
   506   BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b);
       
   507   void compute_dominator(BlockBegin* cur, BlockBegin* parent);
       
   508   int  compute_weight(BlockBegin* cur);
       
   509   bool ready_for_processing(BlockBegin* cur);
       
   510   void sort_into_work_list(BlockBegin* b);
       
   511   void append_block(BlockBegin* cur);
       
   512   void compute_order(BlockBegin* start_block);
       
   513 
       
   514   // fixup of dominators for non-natural loops
       
   515   bool compute_dominators_iter();
       
   516   void compute_dominators();
       
   517 
       
   518   // debug functions
       
   519   NOT_PRODUCT(void print_blocks();)
       
   520   DEBUG_ONLY(void verify();)
       
   521 
       
   522  public:
       
   523   ComputeLinearScanOrder(BlockBegin* start_block);
       
   524 
       
   525   // accessors for final result
       
   526   BlockList* linear_scan_order() const    { return _linear_scan_order; }
       
   527   int        num_loops() const            { return _num_loops; }
       
   528 };
       
   529 
       
   530 
       
   531 ComputeLinearScanOrder::ComputeLinearScanOrder(BlockBegin* start_block) :
       
   532   _max_block_id(BlockBegin::number_of_blocks()),
       
   533   _num_blocks(0),
       
   534   _num_loops(0),
       
   535   _iterative_dominators(false),
       
   536   _visited_blocks(_max_block_id),
       
   537   _active_blocks(_max_block_id),
       
   538   _dominator_blocks(_max_block_id),
       
   539   _forward_branches(_max_block_id, 0),
       
   540   _loop_end_blocks(8),
       
   541   _work_list(8),
       
   542   _linear_scan_order(NULL), // initialized later with correct size
       
   543   _loop_map(0, 0)           // initialized later with correct size
       
   544 {
       
   545   TRACE_LINEAR_SCAN(2, "***** computing linear-scan block order");
       
   546 
       
   547   init_visited();
       
   548   count_edges(start_block, NULL);
       
   549 
       
   550   if (_num_loops > 0) {
       
   551     mark_loops();
       
   552     clear_non_natural_loops(start_block);
       
   553     assign_loop_depth(start_block);
       
   554   }
       
   555 
       
   556   compute_order(start_block);
       
   557   compute_dominators();
       
   558 
       
   559   NOT_PRODUCT(print_blocks());
       
   560   DEBUG_ONLY(verify());
       
   561 }
       
   562 
       
   563 
       
   564 // Traverse the CFG:
       
   565 // * count total number of blocks
       
   566 // * count all incoming edges and backward incoming edges
       
   567 // * number loop header blocks
       
   568 // * create a list with all loop end blocks
       
   569 void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) {
       
   570   TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != NULL ? parent->block_id() : -1));
       
   571   assert(cur->dominator() == NULL, "dominator already initialized");
       
   572 
       
   573   if (is_active(cur)) {
       
   574     TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch"));
       
   575     assert(is_visited(cur), "block must be visisted when block is active");
       
   576     assert(parent != NULL, "must have parent");
       
   577     assert(parent->number_of_sux() == 1, "loop end blocks must have one successor (critical edges are split)");
       
   578 
       
   579     cur->set(BlockBegin::linear_scan_loop_header_flag);
       
   580     cur->set(BlockBegin::backward_branch_target_flag);
       
   581 
       
   582     parent->set(BlockBegin::linear_scan_loop_end_flag);
       
   583     _loop_end_blocks.append(parent);
       
   584     return;
       
   585   }
       
   586 
       
   587   // increment number of incoming forward branches
       
   588   inc_forward_branches(cur);
       
   589 
       
   590   if (is_visited(cur)) {
       
   591     TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited"));
       
   592     return;
       
   593   }
       
   594 
       
   595   _num_blocks++;
       
   596   set_visited(cur);
       
   597   set_active(cur);
       
   598 
       
   599   // recursive call for all successors
       
   600   int i;
       
   601   for (i = cur->number_of_sux() - 1; i >= 0; i--) {
       
   602     count_edges(cur->sux_at(i), cur);
       
   603   }
       
   604   for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
       
   605     count_edges(cur->exception_handler_at(i), cur);
       
   606   }
       
   607 
       
   608   clear_active(cur);
       
   609 
       
   610   // Each loop has a unique number.
       
   611   // When multiple loops are nested, assign_loop_depth assumes that the
       
   612   // innermost loop has the lowest number. This is guaranteed by setting
       
   613   // the loop number after the recursive calls for the successors above
       
   614   // have returned.
       
   615   if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
       
   616     assert(cur->loop_index() == -1, "cannot set loop-index twice");
       
   617     TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops));
       
   618 
       
   619     cur->set_loop_index(_num_loops);
       
   620     _num_loops++;
       
   621   }
       
   622 
       
   623   TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id()));
       
   624 }
       
   625 
       
   626 
       
   627 void ComputeLinearScanOrder::mark_loops() {
       
   628   TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops"));
       
   629 
       
   630   _loop_map = BitMap2D(_num_loops, _max_block_id);
       
   631   _loop_map.clear();
       
   632 
       
   633   for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) {
       
   634     BlockBegin* loop_end   = _loop_end_blocks.at(i);
       
   635     BlockBegin* loop_start = loop_end->sux_at(0);
       
   636     int         loop_idx   = loop_start->loop_index();
       
   637 
       
   638     TRACE_LINEAR_SCAN(3, tty->print_cr("Processing loop from B%d to B%d (loop %d):", loop_start->block_id(), loop_end->block_id(), loop_idx));
       
   639     assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set");
       
   640     assert(loop_end->number_of_sux() == 1, "incorrect number of successors");
       
   641     assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set");
       
   642     assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set");
       
   643     assert(_work_list.is_empty(), "work list must be empty before processing");
       
   644 
       
   645     // add the end-block of the loop to the working list
       
   646     _work_list.push(loop_end);
       
   647     set_block_in_loop(loop_idx, loop_end);
       
   648     do {
       
   649       BlockBegin* cur = _work_list.pop();
       
   650 
       
   651       TRACE_LINEAR_SCAN(3, tty->print_cr("    processing B%d", cur->block_id()));
       
   652       assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list");
       
   653 
       
   654       // recursive processing of all predecessors ends when start block of loop is reached
       
   655       if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) {
       
   656         for (int j = cur->number_of_preds() - 1; j >= 0; j--) {
       
   657           BlockBegin* pred = cur->pred_at(j);
       
   658 
       
   659           if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) {
       
   660             // this predecessor has not been processed yet, so add it to work list
       
   661             TRACE_LINEAR_SCAN(3, tty->print_cr("    pushing B%d", pred->block_id()));
       
   662             _work_list.push(pred);
       
   663             set_block_in_loop(loop_idx, pred);
       
   664           }
       
   665         }
       
   666       }
       
   667     } while (!_work_list.is_empty());
       
   668   }
       
   669 }
       
   670 
       
   671 
       
   672 // check for non-natural loops (loops where the loop header does not dominate
       
   673 // all other loop blocks = loops with mulitple entries).
       
   674 // such loops are ignored
       
   675 void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) {
       
   676   for (int i = _num_loops - 1; i >= 0; i--) {
       
   677     if (is_block_in_loop(i, start_block)) {
       
   678       // loop i contains the entry block of the method
       
   679       // -> this is not a natural loop, so ignore it
       
   680       TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
       
   681 
       
   682       for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
       
   683         clear_block_in_loop(i, block_id);
       
   684       }
       
   685       _iterative_dominators = true;
       
   686     }
       
   687   }
       
   688 }
       
   689 
       
   690 void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) {
       
   691   TRACE_LINEAR_SCAN(3, "----- computing loop-depth and weight");
       
   692   init_visited();
       
   693 
       
   694   assert(_work_list.is_empty(), "work list must be empty before processing");
       
   695   _work_list.append(start_block);
       
   696 
       
   697   do {
       
   698     BlockBegin* cur = _work_list.pop();
       
   699 
       
   700     if (!is_visited(cur)) {
       
   701       set_visited(cur);
       
   702       TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id()));
       
   703 
       
   704       // compute loop-depth and loop-index for the block
       
   705       assert(cur->loop_depth() == 0, "cannot set loop-depth twice");
       
   706       int i;
       
   707       int loop_depth = 0;
       
   708       int min_loop_idx = -1;
       
   709       for (i = _num_loops - 1; i >= 0; i--) {
       
   710         if (is_block_in_loop(i, cur)) {
       
   711           loop_depth++;
       
   712           min_loop_idx = i;
       
   713         }
       
   714       }
       
   715       cur->set_loop_depth(loop_depth);
       
   716       cur->set_loop_index(min_loop_idx);
       
   717 
       
   718       // append all unvisited successors to work list
       
   719       for (i = cur->number_of_sux() - 1; i >= 0; i--) {
       
   720         _work_list.append(cur->sux_at(i));
       
   721       }
       
   722       for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
       
   723         _work_list.append(cur->exception_handler_at(i));
       
   724       }
       
   725     }
       
   726   } while (!_work_list.is_empty());
       
   727 }
       
   728 
       
   729 
       
   730 BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) {
       
   731   assert(a != NULL && b != NULL, "must have input blocks");
       
   732 
       
   733   _dominator_blocks.clear();
       
   734   while (a != NULL) {
       
   735     _dominator_blocks.set_bit(a->block_id());
       
   736     assert(a->dominator() != NULL || a == _linear_scan_order->at(0), "dominator must be initialized");
       
   737     a = a->dominator();
       
   738   }
       
   739   while (b != NULL && !_dominator_blocks.at(b->block_id())) {
       
   740     assert(b->dominator() != NULL || b == _linear_scan_order->at(0), "dominator must be initialized");
       
   741     b = b->dominator();
       
   742   }
       
   743 
       
   744   assert(b != NULL, "could not find dominator");
       
   745   return b;
       
   746 }
       
   747 
       
   748 void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) {
       
   749   if (cur->dominator() == NULL) {
       
   750     TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id()));
       
   751     cur->set_dominator(parent);
       
   752 
       
   753   } else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) {
       
   754     TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id()));
       
   755     assert(cur->number_of_preds() > 1, "");
       
   756     cur->set_dominator(common_dominator(cur->dominator(), parent));
       
   757   }
       
   758 }
       
   759 
       
   760 
       
   761 int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) {
       
   762   BlockBegin* single_sux = NULL;
       
   763   if (cur->number_of_sux() == 1) {
       
   764     single_sux = cur->sux_at(0);
       
   765   }
       
   766 
       
   767   // limit loop-depth to 15 bit (only for security reason, it will never be so big)
       
   768   int weight = (cur->loop_depth() & 0x7FFF) << 16;
       
   769 
       
   770   // general macro for short definition of weight flags
       
   771   // the first instance of INC_WEIGHT_IF has the highest priority
       
   772   int cur_bit = 15;
       
   773   #define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--;
       
   774 
       
   775   // this is necessery for the (very rare) case that two successing blocks have
       
   776   // the same loop depth, but a different loop index (can happen for endless loops
       
   777   // with exception handlers)
       
   778   INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag));
       
   779 
       
   780   // loop end blocks (blocks that end with a backward branch) are added
       
   781   // after all other blocks of the loop.
       
   782   INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag));
       
   783 
       
   784   // critical edge split blocks are prefered because than they have a bigger
       
   785   // proability to be completely empty
       
   786   INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag));
       
   787 
       
   788   // exceptions should not be thrown in normal control flow, so these blocks
       
   789   // are added as late as possible
       
   790   INC_WEIGHT_IF(cur->end()->as_Throw() == NULL  && (single_sux == NULL || single_sux->end()->as_Throw()  == NULL));
       
   791   INC_WEIGHT_IF(cur->end()->as_Return() == NULL && (single_sux == NULL || single_sux->end()->as_Return() == NULL));
       
   792 
       
   793   // exceptions handlers are added as late as possible
       
   794   INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag));
       
   795 
       
   796   // guarantee that weight is > 0
       
   797   weight |= 1;
       
   798 
       
   799   #undef INC_WEIGHT_IF
       
   800   assert(cur_bit >= 0, "too many flags");
       
   801   assert(weight > 0, "weight cannot become negative");
       
   802 
       
   803   return weight;
       
   804 }
       
   805 
       
   806 bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) {
       
   807   // Discount the edge just traveled.
       
   808   // When the number drops to zero, all forward branches were processed
       
   809   if (dec_forward_branches(cur) != 0) {
       
   810     return false;
       
   811   }
       
   812 
       
   813   assert(_linear_scan_order->index_of(cur) == -1, "block already processed (block can be ready only once)");
       
   814   assert(_work_list.index_of(cur) == -1, "block already in work-list (block can be ready only once)");
       
   815   return true;
       
   816 }
       
   817 
       
   818 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) {
       
   819   assert(_work_list.index_of(cur) == -1, "block already in work list");
       
   820 
       
   821   int cur_weight = compute_weight(cur);
       
   822 
       
   823   // the linear_scan_number is used to cache the weight of a block
       
   824   cur->set_linear_scan_number(cur_weight);
       
   825 
       
   826 #ifndef PRODUCT
       
   827   if (StressLinearScan) {
       
   828     _work_list.insert_before(0, cur);
       
   829     return;
       
   830   }
       
   831 #endif
       
   832 
       
   833   _work_list.append(NULL); // provide space for new element
       
   834 
       
   835   int insert_idx = _work_list.length() - 1;
       
   836   while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) {
       
   837     _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1));
       
   838     insert_idx--;
       
   839   }
       
   840   _work_list.at_put(insert_idx, cur);
       
   841 
       
   842   TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id()));
       
   843   TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d  weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number()));
       
   844 
       
   845 #ifdef ASSERT
       
   846   for (int i = 0; i < _work_list.length(); i++) {
       
   847     assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
       
   848     assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
       
   849   }
       
   850 #endif
       
   851 }
       
   852 
       
   853 void ComputeLinearScanOrder::append_block(BlockBegin* cur) {
       
   854   TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number()));
       
   855   assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice");
       
   856 
       
   857   // currently, the linear scan order and code emit order are equal.
       
   858   // therefore the linear_scan_number and the weight of a block must also
       
   859   // be equal.
       
   860   cur->set_linear_scan_number(_linear_scan_order->length());
       
   861   _linear_scan_order->append(cur);
       
   862 }
       
   863 
       
   864 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
       
   865   TRACE_LINEAR_SCAN(3, "----- computing final block order");
       
   866 
       
   867   // the start block is always the first block in the linear scan order
       
   868   _linear_scan_order = new BlockList(_num_blocks);
       
   869   append_block(start_block);
       
   870 
       
   871   assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
       
   872   BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
       
   873   BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
       
   874 
       
   875   BlockBegin* sux_of_osr_entry = NULL;
       
   876   if (osr_entry != NULL) {
       
   877     // special handling for osr entry:
       
   878     // ignore the edge between the osr entry and its successor for processing
       
   879     // the osr entry block is added manually below
       
   880     assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor");
       
   881     assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow");
       
   882 
       
   883     sux_of_osr_entry = osr_entry->sux_at(0);
       
   884     dec_forward_branches(sux_of_osr_entry);
       
   885 
       
   886     compute_dominator(osr_entry, start_block);
       
   887     _iterative_dominators = true;
       
   888   }
       
   889   compute_dominator(std_entry, start_block);
       
   890 
       
   891   // start processing with standard entry block
       
   892   assert(_work_list.is_empty(), "list must be empty before processing");
       
   893 
       
   894   if (ready_for_processing(std_entry)) {
       
   895     sort_into_work_list(std_entry);
       
   896   } else {
       
   897     assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)");
       
   898   }
       
   899 
       
   900   do {
       
   901     BlockBegin* cur = _work_list.pop();
       
   902 
       
   903     if (cur == sux_of_osr_entry) {
       
   904       // the osr entry block is ignored in normal processing, it is never added to the
       
   905       // work list. Instead, it is added as late as possible manually here.
       
   906       append_block(osr_entry);
       
   907       compute_dominator(cur, osr_entry);
       
   908     }
       
   909     append_block(cur);
       
   910 
       
   911     int i;
       
   912     int num_sux = cur->number_of_sux();
       
   913     // changed loop order to get "intuitive" order of if- and else-blocks
       
   914     for (i = 0; i < num_sux; i++) {
       
   915       BlockBegin* sux = cur->sux_at(i);
       
   916       compute_dominator(sux, cur);
       
   917       if (ready_for_processing(sux)) {
       
   918         sort_into_work_list(sux);
       
   919       }
       
   920     }
       
   921     num_sux = cur->number_of_exception_handlers();
       
   922     for (i = 0; i < num_sux; i++) {
       
   923       BlockBegin* sux = cur->exception_handler_at(i);
       
   924       compute_dominator(sux, cur);
       
   925       if (ready_for_processing(sux)) {
       
   926         sort_into_work_list(sux);
       
   927       }
       
   928     }
       
   929   } while (_work_list.length() > 0);
       
   930 }
       
   931 
       
   932 
       
   933 bool ComputeLinearScanOrder::compute_dominators_iter() {
       
   934   bool changed = false;
       
   935   int num_blocks = _linear_scan_order->length();
       
   936 
       
   937   assert(_linear_scan_order->at(0)->dominator() == NULL, "must not have dominator");
       
   938   assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors");
       
   939   for (int i = 1; i < num_blocks; i++) {
       
   940     BlockBegin* block = _linear_scan_order->at(i);
       
   941 
       
   942     BlockBegin* dominator = block->pred_at(0);
       
   943     int num_preds = block->number_of_preds();
       
   944     for (int i = 1; i < num_preds; i++) {
       
   945       dominator = common_dominator(dominator, block->pred_at(i));
       
   946     }
       
   947 
       
   948     if (dominator != block->dominator()) {
       
   949       TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: updating dominator of B%d from B%d to B%d", block->block_id(), block->dominator()->block_id(), dominator->block_id()));
       
   950 
       
   951       block->set_dominator(dominator);
       
   952       changed = true;
       
   953     }
       
   954   }
       
   955   return changed;
       
   956 }
       
   957 
       
   958 void ComputeLinearScanOrder::compute_dominators() {
       
   959   TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators));
       
   960 
       
   961   // iterative computation of dominators is only required for methods with non-natural loops
       
   962   // and OSR-methods. For all other methods, the dominators computed when generating the
       
   963   // linear scan block order are correct.
       
   964   if (_iterative_dominators) {
       
   965     do {
       
   966       TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation"));
       
   967     } while (compute_dominators_iter());
       
   968   }
       
   969 
       
   970   // check that dominators are correct
       
   971   assert(!compute_dominators_iter(), "fix point not reached");
       
   972 }
       
   973 
       
   974 
       
   975 #ifndef PRODUCT
       
   976 void ComputeLinearScanOrder::print_blocks() {
       
   977   if (TraceLinearScanLevel >= 2) {
       
   978     tty->print_cr("----- loop information:");
       
   979     for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
       
   980       BlockBegin* cur = _linear_scan_order->at(block_idx);
       
   981 
       
   982       tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id());
       
   983       for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
       
   984         tty->print ("%d ", is_block_in_loop(loop_idx, cur));
       
   985       }
       
   986       tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth());
       
   987     }
       
   988   }
       
   989 
       
   990   if (TraceLinearScanLevel >= 1) {
       
   991     tty->print_cr("----- linear-scan block order:");
       
   992     for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
       
   993       BlockBegin* cur = _linear_scan_order->at(block_idx);
       
   994       tty->print("%4d: B%2d    loop: %2d  depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth());
       
   995 
       
   996       tty->print(cur->is_set(BlockBegin::exception_entry_flag)         ? " ex" : "   ");
       
   997       tty->print(cur->is_set(BlockBegin::critical_edge_split_flag)     ? " ce" : "   ");
       
   998       tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : "   ");
       
   999       tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag)    ? " le" : "   ");
       
  1000 
       
  1001       if (cur->dominator() != NULL) {
       
  1002         tty->print("    dom: B%d ", cur->dominator()->block_id());
       
  1003       } else {
       
  1004         tty->print("    dom: NULL ");
       
  1005       }
       
  1006 
       
  1007       if (cur->number_of_preds() > 0) {
       
  1008         tty->print("    preds: ");
       
  1009         for (int j = 0; j < cur->number_of_preds(); j++) {
       
  1010           BlockBegin* pred = cur->pred_at(j);
       
  1011           tty->print("B%d ", pred->block_id());
       
  1012         }
       
  1013       }
       
  1014       if (cur->number_of_sux() > 0) {
       
  1015         tty->print("    sux: ");
       
  1016         for (int j = 0; j < cur->number_of_sux(); j++) {
       
  1017           BlockBegin* sux = cur->sux_at(j);
       
  1018           tty->print("B%d ", sux->block_id());
       
  1019         }
       
  1020       }
       
  1021       if (cur->number_of_exception_handlers() > 0) {
       
  1022         tty->print("    ex: ");
       
  1023         for (int j = 0; j < cur->number_of_exception_handlers(); j++) {
       
  1024           BlockBegin* ex = cur->exception_handler_at(j);
       
  1025           tty->print("B%d ", ex->block_id());
       
  1026         }
       
  1027       }
       
  1028       tty->cr();
       
  1029     }
       
  1030   }
       
  1031 }
       
  1032 #endif
       
  1033 
       
  1034 #ifdef ASSERT
       
  1035 void ComputeLinearScanOrder::verify() {
       
  1036   assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list");
       
  1037 
       
  1038   if (StressLinearScan) {
       
  1039     // blocks are scrambled when StressLinearScan is used
       
  1040     return;
       
  1041   }
       
  1042 
       
  1043   // check that all successors of a block have a higher linear-scan-number
       
  1044   // and that all predecessors of a block have a lower linear-scan-number
       
  1045   // (only backward branches of loops are ignored)
       
  1046   int i;
       
  1047   for (i = 0; i < _linear_scan_order->length(); i++) {
       
  1048     BlockBegin* cur = _linear_scan_order->at(i);
       
  1049 
       
  1050     assert(cur->linear_scan_number() == i, "incorrect linear_scan_number");
       
  1051     assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->index_of(cur), "incorrect linear_scan_number");
       
  1052 
       
  1053     int j;
       
  1054     for (j = cur->number_of_sux() - 1; j >= 0; j--) {
       
  1055       BlockBegin* sux = cur->sux_at(j);
       
  1056 
       
  1057       assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number");
       
  1058       if (!cur->is_set(BlockBegin::linear_scan_loop_end_flag)) {
       
  1059         assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
       
  1060       }
       
  1061       if (cur->loop_depth() == sux->loop_depth()) {
       
  1062         assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index");
       
  1063       }
       
  1064     }
       
  1065 
       
  1066     for (j = cur->number_of_preds() - 1; j >= 0; j--) {
       
  1067       BlockBegin* pred = cur->pred_at(j);
       
  1068 
       
  1069       assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number");
       
  1070       if (!cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
       
  1071         assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
       
  1072       }
       
  1073       if (cur->loop_depth() == pred->loop_depth()) {
       
  1074         assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index");
       
  1075       }
       
  1076 
       
  1077       assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors");
       
  1078     }
       
  1079 
       
  1080     // check dominator
       
  1081     if (i == 0) {
       
  1082       assert(cur->dominator() == NULL, "first block has no dominator");
       
  1083     } else {
       
  1084       assert(cur->dominator() != NULL, "all but first block must have dominator");
       
  1085     }
       
  1086     assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0), "Single predecessor must also be dominator");
       
  1087   }
       
  1088 
       
  1089   // check that all loops are continuous
       
  1090   for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
       
  1091     int block_idx = 0;
       
  1092     assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop");
       
  1093 
       
  1094     // skip blocks before the loop
       
  1095     while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
       
  1096       block_idx++;
       
  1097     }
       
  1098     // skip blocks of loop
       
  1099     while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
       
  1100       block_idx++;
       
  1101     }
       
  1102     // after the first non-loop block, there must not be another loop-block
       
  1103     while (block_idx < _num_blocks) {
       
  1104       assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order");
       
  1105       block_idx++;
       
  1106     }
       
  1107   }
       
  1108 }
       
  1109 #endif
       
  1110 
       
  1111 
       
  1112 void IR::compute_code() {
       
  1113   assert(is_valid(), "IR must be valid");
       
  1114 
       
  1115   ComputeLinearScanOrder compute_order(start());
       
  1116   _num_loops = compute_order.num_loops();
       
  1117   _code = compute_order.linear_scan_order();
       
  1118 }
       
  1119 
       
  1120 
       
  1121 void IR::compute_use_counts() {
       
  1122   // make sure all values coming out of this block get evaluated.
       
  1123   int num_blocks = _code->length();
       
  1124   for (int i = 0; i < num_blocks; i++) {
       
  1125     _code->at(i)->end()->state()->pin_stack_for_linear_scan();
       
  1126   }
       
  1127 
       
  1128   // compute use counts
       
  1129   UseCountComputer::compute(_code);
       
  1130 }
       
  1131 
       
  1132 
       
  1133 void IR::iterate_preorder(BlockClosure* closure) {
       
  1134   assert(is_valid(), "IR must be valid");
       
  1135   start()->iterate_preorder(closure);
       
  1136 }
       
  1137 
       
  1138 
       
  1139 void IR::iterate_postorder(BlockClosure* closure) {
       
  1140   assert(is_valid(), "IR must be valid");
       
  1141   start()->iterate_postorder(closure);
       
  1142 }
       
  1143 
       
  1144 void IR::iterate_linear_scan_order(BlockClosure* closure) {
       
  1145   linear_scan_order()->iterate_forward(closure);
       
  1146 }
       
  1147 
       
  1148 
       
  1149 #ifndef PRODUCT
       
  1150 class BlockPrinter: public BlockClosure {
       
  1151  private:
       
  1152   InstructionPrinter* _ip;
       
  1153   bool                _cfg_only;
       
  1154   bool                _live_only;
       
  1155 
       
  1156  public:
       
  1157   BlockPrinter(InstructionPrinter* ip, bool cfg_only, bool live_only = false) {
       
  1158     _ip       = ip;
       
  1159     _cfg_only = cfg_only;
       
  1160     _live_only = live_only;
       
  1161   }
       
  1162 
       
  1163   virtual void block_do(BlockBegin* block) {
       
  1164     if (_cfg_only) {
       
  1165       _ip->print_instr(block); tty->cr();
       
  1166     } else {
       
  1167       block->print_block(*_ip, _live_only);
       
  1168     }
       
  1169   }
       
  1170 };
       
  1171 
       
  1172 
       
  1173 void IR::print(BlockBegin* start, bool cfg_only, bool live_only) {
       
  1174   ttyLocker ttyl;
       
  1175   InstructionPrinter ip(!cfg_only);
       
  1176   BlockPrinter bp(&ip, cfg_only, live_only);
       
  1177   start->iterate_preorder(&bp);
       
  1178   tty->cr();
       
  1179 }
       
  1180 
       
  1181 void IR::print(bool cfg_only, bool live_only) {
       
  1182   if (is_valid()) {
       
  1183     print(start(), cfg_only, live_only);
       
  1184   } else {
       
  1185     tty->print_cr("invalid IR");
       
  1186   }
       
  1187 }
       
  1188 
       
  1189 
       
  1190 define_array(BlockListArray, BlockList*)
       
  1191 define_stack(BlockListList, BlockListArray)
       
  1192 
       
  1193 class PredecessorValidator : public BlockClosure {
       
  1194  private:
       
  1195   BlockListList* _predecessors;
       
  1196   BlockList*     _blocks;
       
  1197 
       
  1198   static int cmp(BlockBegin** a, BlockBegin** b) {
       
  1199     return (*a)->block_id() - (*b)->block_id();
       
  1200   }
       
  1201 
       
  1202  public:
       
  1203   PredecessorValidator(IR* hir) {
       
  1204     ResourceMark rm;
       
  1205     _predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL);
       
  1206     _blocks = new BlockList();
       
  1207 
       
  1208     int i;
       
  1209     hir->start()->iterate_preorder(this);
       
  1210     if (hir->code() != NULL) {
       
  1211       assert(hir->code()->length() == _blocks->length(), "must match");
       
  1212       for (i = 0; i < _blocks->length(); i++) {
       
  1213         assert(hir->code()->contains(_blocks->at(i)), "should be in both lists");
       
  1214       }
       
  1215     }
       
  1216 
       
  1217     for (i = 0; i < _blocks->length(); i++) {
       
  1218       BlockBegin* block = _blocks->at(i);
       
  1219       BlockList* preds = _predecessors->at(block->block_id());
       
  1220       if (preds == NULL) {
       
  1221         assert(block->number_of_preds() == 0, "should be the same");
       
  1222         continue;
       
  1223       }
       
  1224 
       
  1225       // clone the pred list so we can mutate it
       
  1226       BlockList* pred_copy = new BlockList();
       
  1227       int j;
       
  1228       for (j = 0; j < block->number_of_preds(); j++) {
       
  1229         pred_copy->append(block->pred_at(j));
       
  1230       }
       
  1231       // sort them in the same order
       
  1232       preds->sort(cmp);
       
  1233       pred_copy->sort(cmp);
       
  1234       int length = MIN2(preds->length(), block->number_of_preds());
       
  1235       for (j = 0; j < block->number_of_preds(); j++) {
       
  1236         assert(preds->at(j) == pred_copy->at(j), "must match");
       
  1237       }
       
  1238 
       
  1239       assert(preds->length() == block->number_of_preds(), "should be the same");
       
  1240     }
       
  1241   }
       
  1242 
       
  1243   virtual void block_do(BlockBegin* block) {
       
  1244     _blocks->append(block);
       
  1245     BlockEnd* be = block->end();
       
  1246     int n = be->number_of_sux();
       
  1247     int i;
       
  1248     for (i = 0; i < n; i++) {
       
  1249       BlockBegin* sux = be->sux_at(i);
       
  1250       assert(!sux->is_set(BlockBegin::exception_entry_flag), "must not be xhandler");
       
  1251 
       
  1252       BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL);
       
  1253       if (preds == NULL) {
       
  1254         preds = new BlockList();
       
  1255         _predecessors->at_put(sux->block_id(), preds);
       
  1256       }
       
  1257       preds->append(block);
       
  1258     }
       
  1259 
       
  1260     n = block->number_of_exception_handlers();
       
  1261     for (i = 0; i < n; i++) {
       
  1262       BlockBegin* sux = block->exception_handler_at(i);
       
  1263       assert(sux->is_set(BlockBegin::exception_entry_flag), "must be xhandler");
       
  1264 
       
  1265       BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL);
       
  1266       if (preds == NULL) {
       
  1267         preds = new BlockList();
       
  1268         _predecessors->at_put(sux->block_id(), preds);
       
  1269       }
       
  1270       preds->append(block);
       
  1271     }
       
  1272   }
       
  1273 };
       
  1274 
       
  1275 void IR::verify() {
       
  1276 #ifdef ASSERT
       
  1277   PredecessorValidator pv(this);
       
  1278 #endif
       
  1279 }
       
  1280 
       
  1281 #endif // PRODUCT
       
  1282 
       
  1283 void SubstitutionResolver::substitute(Value* v) {
       
  1284   Value v0 = *v;
       
  1285   if (v0) {
       
  1286     Value vs = v0->subst();
       
  1287     if (vs != v0) {
       
  1288       *v = v0->subst();
       
  1289     }
       
  1290   }
       
  1291 }
       
  1292 
       
  1293 #ifdef ASSERT
       
  1294 void check_substitute(Value* v) {
       
  1295   Value v0 = *v;
       
  1296   if (v0) {
       
  1297     Value vs = v0->subst();
       
  1298     assert(vs == v0, "missed substitution");
       
  1299   }
       
  1300 }
       
  1301 #endif
       
  1302 
       
  1303 
       
  1304 void SubstitutionResolver::block_do(BlockBegin* block) {
       
  1305   Instruction* last = NULL;
       
  1306   for (Instruction* n = block; n != NULL;) {
       
  1307     n->values_do(substitute);
       
  1308     // need to remove this instruction from the instruction stream
       
  1309     if (n->subst() != n) {
       
  1310       assert(last != NULL, "must have last");
       
  1311       last->set_next(n->next(), n->next()->bci());
       
  1312     } else {
       
  1313       last = n;
       
  1314     }
       
  1315     n = last->next();
       
  1316   }
       
  1317 
       
  1318 #ifdef ASSERT
       
  1319   if (block->state()) block->state()->values_do(check_substitute);
       
  1320   block->block_values_do(check_substitute);
       
  1321   if (block->end() && block->end()->state()) block->end()->state()->values_do(check_substitute);
       
  1322 #endif
       
  1323 }