cfgnode.hpp revision 196
/*
* Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.com if you need additional information or
* have any questions.
*
*/
// Portions of code courtesy of Clifford Click
// Optimization - Graph Style
class Matcher;
class Node;
class RegionNode;
class TypeNode;
class PhiNode;
class GotoNode;
class MultiNode;
class MultiBranchNode;
class IfNode;
class PCTableNode;
class JumpNode;
class CatchNode;
class NeverBranchNode;
class ProjNode;
class CProjNode;
class IfTrueNode;
class IfFalseNode;
class CatchProjNode;
class JProjNode;
class JumpProjNode;
class SCMemProjNode;
class PhaseIdealLoop;
//------------------------------RegionNode-------------------------------------
// The class of RegionNodes, which can be mapped to basic blocks in the
// program. Their inputs point to Control sources. PhiNodes (described
// below) have an input point to a RegionNode. Merged data inputs to PhiNodes
// correspond 1-to-1 with RegionNode inputs. The zero input of a PhiNode is
// the RegionNode, and the zero input of the RegionNode is itself.
class RegionNode : public Node {
public:
// Node layout (parallels PhiNode):
enum { Region, // Generally points to self.
Control // Control arcs are [1..len)
};
init_req(0,this);
}
if (r == NULL)
return nonnull_req();
return NULL; // not a copy!
}
// Is this region node unreachable from root?
virtual int Opcode() const;
virtual bool is_CFG () const { return true; }
virtual bool depends_only_on_test() const { return false; }
virtual const RegMask &out_RegMask() const;
};
//------------------------------JProjNode--------------------------------------
// jump projection for node that produces multiple control-flow paths
public:
virtual int Opcode() const;
virtual bool is_CFG() const { return true; }
virtual const RegMask& out_RegMask() const;
};
//------------------------------PhiNode----------------------------------------
// PhiNodes merge values from different Control paths. Slot 0 points to the
// controlling RegionNode. Other slots map 1-for-1 with incoming control flow
// paths to the RegionNode. For speed reasons (to avoid another pass) we
// can turn PhiNodes into copys in-place by NULL'ing out their RegionNode
// input in slot 0.
const int _inst_id; // Instance id of the memory slice.
const int _inst_index; // Alias index of the instance memory slice.
// Array elements references have the same alias_idx but different offset.
const int _inst_offset; // Offset of the instance memory slice.
// Size is bigger to hold the _adr_type field.
// Determine if CMoveNode::is_cmove_id can be used at this join point.
public:
// Node layout (parallels RegionNode):
enum { Region, // Control input is the Phi's region.
Input // Input values are [1..len)
};
{
init_req(0, r);
}
// create a new phi with in edges matching r and set (initially) to x
// extra type arguments override the new phi's bottom_type and adr_type
// create a new phi with narrowed memory type
// like make(r, x), but does not initialize the in edges to x
// Accessors
RegionNode* region() const { Node* r = in(Region); assert(!r || r->is_Region(), ""); return (RegionNode*)r; }
// The node is a real phi if _in[0] is a Region node.
return NULL; // not a copy!
}
// Determine a unique non-trivial input, if any.
// Ignore casts if it helps. Return NULL on failure.
// Check for a simple dead loop.
// Is it unsafe data loop? It becomes a dead loop if this phi node removed.
int is_diamond_phi() const;
virtual int Opcode() const;
const int inst_index() const { return _inst_index; }
const int inst_offset() const { return _inst_offset; }
inst_index() == index &&
inst_offset() == offset &&
}
virtual const RegMask &out_RegMask() const;
#ifndef PRODUCT
#endif
#ifdef ASSERT
void verify_adr_type(bool recursive = false) const;
#else //ASSERT
void verify_adr_type(bool recursive = false) const {}
#endif //ASSERT
};
//------------------------------GotoNode---------------------------------------
// GotoNodes perform direct branches.
public:
}
virtual int Opcode() const;
virtual bool pinned() const { return true; }
virtual bool is_CFG() const { return true; }
virtual const Node *is_block_proj() const { return this; }
virtual bool depends_only_on_test() const { return false; }
virtual const RegMask &out_RegMask() const;
};
//------------------------------CProjNode--------------------------------------
// control projection for node that produces multiple control-flow paths
public:
virtual int Opcode() const;
virtual bool is_CFG() const { return true; }
virtual const RegMask &out_RegMask() const;
};
//---------------------------MultiBranchNode-----------------------------------
// This class defines a MultiBranchNode, a MultiNode which yields multiple
// control values. These are distinguished from other types of MultiNodes
// which yield multiple values, but control is always and only projection #0.
class MultiBranchNode : public MultiNode {
public:
}
// returns required number of users to be well formed.
virtual int required_outcnt() const = 0;
};
//------------------------------IfNode-----------------------------------------
// Output selected Control, based on a boolean test
class IfNode : public MultiBranchNode {
// Size is bigger to hold the probability field. However, _prob does not
// change the semantics so it does not appear in the hash & cmp functions.
public:
// Degrees of branch prediction probability by order of magnitude:
// PROB_UNLIKELY_1e(N) is a 1 in 1eN chance.
// PROB_LIKELY_1e(N) is a 1 - PROB_UNLIKELY_1e(N)
#define PROB_UNLIKELY_MAG(N) (1e- ## N ## f)
// Maximum and minimum branch prediction probabilties
// 1 in 1,000,000 (magnitude 6)
//
// Although PROB_NEVER == PROB_MIN and PROB_ALWAYS == PROB_MAX
// they are used to distinguish different situations:
//
// The name PROB_MAX (PROB_MIN) is for probabilities which correspond to
// very likely (unlikely) but with a concrete possibility of a rare
// contrary case. These constants would be used for pinning
// measurements, and as measures for assertions that have high
// confidence, but some evidence of occasional failure.
//
// The name PROB_ALWAYS (PROB_NEVER) is to stand for situations for which
// there is no evidence at all that the contrary case has ever occurred.
// Static branch prediction probabilities
// 1 in 10 (magnitude 1)
// Fair probability 50/50
#define PROB_FAIR (0.5f)
// Unknown probability sentinel
#define PROB_UNKNOWN (-1.0f)
// Probability "constructors", to distinguish as a probability any manifest
// constant without a names
#define PROB_LIKELY(x) ((float) (x))
#define PROB_UNLIKELY(x) (1.0f - (float)(x))
// Other probabilities in use, but without a unique name, are documented
// here for lack of a better place:
//
// 1 in 1000 probabilities (magnitude 3):
// threshold for converting to conditional move
// likelihood of null check failure if a null HAS been seen before
// likelihood of slow path taken in library calls
//
// 1 in 10,000 probabilities (magnitude 4):
// threshold for making an uncommon trap probability more extreme
// threshold for for making a null check implicit
// likelihood of needing a gc if eden top moves during an allocation
// likelihood of a predicted call failure
//
// 1 in 100,000 probabilities (magnitude 5):
// threshold for ignoring counts when estimating path frequency
// likelihood of FP clipping failure
// likelihood of catching an exception from a try block
// likelihood of null check failure if a null has NOT been seen before
//
// Magic manifest probabilities such as 0.83, 0.7, ... can be found in
// gen_subtype_check() and catch_inline_exceptions().
float _prob; // Probability of true path being taken.
float _fcnt; // Frequency counter
init_req(1,b);
}
virtual int Opcode() const;
virtual bool pinned() const { return true; }
virtual int required_outcnt() const { return 2; }
virtual const RegMask &out_RegMask() const;
// Takes the type of val and filters it through the test represented
// by if_proj and returns a more refined type if one is produced.
// Returns NULL is it couldn't improve the type.
#ifndef PRODUCT
#endif
};
class IfTrueNode : public CProjNode {
public:
}
virtual int Opcode() const;
};
class IfFalseNode : public CProjNode {
public:
}
virtual int Opcode() const;
};
//------------------------------PCTableNode------------------------------------
// Build an indirect branch table. Given a control and a table index,
// control is passed to the Projection matching the table index. Used to
// implement switch statements and exception-handling capabilities.
// Undefined behavior if passed-in index is not inside the table.
class PCTableNode : public MultiBranchNode {
public:
}
virtual int Opcode() const;
virtual const Type *bottom_type() const;
virtual bool pinned() const { return true; }
virtual int required_outcnt() const { return _size; }
};
//------------------------------JumpNode---------------------------------------
// Indirect branch. Uses PCTable above to implement a switch statement.
// It emits as a table load and local branch.
class JumpNode : public PCTableNode {
public:
}
virtual int Opcode() const;
virtual const RegMask& out_RegMask() const;
virtual const Node* is_block_proj() const { return this; }
};
class JumpProjNode : public JProjNode {
private:
const int _dest_bci;
const int _switch_val;
public:
}
virtual int Opcode() const;
int switch_val() const { return _switch_val; }
#ifndef PRODUCT
#endif
};
//------------------------------CatchNode--------------------------------------
// Helper node to fork exceptions. "Catch" catches any exceptions thrown by
// a just-prior call. Looks like a PCTableNode but emits no code - just the
// table. The table lookup and branch is implemented by RethrowNode.
class CatchNode : public PCTableNode {
public:
}
virtual int Opcode() const;
};
// CatchProjNode controls which exception handler is targetted after a call.
// It is passed in the bci of the target handler, or no_handler_bci in case
// the projection doesn't lead to an exception handler.
class CatchProjNode : public CProjNode {
private:
const int _handler_bci;
public:
enum {
fall_through_index = 0, // the fall through projection index
};
}
virtual int Opcode() const;
int handler_bci() const { return _handler_bci; }
bool is_handler_proj() const { return _handler_bci >= 0; }
#ifndef PRODUCT
#endif
};
//---------------------------------CreateExNode--------------------------------
// Helper node to create the exception coming back from a call
class CreateExNode : public TypeNode {
public:
}
virtual int Opcode() const;
virtual bool pinned() const { return true; }
};
//------------------------------NeverBranchNode-------------------------------
// The never-taken branch. Used to give the appearance of exiting infinite
// loops to those algorithms that like all paths to be reachable. Encodes
// empty.
class NeverBranchNode : public MultiBranchNode {
public:
virtual int Opcode() const;
virtual bool pinned() const { return true; };
virtual int required_outcnt() const { return 2; }
#ifndef PRODUCT
#endif
};