hotspot/src/share/vm/opto/gcm.cpp
author goetz
Thu, 20 Jun 2013 16:30:44 -0700
changeset 22807 1cf02ef734e2
parent 15871 b04dd94da4e6
child 22828 17ecb098bc1e
permissions -rw-r--r--
8016586: PPC64 (part 3): basic changes for PPC64 Summary: added #includes needed for ppc64 port. Renamed _MODEL_ppc to _MODEL_ppc_32 and renamed corresponding old _ppc files to _ppc_32. Reviewed-by: dholmes, kvn
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
     1
/*
13963
e5b53c306fb5 7197424: update copyright year to match last edit in jdk8 hotspot repository
mikael
parents: 11567
diff changeset
     2
 * Copyright (c) 1997, 2012, 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: 3186
diff changeset
    19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
f4b087cbb361 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 3186
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: 3186
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
7397
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    25
#include "precompiled.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    26
#include "libadt/vectset.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    27
#include "memory/allocation.inline.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    28
#include "opto/block.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    29
#include "opto/c2compiler.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    30
#include "opto/callnode.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    31
#include "opto/cfgnode.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    32
#include "opto/machnode.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    33
#include "opto/opcodes.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    34
#include "opto/phaseX.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    35
#include "opto/rootnode.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    36
#include "opto/runtime.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    37
#include "runtime/deoptimization.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    38
#ifdef TARGET_ARCH_MODEL_x86_32
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    39
# include "adfiles/ad_x86_32.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    40
#endif
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    41
#ifdef TARGET_ARCH_MODEL_x86_64
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    42
# include "adfiles/ad_x86_64.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    43
#endif
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    44
#ifdef TARGET_ARCH_MODEL_sparc
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    45
# include "adfiles/ad_sparc.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    46
#endif
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    47
#ifdef TARGET_ARCH_MODEL_zero
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    48
# include "adfiles/ad_zero.hpp"
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    49
#endif
8107
78e5bd944384 7016023: Enable building ARM and PPC from src/closed repository
bobv
parents: 7433
diff changeset
    50
#ifdef TARGET_ARCH_MODEL_arm
78e5bd944384 7016023: Enable building ARM and PPC from src/closed repository
bobv
parents: 7433
diff changeset
    51
# include "adfiles/ad_arm.hpp"
78e5bd944384 7016023: Enable building ARM and PPC from src/closed repository
bobv
parents: 7433
diff changeset
    52
#endif
22807
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    53
#ifdef TARGET_ARCH_MODEL_ppc_32
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    54
# include "adfiles/ad_ppc_32.hpp"
8107
78e5bd944384 7016023: Enable building ARM and PPC from src/closed repository
bobv
parents: 7433
diff changeset
    55
#endif
22807
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    56
#ifdef TARGET_ARCH_MODEL_ppc_64
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    57
# include "adfiles/ad_ppc_64.hpp"
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    58
#endif
1cf02ef734e2 8016586: PPC64 (part 3): basic changes for PPC64
goetz
parents: 15871
diff changeset
    59
7397
5b173b4ca846 6989984: Use standard include model for Hospot
stefank
parents: 6180
diff changeset
    60
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
    61
// Portions of code courtesy of Clifford Click
489c9b5090e2 Initial load
duke
parents:
diff changeset
    62
489c9b5090e2 Initial load
duke
parents:
diff changeset
    63
// Optimization - Graph Style
489c9b5090e2 Initial load
duke
parents:
diff changeset
    64
2016
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
    65
// To avoid float value underflow
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
    66
#define MIN_BLOCK_FREQUENCY 1.e-35f
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
    67
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
    68
//----------------------------schedule_node_into_block-------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
    69
// Insert node n into block b. Look for projections of n and make sure they
489c9b5090e2 Initial load
duke
parents:
diff changeset
    70
// are in b also.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    71
void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    72
  // Set basic block of n, Add n to b,
489c9b5090e2 Initial load
duke
parents:
diff changeset
    73
  _bbs.map(n->_idx, b);
489c9b5090e2 Initial load
duke
parents:
diff changeset
    74
  b->add_inst(n);
489c9b5090e2 Initial load
duke
parents:
diff changeset
    75
489c9b5090e2 Initial load
duke
parents:
diff changeset
    76
  // After Matching, nearly any old Node may have projections trailing it.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    77
  // These are usually machine-dependent flags.  In any case, they might
489c9b5090e2 Initial load
duke
parents:
diff changeset
    78
  // float to another block below this one.  Move them up.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    79
  for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    80
    Node*  use  = n->fast_out(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
    81
    if (use->is_Proj()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    82
      Block* buse = _bbs[use->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
    83
      if (buse != b) {              // In wrong block?
489c9b5090e2 Initial load
duke
parents:
diff changeset
    84
        if (buse != NULL)
489c9b5090e2 Initial load
duke
parents:
diff changeset
    85
          buse->find_remove(use);   // Remove from wrong block
489c9b5090e2 Initial load
duke
parents:
diff changeset
    86
        _bbs.map(use->_idx, b);     // Re-insert in this block
489c9b5090e2 Initial load
duke
parents:
diff changeset
    87
        b->add_inst(use);
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
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    93
//----------------------------replace_block_proj_ctrl-------------------------
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    94
// Nodes that have is_block_proj() nodes as their control need to use
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    95
// the appropriate Region for their actual block as their control since
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    96
// the projection will be in a predecessor block.
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    97
void PhaseCFG::replace_block_proj_ctrl( Node *n ) {
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    98
  const Node *in0 = n->in(0);
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
    99
  assert(in0 != NULL, "Only control-dependent");
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   100
  const Node *p = in0->is_block_proj();
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   101
  if (p != NULL && p != n) {    // Control from a block projection?
11191
d54ab5dcba83 6890673: Eliminate allocations immediately after EA
kvn
parents: 10255
diff changeset
   102
    assert(!n->pinned() || n->is_MachConstantBase(), "only pinned MachConstantBase node is expected here");
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   103
    // Find trailing Region
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   104
    Block *pb = _bbs[in0->_idx]; // Block-projection already has basic block
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   105
    uint j = 0;
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   106
    if (pb->_num_succs != 1) {  // More then 1 successor?
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   107
      // Search for successor
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   108
      uint max = pb->_nodes.size();
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   109
      assert( max > 1, "" );
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   110
      uint start = max - pb->_num_succs;
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   111
      // Find which output path belongs to projection
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   112
      for (j = start; j < max; j++) {
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   113
        if( pb->_nodes[j] == in0 )
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   114
          break;
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   115
      }
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   116
      assert( j < max, "must find" );
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   117
      // Change control to match head of successor basic block
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   118
      j -= start;
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   119
    }
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   120
    n->set_req(0, pb->_succs[j]->head());
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   121
  }
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   122
}
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   123
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   124
489c9b5090e2 Initial load
duke
parents:
diff changeset
   125
//------------------------------schedule_pinned_nodes--------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   126
// Set the basic block for Nodes pinned into blocks
489c9b5090e2 Initial load
duke
parents:
diff changeset
   127
void PhaseCFG::schedule_pinned_nodes( VectorSet &visited ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   128
  // Allocate node stack of size C->unique()+8 to avoid frequent realloc
489c9b5090e2 Initial load
duke
parents:
diff changeset
   129
  GrowableArray <Node *> spstack(C->unique()+8);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   130
  spstack.push(_root);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   131
  while ( spstack.is_nonempty() ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   132
    Node *n = spstack.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   133
    if( !visited.test_set(n->_idx) ) { // Test node and flag it as visited
489c9b5090e2 Initial load
duke
parents:
diff changeset
   134
      if( n->pinned() && !_bbs.lookup(n->_idx) ) {  // Pinned?  Nail it down!
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   135
        assert( n->in(0), "pinned Node must have Control" );
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   136
        // Before setting block replace block_proj control edge
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   137
        replace_block_proj_ctrl(n);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   138
        Node *input = n->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   139
        while( !input->is_block_start() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   140
          input = input->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   141
        Block *b = _bbs[input->_idx];  // Basic block of controlling input
489c9b5090e2 Initial load
duke
parents:
diff changeset
   142
        schedule_node_into_block(n, b);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   143
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   144
      for( int i = n->req() - 1; i >= 0; --i ) {  // For all inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   145
        if( n->in(i) != NULL )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   146
          spstack.push(n->in(i));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   147
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   148
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   149
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   150
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   151
489c9b5090e2 Initial load
duke
parents:
diff changeset
   152
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   153
// Assert that new input b2 is dominated by all previous inputs.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   154
// Check this by by seeing that it is dominated by b1, the deepest
489c9b5090e2 Initial load
duke
parents:
diff changeset
   155
// input observed until b2.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   156
static void assert_dom(Block* b1, Block* b2, Node* n, Block_Array &bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   157
  if (b1 == NULL)  return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   158
  assert(b1->_dom_depth < b2->_dom_depth, "sanity");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   159
  Block* tmp = b2;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   160
  while (tmp != b1 && tmp != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   161
    tmp = tmp->_idom;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   162
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   163
  if (tmp != b1) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   164
    // Detected an unschedulable graph.  Print some nice stuff and die.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   165
    tty->print_cr("!!! Unschedulable graph !!!");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   166
    for (uint j=0; j<n->len(); j++) { // For all inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   167
      Node* inn = n->in(j); // Get input
489c9b5090e2 Initial load
duke
parents:
diff changeset
   168
      if (inn == NULL)  continue;  // Ignore NULL, missing inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   169
      Block* inb = bbs[inn->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   170
      tty->print("B%d idom=B%d depth=%2d ",inb->_pre_order,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   171
                 inb->_idom ? inb->_idom->_pre_order : 0, inb->_dom_depth);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   172
      inn->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   173
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   174
    tty->print("Failing node: ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   175
    n->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   176
    assert(false, "unscheduable graph");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   177
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   178
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   179
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   180
489c9b5090e2 Initial load
duke
parents:
diff changeset
   181
static Block* find_deepest_input(Node* n, Block_Array &bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   182
  // Find the last input dominated by all other inputs.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   183
  Block* deepb           = NULL;        // Deepest block so far
489c9b5090e2 Initial load
duke
parents:
diff changeset
   184
  int    deepb_dom_depth = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   185
  for (uint k = 0; k < n->len(); k++) { // For all inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   186
    Node* inn = n->in(k);               // Get input
489c9b5090e2 Initial load
duke
parents:
diff changeset
   187
    if (inn == NULL)  continue;         // Ignore NULL, missing inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   188
    Block* inb = bbs[inn->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   189
    assert(inb != NULL, "must already have scheduled this input");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   190
    if (deepb_dom_depth < (int) inb->_dom_depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   191
      // The new inb must be dominated by the previous deepb.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   192
      // The various inputs must be linearly ordered in the dom
489c9b5090e2 Initial load
duke
parents:
diff changeset
   193
      // tree, or else there will not be a unique deepest block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   194
      DEBUG_ONLY(assert_dom(deepb, inb, n, bbs));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   195
      deepb = inb;                      // Save deepest block
489c9b5090e2 Initial load
duke
parents:
diff changeset
   196
      deepb_dom_depth = deepb->_dom_depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   197
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   198
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   199
  assert(deepb != NULL, "must be at least one input to n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   200
  return deepb;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   201
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   202
489c9b5090e2 Initial load
duke
parents:
diff changeset
   203
489c9b5090e2 Initial load
duke
parents:
diff changeset
   204
//------------------------------schedule_early---------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   205
// Find the earliest Block any instruction can be placed in.  Some instructions
489c9b5090e2 Initial load
duke
parents:
diff changeset
   206
// are pinned into Blocks.  Unpinned instructions can appear in last block in
489c9b5090e2 Initial load
duke
parents:
diff changeset
   207
// which all their inputs occur.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   208
bool PhaseCFG::schedule_early(VectorSet &visited, Node_List &roots) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   209
  // Allocate stack with enough space to avoid frequent realloc
489c9b5090e2 Initial load
duke
parents:
diff changeset
   210
  Node_Stack nstack(roots.Size() + 8); // (unique >> 1) + 24 from Java2D stats
489c9b5090e2 Initial load
duke
parents:
diff changeset
   211
  // roots.push(_root); _root will be processed among C->top() inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   212
  roots.push(C->top());
489c9b5090e2 Initial load
duke
parents:
diff changeset
   213
  visited.set(C->top()->_idx);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   214
489c9b5090e2 Initial load
duke
parents:
diff changeset
   215
  while (roots.size() != 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   216
    // Use local variables nstack_top_n & nstack_top_i to cache values
489c9b5090e2 Initial load
duke
parents:
diff changeset
   217
    // on stack's top.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   218
    Node *nstack_top_n = roots.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   219
    uint  nstack_top_i = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   220
//while_nstack_nonempty:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   221
    while (true) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   222
      // Get parent node and next input's index from stack's top.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   223
      Node *n = nstack_top_n;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   224
      uint  i = nstack_top_i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   225
489c9b5090e2 Initial load
duke
parents:
diff changeset
   226
      if (i == 0) {
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   227
        // Fixup some control.  Constants without control get attached
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   228
        // to root and nodes that use is_block_proj() nodes should be attached
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   229
        // to the region that starts their block.
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   230
        const Node *in0 = n->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   231
        if (in0 != NULL) {              // Control-dependent?
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   232
          replace_block_proj_ctrl(n);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   233
        } else {               // n->in(0) == NULL
489c9b5090e2 Initial load
duke
parents:
diff changeset
   234
          if (n->req() == 1) { // This guy is a constant with NO inputs?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   235
            n->set_req(0, _root);
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
489c9b5090e2 Initial load
duke
parents:
diff changeset
   240
      // First, visit all inputs and force them to get a block.  If an
489c9b5090e2 Initial load
duke
parents:
diff changeset
   241
      // input is already in a block we quit following inputs (to avoid
489c9b5090e2 Initial load
duke
parents:
diff changeset
   242
      // cycles). Instead we put that Node on a worklist to be handled
489c9b5090e2 Initial load
duke
parents:
diff changeset
   243
      // later (since IT'S inputs may not have a block yet).
489c9b5090e2 Initial load
duke
parents:
diff changeset
   244
      bool done = true;              // Assume all n's inputs will be processed
489c9b5090e2 Initial load
duke
parents:
diff changeset
   245
      while (i < n->len()) {         // For all inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   246
        Node *in = n->in(i);         // Get input
489c9b5090e2 Initial load
duke
parents:
diff changeset
   247
        ++i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   248
        if (in == NULL) continue;    // Ignore NULL, missing inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   249
        int is_visited = visited.test_set(in->_idx);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   250
        if (!_bbs.lookup(in->_idx)) { // Missing block selection?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   251
          if (is_visited) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   252
            // assert( !visited.test(in->_idx), "did not schedule early" );
489c9b5090e2 Initial load
duke
parents:
diff changeset
   253
            return false;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   254
          }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   255
          nstack.push(n, i);         // Save parent node and next input's index.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   256
          nstack_top_n = in;         // Process current input now.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   257
          nstack_top_i = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   258
          done = false;              // Not all n's inputs processed.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   259
          break; // continue while_nstack_nonempty;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   260
        } else if (!is_visited) {    // Input not yet visited?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   261
          roots.push(in);            // Visit this guy later, using worklist
489c9b5090e2 Initial load
duke
parents:
diff changeset
   262
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   263
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   264
      if (done) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   265
        // All of n's inputs have been processed, complete post-processing.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   266
489c9b5090e2 Initial load
duke
parents:
diff changeset
   267
        // Some instructions are pinned into a block.  These include Region,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   268
        // Phi, Start, Return, and other control-dependent instructions and
489c9b5090e2 Initial load
duke
parents:
diff changeset
   269
        // any projections which depend on them.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   270
        if (!n->pinned()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   271
          // Set earliest legal block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   272
          _bbs.map(n->_idx, find_deepest_input(n, _bbs));
2127
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   273
        } else {
268ea58ed775 6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents: 2016
diff changeset
   274
          assert(_bbs[n->_idx] == _bbs[n->in(0)->_idx], "Pinned Node should be at the same block as its control edge");
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   275
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   276
489c9b5090e2 Initial load
duke
parents:
diff changeset
   277
        if (nstack.is_empty()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   278
          // Finished all nodes on stack.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   279
          // Process next node on the worklist 'roots'.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   280
          break;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   281
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   282
        // Get saved parent node and next input's index.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   283
        nstack_top_n = nstack.node();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   284
        nstack_top_i = nstack.index();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   285
        nstack.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   286
      } //    if (done)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   287
    }   // while (true)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   288
  }     // while (roots.size() != 0)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   289
  return true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   290
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   291
489c9b5090e2 Initial load
duke
parents:
diff changeset
   292
//------------------------------dom_lca----------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   293
// Find least common ancestor in dominator tree
489c9b5090e2 Initial load
duke
parents:
diff changeset
   294
// LCA is a current notion of LCA, to be raised above 'this'.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   295
// As a convenient boundary condition, return 'this' if LCA is NULL.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   296
// Find the LCA of those two nodes.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   297
Block* Block::dom_lca(Block* LCA) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   298
  if (LCA == NULL || LCA == this)  return this;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   299
489c9b5090e2 Initial load
duke
parents:
diff changeset
   300
  Block* anc = this;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   301
  while (anc->_dom_depth > LCA->_dom_depth)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   302
    anc = anc->_idom;           // Walk up till anc is as high as LCA
489c9b5090e2 Initial load
duke
parents:
diff changeset
   303
489c9b5090e2 Initial load
duke
parents:
diff changeset
   304
  while (LCA->_dom_depth > anc->_dom_depth)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   305
    LCA = LCA->_idom;           // Walk up till LCA is as high as anc
489c9b5090e2 Initial load
duke
parents:
diff changeset
   306
489c9b5090e2 Initial load
duke
parents:
diff changeset
   307
  while (LCA != anc) {          // Walk both up till they are the same
489c9b5090e2 Initial load
duke
parents:
diff changeset
   308
    LCA = LCA->_idom;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   309
    anc = anc->_idom;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   310
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   311
489c9b5090e2 Initial load
duke
parents:
diff changeset
   312
  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   313
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   314
489c9b5090e2 Initial load
duke
parents:
diff changeset
   315
//--------------------------raise_LCA_above_use--------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   316
// We are placing a definition, and have been given a def->use edge.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   317
// The definition must dominate the use, so move the LCA upward in the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   318
// dominator tree to dominate the use.  If the use is a phi, adjust
489c9b5090e2 Initial load
duke
parents:
diff changeset
   319
// the LCA only with the phi input paths which actually use this def.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   320
static Block* raise_LCA_above_use(Block* LCA, Node* use, Node* def, Block_Array &bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   321
  Block* buse = bbs[use->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   322
  if (buse == NULL)    return LCA;   // Unused killing Projs have no use block
489c9b5090e2 Initial load
duke
parents:
diff changeset
   323
  if (!use->is_Phi())  return buse->dom_lca(LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   324
  uint pmax = use->req();       // Number of Phi inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   325
  // Why does not this loop just break after finding the matching input to
489c9b5090e2 Initial load
duke
parents:
diff changeset
   326
  // the Phi?  Well...it's like this.  I do not have true def-use/use-def
489c9b5090e2 Initial load
duke
parents:
diff changeset
   327
  // chains.  Means I cannot distinguish, from the def-use direction, which
489c9b5090e2 Initial load
duke
parents:
diff changeset
   328
  // of many use-defs lead from the same use to the same def.  That is, this
489c9b5090e2 Initial load
duke
parents:
diff changeset
   329
  // Phi might have several uses of the same def.  Each use appears in a
489c9b5090e2 Initial load
duke
parents:
diff changeset
   330
  // different predecessor block.  But when I enter here, I cannot distinguish
489c9b5090e2 Initial load
duke
parents:
diff changeset
   331
  // which use-def edge I should find the predecessor block for.  So I find
489c9b5090e2 Initial load
duke
parents:
diff changeset
   332
  // them all.  Means I do a little extra work if a Phi uses the same value
489c9b5090e2 Initial load
duke
parents:
diff changeset
   333
  // more than once.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   334
  for (uint j=1; j<pmax; j++) { // For all inputs
489c9b5090e2 Initial load
duke
parents:
diff changeset
   335
    if (use->in(j) == def) {    // Found matching input?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   336
      Block* pred = bbs[buse->pred(j)->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   337
      LCA = pred->dom_lca(LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   338
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   339
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   340
  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   341
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   342
489c9b5090e2 Initial load
duke
parents:
diff changeset
   343
//----------------------------raise_LCA_above_marks----------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   344
// Return a new LCA that dominates LCA and any of its marked predecessors.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   345
// Search all my parents up to 'early' (exclusive), looking for predecessors
489c9b5090e2 Initial load
duke
parents:
diff changeset
   346
// which are marked with the given index.  Return the LCA (in the dom tree)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   347
// of all marked blocks.  If there are none marked, return the original
489c9b5090e2 Initial load
duke
parents:
diff changeset
   348
// LCA.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   349
static Block* raise_LCA_above_marks(Block* LCA, node_idx_t mark,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   350
                                    Block* early, Block_Array &bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   351
  Block_List worklist;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   352
  worklist.push(LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   353
  while (worklist.size() > 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   354
    Block* mid = worklist.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   355
    if (mid == early)  continue;  // stop searching here
489c9b5090e2 Initial load
duke
parents:
diff changeset
   356
489c9b5090e2 Initial load
duke
parents:
diff changeset
   357
    // Test and set the visited bit.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   358
    if (mid->raise_LCA_visited() == mark)  continue;  // already visited
489c9b5090e2 Initial load
duke
parents:
diff changeset
   359
489c9b5090e2 Initial load
duke
parents:
diff changeset
   360
    // Don't process the current LCA, otherwise the search may terminate early
489c9b5090e2 Initial load
duke
parents:
diff changeset
   361
    if (mid != LCA && mid->raise_LCA_mark() == mark) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   362
      // Raise the LCA.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   363
      LCA = mid->dom_lca(LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   364
      if (LCA == early)  break;   // stop searching everywhere
489c9b5090e2 Initial load
duke
parents:
diff changeset
   365
      assert(early->dominates(LCA), "early is high enough");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   366
      // Resume searching at that point, skipping intermediate levels.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   367
      worklist.push(LCA);
761
312de898447e 6714694: assertion in 64bit server vm (store->find_edge(load) != -1,"missing precedence edge") with COOPs
kvn
parents: 204
diff changeset
   368
      if (LCA == mid)
312de898447e 6714694: assertion in 64bit server vm (store->find_edge(load) != -1,"missing precedence edge") with COOPs
kvn
parents: 204
diff changeset
   369
        continue; // Don't mark as visited to avoid early termination.
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   370
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   371
      // Keep searching through this block's predecessors.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   372
      for (uint j = 1, jmax = mid->num_preds(); j < jmax; j++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   373
        Block* mid_parent = bbs[ mid->pred(j)->_idx ];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   374
        worklist.push(mid_parent);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   375
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   376
    }
761
312de898447e 6714694: assertion in 64bit server vm (store->find_edge(load) != -1,"missing precedence edge") with COOPs
kvn
parents: 204
diff changeset
   377
    mid->set_raise_LCA_visited(mark);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   378
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   379
  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   380
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   381
489c9b5090e2 Initial load
duke
parents:
diff changeset
   382
//--------------------------memory_early_block--------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   383
// This is a variation of find_deepest_input, the heart of schedule_early.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   384
// Find the "early" block for a load, if we considered only memory and
489c9b5090e2 Initial load
duke
parents:
diff changeset
   385
// address inputs, that is, if other data inputs were ignored.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   386
//
489c9b5090e2 Initial load
duke
parents:
diff changeset
   387
// Because a subset of edges are considered, the resulting block will
489c9b5090e2 Initial load
duke
parents:
diff changeset
   388
// be earlier (at a shallower dom_depth) than the true schedule_early
489c9b5090e2 Initial load
duke
parents:
diff changeset
   389
// point of the node. We compute this earlier block as a more permissive
489c9b5090e2 Initial load
duke
parents:
diff changeset
   390
// site for anti-dependency insertion, but only if subsume_loads is enabled.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   391
static Block* memory_early_block(Node* load, Block* early, Block_Array &bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   392
  Node* base;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   393
  Node* index;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   394
  Node* store = load->in(MemNode::Memory);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   395
  load->as_Mach()->memory_inputs(base, index);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   396
489c9b5090e2 Initial load
duke
parents:
diff changeset
   397
  assert(base != NodeSentinel && index != NodeSentinel,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   398
         "unexpected base/index inputs");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   399
489c9b5090e2 Initial load
duke
parents:
diff changeset
   400
  Node* mem_inputs[4];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   401
  int mem_inputs_length = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   402
  if (base != NULL)  mem_inputs[mem_inputs_length++] = base;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   403
  if (index != NULL) mem_inputs[mem_inputs_length++] = index;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   404
  if (store != NULL) mem_inputs[mem_inputs_length++] = store;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   405
489c9b5090e2 Initial load
duke
parents:
diff changeset
   406
  // In the comparision below, add one to account for the control input,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   407
  // which may be null, but always takes up a spot in the in array.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   408
  if (mem_inputs_length + 1 < (int) load->req()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   409
    // This "load" has more inputs than just the memory, base and index inputs.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   410
    // For purposes of checking anti-dependences, we need to start
489c9b5090e2 Initial load
duke
parents:
diff changeset
   411
    // from the early block of only the address portion of the instruction,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   412
    // and ignore other blocks that may have factored into the wider
489c9b5090e2 Initial load
duke
parents:
diff changeset
   413
    // schedule_early calculation.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   414
    if (load->in(0) != NULL) mem_inputs[mem_inputs_length++] = load->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   415
489c9b5090e2 Initial load
duke
parents:
diff changeset
   416
    Block* deepb           = NULL;        // Deepest block so far
489c9b5090e2 Initial load
duke
parents:
diff changeset
   417
    int    deepb_dom_depth = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   418
    for (int i = 0; i < mem_inputs_length; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   419
      Block* inb = bbs[mem_inputs[i]->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   420
      if (deepb_dom_depth < (int) inb->_dom_depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   421
        // The new inb must be dominated by the previous deepb.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   422
        // The various inputs must be linearly ordered in the dom
489c9b5090e2 Initial load
duke
parents:
diff changeset
   423
        // tree, or else there will not be a unique deepest block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   424
        DEBUG_ONLY(assert_dom(deepb, inb, load, bbs));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   425
        deepb = inb;                      // Save deepest block
489c9b5090e2 Initial load
duke
parents:
diff changeset
   426
        deepb_dom_depth = deepb->_dom_depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   427
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   428
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   429
    early = deepb;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   430
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   431
489c9b5090e2 Initial load
duke
parents:
diff changeset
   432
  return early;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   433
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   434
489c9b5090e2 Initial load
duke
parents:
diff changeset
   435
//--------------------------insert_anti_dependences---------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   436
// A load may need to witness memory that nearby stores can overwrite.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   437
// For each nearby store, either insert an "anti-dependence" edge
489c9b5090e2 Initial load
duke
parents:
diff changeset
   438
// from the load to the store, or else move LCA upward to force the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   439
// load to (eventually) be scheduled in a block above the store.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   440
//
489c9b5090e2 Initial load
duke
parents:
diff changeset
   441
// Do not add edges to stores on distinct control-flow paths;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   442
// only add edges to stores which might interfere.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   443
//
489c9b5090e2 Initial load
duke
parents:
diff changeset
   444
// Return the (updated) LCA.  There will not be any possibly interfering
489c9b5090e2 Initial load
duke
parents:
diff changeset
   445
// store between the load's "early block" and the updated LCA.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   446
// Any stores in the updated LCA will have new precedence edges
489c9b5090e2 Initial load
duke
parents:
diff changeset
   447
// back to the load.  The caller is expected to schedule the load
489c9b5090e2 Initial load
duke
parents:
diff changeset
   448
// in the LCA, in which case the precedence edges will make LCM
489c9b5090e2 Initial load
duke
parents:
diff changeset
   449
// preserve anti-dependences.  The caller may also hoist the load
489c9b5090e2 Initial load
duke
parents:
diff changeset
   450
// above the LCA, if it is not the early block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   451
Block* PhaseCFG::insert_anti_dependences(Block* LCA, Node* load, bool verify) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   452
  assert(load->needs_anti_dependence_check(), "must be a load of some sort");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   453
  assert(LCA != NULL, "");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   454
  DEBUG_ONLY(Block* LCA_orig = LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   455
489c9b5090e2 Initial load
duke
parents:
diff changeset
   456
  // Compute the alias index.  Loads and stores with different alias indices
489c9b5090e2 Initial load
duke
parents:
diff changeset
   457
  // do not need anti-dependence edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   458
  uint load_alias_idx = C->get_alias_index(load->adr_type());
489c9b5090e2 Initial load
duke
parents:
diff changeset
   459
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   460
  if (load_alias_idx == Compile::AliasIdxBot && C->AliasLevel() > 0 &&
489c9b5090e2 Initial load
duke
parents:
diff changeset
   461
      (PrintOpto || VerifyAliases ||
489c9b5090e2 Initial load
duke
parents:
diff changeset
   462
       PrintMiscellaneous && (WizardMode || Verbose))) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   463
    // Load nodes should not consume all of memory.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   464
    // Reporting a bottom type indicates a bug in adlc.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   465
    // If some particular type of node validly consumes all of memory,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   466
    // sharpen the preceding "if" to exclude it, so we can catch bugs here.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   467
    tty->print_cr("*** Possible Anti-Dependence Bug:  Load consumes all of memory.");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   468
    load->dump(2);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   469
    if (VerifyAliases)  assert(load_alias_idx != Compile::AliasIdxBot, "");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   470
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   471
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   472
  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrComp),
489c9b5090e2 Initial load
duke
parents:
diff changeset
   473
         "String compare is only known 'load' that does not conflict with any stores");
2348
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   474
  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrEquals),
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   475
         "String equals is a 'load' that does not conflict with any stores");
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   476
  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrIndexOf),
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   477
         "String indexOf is a 'load' that does not conflict with any stores");
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   478
  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_AryEq),
4e71ed4c2709 6761600: Use sse 4.2 in intrinsics
cfang
parents: 2340
diff changeset
   479
         "Arrays equals is a 'load' that do not conflict with any stores");
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   480
489c9b5090e2 Initial load
duke
parents:
diff changeset
   481
  if (!C->alias_type(load_alias_idx)->is_rewritable()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   482
    // It is impossible to spoil this load by putting stores before it,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   483
    // because we know that the stores will never update the value
489c9b5090e2 Initial load
duke
parents:
diff changeset
   484
    // which 'load' must witness.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   485
    return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   486
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   487
489c9b5090e2 Initial load
duke
parents:
diff changeset
   488
  node_idx_t load_index = load->_idx;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   489
489c9b5090e2 Initial load
duke
parents:
diff changeset
   490
  // Note the earliest legal placement of 'load', as determined by
489c9b5090e2 Initial load
duke
parents:
diff changeset
   491
  // by the unique point in the dom tree where all memory effects
489c9b5090e2 Initial load
duke
parents:
diff changeset
   492
  // and other inputs are first available.  (Computed by schedule_early.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   493
  // For normal loads, 'early' is the shallowest place (dom graph wise)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   494
  // to look for anti-deps between this load and any store.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   495
  Block* early = _bbs[load_index];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   496
489c9b5090e2 Initial load
duke
parents:
diff changeset
   497
  // If we are subsuming loads, compute an "early" block that only considers
489c9b5090e2 Initial load
duke
parents:
diff changeset
   498
  // memory or address inputs. This block may be different than the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   499
  // schedule_early block in that it could be at an even shallower depth in the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   500
  // dominator tree, and allow for a broader discovery of anti-dependences.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   501
  if (C->subsume_loads()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   502
    early = memory_early_block(load, early, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   503
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   504
489c9b5090e2 Initial load
duke
parents:
diff changeset
   505
  ResourceArea *area = Thread::current()->resource_area();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   506
  Node_List worklist_mem(area);     // prior memory state to store
489c9b5090e2 Initial load
duke
parents:
diff changeset
   507
  Node_List worklist_store(area);   // possible-def to explore
204
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   508
  Node_List worklist_visited(area); // visited mergemem nodes
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   509
  Node_List non_early_stores(area); // all relevant stores outside of early
489c9b5090e2 Initial load
duke
parents:
diff changeset
   510
  bool must_raise_LCA = false;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   511
489c9b5090e2 Initial load
duke
parents:
diff changeset
   512
#ifdef TRACK_PHI_INPUTS
489c9b5090e2 Initial load
duke
parents:
diff changeset
   513
  // %%% This extra checking fails because MergeMem nodes are not GVNed.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   514
  // Provide "phi_inputs" to check if every input to a PhiNode is from the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   515
  // original memory state.  This indicates a PhiNode for which should not
489c9b5090e2 Initial load
duke
parents:
diff changeset
   516
  // prevent the load from sinking.  For such a block, set_raise_LCA_mark
489c9b5090e2 Initial load
duke
parents:
diff changeset
   517
  // may be overly conservative.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   518
  // Mechanism: count inputs seen for each Phi encountered in worklist_store.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   519
  DEBUG_ONLY(GrowableArray<uint> phi_inputs(area, C->unique(),0,0));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   520
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   521
489c9b5090e2 Initial load
duke
parents:
diff changeset
   522
  // 'load' uses some memory state; look for users of the same state.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   523
  // Recurse through MergeMem nodes to the stores that use them.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   524
489c9b5090e2 Initial load
duke
parents:
diff changeset
   525
  // Each of these stores is a possible definition of memory
489c9b5090e2 Initial load
duke
parents:
diff changeset
   526
  // that 'load' needs to use.  We need to force 'load'
489c9b5090e2 Initial load
duke
parents:
diff changeset
   527
  // to occur before each such store.  When the store is in
489c9b5090e2 Initial load
duke
parents:
diff changeset
   528
  // the same block as 'load', we insert an anti-dependence
489c9b5090e2 Initial load
duke
parents:
diff changeset
   529
  // edge load->store.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   530
489c9b5090e2 Initial load
duke
parents:
diff changeset
   531
  // The relevant stores "nearby" the load consist of a tree rooted
489c9b5090e2 Initial load
duke
parents:
diff changeset
   532
  // at initial_mem, with internal nodes of type MergeMem.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   533
  // Therefore, the branches visited by the worklist are of this form:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   534
  //    initial_mem -> (MergeMem ->)* store
489c9b5090e2 Initial load
duke
parents:
diff changeset
   535
  // The anti-dependence constraints apply only to the fringe of this tree.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   536
489c9b5090e2 Initial load
duke
parents:
diff changeset
   537
  Node* initial_mem = load->in(MemNode::Memory);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   538
  worklist_store.push(initial_mem);
204
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   539
  worklist_visited.push(initial_mem);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   540
  worklist_mem.push(NULL);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   541
  while (worklist_store.size() > 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   542
    // Examine a nearby store to see if it might interfere with our load.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   543
    Node* mem   = worklist_mem.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   544
    Node* store = worklist_store.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   545
    uint op = store->Opcode();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   546
489c9b5090e2 Initial load
duke
parents:
diff changeset
   547
    // MergeMems do not directly have anti-deps.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   548
    // Treat them as internal nodes in a forward tree of memory states,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   549
    // the leaves of which are each a 'possible-def'.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   550
    if (store == initial_mem    // root (exclusive) of tree we are searching
489c9b5090e2 Initial load
duke
parents:
diff changeset
   551
        || op == Op_MergeMem    // internal node of tree we are searching
489c9b5090e2 Initial load
duke
parents:
diff changeset
   552
        ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   553
      mem = store;   // It's not a possibly interfering store.
204
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   554
      if (store == initial_mem)
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   555
        initial_mem = NULL;  // only process initial memory once
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   556
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   557
      for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   558
        store = mem->fast_out(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   559
        if (store->is_MergeMem()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   560
          // Be sure we don't get into combinatorial problems.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   561
          // (Allow phis to be repeated; they can merge two relevant states.)
204
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   562
          uint j = worklist_visited.size();
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   563
          for (; j > 0; j--) {
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   564
            if (worklist_visited.at(j-1) == store)  break;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   565
          }
204
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   566
          if (j > 0)  continue; // already on work list; do not repeat
154149c3f7ba 6590177: jck60019 test assert(!repeated,"do not walk merges twice")
kvn
parents: 1
diff changeset
   567
          worklist_visited.push(store);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   568
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   569
        worklist_mem.push(mem);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   570
        worklist_store.push(store);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   571
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   572
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   573
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   574
489c9b5090e2 Initial load
duke
parents:
diff changeset
   575
    if (op == Op_MachProj || op == Op_Catch)   continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   576
    if (store->needs_anti_dependence_check())  continue;  // not really a store
489c9b5090e2 Initial load
duke
parents:
diff changeset
   577
489c9b5090e2 Initial load
duke
parents:
diff changeset
   578
    // Compute the alias index.  Loads and stores with different alias
489c9b5090e2 Initial load
duke
parents:
diff changeset
   579
    // indices do not need anti-dependence edges.  Wide MemBar's are
489c9b5090e2 Initial load
duke
parents:
diff changeset
   580
    // anti-dependent on everything (except immutable memories).
489c9b5090e2 Initial load
duke
parents:
diff changeset
   581
    const TypePtr* adr_type = store->adr_type();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   582
    if (!C->can_alias(adr_type, load_alias_idx))  continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   583
489c9b5090e2 Initial load
duke
parents:
diff changeset
   584
    // Most slow-path runtime calls do NOT modify Java memory, but
489c9b5090e2 Initial load
duke
parents:
diff changeset
   585
    // they can block and so write Raw memory.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   586
    if (store->is_Mach()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   587
      MachNode* mstore = store->as_Mach();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   588
      if (load_alias_idx != Compile::AliasIdxRaw) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   589
        // Check for call into the runtime using the Java calling
489c9b5090e2 Initial load
duke
parents:
diff changeset
   590
        // convention (and from there into a wrapper); it has no
489c9b5090e2 Initial load
duke
parents:
diff changeset
   591
        // _method.  Can't do this optimization for Native calls because
489c9b5090e2 Initial load
duke
parents:
diff changeset
   592
        // they CAN write to Java memory.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   593
        if (mstore->ideal_Opcode() == Op_CallStaticJava) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   594
          assert(mstore->is_MachSafePoint(), "");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   595
          MachSafePointNode* ms = (MachSafePointNode*) mstore;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   596
          assert(ms->is_MachCallJava(), "");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   597
          MachCallJavaNode* mcj = (MachCallJavaNode*) ms;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   598
          if (mcj->_method == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   599
            // These runtime calls do not write to Java visible memory
489c9b5090e2 Initial load
duke
parents:
diff changeset
   600
            // (other than Raw) and so do not require anti-dependence edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   601
            continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   602
          }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   603
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   604
        // Same for SafePoints: they read/write Raw but only read otherwise.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   605
        // This is basically a workaround for SafePoints only defining control
489c9b5090e2 Initial load
duke
parents:
diff changeset
   606
        // instead of control + memory.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   607
        if (mstore->ideal_Opcode() == Op_SafePoint)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   608
          continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   609
      } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   610
        // Some raw memory, such as the load of "top" at an allocation,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   611
        // can be control dependent on the previous safepoint. See
489c9b5090e2 Initial load
duke
parents:
diff changeset
   612
        // comments in GraphKit::allocate_heap() about control input.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   613
        // Inserting an anti-dep between such a safepoint and a use
489c9b5090e2 Initial load
duke
parents:
diff changeset
   614
        // creates a cycle, and will cause a subsequent failure in
489c9b5090e2 Initial load
duke
parents:
diff changeset
   615
        // local scheduling.  (BugId 4919904)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   616
        // (%%% How can a control input be a safepoint and not a projection??)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   617
        if (mstore->ideal_Opcode() == Op_SafePoint && load->in(0) == mstore)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   618
          continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   619
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   620
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   621
489c9b5090e2 Initial load
duke
parents:
diff changeset
   622
    // Identify a block that the current load must be above,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   623
    // or else observe that 'store' is all the way up in the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   624
    // earliest legal block for 'load'.  In the latter case,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   625
    // immediately insert an anti-dependence edge.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   626
    Block* store_block = _bbs[store->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   627
    assert(store_block != NULL, "unused killing projections skipped above");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   628
489c9b5090e2 Initial load
duke
parents:
diff changeset
   629
    if (store->is_Phi()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   630
      // 'load' uses memory which is one (or more) of the Phi's inputs.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   631
      // It must be scheduled not before the Phi, but rather before
489c9b5090e2 Initial load
duke
parents:
diff changeset
   632
      // each of the relevant Phi inputs.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   633
      //
489c9b5090e2 Initial load
duke
parents:
diff changeset
   634
      // Instead of finding the LCA of all inputs to a Phi that match 'mem',
489c9b5090e2 Initial load
duke
parents:
diff changeset
   635
      // we mark each corresponding predecessor block and do a combined
489c9b5090e2 Initial load
duke
parents:
diff changeset
   636
      // hoisting operation later (raise_LCA_above_marks).
489c9b5090e2 Initial load
duke
parents:
diff changeset
   637
      //
489c9b5090e2 Initial load
duke
parents:
diff changeset
   638
      // Do not assert(store_block != early, "Phi merging memory after access")
489c9b5090e2 Initial load
duke
parents:
diff changeset
   639
      // PhiNode may be at start of block 'early' with backedge to 'early'
489c9b5090e2 Initial load
duke
parents:
diff changeset
   640
      DEBUG_ONLY(bool found_match = false);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   641
      for (uint j = PhiNode::Input, jmax = store->req(); j < jmax; j++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   642
        if (store->in(j) == mem) {   // Found matching input?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   643
          DEBUG_ONLY(found_match = true);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   644
          Block* pred_block = _bbs[store_block->pred(j)->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   645
          if (pred_block != early) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   646
            // If any predecessor of the Phi matches the load's "early block",
489c9b5090e2 Initial load
duke
parents:
diff changeset
   647
            // we do not need a precedence edge between the Phi and 'load'
2131
98f9cef66a34 6810672: Comment typos
twisti
parents: 2127
diff changeset
   648
            // since the load will be forced into a block preceding the Phi.
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   649
            pred_block->set_raise_LCA_mark(load_index);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   650
            assert(!LCA_orig->dominates(pred_block) ||
489c9b5090e2 Initial load
duke
parents:
diff changeset
   651
                   early->dominates(pred_block), "early is high enough");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   652
            must_raise_LCA = true;
2875
549b4d80b29e 6843752: missing code for an anti-dependent Phi in GCM
kvn
parents: 2348
diff changeset
   653
          } else {
549b4d80b29e 6843752: missing code for an anti-dependent Phi in GCM
kvn
parents: 2348
diff changeset
   654
            // anti-dependent upon PHI pinned below 'early', no edge needed
549b4d80b29e 6843752: missing code for an anti-dependent Phi in GCM
kvn
parents: 2348
diff changeset
   655
            LCA = early;             // but can not schedule below 'early'
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   656
          }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   657
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   658
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   659
      assert(found_match, "no worklist bug");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   660
#ifdef TRACK_PHI_INPUTS
489c9b5090e2 Initial load
duke
parents:
diff changeset
   661
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   662
      // This assert asks about correct handling of PhiNodes, which may not
489c9b5090e2 Initial load
duke
parents:
diff changeset
   663
      // have all input edges directly from 'mem'. See BugId 4621264
489c9b5090e2 Initial load
duke
parents:
diff changeset
   664
      int num_mem_inputs = phi_inputs.at_grow(store->_idx,0) + 1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   665
      // Increment by exactly one even if there are multiple copies of 'mem'
489c9b5090e2 Initial load
duke
parents:
diff changeset
   666
      // coming into the phi, because we will run this block several times
489c9b5090e2 Initial load
duke
parents:
diff changeset
   667
      // if there are several copies of 'mem'.  (That's how DU iterators work.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   668
      phi_inputs.at_put(store->_idx, num_mem_inputs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   669
      assert(PhiNode::Input + num_mem_inputs < store->req(),
489c9b5090e2 Initial load
duke
parents:
diff changeset
   670
             "Expect at least one phi input will not be from original memory state");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   671
#endif //ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   672
#endif //TRACK_PHI_INPUTS
489c9b5090e2 Initial load
duke
parents:
diff changeset
   673
    } else if (store_block != early) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   674
      // 'store' is between the current LCA and earliest possible block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   675
      // Label its block, and decide later on how to raise the LCA
489c9b5090e2 Initial load
duke
parents:
diff changeset
   676
      // to include the effect on LCA of this store.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   677
      // If this store's block gets chosen as the raised LCA, we
489c9b5090e2 Initial load
duke
parents:
diff changeset
   678
      // will find him on the non_early_stores list and stick him
489c9b5090e2 Initial load
duke
parents:
diff changeset
   679
      // with a precedence edge.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   680
      // (But, don't bother if LCA is already raised all the way.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   681
      if (LCA != early) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   682
        store_block->set_raise_LCA_mark(load_index);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   683
        must_raise_LCA = true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   684
        non_early_stores.push(store);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   685
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   686
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   687
      // Found a possibly-interfering store in the load's 'early' block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   688
      // This means 'load' cannot sink at all in the dominator tree.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   689
      // Add an anti-dep edge, and squeeze 'load' into the highest block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   690
      assert(store != load->in(0), "dependence cycle found");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   691
      if (verify) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   692
        assert(store->find_edge(load) != -1, "missing precedence edge");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   693
      } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   694
        store->add_prec(load);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   695
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   696
      LCA = early;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   697
      // This turns off the process of gathering non_early_stores.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   698
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   699
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   700
  // (Worklist is now empty; all nearby stores have been visited.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   701
489c9b5090e2 Initial load
duke
parents:
diff changeset
   702
  // Finished if 'load' must be scheduled in its 'early' block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   703
  // If we found any stores there, they have already been given
489c9b5090e2 Initial load
duke
parents:
diff changeset
   704
  // precedence edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   705
  if (LCA == early)  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   706
489c9b5090e2 Initial load
duke
parents:
diff changeset
   707
  // We get here only if there are no possibly-interfering stores
489c9b5090e2 Initial load
duke
parents:
diff changeset
   708
  // in the load's 'early' block.  Move LCA up above all predecessors
489c9b5090e2 Initial load
duke
parents:
diff changeset
   709
  // which contain stores we have noted.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   710
  //
489c9b5090e2 Initial load
duke
parents:
diff changeset
   711
  // The raised LCA block can be a home to such interfering stores,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   712
  // but its predecessors must not contain any such stores.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   713
  //
489c9b5090e2 Initial load
duke
parents:
diff changeset
   714
  // The raised LCA will be a lower bound for placing the load,
489c9b5090e2 Initial load
duke
parents:
diff changeset
   715
  // preventing the load from sinking past any block containing
489c9b5090e2 Initial load
duke
parents:
diff changeset
   716
  // a store that may invalidate the memory state required by 'load'.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   717
  if (must_raise_LCA)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   718
    LCA = raise_LCA_above_marks(LCA, load->_idx, early, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   719
  if (LCA == early)  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   720
489c9b5090e2 Initial load
duke
parents:
diff changeset
   721
  // Insert anti-dependence edges from 'load' to each store
489c9b5090e2 Initial load
duke
parents:
diff changeset
   722
  // in the non-early LCA block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   723
  // Mine the non_early_stores list for such stores.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   724
  if (LCA->raise_LCA_mark() == load_index) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   725
    while (non_early_stores.size() > 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   726
      Node* store = non_early_stores.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   727
      Block* store_block = _bbs[store->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   728
      if (store_block == LCA) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   729
        // add anti_dependence from store to load in its own block
489c9b5090e2 Initial load
duke
parents:
diff changeset
   730
        assert(store != load->in(0), "dependence cycle found");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   731
        if (verify) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   732
          assert(store->find_edge(load) != -1, "missing precedence edge");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   733
        } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   734
          store->add_prec(load);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   735
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   736
      } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   737
        assert(store_block->raise_LCA_mark() == load_index, "block was marked");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   738
        // Any other stores we found must be either inside the new LCA
489c9b5090e2 Initial load
duke
parents:
diff changeset
   739
        // or else outside the original LCA.  In the latter case, they
489c9b5090e2 Initial load
duke
parents:
diff changeset
   740
        // did not interfere with any use of 'load'.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   741
        assert(LCA->dominates(store_block)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   742
               || !LCA_orig->dominates(store_block), "no stray stores");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   743
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   744
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   745
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   746
489c9b5090e2 Initial load
duke
parents:
diff changeset
   747
  // Return the highest block containing stores; any stores
489c9b5090e2 Initial load
duke
parents:
diff changeset
   748
  // within that block have been given anti-dependence edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   749
  return LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   750
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   751
489c9b5090e2 Initial load
duke
parents:
diff changeset
   752
// This class is used to iterate backwards over the nodes in the graph.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   753
489c9b5090e2 Initial load
duke
parents:
diff changeset
   754
class Node_Backward_Iterator {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   755
489c9b5090e2 Initial load
duke
parents:
diff changeset
   756
private:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   757
  Node_Backward_Iterator();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   758
489c9b5090e2 Initial load
duke
parents:
diff changeset
   759
public:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   760
  // Constructor for the iterator
489c9b5090e2 Initial load
duke
parents:
diff changeset
   761
  Node_Backward_Iterator(Node *root, VectorSet &visited, Node_List &stack, Block_Array &bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   762
489c9b5090e2 Initial load
duke
parents:
diff changeset
   763
  // Postincrement operator to iterate over the nodes
489c9b5090e2 Initial load
duke
parents:
diff changeset
   764
  Node *next();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   765
489c9b5090e2 Initial load
duke
parents:
diff changeset
   766
private:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   767
  VectorSet   &_visited;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   768
  Node_List   &_stack;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   769
  Block_Array &_bbs;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   770
};
489c9b5090e2 Initial load
duke
parents:
diff changeset
   771
489c9b5090e2 Initial load
duke
parents:
diff changeset
   772
// Constructor for the Node_Backward_Iterator
489c9b5090e2 Initial load
duke
parents:
diff changeset
   773
Node_Backward_Iterator::Node_Backward_Iterator( Node *root, VectorSet &visited, Node_List &stack, Block_Array &bbs )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   774
  : _visited(visited), _stack(stack), _bbs(bbs) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   775
  // The stack should contain exactly the root
489c9b5090e2 Initial load
duke
parents:
diff changeset
   776
  stack.clear();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   777
  stack.push(root);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   778
489c9b5090e2 Initial load
duke
parents:
diff changeset
   779
  // Clear the visited bits
489c9b5090e2 Initial load
duke
parents:
diff changeset
   780
  visited.Clear();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   781
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   782
489c9b5090e2 Initial load
duke
parents:
diff changeset
   783
// Iterator for the Node_Backward_Iterator
489c9b5090e2 Initial load
duke
parents:
diff changeset
   784
Node *Node_Backward_Iterator::next() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   785
489c9b5090e2 Initial load
duke
parents:
diff changeset
   786
  // If the _stack is empty, then just return NULL: finished.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   787
  if ( !_stack.size() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   788
    return NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   789
489c9b5090e2 Initial load
duke
parents:
diff changeset
   790
  // '_stack' is emulating a real _stack.  The 'visit-all-users' loop has been
489c9b5090e2 Initial load
duke
parents:
diff changeset
   791
  // made stateless, so I do not need to record the index 'i' on my _stack.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   792
  // Instead I visit all users each time, scanning for unvisited users.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   793
  // I visit unvisited not-anti-dependence users first, then anti-dependent
489c9b5090e2 Initial load
duke
parents:
diff changeset
   794
  // children next.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   795
  Node *self = _stack.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   796
489c9b5090e2 Initial load
duke
parents:
diff changeset
   797
  // I cycle here when I am entering a deeper level of recursion.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   798
  // The key variable 'self' was set prior to jumping here.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   799
  while( 1 ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   800
489c9b5090e2 Initial load
duke
parents:
diff changeset
   801
    _visited.set(self->_idx);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   802
489c9b5090e2 Initial load
duke
parents:
diff changeset
   803
    // Now schedule all uses as late as possible.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   804
    uint src     = self->is_Proj() ? self->in(0)->_idx : self->_idx;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   805
    uint src_rpo = _bbs[src]->_rpo;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   806
489c9b5090e2 Initial load
duke
parents:
diff changeset
   807
    // Schedule all nodes in a post-order visit
489c9b5090e2 Initial load
duke
parents:
diff changeset
   808
    Node *unvisited = NULL;  // Unvisited anti-dependent Node, if any
489c9b5090e2 Initial load
duke
parents:
diff changeset
   809
489c9b5090e2 Initial load
duke
parents:
diff changeset
   810
    // Scan for unvisited nodes
489c9b5090e2 Initial load
duke
parents:
diff changeset
   811
    for (DUIterator_Fast imax, i = self->fast_outs(imax); i < imax; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   812
      // For all uses, schedule late
489c9b5090e2 Initial load
duke
parents:
diff changeset
   813
      Node* n = self->fast_out(i); // Use
489c9b5090e2 Initial load
duke
parents:
diff changeset
   814
489c9b5090e2 Initial load
duke
parents:
diff changeset
   815
      // Skip already visited children
489c9b5090e2 Initial load
duke
parents:
diff changeset
   816
      if ( _visited.test(n->_idx) )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   817
        continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   818
489c9b5090e2 Initial load
duke
parents:
diff changeset
   819
      // do not traverse backward control edges
489c9b5090e2 Initial load
duke
parents:
diff changeset
   820
      Node *use = n->is_Proj() ? n->in(0) : n;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   821
      uint use_rpo = _bbs[use->_idx]->_rpo;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   822
489c9b5090e2 Initial load
duke
parents:
diff changeset
   823
      if ( use_rpo < src_rpo )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   824
        continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   825
489c9b5090e2 Initial load
duke
parents:
diff changeset
   826
      // Phi nodes always precede uses in a basic block
489c9b5090e2 Initial load
duke
parents:
diff changeset
   827
      if ( use_rpo == src_rpo && use->is_Phi() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   828
        continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   829
489c9b5090e2 Initial load
duke
parents:
diff changeset
   830
      unvisited = n;      // Found unvisited
489c9b5090e2 Initial load
duke
parents:
diff changeset
   831
489c9b5090e2 Initial load
duke
parents:
diff changeset
   832
      // Check for possible-anti-dependent
489c9b5090e2 Initial load
duke
parents:
diff changeset
   833
      if( !n->needs_anti_dependence_check() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   834
        break;            // Not visited, not anti-dep; schedule it NOW
489c9b5090e2 Initial load
duke
parents:
diff changeset
   835
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   836
489c9b5090e2 Initial load
duke
parents:
diff changeset
   837
    // Did I find an unvisited not-anti-dependent Node?
489c9b5090e2 Initial load
duke
parents:
diff changeset
   838
    if ( !unvisited )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   839
      break;                  // All done with children; post-visit 'self'
489c9b5090e2 Initial load
duke
parents:
diff changeset
   840
489c9b5090e2 Initial load
duke
parents:
diff changeset
   841
    // Visit the unvisited Node.  Contains the obvious push to
489c9b5090e2 Initial load
duke
parents:
diff changeset
   842
    // indicate I'm entering a deeper level of recursion.  I push the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   843
    // old state onto the _stack and set a new state and loop (recurse).
489c9b5090e2 Initial load
duke
parents:
diff changeset
   844
    _stack.push(self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   845
    self = unvisited;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   846
  } // End recursion loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
   847
489c9b5090e2 Initial load
duke
parents:
diff changeset
   848
  return self;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   849
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   850
489c9b5090e2 Initial load
duke
parents:
diff changeset
   851
//------------------------------ComputeLatenciesBackwards----------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   852
// Compute the latency of all the instructions.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   853
void PhaseCFG::ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   854
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   855
  if (trace_opto_pipelining())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   856
    tty->print("\n#---- ComputeLatenciesBackwards ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   857
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   858
489c9b5090e2 Initial load
duke
parents:
diff changeset
   859
  Node_Backward_Iterator iter((Node *)_root, visited, stack, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   860
  Node *n;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   861
489c9b5090e2 Initial load
duke
parents:
diff changeset
   862
  // Walk over all the nodes from last to first
489c9b5090e2 Initial load
duke
parents:
diff changeset
   863
  while (n = iter.next()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   864
    // Set the latency for the definitions of this instruction
489c9b5090e2 Initial load
duke
parents:
diff changeset
   865
    partial_latency_of_defs(n);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   866
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   867
} // end ComputeLatenciesBackwards
489c9b5090e2 Initial load
duke
parents:
diff changeset
   868
489c9b5090e2 Initial load
duke
parents:
diff changeset
   869
//------------------------------partial_latency_of_defs------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   870
// Compute the latency impact of this node on all defs.  This computes
489c9b5090e2 Initial load
duke
parents:
diff changeset
   871
// a number that increases as we approach the beginning of the routine.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   872
void PhaseCFG::partial_latency_of_defs(Node *n) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   873
  // Set the latency for this instruction
489c9b5090e2 Initial load
duke
parents:
diff changeset
   874
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   875
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   876
    tty->print("# latency_to_inputs: node_latency[%d] = %d for node",
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   877
               n->_idx, _node_latency->at_grow(n->_idx));
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   878
    dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   879
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   880
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   881
489c9b5090e2 Initial load
duke
parents:
diff changeset
   882
  if (n->is_Proj())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   883
    n = n->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   884
489c9b5090e2 Initial load
duke
parents:
diff changeset
   885
  if (n->is_Root())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   886
    return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   887
489c9b5090e2 Initial load
duke
parents:
diff changeset
   888
  uint nlen = n->len();
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   889
  uint use_latency = _node_latency->at_grow(n->_idx);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   890
  uint use_pre_order = _bbs[n->_idx]->_pre_order;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   891
489c9b5090e2 Initial load
duke
parents:
diff changeset
   892
  for ( uint j=0; j<nlen; j++ ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   893
    Node *def = n->in(j);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   894
489c9b5090e2 Initial load
duke
parents:
diff changeset
   895
    if (!def || def == n)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   896
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   897
489c9b5090e2 Initial load
duke
parents:
diff changeset
   898
    // Walk backwards thru projections
489c9b5090e2 Initial load
duke
parents:
diff changeset
   899
    if (def->is_Proj())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   900
      def = def->in(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   901
489c9b5090e2 Initial load
duke
parents:
diff changeset
   902
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   903
    if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   904
      tty->print("#    in(%2d): ", j);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   905
      def->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   906
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   907
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   908
489c9b5090e2 Initial load
duke
parents:
diff changeset
   909
    // If the defining block is not known, assume it is ok
489c9b5090e2 Initial load
duke
parents:
diff changeset
   910
    Block *def_block = _bbs[def->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   911
    uint def_pre_order = def_block ? def_block->_pre_order : 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   912
489c9b5090e2 Initial load
duke
parents:
diff changeset
   913
    if ( (use_pre_order <  def_pre_order) ||
489c9b5090e2 Initial load
duke
parents:
diff changeset
   914
         (use_pre_order == def_pre_order && n->is_Phi()) )
489c9b5090e2 Initial load
duke
parents:
diff changeset
   915
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   916
489c9b5090e2 Initial load
duke
parents:
diff changeset
   917
    uint delta_latency = n->latency(j);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   918
    uint current_latency = delta_latency + use_latency;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   919
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   920
    if (_node_latency->at_grow(def->_idx) < current_latency) {
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   921
      _node_latency->at_put_grow(def->_idx, current_latency);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   922
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   923
489c9b5090e2 Initial load
duke
parents:
diff changeset
   924
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   925
    if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   926
      tty->print_cr("#      %d + edge_latency(%d) == %d -> %d, node_latency[%d] = %d",
489c9b5090e2 Initial load
duke
parents:
diff changeset
   927
                    use_latency, j, delta_latency, current_latency, def->_idx,
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   928
                    _node_latency->at_grow(def->_idx));
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   929
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   930
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   931
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   932
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   933
489c9b5090e2 Initial load
duke
parents:
diff changeset
   934
//------------------------------latency_from_use-------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   935
// Compute the latency of a specific use
489c9b5090e2 Initial load
duke
parents:
diff changeset
   936
int PhaseCFG::latency_from_use(Node *n, const Node *def, Node *use) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   937
  // If self-reference, return no latency
489c9b5090e2 Initial load
duke
parents:
diff changeset
   938
  if (use == n || use->is_Root())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   939
    return 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   940
489c9b5090e2 Initial load
duke
parents:
diff changeset
   941
  uint def_pre_order = _bbs[def->_idx]->_pre_order;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   942
  uint latency = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   943
489c9b5090e2 Initial load
duke
parents:
diff changeset
   944
  // If the use is not a projection, then it is simple...
489c9b5090e2 Initial load
duke
parents:
diff changeset
   945
  if (!use->is_Proj()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   946
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   947
    if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   948
      tty->print("#    out(): ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   949
      use->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   950
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   951
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   952
489c9b5090e2 Initial load
duke
parents:
diff changeset
   953
    uint use_pre_order = _bbs[use->_idx]->_pre_order;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   954
489c9b5090e2 Initial load
duke
parents:
diff changeset
   955
    if (use_pre_order < def_pre_order)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   956
      return 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   957
489c9b5090e2 Initial load
duke
parents:
diff changeset
   958
    if (use_pre_order == def_pre_order && use->is_Phi())
489c9b5090e2 Initial load
duke
parents:
diff changeset
   959
      return 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   960
489c9b5090e2 Initial load
duke
parents:
diff changeset
   961
    uint nlen = use->len();
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   962
    uint nl = _node_latency->at_grow(use->_idx);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   963
489c9b5090e2 Initial load
duke
parents:
diff changeset
   964
    for ( uint j=0; j<nlen; j++ ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   965
      if (use->in(j) == n) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   966
        // Change this if we want local latencies
489c9b5090e2 Initial load
duke
parents:
diff changeset
   967
        uint ul = use->latency(j);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   968
        uint  l = ul + nl;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   969
        if (latency < l) latency = l;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   970
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   971
        if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   972
          tty->print_cr("#      %d + edge_latency(%d) == %d -> %d, latency = %d",
489c9b5090e2 Initial load
duke
parents:
diff changeset
   973
                        nl, j, ul, l, latency);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   974
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   975
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
   976
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   977
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   978
  } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   979
    // This is a projection, just grab the latency of the use(s)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   980
    for (DUIterator_Fast jmax, j = use->fast_outs(jmax); j < jmax; j++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   981
      uint l = latency_from_use(use, def, use->fast_out(j));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   982
      if (latency < l) latency = l;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   983
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   984
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   985
489c9b5090e2 Initial load
duke
parents:
diff changeset
   986
  return latency;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   987
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   988
489c9b5090e2 Initial load
duke
parents:
diff changeset
   989
//------------------------------latency_from_uses------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
   990
// Compute the latency of this instruction relative to all of it's uses.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   991
// This computes a number that increases as we approach the beginning of the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   992
// routine.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   993
void PhaseCFG::latency_from_uses(Node *n) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   994
  // Set the latency for this instruction
489c9b5090e2 Initial load
duke
parents:
diff changeset
   995
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
   996
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   997
    tty->print("# latency_from_outputs: node_latency[%d] = %d for node",
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   998
               n->_idx, _node_latency->at_grow(n->_idx));
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   999
    dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1000
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1001
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1002
  uint latency=0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1003
  const Node *def = n->is_Proj() ? n->in(0): n;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1004
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1005
  for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1006
    uint l = latency_from_use(n, def, n->fast_out(i));
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1007
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1008
    if (latency < l) latency = l;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1009
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1010
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1011
  _node_latency->at_put_grow(n->_idx, latency);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1012
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1013
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1014
//------------------------------hoist_to_cheaper_block-------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1015
// Pick a block for node self, between early and LCA, that is a cheaper
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1016
// alternative to LCA.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1017
Block* PhaseCFG::hoist_to_cheaper_block(Block* LCA, Block* early, Node* self) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1018
  const double delta = 1+PROB_UNLIKELY_MAG(4);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1019
  Block* least       = LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1020
  double least_freq  = least->_freq;
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1021
  uint target        = _node_latency->at_grow(self->_idx);
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1022
  uint start_latency = _node_latency->at_grow(LCA->_nodes[0]->_idx);
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1023
  uint end_latency   = _node_latency->at_grow(LCA->_nodes[LCA->end_idx()]->_idx);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1024
  bool in_latency    = (target <= start_latency);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1025
  const Block* root_block = _bbs[_root->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1026
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1027
  // Turn off latency scheduling if scheduling is just plain off
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1028
  if (!C->do_scheduling())
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1029
    in_latency = true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1030
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1031
  // Do not hoist (to cover latency) instructions which target a
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1032
  // single register.  Hoisting stretches the live range of the
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1033
  // single register and may force spilling.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1034
  MachNode* mach = self->is_Mach() ? self->as_Mach() : NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1035
  if (mach && mach->out_RegMask().is_bound1() && mach->out_RegMask().is_NotEmpty())
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1036
    in_latency = true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1037
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1038
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1039
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1040
    tty->print("# Find cheaper block for latency %d: ",
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1041
      _node_latency->at_grow(self->_idx));
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1042
    self->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1043
    tty->print_cr("#   B%d: start latency for [%4d]=%d, end latency for [%4d]=%d, freq=%g",
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1044
      LCA->_pre_order,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1045
      LCA->_nodes[0]->_idx,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1046
      start_latency,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1047
      LCA->_nodes[LCA->end_idx()]->_idx,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1048
      end_latency,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1049
      least_freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1050
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1051
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1052
15871
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1053
  int cand_cnt = 0;  // number of candidates tried
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1054
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1055
  // Walk up the dominator tree from LCA (Lowest common ancestor) to
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1056
  // the earliest legal location.  Capture the least execution frequency.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1057
  while (LCA != early) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1058
    LCA = LCA->_idom;         // Follow up the dominator tree
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1059
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1060
    if (LCA == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1061
      // Bailout without retry
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1062
      C->record_method_not_compilable("late schedule failed: LCA == NULL");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1063
      return least;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1064
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1065
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1066
    // Don't hoist machine instructions to the root basic block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1067
    if (mach && LCA == root_block)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1068
      break;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1069
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1070
    uint start_lat = _node_latency->at_grow(LCA->_nodes[0]->_idx);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1071
    uint end_idx   = LCA->end_idx();
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1072
    uint end_lat   = _node_latency->at_grow(LCA->_nodes[end_idx]->_idx);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1073
    double LCA_freq = LCA->_freq;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1074
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1075
    if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1076
      tty->print_cr("#   B%d: start latency for [%4d]=%d, end latency for [%4d]=%d, freq=%g",
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1077
        LCA->_pre_order, LCA->_nodes[0]->_idx, start_lat, end_idx, end_lat, LCA_freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1078
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1079
#endif
15871
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1080
    cand_cnt++;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1081
    if (LCA_freq < least_freq              || // Better Frequency
15871
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1082
        (StressGCM && Compile::randomized_select(cand_cnt)) || // Should be randomly accepted in stress mode
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1083
         (!StressGCM                    &&    // Otherwise, choose with latency
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1084
          !in_latency                   &&    // No block containing latency
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1085
          LCA_freq < least_freq * delta &&    // No worse frequency
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1086
          target >= end_lat             &&    // within latency range
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1087
          !self->is_iteratively_computed() )  // But don't hoist IV increments
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1088
             // because they may end up above other uses of their phi forcing
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1089
             // their result register to be different from their input.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1090
       ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1091
      least = LCA;            // Found cheaper block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1092
      least_freq = LCA_freq;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1093
      start_latency = start_lat;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1094
      end_latency = end_lat;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1095
      if (target <= start_lat)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1096
        in_latency = true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1097
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1098
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1099
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1100
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1101
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1102
    tty->print_cr("#  Choose block B%d with start latency=%d and freq=%g",
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1103
      least->_pre_order, start_latency, least_freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1104
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1105
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1106
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1107
  // See if the latency needs to be updated
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1108
  if (target < end_latency) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1109
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1110
    if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1111
      tty->print_cr("#  Change latency for [%4d] from %d to %d", self->_idx, target, end_latency);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1112
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1113
#endif
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1114
    _node_latency->at_put_grow(self->_idx, end_latency);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1115
    partial_latency_of_defs(self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1116
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1117
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1118
  return least;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1119
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1120
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1121
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1122
//------------------------------schedule_late-----------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1123
// Now schedule all codes as LATE as possible.  This is the LCA in the
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1124
// dominator tree of all USES of a value.  Pick the block with the least
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1125
// loop nesting depth that is lowest in the dominator tree.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1126
extern const char must_clone[];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1127
void PhaseCFG::schedule_late(VectorSet &visited, Node_List &stack) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1128
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1129
  if (trace_opto_pipelining())
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1130
    tty->print("\n#---- schedule_late ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1131
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1132
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1133
  Node_Backward_Iterator iter((Node *)_root, visited, stack, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1134
  Node *self;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1135
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1136
  // Walk over all the nodes from last to first
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1137
  while (self = iter.next()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1138
    Block* early = _bbs[self->_idx];   // Earliest legal placement
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1139
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1140
    if (self->is_top()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1141
      // Top node goes in bb #2 with other constants.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1142
      // It must be special-cased, because it has no out edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1143
      early->add_inst(self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1144
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1145
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1146
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1147
    // No uses, just terminate
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1148
    if (self->outcnt() == 0) {
10255
bab46e6f7661 7069452: Cleanup NodeFlags
kvn
parents: 8921
diff changeset
  1149
      assert(self->is_MachProj(), "sanity");
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1150
      continue;                   // Must be a dead machine projection
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1151
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1152
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1153
    // If node is pinned in the block, then no scheduling can be done.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1154
    if( self->pinned() )          // Pinned in block?
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1155
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1156
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1157
    MachNode* mach = self->is_Mach() ? self->as_Mach() : NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1158
    if (mach) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1159
      switch (mach->ideal_Opcode()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1160
      case Op_CreateEx:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1161
        // Don't move exception creation
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1162
        early->add_inst(self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1163
        continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1164
        break;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1165
      case Op_CheckCastPP:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1166
        // Don't move CheckCastPP nodes away from their input, if the input
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1167
        // is a rawptr (5071820).
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1168
        Node *def = self->in(1);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1169
        if (def != NULL && def->bottom_type()->base() == Type::RawPtr) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1170
          early->add_inst(self);
3186
11ba3d09bd0e 6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents: 2875
diff changeset
  1171
#ifdef ASSERT
11ba3d09bd0e 6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents: 2875
diff changeset
  1172
          _raw_oops.push(def);
11ba3d09bd0e 6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents: 2875
diff changeset
  1173
#endif
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1174
          continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1175
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1176
        break;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1177
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1178
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1179
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1180
    // Gather LCA of all uses
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1181
    Block *LCA = NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1182
    {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1183
      for (DUIterator_Fast imax, i = self->fast_outs(imax); i < imax; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1184
        // For all uses, find LCA
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1185
        Node* use = self->fast_out(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1186
        LCA = raise_LCA_above_use(LCA, use, self, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1187
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1188
    }  // (Hide defs of imax, i from rest of block.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1189
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1190
    // Place temps in the block of their use.  This isn't a
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1191
    // requirement for correctness but it reduces useless
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1192
    // interference between temps and other nodes.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1193
    if (mach != NULL && mach->is_MachTemp()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1194
      _bbs.map(self->_idx, LCA);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1195
      LCA->add_inst(self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1196
      continue;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1197
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1198
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1199
    // Check if 'self' could be anti-dependent on memory
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1200
    if (self->needs_anti_dependence_check()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1201
      // Hoist LCA above possible-defs and insert anti-dependences to
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1202
      // defs in new LCA block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1203
      LCA = insert_anti_dependences(LCA, self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1204
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1205
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1206
    if (early->_dom_depth > LCA->_dom_depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1207
      // Somehow the LCA has moved above the earliest legal point.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1208
      // (One way this can happen is via memory_early_block.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1209
      if (C->subsume_loads() == true && !C->failing()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1210
        // Retry with subsume_loads == false
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1211
        // If this is the first failure, the sentinel string will "stick"
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1212
        // to the Compile object, and the C2Compiler will see it and retry.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1213
        C->record_failure(C2Compiler::retry_no_subsuming_loads());
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1214
      } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1215
        // Bailout without retry when (early->_dom_depth > LCA->_dom_depth)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1216
        C->record_method_not_compilable("late schedule failed: incorrect graph");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1217
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1218
      return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1219
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1220
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1221
    // If there is no opportunity to hoist, then we're done.
15871
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1222
    // In stress mode, try to hoist even the single operations.
b04dd94da4e6 8009120: Fuzz instruction scheduling in HotSpot compilers
shade
parents: 14623
diff changeset
  1223
    bool try_to_hoist = StressGCM || (LCA != early);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1224
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1225
    // Must clone guys stay next to use; no hoisting allowed.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1226
    // Also cannot hoist guys that alter memory or are otherwise not
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1227
    // allocatable (hoisting can make a value live longer, leading to
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1228
    // anti and output dependency problems which are normally resolved
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1229
    // by the register allocator giving everyone a different register).
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1230
    if (mach != NULL && must_clone[mach->ideal_Opcode()])
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1231
      try_to_hoist = false;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1232
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1233
    Block* late = NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1234
    if (try_to_hoist) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1235
      // Now find the block with the least execution frequency.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1236
      // Start at the latest schedule and work up to the earliest schedule
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1237
      // in the dominator tree.  Thus the Node will dominate all its uses.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1238
      late = hoist_to_cheaper_block(LCA, early, self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1239
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1240
      // Just use the LCA of the uses.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1241
      late = LCA;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1242
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1243
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1244
    // Put the node into target block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1245
    schedule_node_into_block(self, late);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1246
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1247
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1248
    if (self->needs_anti_dependence_check()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1249
      // since precedence edges are only inserted when we're sure they
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1250
      // are needed make sure that after placement in a block we don't
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1251
      // need any new precedence edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1252
      verify_anti_dependences(late, self);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1253
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1254
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1255
  } // Loop until all nodes have been visited
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1256
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1257
} // end ScheduleLate
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1258
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1259
//------------------------------GlobalCodeMotion-------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1260
void PhaseCFG::GlobalCodeMotion( Matcher &matcher, uint unique, Node_List &proj_list ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1261
  ResourceMark rm;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1262
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1263
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1264
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1265
    tty->print("\n---- Start GlobalCodeMotion ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1266
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1267
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1268
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1269
  // Initialize the bbs.map for things on the proj_list
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1270
  uint i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1271
  for( i=0; i < proj_list.size(); i++ )
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1272
    _bbs.map(proj_list[i]->_idx, NULL);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1273
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1274
  // Set the basic block for Nodes pinned into blocks
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1275
  Arena *a = Thread::current()->resource_area();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1276
  VectorSet visited(a);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1277
  schedule_pinned_nodes( visited );
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1278
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1279
  // Find the earliest Block any instruction can be placed in.  Some
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1280
  // instructions are pinned into Blocks.  Unpinned instructions can
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1281
  // appear in last block in which all their inputs occur.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1282
  visited.Clear();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1283
  Node_List stack(a);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1284
  stack.map( (unique >> 1) + 16, NULL); // Pre-grow the list
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1285
  if (!schedule_early(visited, stack)) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1286
    // Bailout without retry
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1287
    C->record_method_not_compilable("early schedule failed");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1288
    return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1289
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1290
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1291
  // Build Def-Use edges.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1292
  proj_list.push(_root);        // Add real root as another root
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1293
  proj_list.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1294
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1295
  // Compute the latency information (via backwards walk) for all the
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1296
  // instructions in the graph
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1297
  _node_latency = new GrowableArray<uint>(); // resource_area allocation
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1298
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1299
  if( C->do_scheduling() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1300
    ComputeLatenciesBackwards(visited, stack);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1301
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1302
  // Now schedule all codes as LATE as possible.  This is the LCA in the
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1303
  // dominator tree of all USES of a value.  Pick the block with the least
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1304
  // loop nesting depth that is lowest in the dominator tree.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1305
  // ( visited.Clear() called in schedule_late()->Node_Backward_Iterator() )
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1306
  schedule_late(visited, stack);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1307
  if( C->failing() ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1308
    // schedule_late fails only when graph is incorrect.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1309
    assert(!VerifyGraphEdges, "verification should have failed");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1310
    return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1311
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1312
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1313
  unique = C->unique();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1314
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1315
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1316
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1317
    tty->print("\n---- Detect implicit null checks ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1318
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1319
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1320
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1321
  // Detect implicit-null-check opportunities.  Basically, find NULL checks
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1322
  // with suitable memory ops nearby.  Use the memory op to do the NULL check.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1323
  // I can generate a memory op if there is not one nearby.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1324
  if (C->is_method_compilation()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1325
    // Don't do it for natives, adapters, or runtime stubs
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1326
    int allowed_reasons = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1327
    // ...and don't do it when there have been too many traps, globally.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1328
    for (int reason = (int)Deoptimization::Reason_none+1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1329
         reason < Compile::trapHistLength; reason++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1330
      assert(reason < BitsPerInt, "recode bit map");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1331
      if (!C->too_many_traps((Deoptimization::DeoptReason) reason))
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1332
        allowed_reasons |= nth_bit(reason);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1333
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1334
    // By reversing the loop direction we get a very minor gain on mpegaudio.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1335
    // Feel free to revert to a forward loop for clarity.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1336
    // for( int i=0; i < (int)matcher._null_check_tests.size(); i+=2 ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1337
    for( int i= matcher._null_check_tests.size()-2; i>=0; i-=2 ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1338
      Node *proj = matcher._null_check_tests[i  ];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1339
      Node *val  = matcher._null_check_tests[i+1];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1340
      _bbs[proj->_idx]->implicit_null_check(this, proj, val, allowed_reasons);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1341
      // The implicit_null_check will only perform the transformation
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1342
      // if the null branch is truly uncommon, *and* it leads to an
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1343
      // uncommon trap.  Combined with the too_many_traps guards
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1344
      // above, this prevents SEGV storms reported in 6366351,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1345
      // by recompiling offending methods without this optimization.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1346
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1347
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1348
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1349
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1350
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1351
    tty->print("\n---- Start Local Scheduling ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1352
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1353
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1354
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1355
  // Schedule locally.  Right now a simple topological sort.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1356
  // Later, do a real latency aware scheduler.
11567
512b2c76e3b7 7116050: C2/ARM: memory stomping error with DivideMcTests
roland
parents: 11191
diff changeset
  1357
  uint max_idx = C->unique();
512b2c76e3b7 7116050: C2/ARM: memory stomping error with DivideMcTests
roland
parents: 11191
diff changeset
  1358
  GrowableArray<int> ready_cnt(max_idx, max_idx, -1);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1359
  visited.Clear();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1360
  for (i = 0; i < _num_blocks; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1361
    if (!_blocks[i]->schedule_local(this, matcher, ready_cnt, visited)) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1362
      if (!C->failure_reason_is(C2Compiler::retry_no_subsuming_loads())) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1363
        C->record_method_not_compilable("local schedule failed");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1364
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1365
      return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1366
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1367
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1368
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1369
  // If we inserted any instructions between a Call and his CatchNode,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1370
  // clone the instructions on all paths below the Catch.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1371
  for( i=0; i < _num_blocks; i++ )
14623
70c4c1be0a14 7092905: C2: Keep track of the number of dead nodes
bharadwaj
parents: 13963
diff changeset
  1372
    _blocks[i]->call_catch_cleanup(_bbs, C);
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1373
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1374
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1375
  if (trace_opto_pipelining()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1376
    tty->print("\n---- After GlobalCodeMotion ----\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1377
    for (uint i = 0; i < _num_blocks; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1378
      _blocks[i]->dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1379
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1380
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1381
#endif
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1382
  // Dead.
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
  1383
  _node_latency = (GrowableArray<uint> *)0xdeadbeef;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1384
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1385
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1386
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1387
//------------------------------Estimate_Block_Frequency-----------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1388
// Estimate block frequencies based on IfNode probabilities.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1389
void PhaseCFG::Estimate_Block_Frequency() {
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1390
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1391
  // Force conditional branches leading to uncommon traps to be unlikely,
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1392
  // not because we get to the uncommon_trap with less relative frequency,
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1393
  // but because an uncommon_trap typically causes a deopt, so we only get
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1394
  // there once.
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1395
  if (C->do_freq_based_layout()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1396
    Block_List worklist;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1397
    Block* root_blk = _blocks[0];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1398
    for (uint i = 1; i < root_blk->num_preds(); i++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1399
      Block *pb = _bbs[root_blk->pred(i)->_idx];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1400
      if (pb->has_uncommon_code()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1401
        worklist.push(pb);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1402
      }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1403
    }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1404
    while (worklist.size() > 0) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1405
      Block* uct = worklist.pop();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1406
      if (uct == _broot) continue;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1407
      for (uint i = 1; i < uct->num_preds(); i++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1408
        Block *pb = _bbs[uct->pred(i)->_idx];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1409
        if (pb->_num_succs == 1) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1410
          worklist.push(pb);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1411
        } else if (pb->num_fall_throughs() == 2) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1412
          pb->update_uncommon_branch(uct);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1413
        }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1414
      }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1415
    }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1416
  }
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1417
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1418
  // Create the loop tree and calculate loop depth.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1419
  _root_loop = create_loop_tree();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1420
  _root_loop->compute_loop_depth(0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1421
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1422
  // Compute block frequency of each block, relative to a single loop entry.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1423
  _root_loop->compute_freq();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1424
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1425
  // Adjust all frequencies to be relative to a single method entry
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1426
  _root_loop->_freq = 1.0;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1427
  _root_loop->scale_freq();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1428
2340
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1429
  // Save outmost loop frequency for LRG frequency threshold
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1430
  _outer_loop_freq = _root_loop->outer_loop_freq();
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1431
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1432
  // force paths ending at uncommon traps to be infrequent
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1433
  if (!C->do_freq_based_layout()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1434
    Block_List worklist;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1435
    Block* root_blk = _blocks[0];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1436
    for (uint i = 1; i < root_blk->num_preds(); i++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1437
      Block *pb = _bbs[root_blk->pred(i)->_idx];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1438
      if (pb->has_uncommon_code()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1439
        worklist.push(pb);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1440
      }
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1441
    }
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1442
    while (worklist.size() > 0) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1443
      Block* uct = worklist.pop();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1444
      uct->_freq = PROB_MIN;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1445
      for (uint i = 1; i < uct->num_preds(); i++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1446
        Block *pb = _bbs[uct->pred(i)->_idx];
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1447
        if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1448
          worklist.push(pb);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1449
        }
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1450
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1451
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1452
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1453
2016
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1454
#ifdef ASSERT
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1455
  for (uint i = 0; i < _num_blocks; i++ ) {
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1456
    Block *b = _blocks[i];
2131
98f9cef66a34 6810672: Comment typos
twisti
parents: 2127
diff changeset
  1457
    assert(b->_freq >= MIN_BLOCK_FREQUENCY, "Register Allocator requires meaningful block frequency");
2016
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1458
  }
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1459
#endif
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1460
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1461
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1462
  if (PrintCFGBlockFreq) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1463
    tty->print_cr("CFG Block Frequencies");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1464
    _root_loop->dump_tree();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1465
    if (Verbose) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1466
      tty->print_cr("PhaseCFG dump");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1467
      dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1468
      tty->print_cr("Node dump");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1469
      _root->dump(99999);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1470
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1471
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1472
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1473
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1474
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1475
//----------------------------create_loop_tree--------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1476
// Create a loop tree from the CFG
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1477
CFGLoop* PhaseCFG::create_loop_tree() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1478
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1479
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1480
  assert( _blocks[0] == _broot, "" );
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1481
  for (uint i = 0; i < _num_blocks; i++ ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1482
    Block *b = _blocks[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1483
    // Check that _loop field are clear...we could clear them if not.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1484
    assert(b->_loop == NULL, "clear _loop expected");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1485
    // Sanity check that the RPO numbering is reflected in the _blocks array.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1486
    // It doesn't have to be for the loop tree to be built, but if it is not,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1487
    // then the blocks have been reordered since dom graph building...which
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1488
    // may question the RPO numbering
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1489
    assert(b->_rpo == i, "unexpected reverse post order number");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1490
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1491
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1492
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1493
  int idct = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1494
  CFGLoop* root_loop = new CFGLoop(idct++);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1495
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1496
  Block_List worklist;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1497
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1498
  // Assign blocks to loops
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1499
  for(uint i = _num_blocks - 1; i > 0; i-- ) { // skip Root block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1500
    Block *b = _blocks[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1501
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1502
    if (b->head()->is_Loop()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1503
      Block* loop_head = b;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1504
      assert(loop_head->num_preds() - 1 == 2, "loop must have 2 predecessors");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1505
      Node* tail_n = loop_head->pred(LoopNode::LoopBackControl);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1506
      Block* tail = _bbs[tail_n->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1507
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1508
      // Defensively filter out Loop nodes for non-single-entry loops.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1509
      // For all reasonable loops, the head occurs before the tail in RPO.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1510
      if (i <= tail->_rpo) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1511
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1512
        // The tail and (recursive) predecessors of the tail
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1513
        // are made members of a new loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1514
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1515
        assert(worklist.size() == 0, "nonempty worklist");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1516
        CFGLoop* nloop = new CFGLoop(idct++);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1517
        assert(loop_head->_loop == NULL, "just checking");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1518
        loop_head->_loop = nloop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1519
        // Add to nloop so push_pred() will skip over inner loops
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1520
        nloop->add_member(loop_head);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1521
        nloop->push_pred(loop_head, LoopNode::LoopBackControl, worklist, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1522
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1523
        while (worklist.size() > 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1524
          Block* member = worklist.pop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1525
          if (member != loop_head) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1526
            for (uint j = 1; j < member->num_preds(); j++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1527
              nloop->push_pred(member, j, worklist, _bbs);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1528
            }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1529
          }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1530
        }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1531
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1532
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1533
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1534
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1535
  // Create a member list for each loop consisting
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1536
  // of both blocks and (immediate child) loops.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1537
  for (uint i = 0; i < _num_blocks; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1538
    Block *b = _blocks[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1539
    CFGLoop* lp = b->_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1540
    if (lp == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1541
      // Not assigned to a loop. Add it to the method's pseudo loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1542
      b->_loop = root_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1543
      lp = root_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1544
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1545
    if (lp == root_loop || b != lp->head()) { // loop heads are already members
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1546
      lp->add_member(b);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1547
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1548
    if (lp != root_loop) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1549
      if (lp->parent() == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1550
        // Not a nested loop. Make it a child of the method's pseudo loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1551
        root_loop->add_nested_loop(lp);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1552
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1553
      if (b == lp->head()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1554
        // Add nested loop to member list of parent loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1555
        lp->parent()->add_member(lp);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1556
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1557
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1558
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1559
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1560
  return root_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1561
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1562
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1563
//------------------------------push_pred--------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1564
void CFGLoop::push_pred(Block* blk, int i, Block_List& worklist, Block_Array& node_to_blk) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1565
  Node* pred_n = blk->pred(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1566
  Block* pred = node_to_blk[pred_n->_idx];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1567
  CFGLoop *pred_loop = pred->_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1568
  if (pred_loop == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1569
    // Filter out blocks for non-single-entry loops.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1570
    // For all reasonable loops, the head occurs before the tail in RPO.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1571
    if (pred->_rpo > head()->_rpo) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1572
      pred->_loop = this;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1573
      worklist.push(pred);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1574
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1575
  } else if (pred_loop != this) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1576
    // Nested loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1577
    while (pred_loop->_parent != NULL && pred_loop->_parent != this) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1578
      pred_loop = pred_loop->_parent;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1579
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1580
    // Make pred's loop be a child
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1581
    if (pred_loop->_parent == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1582
      add_nested_loop(pred_loop);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1583
      // Continue with loop entry predecessor.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1584
      Block* pred_head = pred_loop->head();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1585
      assert(pred_head->num_preds() - 1 == 2, "loop must have 2 predecessors");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1586
      assert(pred_head != head(), "loop head in only one loop");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1587
      push_pred(pred_head, LoopNode::EntryControl, worklist, node_to_blk);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1588
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1589
      assert(pred_loop->_parent == this && _parent == NULL, "just checking");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1590
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1591
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1592
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1593
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1594
//------------------------------add_nested_loop--------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1595
// Make cl a child of the current loop in the loop tree.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1596
void CFGLoop::add_nested_loop(CFGLoop* cl) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1597
  assert(_parent == NULL, "no parent yet");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1598
  assert(cl != this, "not my own parent");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1599
  cl->_parent = this;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1600
  CFGLoop* ch = _child;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1601
  if (ch == NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1602
    _child = cl;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1603
  } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1604
    while (ch->_sibling != NULL) { ch = ch->_sibling; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1605
    ch->_sibling = cl;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1606
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1607
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1608
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1609
//------------------------------compute_loop_depth-----------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1610
// Store the loop depth in each CFGLoop object.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1611
// Recursively walk the children to do the same for them.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1612
void CFGLoop::compute_loop_depth(int depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1613
  _depth = depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1614
  CFGLoop* ch = _child;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1615
  while (ch != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1616
    ch->compute_loop_depth(depth + 1);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1617
    ch = ch->_sibling;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1618
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1619
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1620
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1621
//------------------------------compute_freq-----------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1622
// Compute the frequency of each block and loop, relative to a single entry
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1623
// into the dominating loop head.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1624
void CFGLoop::compute_freq() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1625
  // Bottom up traversal of loop tree (visit inner loops first.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1626
  // Set loop head frequency to 1.0, then transitively
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1627
  // compute frequency for all successors in the loop,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1628
  // as well as for each exit edge.  Inner loops are
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1629
  // treated as single blocks with loop exit targets
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1630
  // as the successor blocks.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1631
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1632
  // Nested loops first
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1633
  CFGLoop* ch = _child;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1634
  while (ch != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1635
    ch->compute_freq();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1636
    ch = ch->_sibling;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1637
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1638
  assert (_members.length() > 0, "no empty loops");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1639
  Block* hd = head();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1640
  hd->_freq = 1.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1641
  for (int i = 0; i < _members.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1642
    CFGElement* s = _members.at(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1643
    float freq = s->_freq;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1644
    if (s->is_block()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1645
      Block* b = s->as_Block();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1646
      for (uint j = 0; j < b->_num_succs; j++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1647
        Block* sb = b->_succs[j];
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1648
        update_succ_freq(sb, freq * b->succ_prob(j));
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1649
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1650
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1651
      CFGLoop* lp = s->as_CFGLoop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1652
      assert(lp->_parent == this, "immediate child");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1653
      for (int k = 0; k < lp->_exits.length(); k++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1654
        Block* eb = lp->_exits.at(k).get_target();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1655
        float prob = lp->_exits.at(k).get_prob();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1656
        update_succ_freq(eb, freq * prob);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1657
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1658
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1659
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1660
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1661
  // For all loops other than the outer, "method" loop,
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1662
  // sum and normalize the exit probability. The "method" loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1663
  // should keep the initial exit probability of 1, so that
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1664
  // inner blocks do not get erroneously scaled.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1665
  if (_depth != 0) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1666
    // Total the exit probabilities for this loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1667
    float exits_sum = 0.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1668
    for (int i = 0; i < _exits.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1669
      exits_sum += _exits.at(i).get_prob();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1670
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1671
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1672
    // Normalize the exit probabilities. Until now, the
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1673
    // probabilities estimate the possibility of exit per
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1674
    // a single loop iteration; afterward, they estimate
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1675
    // the probability of exit per loop entry.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1676
    for (int i = 0; i < _exits.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1677
      Block* et = _exits.at(i).get_target();
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1678
      float new_prob = 0.0f;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1679
      if (_exits.at(i).get_prob() > 0.0f) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1680
        new_prob = _exits.at(i).get_prob() / exits_sum;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1681
      }
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1682
      BlockProbPair bpp(et, new_prob);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1683
      _exits.at_put(i, bpp);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1684
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1685
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1686
    // Save the total, but guard against unreasonable probability,
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1687
    // as the value is used to estimate the loop trip count.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1688
    // An infinite trip count would blur relative block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1689
    // frequencies.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1690
    if (exits_sum > 1.0f) exits_sum = 1.0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1691
    if (exits_sum < PROB_MIN) exits_sum = PROB_MIN;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1692
    _exit_prob = exits_sum;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1693
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1694
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1695
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1696
//------------------------------succ_prob-------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1697
// Determine the probability of reaching successor 'i' from the receiver block.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1698
float Block::succ_prob(uint i) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1699
  int eidx = end_idx();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1700
  Node *n = _nodes[eidx];  // Get ending Node
1070
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1701
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1702
  int op = n->Opcode();
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1703
  if (n->is_Mach()) {
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1704
    if (n->is_MachNullCheck()) {
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1705
      // Can only reach here if called after lcm. The original Op_If is gone,
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1706
      // so we attempt to infer the probability from one or both of the
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1707
      // successor blocks.
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1708
      assert(_num_succs == 2, "expecting 2 successors of a null check");
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1709
      // If either successor has only one predecessor, then the
2131
98f9cef66a34 6810672: Comment typos
twisti
parents: 2127
diff changeset
  1710
      // probability estimate can be derived using the
1070
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1711
      // relative frequency of the successor and this block.
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1712
      if (_succs[i]->num_preds() == 2) {
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1713
        return _succs[i]->_freq / _freq;
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1714
      } else if (_succs[1-i]->num_preds() == 2) {
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1715
        return 1 - (_succs[1-i]->_freq / _freq);
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1716
      } else {
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1717
        // Estimate using both successor frequencies
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1718
        float freq = _succs[i]->_freq;
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1719
        return freq / (freq + _succs[1-i]->_freq);
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1720
      }
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1721
    }
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1722
    op = n->as_Mach()->ideal_Opcode();
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1723
  }
e03de091796e 6611837: block frequency is zero
rasbold
parents: 781
diff changeset
  1724
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1725
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1726
  // Switch on branch type
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1727
  switch( op ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1728
  case Op_CountedLoopEnd:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1729
  case Op_If: {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1730
    assert (i < 2, "just checking");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1731
    // Conditionals pass on only part of their frequency
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1732
    float prob  = n->as_MachIf()->_prob;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1733
    assert(prob >= 0.0 && prob <= 1.0, "out of range probability");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1734
    // If succ[i] is the FALSE branch, invert path info
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1735
    if( _nodes[i + eidx + 1]->Opcode() == Op_IfFalse ) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1736
      return 1.0f - prob; // not taken
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1737
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1738
      return prob; // taken
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1739
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1740
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1741
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1742
  case Op_Jump:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1743
    // Divide the frequency between all successors evenly
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1744
    return 1.0f/_num_succs;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1745
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1746
  case Op_Catch: {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1747
    const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1748
    if (ci->_con == CatchProjNode::fall_through_index) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1749
      // Fall-thru path gets the lion's share.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1750
      return 1.0f - PROB_UNLIKELY_MAG(5)*_num_succs;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1751
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1752
      // Presume exceptional paths are equally unlikely
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1753
      return PROB_UNLIKELY_MAG(5);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1754
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1755
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1756
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1757
  case Op_Root:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1758
  case Op_Goto:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1759
    // Pass frequency straight thru to target
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1760
    return 1.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1761
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1762
  case Op_NeverBranch:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1763
    return 0.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1764
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1765
  case Op_TailCall:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1766
  case Op_TailJump:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1767
  case Op_Return:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1768
  case Op_Halt:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1769
  case Op_Rethrow:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1770
    // Do not push out freq to root block
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1771
    return 0.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1772
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1773
  default:
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1774
    ShouldNotReachHere();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1775
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1776
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1777
  return 0.0f;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1778
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1779
1498
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1780
//------------------------------num_fall_throughs-----------------------------
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1781
// Return the number of fall-through candidates for a block
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1782
int Block::num_fall_throughs() {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1783
  int eidx = end_idx();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1784
  Node *n = _nodes[eidx];  // Get ending Node
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1785
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1786
  int op = n->Opcode();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1787
  if (n->is_Mach()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1788
    if (n->is_MachNullCheck()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1789
      // In theory, either side can fall-thru, for simplicity sake,
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1790
      // let's say only the false branch can now.
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1791
      return 1;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1792
    }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1793
    op = n->as_Mach()->ideal_Opcode();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1794
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1795
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1796
  // Switch on branch type
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1797
  switch( op ) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1798
  case Op_CountedLoopEnd:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1799
  case Op_If:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1800
    return 2;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1801
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1802
  case Op_Root:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1803
  case Op_Goto:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1804
    return 1;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1805
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1806
  case Op_Catch: {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1807
    for (uint i = 0; i < _num_succs; i++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1808
      const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1809
      if (ci->_con == CatchProjNode::fall_through_index) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1810
        return 1;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1811
      }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1812
    }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1813
    return 0;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1814
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1815
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1816
  case Op_Jump:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1817
  case Op_NeverBranch:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1818
  case Op_TailCall:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1819
  case Op_TailJump:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1820
  case Op_Return:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1821
  case Op_Halt:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1822
  case Op_Rethrow:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1823
    return 0;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1824
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1825
  default:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1826
    ShouldNotReachHere();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1827
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1828
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1829
  return 0;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1830
}
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1831
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1832
//------------------------------succ_fall_through-----------------------------
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1833
// Return true if a specific successor could be fall-through target.
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1834
bool Block::succ_fall_through(uint i) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1835
  int eidx = end_idx();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1836
  Node *n = _nodes[eidx];  // Get ending Node
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1837
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1838
  int op = n->Opcode();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1839
  if (n->is_Mach()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1840
    if (n->is_MachNullCheck()) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1841
      // In theory, either side can fall-thru, for simplicity sake,
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1842
      // let's say only the false branch can now.
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1843
      return _nodes[i + eidx + 1]->Opcode() == Op_IfFalse;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1844
    }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1845
    op = n->as_Mach()->ideal_Opcode();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1846
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1847
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1848
  // Switch on branch type
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1849
  switch( op ) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1850
  case Op_CountedLoopEnd:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1851
  case Op_If:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1852
  case Op_Root:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1853
  case Op_Goto:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1854
    return true;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1855
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1856
  case Op_Catch: {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1857
    const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1858
    return ci->_con == CatchProjNode::fall_through_index;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1859
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1860
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1861
  case Op_Jump:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1862
  case Op_NeverBranch:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1863
  case Op_TailCall:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1864
  case Op_TailJump:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1865
  case Op_Return:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1866
  case Op_Halt:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1867
  case Op_Rethrow:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1868
    return false;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1869
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1870
  default:
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1871
    ShouldNotReachHere();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1872
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1873
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1874
  return false;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1875
}
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1876
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1877
//------------------------------update_uncommon_branch------------------------
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1878
// Update the probability of a two-branch to be uncommon
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1879
void Block::update_uncommon_branch(Block* ub) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1880
  int eidx = end_idx();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1881
  Node *n = _nodes[eidx];  // Get ending Node
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1882
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1883
  int op = n->as_Mach()->ideal_Opcode();
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1884
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1885
  assert(op == Op_CountedLoopEnd || op == Op_If, "must be a If");
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1886
  assert(num_fall_throughs() == 2, "must be a two way branch block");
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1887
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1888
  // Which successor is ub?
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1889
  uint s;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1890
  for (s = 0; s <_num_succs; s++) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1891
    if (_succs[s] == ub) break;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1892
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1893
  assert(s < 2, "uncommon successor must be found");
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1894
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1895
  // If ub is the true path, make the proability small, else
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1896
  // ub is the false path, and make the probability large
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1897
  bool invert = (_nodes[s + eidx + 1]->Opcode() == Op_IfFalse);
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1898
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1899
  // Get existing probability
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1900
  float p = n->as_MachIf()->_prob;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1901
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1902
  if (invert) p = 1.0 - p;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1903
  if (p > PROB_MIN) {
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1904
    p = PROB_MIN;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1905
  }
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1906
  if (invert) p = 1.0 - p;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1907
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1908
  n->as_MachIf()->_prob = p;
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1909
}
346bf226078e 6743900: frequency based block layout
rasbold
parents: 1070
diff changeset
  1910
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1911
//------------------------------update_succ_freq-------------------------------
2131
98f9cef66a34 6810672: Comment typos
twisti
parents: 2127
diff changeset
  1912
// Update the appropriate frequency associated with block 'b', a successor of
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1913
// a block in this loop.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1914
void CFGLoop::update_succ_freq(Block* b, float freq) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1915
  if (b->_loop == this) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1916
    if (b == head()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1917
      // back branch within the loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1918
      // Do nothing now, the loop carried frequency will be
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1919
      // adjust later in scale_freq().
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1920
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1921
      // simple branch within the loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1922
      b->_freq += freq;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1923
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1924
  } else if (!in_loop_nest(b)) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1925
    // branch is exit from this loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1926
    BlockProbPair bpp(b, freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1927
    _exits.append(bpp);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1928
  } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1929
    // branch into nested loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1930
    CFGLoop* ch = b->_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1931
    ch->_freq += freq;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1932
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1933
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1934
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1935
//------------------------------in_loop_nest-----------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1936
// Determine if block b is in the receiver's loop nest.
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1937
bool CFGLoop::in_loop_nest(Block* b) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1938
  int depth = _depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1939
  CFGLoop* b_loop = b->_loop;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1940
  int b_depth = b_loop->_depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1941
  if (depth == b_depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1942
    return true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1943
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1944
  while (b_depth > depth) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1945
    b_loop = b_loop->_parent;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1946
    b_depth = b_loop->_depth;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1947
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1948
  return b_loop == this;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1949
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1950
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1951
//------------------------------scale_freq-------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1952
// Scale frequency of loops and blocks by trip counts from outer loops
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1953
// Do a top down traversal of loop tree (visit outer loops first.)
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1954
void CFGLoop::scale_freq() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1955
  float loop_freq = _freq * trip_count();
2340
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1956
  _freq = loop_freq;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1957
  for (int i = 0; i < _members.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1958
    CFGElement* s = _members.at(i);
2016
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1959
    float block_freq = s->_freq * loop_freq;
2147
9088094e3e81 6812721: Block's frequency should not be NaN
kvn
parents: 2131
diff changeset
  1960
    if (g_isnan(block_freq) || block_freq < MIN_BLOCK_FREQUENCY)
9088094e3e81 6812721: Block's frequency should not be NaN
kvn
parents: 2131
diff changeset
  1961
      block_freq = MIN_BLOCK_FREQUENCY;
2016
c1f73fa547fe 6784930: server jvm fails with assert(!n->is_SpillCopy(),"")
kvn
parents: 1498
diff changeset
  1962
    s->_freq = block_freq;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1963
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1964
  CFGLoop* ch = _child;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1965
  while (ch != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1966
    ch->scale_freq();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1967
    ch = ch->_sibling;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1968
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1969
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1970
2340
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1971
// Frequency of outer loop
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1972
float CFGLoop::outer_loop_freq() const {
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1973
  if (_child != NULL) {
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1974
    return _child->_freq;
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1975
  }
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1976
  return _freq;
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1977
}
cb47f8209cd8 6810845: Performance regression in mpegaudio on x64
kvn
parents: 2154
diff changeset
  1978
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1979
#ifndef PRODUCT
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1980
//------------------------------dump_tree--------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1981
void CFGLoop::dump_tree() const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1982
  dump();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1983
  if (_child != NULL)   _child->dump_tree();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1984
  if (_sibling != NULL) _sibling->dump_tree();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1985
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1986
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1987
//------------------------------dump-------------------------------------------
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1988
void CFGLoop::dump() const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1989
  for (int i = 0; i < _depth; i++) tty->print("   ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1990
  tty->print("%s: %d  trip_count: %6.0f freq: %6.0f\n",
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1991
             _depth == 0 ? "Method" : "Loop", _id, trip_count(), _freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1992
  for (int i = 0; i < _depth; i++) tty->print("   ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1993
  tty->print("         members:", _id);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1994
  int k = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1995
  for (int i = 0; i < _members.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1996
    if (k++ >= 6) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1997
      tty->print("\n              ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1998
      for (int j = 0; j < _depth+1; j++) tty->print("   ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  1999
      k = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2000
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2001
    CFGElement *s = _members.at(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2002
    if (s->is_block()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2003
      Block *b = s->as_Block();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2004
      tty->print(" B%d(%6.3f)", b->_pre_order, b->_freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2005
    } else {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2006
      CFGLoop* lp = s->as_CFGLoop();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2007
      tty->print(" L%d(%6.3f)", lp->_id, lp->_freq);
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2008
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2009
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2010
  tty->print("\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2011
  for (int i = 0; i < _depth; i++) tty->print("   ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2012
  tty->print("         exits:  ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2013
  k = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2014
  for (int i = 0; i < _exits.length(); i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2015
    if (k++ >= 7) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2016
      tty->print("\n              ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2017
      for (int j = 0; j < _depth+1; j++) tty->print("   ");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2018
      k = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2019
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2020
    Block *blk = _exits.at(i).get_target();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2021
    float prob = _exits.at(i).get_prob();
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2022
    tty->print(" ->%d@%d%%", blk->_pre_order, (int)(prob*100));
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2023
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2024
  tty->print("\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2025
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
  2026
#endif