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);