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