常量传播的lattice有三级，buttom表示不能保证是常量，中间表示常量，top表示变量可能未确定/未初始化。CCP处理之后，所有值不是常量就是buttom。
一般有两种算法，一种是SSC（Sparse Simple Constant Propagation，Reif and Lewis），一种是SCC（Sparse Conditional Constant Propagation），C2是后者。
PhaseCCP是PhaseItreGVN的子类，他在Optimize中有两步：
...
// Conditional Constant Propagation;
PhaseCCP ccp( &igvn );
assert( true, "Break here to ccp.dump_nodes_and_types(_root,999,1)");
{
TracePhase tp("ccp", &timers[_t_ccp]);
ccp.do_transform();
}
print_method(PHASE_CPP1, 2);
assert( true, "Break here to ccp.dump_old2new_map()");
// Iterative Global Value Numbering, including ideal transforms
{
TracePhase tp("iterGVN2", &timers[_t_iterGVN2]);
igvn = ccp;
igvn.optimize();
}
print_method(PHASE_ITER_GVN2, 2);
...
构造PhaseCCP的时候会执行PhaseCCP::analyze，然后做ccp.do_transofrm，再然后使用igvn.optimize做ccp的transform。
PhaseCCP::analyze
void PhaseCCP::analyze() {
// Initialize all types to TOP, optimistic analysis
for (int i = C->unique() - 1; i >= 0; i--) {
_types.map(i,Type::TOP);
}
// Push root onto worklist
Unique_Node_List worklist;
worklist.push(C->root());
// Pull from worklist; compute new value; push changes out.
// This loop is the meat of CCP.
while( worklist.size() ) {
Node* n; // Node to be examined in this iteration
if (StressCCP) {
n = worklist.remove(C->random() % worklist.size());
} else {
n = worklist.pop();
}
const Type *t = n->Value(this);
if (t != type(n)) {
assert(ccp_type_widens(t, type(n)), "ccp type must widen");
#ifndef PRODUCT
if( TracePhaseCCP ) {
t->dump();
do { tty->print("\t"); } while (tty->position() < 16);
n->dump();
}
#endif
set_type(n, t);
for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
Node* m = n->fast_out(i); // Get user
if (m->is_Region()) { // New path to Region? Must recheck Phis too
for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) {
Node* p = m->fast_out(i2); // Propagate changes to uses
if (p->bottom_type() != type(p)) { // If not already bottomed out
worklist.push(p); // Propagate change to user
}
}
}
// If we changed the receiver type to a call, we need to revisit
// the Catch following the call. It's looking for a non-NULL
// receiver to know when to enable the regular fall-through path
// in addition to the NullPtrException path
if (m->is_Call()) {
for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) {
Node* p = m->fast_out(i2); // Propagate changes to uses
if (p->is_Proj() && p->as_Proj()->_con == TypeFunc::Control) {
Node* catch_node = p->find_out_with(Op_Catch);
if (catch_node != NULL) {
worklist.push(catch_node);
}
}
}
}
if (m->bottom_type() != type(m)) { // If not already bottomed out
worklist.push(m); // Propagate change to user
}
// CmpU nodes can get their type information from two nodes up in the
// graph (instead of from the nodes immediately above). Make sure they
// are added to the worklist if nodes they depend on are updated, since
// they could be missed and get wrong types otherwise.
uint m_op = m->Opcode();
if (m_op == Op_AddI || m_op == Op_SubI) {
for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) {
Node* p = m->fast_out(i2); // Propagate changes to uses
if (p->Opcode() == Op_CmpU) {
// Got a CmpU which might need the new type information from node n.
if(p->bottom_type() != type(p)) { // If not already bottomed out
worklist.push(p); // Propagate change to user
}
}
}
}
// If n is used in a counted loop exit condition then the type
// of the counted loop's Phi depends on the type of n. See
// PhiNode::Value().
if (m_op == Op_CmpI) {
PhiNode* phi = countedloop_phi_from_cmp((CmpINode*)m, n);
if (phi != NULL) {
worklist.push(phi);
}
}
// Loading the java mirror from a Klass requires two loads and the type
// of the mirror load depends on the type of 'n'. See LoadNode::Value().
BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
if (m_op == Op_LoadP && m->bottom_type()->isa_rawptr()) {
for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) {
Node* u = m->fast_out(i2);
const Type* ut = u->bottom_type();
if (u->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(u)) {
if (has_load_barrier_nodes) {
// Search for load barriers behind the load
for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
Node* b = u->fast_out(i3);
if (bs->is_gc_barrier_node(b)) {
worklist.push(b);
}
}
}
worklist.push(u);
}
}
}
}
}
}
}
看着这么多，其实吧中间的for省略一下，就很直白了：
void PhaseCCP::analyze() {
// 乐观分析，即最开始将所有types都初始化为TOP
for (int i = C->unique() - 1; i >= 0; i--) {
_types.map(i,Type::TOP);
}
// ROOT放到worklist里
Unique_Node_List worklist;
worklist.push(C->root());
// 1)worklsit取值 2)算新type 3)然后如果新type和之前记录的不一样，就更新
while( worklist.size() ) {
Node* n; // Node to be examined in this iteration
if (StressCCP) {
n = worklist.remove(C->random() % worklist.size());
} else {
// 1)worklsit取值
n = worklist.pop();
}
// 2)算新type
const Type *t = n->Value(this);
// 3)如果新type和之前记录的不一样
if (t != type(n)) {
assert(ccp_type_widens(t, type(n)), "ccp type must widen");
// 就更新
set_type(n, t);
// 处理一下当前node的use，特殊处理一些cases
for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
... // 某些特殊情况需要加入worklist
// 看当前节点的use的type是不是最坏情况，如果不是，就加到worklist
if (m->bottom_type() != type(m)) {
worklist.push(m);
}
... // 某些特殊情况需要加入worklist
}
}
}
}
analyze就是把整个图的所有节点都先初始化成TOP，然后从ROOT出发，计算当前节点的新type，如果新type和之前记录的不一样（如果是第一次就是新type不是TOP），那么就记录新type，然后看看当前节点的use，如果use的type不是最坏情况，那么把它加入worklist，等待下一次使用。
或者更简洁来说，analyze就是把ir所有node的type初始化为TOP（最好情况），然后为所有node再算一次type，直到type不改变，或者type已经是bottom（最坏情况）。
PhaseCCP::transform
//------------------------------do_transform-----------------------------------
// Top level driver for the recursive transformer
void PhaseCCP::do_transform() {
// Correct leaves of new-space Nodes; they point to old-space.
C->set_root( transform(C->root())->as_Root() );
assert( C->top(), "missing TOP node" );
assert( C->root(), "missing root" );
}
//------------------------------transform--------------------------------------
// Given a Node in old-space, clone him into new-space.
// Convert any of his old-space children into new-space children.
Node *PhaseCCP::transform( Node *n ) {
Node *new_node = _nodes[n->_idx]; // Check for transformed node
if( new_node != NULL )
return new_node; // Been there, done that, return old answer
new_node = transform_once(n); // Check for constant
_nodes.map( n->_idx, new_node ); // Flag as having been cloned
// Allocate stack of size _nodes.Size()/2 to avoid frequent realloc
GrowableArray <Node *> trstack(C->live_nodes() >> 1);
trstack.push(new_node); // Process children of cloned node
while ( trstack.is_nonempty() ) {
Node *clone = trstack.pop();
uint cnt = clone->req();
for( uint i = 0; i < cnt; i++ ) { // For all inputs do
Node *input = clone->in(i);
if( input != NULL ) { // Ignore NULLs
Node *new_input = _nodes[input->_idx]; // Check for cloned input node
if( new_input == NULL ) {
new_input = transform_once(input); // Check for constant
_nodes.map( input->_idx, new_input );// Flag as having been cloned
trstack.push(new_input);
}
assert( new_input == clone->in(i), "insanity check");
}
}
}
return new_node;
}
do_transform从root出发，对整个ir的node挨个调用一次transform_once，所以，变形的核心是transform_once：
Node *PhaseCCP::transform_once( Node *n ) {
const Type *t = type(n);
// Constant? Use constant Node instead
if( t->singleton() ) {
Node *nn = n; // Default is to return the original constant
if( t == Type::TOP ) {
// cache my top node on the Compile instance
if( C->cached_top_node() == NULL || C->cached_top_node()->in(0) == NULL ) {
C->set_cached_top_node(ConNode::make(Type::TOP));
set_type(C->top(), Type::TOP);
}
nn = C->top();
}
if( !n->is_Con() ) {
if( t != Type::TOP ) {
nn = makecon(t); // ConNode::make(t);
NOT_PRODUCT( inc_constants(); )
} else if( n->is_Region() ) { // Unreachable region
// Note: nn == C->top()
n->set_req(0, NULL); // Cut selfreference
bool progress = true;
uint max = n->outcnt();
DUIterator i;
while (progress) {
progress = false;
// Eagerly remove dead phis to avoid phis copies creation.
for (i = n->outs(); n->has_out(i); i++) {
Node* m = n->out(i);
if (m->is_Phi()) {
assert(type(m) == Type::TOP, "Unreachable region should not have live phis.");
replace_node(m, nn);
if (max != n->outcnt()) {
progress = true;
i = n->refresh_out_pos(i);
max = n->outcnt();
}
}
}
}
}
replace_node(n,nn); // Update DefUse edges for new constant
}
return nn;
}
// If x is a TypeNode, capture any more-precise type permanently into Node
if (t != n->bottom_type()) {
hash_delete(n); // changing bottom type may force a rehash
n->raise_bottom_type(t);
_worklist.push(n); // n re-enters the hash table via the worklist
}
// TEMPORARY fix to ensure that 2nd GVN pass eliminates NULL checks
switch( n->Opcode() ) {
case Op_FastLock: // Revisit FastLocks for lock coarsening
case Op_If:
case Op_CountedLoopEnd:
case Op_Region:
case Op_Loop:
case Op_CountedLoop:
case Op_Conv2B:
case Op_Opaque1:
case Op_Opaque2:
_worklist.push(n);
break;
default:
break;
}
return n;
}