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