hotspot/src/share/vm/opto/gcm.cpp
Print this page
rev 611 : Merge
*** 1,10 ****
#ifdef USE_PRAGMA_IDENT_SRC
#pragma ident "@(#)gcm.cpp 1.259 08/07/10 14:40:09 JVM"
#endif
/*
! * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
--- 1,10 ----
#ifdef USE_PRAGMA_IDENT_SRC
#pragma ident "@(#)gcm.cpp 1.259 08/07/10 14:40:09 JVM"
#endif
/*
! * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*** 30,39 ****
--- 30,42 ----
// Optimization - Graph Style
#include "incls/_precompiled.incl"
#include "incls/_gcm.cpp.incl"
+ // To avoid float value underflow
+ #define MIN_BLOCK_FREQUENCY 1.e-35f
+
//----------------------------schedule_node_into_block-------------------------
// Insert node n into block b. Look for projections of n and make sure they
// are in b also.
void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {
// Set basic block of n, Add n to b,
*** 451,463 ****
}
ResourceArea *area = Thread::current()->resource_area();
Node_List worklist_mem(area); // prior memory state to store
Node_List worklist_store(area); // possible-def to explore
Node_List non_early_stores(area); // all relevant stores outside of early
bool must_raise_LCA = false;
- DEBUG_ONLY(VectorSet should_not_repeat(area));
#ifdef TRACK_PHI_INPUTS
// %%% This extra checking fails because MergeMem nodes are not GVNed.
// Provide "phi_inputs" to check if every input to a PhiNode is from the
// original memory state. This indicates a PhiNode for which should not
--- 454,466 ----
}
ResourceArea *area = Thread::current()->resource_area();
Node_List worklist_mem(area); // prior memory state to store
Node_List worklist_store(area); // possible-def to explore
+ Node_List worklist_visited(area); // visited mergemem nodes
Node_List non_early_stores(area); // all relevant stores outside of early
bool must_raise_LCA = false;
#ifdef TRACK_PHI_INPUTS
// %%% This extra checking fails because MergeMem nodes are not GVNed.
// Provide "phi_inputs" to check if every input to a PhiNode is from the
// original memory state. This indicates a PhiNode for which should not
*** 482,493 ****
// initial_mem -> (MergeMem ->)* store
// The anti-dependence constraints apply only to the fringe of this tree.
Node* initial_mem = load->in(MemNode::Memory);
worklist_store.push(initial_mem);
worklist_mem.push(NULL);
- DEBUG_ONLY(should_not_repeat.test_set(initial_mem->_idx));
while (worklist_store.size() > 0) {
// Examine a nearby store to see if it might interfere with our load.
Node* mem = worklist_mem.pop();
Node* store = worklist_store.pop();
uint op = store->Opcode();
--- 485,496 ----
// initial_mem -> (MergeMem ->)* store
// The anti-dependence constraints apply only to the fringe of this tree.
Node* initial_mem = load->in(MemNode::Memory);
worklist_store.push(initial_mem);
+ worklist_visited.push(initial_mem);
worklist_mem.push(NULL);
while (worklist_store.size() > 0) {
// Examine a nearby store to see if it might interfere with our load.
Node* mem = worklist_mem.pop();
Node* store = worklist_store.pop();
uint op = store->Opcode();
*** 497,518 ****
// the leaves of which are each a 'possible-def'.
if (store == initial_mem // root (exclusive) of tree we are searching
|| op == Op_MergeMem // internal node of tree we are searching
) {
mem = store; // It's not a possibly interfering store.
for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
store = mem->fast_out(i);
if (store->is_MergeMem()) {
// Be sure we don't get into combinatorial problems.
// (Allow phis to be repeated; they can merge two relevant states.)
! uint i = worklist_store.size();
! for (; i > 0; i--) {
! if (worklist_store.at(i-1) == store) break;
! }
! if (i > 0) continue; // already on work list; do not repeat
! DEBUG_ONLY(int repeated = should_not_repeat.test_set(store->_idx));
! assert(!repeated, "do not walk merges twice");
}
worklist_mem.push(mem);
worklist_store.push(store);
}
continue;
--- 500,523 ----
// the leaves of which are each a 'possible-def'.
if (store == initial_mem // root (exclusive) of tree we are searching
|| op == Op_MergeMem // internal node of tree we are searching
) {
mem = store; // It's not a possibly interfering store.
+ if (store == initial_mem)
+ initial_mem = NULL; // only process initial memory once
+
for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
store = mem->fast_out(i);
if (store->is_MergeMem()) {
// Be sure we don't get into combinatorial problems.
// (Allow phis to be repeated; they can merge two relevant states.)
! uint j = worklist_visited.size();
! for (; j > 0; j--) {
! if (worklist_visited.at(j-1) == store) break;
! }
! if (j > 0) continue; // already on work list; do not repeat
! worklist_visited.push(store);
}
worklist_mem.push(mem);
worklist_store.push(store);
}
continue;
*** 1318,1363 ****
//------------------------------Estimate_Block_Frequency-----------------------
// Estimate block frequencies based on IfNode probabilities.
void PhaseCFG::Estimate_Block_Frequency() {
! int cnts = C->method() ? C->method()->interpreter_invocation_count() : 1;
! // Most of our algorithms will die horribly if frequency can become
! // negative so make sure cnts is a sane value.
! if( cnts <= 0 ) cnts = 1;
! float f = (float)cnts/(float)FreqCountInvocations;
// Create the loop tree and calculate loop depth.
_root_loop = create_loop_tree();
_root_loop->compute_loop_depth(0);
// Compute block frequency of each block, relative to a single loop entry.
_root_loop->compute_freq();
// Adjust all frequencies to be relative to a single method entry
! _root_loop->_freq = f * 1.0;
_root_loop->scale_freq();
// force paths ending at uncommon traps to be infrequent
Block_List worklist;
Block* root_blk = _blocks[0];
! for (uint i = 0; i < root_blk->num_preds(); i++) {
Block *pb = _bbs[root_blk->pred(i)->_idx];
if (pb->has_uncommon_code()) {
worklist.push(pb);
}
}
while (worklist.size() > 0) {
Block* uct = worklist.pop();
uct->_freq = PROB_MIN;
! for (uint i = 0; i < uct->num_preds(); i++) {
Block *pb = _bbs[uct->pred(i)->_idx];
if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
worklist.push(pb);
}
}
}
#ifndef PRODUCT
if (PrintCFGBlockFreq) {
tty->print_cr("CFG Block Frequencies");
_root_loop->dump_tree();
--- 1323,1399 ----
//------------------------------Estimate_Block_Frequency-----------------------
// Estimate block frequencies based on IfNode probabilities.
void PhaseCFG::Estimate_Block_Frequency() {
!
! // Force conditional branches leading to uncommon traps to be unlikely,
! // not because we get to the uncommon_trap with less relative frequency,
! // but because an uncommon_trap typically causes a deopt, so we only get
! // there once.
! if (C->do_freq_based_layout()) {
! Block_List worklist;
! Block* root_blk = _blocks[0];
! for (uint i = 1; i < root_blk->num_preds(); i++) {
! Block *pb = _bbs[root_blk->pred(i)->_idx];
! if (pb->has_uncommon_code()) {
! worklist.push(pb);
! }
! }
! while (worklist.size() > 0) {
! Block* uct = worklist.pop();
! if (uct == _broot) continue;
! for (uint i = 1; i < uct->num_preds(); i++) {
! Block *pb = _bbs[uct->pred(i)->_idx];
! if (pb->_num_succs == 1) {
! worklist.push(pb);
! } else if (pb->num_fall_throughs() == 2) {
! pb->update_uncommon_branch(uct);
! }
! }
! }
! }
// Create the loop tree and calculate loop depth.
_root_loop = create_loop_tree();
_root_loop->compute_loop_depth(0);
// Compute block frequency of each block, relative to a single loop entry.
_root_loop->compute_freq();
// Adjust all frequencies to be relative to a single method entry
! _root_loop->_freq = 1.0;
_root_loop->scale_freq();
// force paths ending at uncommon traps to be infrequent
+ if (!C->do_freq_based_layout()) {
Block_List worklist;
Block* root_blk = _blocks[0];
! for (uint i = 1; i < root_blk->num_preds(); i++) {
Block *pb = _bbs[root_blk->pred(i)->_idx];
if (pb->has_uncommon_code()) {
worklist.push(pb);
}
}
while (worklist.size() > 0) {
Block* uct = worklist.pop();
uct->_freq = PROB_MIN;
! for (uint i = 1; i < uct->num_preds(); i++) {
Block *pb = _bbs[uct->pred(i)->_idx];
if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
worklist.push(pb);
}
}
}
+ }
+
+ #ifdef ASSERT
+ for (uint i = 0; i < _num_blocks; i++ ) {
+ Block *b = _blocks[i];
+ assert(b->_freq >= MIN_BLOCK_FREQUENCY, "Register Allocator requires meaningful block frequency");
+ }
+ #endif
#ifndef PRODUCT
if (PrintCFGBlockFreq) {
tty->print_cr("CFG Block Frequencies");
_root_loop->dump_tree();
*** 1555,1580 ****
update_succ_freq(eb, freq * prob);
}
}
}
- #if 0
- // Raise frequency of the loop backedge block, in an effort
- // to keep it empty. Skip the method level "loop".
- if (_parent != NULL) {
- CFGElement* s = _members.at(_members.length() - 1);
- if (s->is_block()) {
- Block* bk = s->as_Block();
- if (bk->_num_succs == 1 && bk->_succs[0] == hd) {
- // almost any value >= 1.0f works
- // FIXME: raw constant
- bk->_freq = 1.05f;
- }
- }
- }
- #endif
-
// For all loops other than the outer, "method" loop,
// sum and normalize the exit probability. The "method" loop
// should keep the initial exit probability of 1, so that
// inner blocks do not get erroneously scaled.
if (_depth != 0) {
--- 1591,1600 ----
*** 1588,1603 ****
// probabilities estimate the possibility of exit per
// a single loop iteration; afterward, they estimate
// the probability of exit per loop entry.
for (int i = 0; i < _exits.length(); i++) {
Block* et = _exits.at(i).get_target();
! float new_prob = _exits.at(i).get_prob() / exits_sum;
BlockProbPair bpp(et, new_prob);
_exits.at_put(i, bpp);
}
! // Save the total, but guard against unreasoable probability,
// as the value is used to estimate the loop trip count.
// An infinite trip count would blur relative block
// frequencies.
if (exits_sum > 1.0f) exits_sum = 1.0;
if (exits_sum < PROB_MIN) exits_sum = PROB_MIN;
--- 1608,1626 ----
// probabilities estimate the possibility of exit per
// a single loop iteration; afterward, they estimate
// the probability of exit per loop entry.
for (int i = 0; i < _exits.length(); i++) {
Block* et = _exits.at(i).get_target();
! float new_prob = 0.0f;
! if (_exits.at(i).get_prob() > 0.0f) {
! new_prob = _exits.at(i).get_prob() / exits_sum;
! }
BlockProbPair bpp(et, new_prob);
_exits.at_put(i, bpp);
}
! // Save the total, but guard against unreasonable probability,
// as the value is used to estimate the loop trip count.
// An infinite trip count would blur relative block
// frequencies.
if (exits_sum > 1.0f) exits_sum = 1.0;
if (exits_sum < PROB_MIN) exits_sum = PROB_MIN;
*** 1608,1618 ****
//------------------------------succ_prob-------------------------------------
// Determine the probability of reaching successor 'i' from the receiver block.
float Block::succ_prob(uint i) {
int eidx = end_idx();
Node *n = _nodes[eidx]; // Get ending Node
! int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode();
// Switch on branch type
switch( op ) {
case Op_CountedLoopEnd:
case Op_If: {
--- 1631,1664 ----
//------------------------------succ_prob-------------------------------------
// Determine the probability of reaching successor 'i' from the receiver block.
float Block::succ_prob(uint i) {
int eidx = end_idx();
Node *n = _nodes[eidx]; // Get ending Node
!
! int op = n->Opcode();
! if (n->is_Mach()) {
! if (n->is_MachNullCheck()) {
! // Can only reach here if called after lcm. The original Op_If is gone,
! // so we attempt to infer the probability from one or both of the
! // successor blocks.
! assert(_num_succs == 2, "expecting 2 successors of a null check");
! // If either successor has only one predecessor, then the
! // probabiltity estimate can be derived using the
! // relative frequency of the successor and this block.
! if (_succs[i]->num_preds() == 2) {
! return _succs[i]->_freq / _freq;
! } else if (_succs[1-i]->num_preds() == 2) {
! return 1 - (_succs[1-i]->_freq / _freq);
! } else {
! // Estimate using both successor frequencies
! float freq = _succs[i]->_freq;
! return freq / (freq + _succs[1-i]->_freq);
! }
! }
! op = n->as_Mach()->ideal_Opcode();
! }
!
// Switch on branch type
switch( op ) {
case Op_CountedLoopEnd:
case Op_If: {
*** 1664,1673 ****
--- 1710,1850 ----
}
return 0.0f;
}
+ //------------------------------num_fall_throughs-----------------------------
+ // Return the number of fall-through candidates for a block
+ int Block::num_fall_throughs() {
+ int eidx = end_idx();
+ Node *n = _nodes[eidx]; // Get ending Node
+
+ int op = n->Opcode();
+ if (n->is_Mach()) {
+ if (n->is_MachNullCheck()) {
+ // In theory, either side can fall-thru, for simplicity sake,
+ // let's say only the false branch can now.
+ return 1;
+ }
+ op = n->as_Mach()->ideal_Opcode();
+ }
+
+ // Switch on branch type
+ switch( op ) {
+ case Op_CountedLoopEnd:
+ case Op_If:
+ return 2;
+
+ case Op_Root:
+ case Op_Goto:
+ return 1;
+
+ case Op_Catch: {
+ for (uint i = 0; i < _num_succs; i++) {
+ const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj();
+ if (ci->_con == CatchProjNode::fall_through_index) {
+ return 1;
+ }
+ }
+ return 0;
+ }
+
+ case Op_Jump:
+ case Op_NeverBranch:
+ case Op_TailCall:
+ case Op_TailJump:
+ case Op_Return:
+ case Op_Halt:
+ case Op_Rethrow:
+ return 0;
+
+ default:
+ ShouldNotReachHere();
+ }
+
+ return 0;
+ }
+
+ //------------------------------succ_fall_through-----------------------------
+ // Return true if a specific successor could be fall-through target.
+ bool Block::succ_fall_through(uint i) {
+ int eidx = end_idx();
+ Node *n = _nodes[eidx]; // Get ending Node
+
+ int op = n->Opcode();
+ if (n->is_Mach()) {
+ if (n->is_MachNullCheck()) {
+ // In theory, either side can fall-thru, for simplicity sake,
+ // let's say only the false branch can now.
+ return _nodes[i + eidx + 1]->Opcode() == Op_IfFalse;
+ }
+ op = n->as_Mach()->ideal_Opcode();
+ }
+
+ // Switch on branch type
+ switch( op ) {
+ case Op_CountedLoopEnd:
+ case Op_If:
+ case Op_Root:
+ case Op_Goto:
+ return true;
+
+ case Op_Catch: {
+ const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj();
+ return ci->_con == CatchProjNode::fall_through_index;
+ }
+
+ case Op_Jump:
+ case Op_NeverBranch:
+ case Op_TailCall:
+ case Op_TailJump:
+ case Op_Return:
+ case Op_Halt:
+ case Op_Rethrow:
+ return false;
+
+ default:
+ ShouldNotReachHere();
+ }
+
+ return false;
+ }
+
+ //------------------------------update_uncommon_branch------------------------
+ // Update the probability of a two-branch to be uncommon
+ void Block::update_uncommon_branch(Block* ub) {
+ int eidx = end_idx();
+ Node *n = _nodes[eidx]; // Get ending Node
+
+ int op = n->as_Mach()->ideal_Opcode();
+
+ assert(op == Op_CountedLoopEnd || op == Op_If, "must be a If");
+ assert(num_fall_throughs() == 2, "must be a two way branch block");
+
+ // Which successor is ub?
+ uint s;
+ for (s = 0; s <_num_succs; s++) {
+ if (_succs[s] == ub) break;
+ }
+ assert(s < 2, "uncommon successor must be found");
+
+ // If ub is the true path, make the proability small, else
+ // ub is the false path, and make the probability large
+ bool invert = (_nodes[s + eidx + 1]->Opcode() == Op_IfFalse);
+
+ // Get existing probability
+ float p = n->as_MachIf()->_prob;
+
+ if (invert) p = 1.0 - p;
+ if (p > PROB_MIN) {
+ p = PROB_MIN;
+ }
+ if (invert) p = 1.0 - p;
+
+ n->as_MachIf()->_prob = p;
+ }
+
//------------------------------update_succ_freq-------------------------------
// Update the appropriate frequency associated with block 'b', a succesor of
// a block in this loop.
void CFGLoop::update_succ_freq(Block* b, float freq) {
if (b->_loop == this) {
*** 1711,1721 ****
// Do a top down traversal of loop tree (visit outer loops first.)
void CFGLoop::scale_freq() {
float loop_freq = _freq * trip_count();
for (int i = 0; i < _members.length(); i++) {
CFGElement* s = _members.at(i);
! s->_freq *= loop_freq;
}
CFGLoop* ch = _child;
while (ch != NULL) {
ch->scale_freq();
ch = ch->_sibling;
--- 1888,1901 ----
// Do a top down traversal of loop tree (visit outer loops first.)
void CFGLoop::scale_freq() {
float loop_freq = _freq * trip_count();
for (int i = 0; i < _members.length(); i++) {
CFGElement* s = _members.at(i);
! float block_freq = s->_freq * loop_freq;
! if (g_isnan(block_freq) || block_freq < MIN_BLOCK_FREQUENCY)
! block_freq = MIN_BLOCK_FREQUENCY;
! s->_freq = block_freq;
}
CFGLoop* ch = _child;
while (ch != NULL) {
ch->scale_freq();
ch = ch->_sibling;