从GVN开始
C1在build_hir的时候会构造GlobalValueNumbering：
GlobalValueNumbering::GlobalValueNumbering(IR* ir)
: _compilation(ir->compilation())
, _current_map(NULL)
, _value_maps(ir->linear_scan_order()->length(), ir->linear_scan_order()->length(), NULL)
, _has_substitutions(false)
{
TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
ShortLoopOptimizer short_loop_optimizer(this);
BlockList* blocks = ir->linear_scan_order();
int num_blocks = blocks->length();
BlockBegin* start_block = blocks->at(0);
assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block");
assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions");
// method parameters are not linked in instructions list, so process them separateley
for_each_state_value(start_block->state(), value,
assert(value->as_Local() != NULL, "only method parameters allowed");
set_processed(value); // !!!!!!!!value加入invariant集，即函数形参
);
// initial, empty value map with nesting 0
set_value_map_of(start_block, new ValueMap());
// ！！！！！！遍历所有bblock
for (int i = 1; i < num_blocks; i++) {
BlockBegin* block = blocks->at(i);
TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id()));
int num_preds = block->number_of_preds();
assert(num_preds > 0, "block must have predecessors");
BlockBegin* dominator = block->dominator();
assert(dominator != NULL, "dominator must exist");
assert(value_map_of(dominator) != NULL, "value map of dominator must exist");
// create new value map with increased nesting
_current_map = new ValueMap(value_map_of(dominator));
if (num_preds == 1 && !block->is_set(BlockBegin::exception_entry_flag)) {
assert(dominator == block->pred_at(0), "dominator must be equal to predecessor");
// nothing to do here
} else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
// block has incoming backward branches -> try to optimize short loops
// ！！！！！！！如果是bblock循环头，那么执行ShortLoopOptimizer
if (!short_loop_optimizer.process(block)) {
// loop is too complicated, so kill all memory loads because there might be
// stores to them in the loop
current_map()->kill_memory();
}
} else {
// only incoming forward branches that are already processed
for (int j = 0; j < num_preds; j++) {
BlockBegin* pred = block->pred_at(j);
ValueMap* pred_map = value_map_of(pred);
if (pred_map != NULL) {
// propagate killed values of the predecessor to this block
current_map()->kill_map(value_map_of(pred));
} else {
// kill all memory loads because predecessor not yet processed
// (this can happen with non-natural loops and OSR-compiles)
current_map()->kill_memory();
}
}
}
// phi functions are not linked in instructions list, so process them separateley
for_each_phi_fun(block, phi,
set_processed(phi);
);
TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print());
// visit all instructions of this block
for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
// check if instruction kills any values
instr->visit(this);
// perform actual value numbering
substitute(instr);
}
// remember value map for successors
set_value_map_of(block, current_map());
}
if (_has_substitutions) {
SubstitutionResolver resolver(ir);
}
TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics());
}
这里做的事情也很简单，遍历所有bblock，如果发现某个bblock是循环头，那么执行ShortLoopOptimizer
到ShortLoopOptimizer
bool ShortLoopOptimizer::process(BlockBegin* loop_header) {
TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block"));
_too_complicated_loop = false;
_loop_blocks.clear();
_loop_blocks.append(loop_header);
for (int i = 0; i < _loop_blocks.length(); i++) {
BlockBegin* block = _loop_blocks.at(i);
TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id()));
if (block->is_set(BlockBegin::exception_entry_flag)) {
// this would be too complicated
return false;
}
// add predecessors to worklist
for (int j = block->number_of_preds() - 1; j >= 0; j--) {
BlockBegin* pred = block->pred_at(j);
if (pred->is_set(BlockBegin::osr_entry_flag)) {
return false;
}
ValueMap* pred_map = value_map_of(pred);
if (pred_map != NULL) {
current_map()->kill_map(pred_map);
} else if (!_loop_blocks.contains(pred)) {
if (_loop_blocks.length() >= ValueMapMaxLoopSize) {
return false;
}
_loop_blocks.append(pred);
}
}
// use the instruction visitor for killing values
for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
instr->visit(this);
if (_too_complicated_loop) {
return false;
}
}
}
bool optimistic = this->_gvn->compilation()->is_optimistic();
if (UseLoopInvariantCodeMotion && optimistic) {
LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks);
}
TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
return true;
}
ShortLoopOptimizer实际是个ValueNumberingVisitor，从上面的代码上不难看出，它做的事情是，遍历所有bblock，搜集循环的bblock，然后visit的所有instr检查他们是否不能做Value numbering（比如a kill了b，b就不能用来value numbering替换其他instr）。最后ShortLoopOptimizer执行LoopInvariantCodeMotion
最后LoopInvariantCodeMotion
LoopInvariantCodeMotion::LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks)
: _gvn(gvn), _short_loop_optimizer(slo), _insertion_point(NULL), _state(NULL), _insert_is_pred(false) {
TRACE_VALUE_NUMBERING(tty->print_cr("using loop invariant code motion loop_header = %d", loop_header->block_id()));
TRACE_VALUE_NUMBERING(tty->print_cr("** loop invariant code motion for short loop B%d", loop_header->block_id()));
BlockBegin* insertion_block = loop_header->dominator();
if (insertion_block->number_of_preds() == 0) {
return; // only the entry block does not have a predecessor
}
assert(insertion_block->end()->as_Base() == NULL, "cannot insert into entry block");
_insertion_point = insertion_block->end()->prev();
_insert_is_pred = loop_header->is_predecessor(insertion_block);
BlockEnd *block_end = insertion_block->end();
_state = block_end->state_before();
if (!_state) {
// If, TableSwitch and LookupSwitch always have state_before when
// loop invariant code motion happens..
assert(block_end->as_Goto(), "Block has to be goto");
_state = block_end->state();
}
// the loop_blocks are filled by going backward from the loop header, so this processing order is best
assert(loop_blocks->at(0) == loop_header, "loop header must be first loop block");
process_block(loop_header);
for (int i = loop_blocks->length() - 1; i >= 1; i--) {
process_block(loop_blocks->at(i));
}
}
LoopInvariantCodeMotion遍历之前搜集的所有属于循环的bblock，再process_block这些bblock：
void LoopInvariantCodeMotion::process_block(BlockBegin* block) {
TRACE_VALUE_NUMBERING(tty->print_cr("processing block B%d", block->block_id()));
Instruction* prev = block;
Instruction* cur = block->next();
// ！！！！！遍历bblock的所有instr
while (cur != NULL) {
// determine if cur instruction is loop invariant
// only selected instruction types are processed here
bool cur_invariant = false;
//！！！！！！看当前instr是否是invariant instr
if (cur->as_Constant() != NULL) {
cur_invariant = !cur->can_trap();
} else if (cur->as_ArithmeticOp() != NULL || cur->as_LogicOp() != NULL || cur->as_ShiftOp() != NULL) {
assert(cur->as_Op2() != NULL, "must be Op2");
Op2* op2 = (Op2*)cur;
cur_invariant = !op2->can_trap() && is_invariant(op2->x()) && is_invariant(op2->y());
} else if (cur->as_LoadField() != NULL) {
LoadField* lf = (LoadField*)cur;
// deoptimizes on NullPointerException
cur_invariant = !lf->needs_patching() && !lf->field()->is_volatile() && !_short_loop_optimizer->has_field_store(lf->field()->type()->basic_type()) && is_invariant(lf->obj()) && _insert_is_pred;
} else if (cur->as_ArrayLength() != NULL) {
ArrayLength *length = cur->as_ArrayLength();
cur_invariant = is_invariant(length->array());
} else if (cur->as_LoadIndexed() != NULL) {
LoadIndexed *li = (LoadIndexed *)cur->as_LoadIndexed();
cur_invariant = !_short_loop_optimizer->has_indexed_store(as_BasicType(cur->type())) && is_invariant(li->array()) && is_invariant(li->index()) && _insert_is_pred;
}
// ！！！！！！如果是invariant
if (cur_invariant) {
// perform value numbering and mark instruction as loop-invariant
// ！！！！！先尝试value numbering
_gvn->substitute(cur);
if (cur->as_Constant() == NULL) {
// ensure that code for non-constant instructions is always generated
cur->pin();
}
// remove cur instruction from loop block and append it to block before loop
// ！！！！！！再将invariant instr从当前bblock移动到循环的前面去，这就是code motion了
Instruction* next = cur->next();
Instruction* in = _insertion_point->next();
_insertion_point = _insertion_point->set_next(cur);
cur->set_next(in);
// Deoptimize on exception
cur->set_flag(Instruction::DeoptimizeOnException, true);
// Clear exception handlers
cur->set_exception_handlers(NULL);
TRACE_VALUE_NUMBERING(tty->print_cr("Instruction %c%d is loop invariant", cur->type()->tchar(), cur->id()));
TRACE_VALUE_NUMBERING(cur->print_line());
if (cur->state_before() != NULL) {
cur->set_state_before(_state->copy());
}
if (cur->exception_state() != NULL) {
cur->set_exception_state(_state->copy());
}
cur = prev->set_next(next);
} else {
prev = cur;
cur = cur->next();
}
}
}
process_block也很直白，它遍历当前bblock的所有instr，如果发现instr是invariant，就把它移动到循环的前面去。