Mercurial > hg > graal-compiler
view src/share/vm/c1/c1_IR.cpp @ 2149:7e37af9d69ef
7011379: G1: overly long concurrent marking cycles
Summary: This changeset introduces filtering of SATB buffers at the point when they are about to be enqueued. If this filtering clears enough entries on each buffer, the buffer can then be re-used and not enqueued. This cuts down the number of SATB buffers that need to be processed by the concurrent marking threads.
Reviewed-by: johnc, ysr
author | tonyp |
---|---|
date | Wed, 19 Jan 2011 09:35:17 -0500 |
parents | 5ddfcf4b079e |
children | 701a83c86f28 |
line wrap: on
line source
/* * Copyright (c) 1999, 2010, Oracle and/or its affiliates. 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. * * 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #include "precompiled.hpp" #include "c1/c1_Compilation.hpp" #include "c1/c1_FrameMap.hpp" #include "c1/c1_GraphBuilder.hpp" #include "c1/c1_IR.hpp" #include "c1/c1_InstructionPrinter.hpp" #include "c1/c1_Optimizer.hpp" #include "utilities/bitMap.inline.hpp" // Implementation of XHandlers // // Note: This code could eventually go away if we are // just using the ciExceptionHandlerStream. XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) { ciExceptionHandlerStream s(method); while (!s.is_done()) { _list.append(new XHandler(s.handler())); s.next(); } assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent"); } // deep copy of all XHandler contained in list XHandlers::XHandlers(XHandlers* other) : _list(other->length()) { for (int i = 0; i < other->length(); i++) { _list.append(new XHandler(other->handler_at(i))); } } // Returns whether a particular exception type can be caught. Also // returns true if klass is unloaded or any exception handler // classes are unloaded. type_is_exact indicates whether the throw // is known to be exactly that class or it might throw a subtype. bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const { // the type is unknown so be conservative if (!klass->is_loaded()) { return true; } for (int i = 0; i < length(); i++) { XHandler* handler = handler_at(i); if (handler->is_catch_all()) { // catch of ANY return true; } ciInstanceKlass* handler_klass = handler->catch_klass(); // if it's unknown it might be catchable if (!handler_klass->is_loaded()) { return true; } // if the throw type is definitely a subtype of the catch type // then it can be caught. if (klass->is_subtype_of(handler_klass)) { return true; } if (!type_is_exact) { // If the type isn't exactly known then it can also be caught by // catch statements where the inexact type is a subtype of the // catch type. // given: foo extends bar extends Exception // throw bar can be caught by catch foo, catch bar, and catch // Exception, however it can't be caught by any handlers without // bar in its type hierarchy. if (handler_klass->is_subtype_of(klass)) { return true; } } } return false; } bool XHandlers::equals(XHandlers* others) const { if (others == NULL) return false; if (length() != others->length()) return false; for (int i = 0; i < length(); i++) { if (!handler_at(i)->equals(others->handler_at(i))) return false; } return true; } bool XHandler::equals(XHandler* other) const { assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco"); if (entry_pco() != other->entry_pco()) return false; if (scope_count() != other->scope_count()) return false; if (_desc != other->_desc) return false; assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal"); return true; } // Implementation of IRScope BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) { GraphBuilder gm(compilation, this); NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats()); if (compilation->bailed_out()) return NULL; return gm.start(); } IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph) : _callees(2) , _compilation(compilation) , _requires_phi_function(method->max_locals()) { _caller = caller; _level = caller == NULL ? 0 : caller->level() + 1; _method = method; _xhandlers = new XHandlers(method); _number_of_locks = 0; _monitor_pairing_ok = method->has_balanced_monitors(); _start = NULL; if (osr_bci == -1) { _requires_phi_function.clear(); } else { // selective creation of phi functions is not possibel in osr-methods _requires_phi_function.set_range(0, method->max_locals()); } assert(method->holder()->is_loaded() , "method holder must be loaded"); // build graph if monitor pairing is ok if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci); } int IRScope::max_stack() const { int my_max = method()->max_stack(); int callee_max = 0; for (int i = 0; i < number_of_callees(); i++) { callee_max = MAX2(callee_max, callee_no(i)->max_stack()); } return my_max + callee_max; } bool IRScopeDebugInfo::should_reexecute() { ciMethod* cur_method = scope()->method(); int cur_bci = bci(); if (cur_method != NULL && cur_bci != SynchronizationEntryBCI) { Bytecodes::Code code = cur_method->java_code_at_bci(cur_bci); return Interpreter::bytecode_should_reexecute(code); } else return false; } // Implementation of CodeEmitInfo // Stack must be NON-null CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers) : _scope(stack->scope()) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack) , _exception_handlers(exception_handlers) , _is_method_handle_invoke(false) { assert(_stack != NULL, "must be non null"); } CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack) : _scope(info->_scope) , _exception_handlers(NULL) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack == NULL ? info->_stack : stack) , _is_method_handle_invoke(info->_is_method_handle_invoke) { // deep copy of exception handlers if (info->_exception_handlers != NULL) { _exception_handlers = new XHandlers(info->_exception_handlers); } } void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) { // record the safepoint before recording the debug info for enclosing scopes recorder->add_safepoint(pc_offset, _oop_map->deep_copy()); _scope_debug_info->record_debug_info(recorder, pc_offset, true/*topmost*/, _is_method_handle_invoke); recorder->end_safepoint(pc_offset); } void CodeEmitInfo::add_register_oop(LIR_Opr opr) { assert(_oop_map != NULL, "oop map must already exist"); assert(opr->is_single_cpu(), "should not call otherwise"); VMReg name = frame_map()->regname(opr); _oop_map->set_oop(name); } // Implementation of IR IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) : _locals_size(in_WordSize(-1)) , _num_loops(0) { // setup IR fields _compilation = compilation; _top_scope = new IRScope(compilation, NULL, -1, method, osr_bci, true); _code = NULL; } void IR::optimize() { Optimizer opt(this); if (!compilation()->profile_branches()) { if (DoCEE) { opt.eliminate_conditional_expressions(); #ifndef PRODUCT if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); } if (PrintIR || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); } #endif } if (EliminateBlocks) { opt.eliminate_blocks(); #ifndef PRODUCT if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); } if (PrintIR || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); } #endif } } if (EliminateNullChecks) { opt.eliminate_null_checks(); #ifndef PRODUCT if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); } if (PrintIR || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); } #endif } } static int sort_pairs(BlockPair** a, BlockPair** b) { if ((*a)->from() == (*b)->from()) { return (*a)->to()->block_id() - (*b)->to()->block_id(); } else { return (*a)->from()->block_id() - (*b)->from()->block_id(); } } class CriticalEdgeFinder: public BlockClosure { BlockPairList blocks; IR* _ir; public: CriticalEdgeFinder(IR* ir): _ir(ir) {} void block_do(BlockBegin* bb) { BlockEnd* be = bb->end(); int nos = be->number_of_sux(); if (nos >= 2) { for (int i = 0; i < nos; i++) { BlockBegin* sux = be->sux_at(i); if (sux->number_of_preds() >= 2) { blocks.append(new BlockPair(bb, sux)); } } } } void split_edges() { BlockPair* last_pair = NULL; blocks.sort(sort_pairs); for (int i = 0; i < blocks.length(); i++) { BlockPair* pair = blocks.at(i); if (last_pair != NULL && pair->is_same(last_pair)) continue; BlockBegin* from = pair->from(); BlockBegin* to = pair->to(); BlockBegin* split = from->insert_block_between(to); #ifndef PRODUCT if ((PrintIR || PrintIR1) && Verbose) { tty->print_cr("Split critical edge B%d -> B%d (new block B%d)", from->block_id(), to->block_id(), split->block_id()); } #endif last_pair = pair; } } }; void IR::split_critical_edges() { CriticalEdgeFinder cef(this); iterate_preorder(&cef); cef.split_edges(); } class UseCountComputer: public ValueVisitor, BlockClosure { private: void visit(Value* n) { // Local instructions and Phis for expression stack values at the // start of basic blocks are not added to the instruction list if (!(*n)->is_linked() && (*n)->can_be_linked()) { assert(false, "a node was not appended to the graph"); Compilation::current()->bailout("a node was not appended to the graph"); } // use n's input if not visited before if (!(*n)->is_pinned() && !(*n)->has_uses()) { // note: a) if the instruction is pinned, it will be handled by compute_use_count // b) if the instruction has uses, it was touched before // => in both cases we don't need to update n's values uses_do(n); } // use n (*n)->_use_count++; } Values* worklist; int depth; enum { max_recurse_depth = 20 }; void uses_do(Value* n) { depth++; if (depth > max_recurse_depth) { // don't allow the traversal to recurse too deeply worklist->push(*n); } else { (*n)->input_values_do(this); // special handling for some instructions if ((*n)->as_BlockEnd() != NULL) { // note on BlockEnd: // must 'use' the stack only if the method doesn't // terminate, however, in those cases stack is empty (*n)->state_values_do(this); } } depth--; } void block_do(BlockBegin* b) { depth = 0; // process all pinned nodes as the roots of expression trees for (Instruction* n = b; n != NULL; n = n->next()) { if (n->is_pinned()) uses_do(&n); } assert(depth == 0, "should have counted back down"); // now process any unpinned nodes which recursed too deeply while (worklist->length() > 0) { Value t = worklist->pop(); if (!t->is_pinned()) { // compute the use count uses_do(&t); // pin the instruction so that LIRGenerator doesn't recurse // too deeply during it's evaluation. t->pin(); } } assert(depth == 0, "should have counted back down"); } UseCountComputer() { worklist = new Values(); depth = 0; } public: static void compute(BlockList* blocks) { UseCountComputer ucc; blocks->iterate_backward(&ucc); } }; // helper macro for short definition of trace-output inside code #ifndef PRODUCT #define TRACE_LINEAR_SCAN(level, code) \ if (TraceLinearScanLevel >= level) { \ code; \ } #else #define TRACE_LINEAR_SCAN(level, code) #endif class ComputeLinearScanOrder : public StackObj { private: int _max_block_id; // the highest block_id of a block int _num_blocks; // total number of blocks (smaller than _max_block_id) int _num_loops; // total number of loops bool _iterative_dominators;// method requires iterative computation of dominatiors BlockList* _linear_scan_order; // the resulting list of blocks in correct order BitMap _visited_blocks; // used for recursive processing of blocks BitMap _active_blocks; // used for recursive processing of blocks BitMap _dominator_blocks; // temproary BitMap used for computation of dominator intArray _forward_branches; // number of incoming forward branches for each block BlockList _loop_end_blocks; // list of all loop end blocks collected during count_edges BitMap2D _loop_map; // two-dimensional bit set: a bit is set if a block is contained in a loop BlockList _work_list; // temporary list (used in mark_loops and compute_order) Compilation* _compilation; // accessors for _visited_blocks and _active_blocks void init_visited() { _active_blocks.clear(); _visited_blocks.clear(); } bool is_visited(BlockBegin* b) const { return _visited_blocks.at(b->block_id()); } bool is_active(BlockBegin* b) const { return _active_blocks.at(b->block_id()); } void set_visited(BlockBegin* b) { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); } void set_active(BlockBegin* b) { assert(!is_active(b), "already set"); _active_blocks.set_bit(b->block_id()); } void clear_active(BlockBegin* b) { assert(is_active(b), "not already"); _active_blocks.clear_bit(b->block_id()); } // accessors for _forward_branches void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); } int dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); } // accessors for _loop_map bool is_block_in_loop (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); } void set_block_in_loop (int loop_idx, BlockBegin* b) { _loop_map.set_bit(loop_idx, b->block_id()); } void clear_block_in_loop(int loop_idx, int block_id) { _loop_map.clear_bit(loop_idx, block_id); } // count edges between blocks void count_edges(BlockBegin* cur, BlockBegin* parent); // loop detection void mark_loops(); void clear_non_natural_loops(BlockBegin* start_block); void assign_loop_depth(BlockBegin* start_block); // computation of final block order BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b); void compute_dominator(BlockBegin* cur, BlockBegin* parent); int compute_weight(BlockBegin* cur); bool ready_for_processing(BlockBegin* cur); void sort_into_work_list(BlockBegin* b); void append_block(BlockBegin* cur); void compute_order(BlockBegin* start_block); // fixup of dominators for non-natural loops bool compute_dominators_iter(); void compute_dominators(); // debug functions NOT_PRODUCT(void print_blocks();) DEBUG_ONLY(void verify();) Compilation* compilation() const { return _compilation; } public: ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block); // accessors for final result BlockList* linear_scan_order() const { return _linear_scan_order; } int num_loops() const { return _num_loops; } }; ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) : _max_block_id(BlockBegin::number_of_blocks()), _num_blocks(0), _num_loops(0), _iterative_dominators(false), _visited_blocks(_max_block_id), _active_blocks(_max_block_id), _dominator_blocks(_max_block_id), _forward_branches(_max_block_id, 0), _loop_end_blocks(8), _work_list(8), _linear_scan_order(NULL), // initialized later with correct size _loop_map(0, 0), // initialized later with correct size _compilation(c) { TRACE_LINEAR_SCAN(2, "***** computing linear-scan block order"); init_visited(); count_edges(start_block, NULL); if (compilation()->is_profiling()) { ciMethod *method = compilation()->method(); if (!method->is_accessor()) { ciMethodData* md = method->method_data_or_null(); assert(md != NULL, "Sanity"); md->set_compilation_stats(_num_loops, _num_blocks); } } if (_num_loops > 0) { mark_loops(); clear_non_natural_loops(start_block); assign_loop_depth(start_block); } compute_order(start_block); compute_dominators(); NOT_PRODUCT(print_blocks()); DEBUG_ONLY(verify()); } // Traverse the CFG: // * count total number of blocks // * count all incoming edges and backward incoming edges // * number loop header blocks // * create a list with all loop end blocks void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) { TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != NULL ? parent->block_id() : -1)); assert(cur->dominator() == NULL, "dominator already initialized"); if (is_active(cur)) { TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch")); assert(is_visited(cur), "block must be visisted when block is active"); assert(parent != NULL, "must have parent"); cur->set(BlockBegin::linear_scan_loop_header_flag); cur->set(BlockBegin::backward_branch_target_flag); parent->set(BlockBegin::linear_scan_loop_end_flag); // When a loop header is also the start of an exception handler, then the backward branch is // an exception edge. Because such edges are usually critical edges which cannot be split, the // loop must be excluded here from processing. if (cur->is_set(BlockBegin::exception_entry_flag)) { // Make sure that dominators are correct in this weird situation _iterative_dominators = true; return; } assert(parent->number_of_sux() == 1 && parent->sux_at(0) == cur, "loop end blocks must have one successor (critical edges are split)"); _loop_end_blocks.append(parent); return; } // increment number of incoming forward branches inc_forward_branches(cur); if (is_visited(cur)) { TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited")); return; } _num_blocks++; set_visited(cur); set_active(cur); // recursive call for all successors int i; for (i = cur->number_of_sux() - 1; i >= 0; i--) { count_edges(cur->sux_at(i), cur); } for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { count_edges(cur->exception_handler_at(i), cur); } clear_active(cur); // Each loop has a unique number. // When multiple loops are nested, assign_loop_depth assumes that the // innermost loop has the lowest number. This is guaranteed by setting // the loop number after the recursive calls for the successors above // have returned. if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) { assert(cur->loop_index() == -1, "cannot set loop-index twice"); TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops)); cur->set_loop_index(_num_loops); _num_loops++; } TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id())); } void ComputeLinearScanOrder::mark_loops() { TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops")); _loop_map = BitMap2D(_num_loops, _max_block_id); _loop_map.clear(); for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) { BlockBegin* loop_end = _loop_end_blocks.at(i); BlockBegin* loop_start = loop_end->sux_at(0); int loop_idx = loop_start->loop_index(); TRACE_LINEAR_SCAN(3, tty->print_cr("Processing loop from B%d to B%d (loop %d):", loop_start->block_id(), loop_end->block_id(), loop_idx)); assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set"); assert(loop_end->number_of_sux() == 1, "incorrect number of successors"); assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set"); assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set"); assert(_work_list.is_empty(), "work list must be empty before processing"); // add the end-block of the loop to the working list _work_list.push(loop_end); set_block_in_loop(loop_idx, loop_end); do { BlockBegin* cur = _work_list.pop(); TRACE_LINEAR_SCAN(3, tty->print_cr(" processing B%d", cur->block_id())); assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list"); // recursive processing of all predecessors ends when start block of loop is reached if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) { for (int j = cur->number_of_preds() - 1; j >= 0; j--) { BlockBegin* pred = cur->pred_at(j); if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) { // this predecessor has not been processed yet, so add it to work list TRACE_LINEAR_SCAN(3, tty->print_cr(" pushing B%d", pred->block_id())); _work_list.push(pred); set_block_in_loop(loop_idx, pred); } } } } while (!_work_list.is_empty()); } } // check for non-natural loops (loops where the loop header does not dominate // all other loop blocks = loops with mulitple entries). // such loops are ignored void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) { for (int i = _num_loops - 1; i >= 0; i--) { if (is_block_in_loop(i, start_block)) { // loop i contains the entry block of the method // -> this is not a natural loop, so ignore it TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i)); for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) { clear_block_in_loop(i, block_id); } _iterative_dominators = true; } } } void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) { TRACE_LINEAR_SCAN(3, "----- computing loop-depth and weight"); init_visited(); assert(_work_list.is_empty(), "work list must be empty before processing"); _work_list.append(start_block); do { BlockBegin* cur = _work_list.pop(); if (!is_visited(cur)) { set_visited(cur); TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id())); // compute loop-depth and loop-index for the block assert(cur->loop_depth() == 0, "cannot set loop-depth twice"); int i; int loop_depth = 0; int min_loop_idx = -1; for (i = _num_loops - 1; i >= 0; i--) { if (is_block_in_loop(i, cur)) { loop_depth++; min_loop_idx = i; } } cur->set_loop_depth(loop_depth); cur->set_loop_index(min_loop_idx); // append all unvisited successors to work list for (i = cur->number_of_sux() - 1; i >= 0; i--) { _work_list.append(cur->sux_at(i)); } for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { _work_list.append(cur->exception_handler_at(i)); } } } while (!_work_list.is_empty()); } BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) { assert(a != NULL && b != NULL, "must have input blocks"); _dominator_blocks.clear(); while (a != NULL) { _dominator_blocks.set_bit(a->block_id()); assert(a->dominator() != NULL || a == _linear_scan_order->at(0), "dominator must be initialized"); a = a->dominator(); } while (b != NULL && !_dominator_blocks.at(b->block_id())) { assert(b->dominator() != NULL || b == _linear_scan_order->at(0), "dominator must be initialized"); b = b->dominator(); } assert(b != NULL, "could not find dominator"); return b; } void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) { if (cur->dominator() == NULL) { TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id())); cur->set_dominator(parent); } else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) { TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id())); assert(cur->number_of_preds() > 1, ""); cur->set_dominator(common_dominator(cur->dominator(), parent)); } } int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) { BlockBegin* single_sux = NULL; if (cur->number_of_sux() == 1) { single_sux = cur->sux_at(0); } // limit loop-depth to 15 bit (only for security reason, it will never be so big) int weight = (cur->loop_depth() & 0x7FFF) << 16; // general macro for short definition of weight flags // the first instance of INC_WEIGHT_IF has the highest priority int cur_bit = 15; #define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--; // this is necessery for the (very rare) case that two successing blocks have // the same loop depth, but a different loop index (can happen for endless loops // with exception handlers) INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag)); // loop end blocks (blocks that end with a backward branch) are added // after all other blocks of the loop. INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag)); // critical edge split blocks are prefered because than they have a bigger // proability to be completely empty INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag)); // exceptions should not be thrown in normal control flow, so these blocks // are added as late as possible INC_WEIGHT_IF(cur->end()->as_Throw() == NULL && (single_sux == NULL || single_sux->end()->as_Throw() == NULL)); INC_WEIGHT_IF(cur->end()->as_Return() == NULL && (single_sux == NULL || single_sux->end()->as_Return() == NULL)); // exceptions handlers are added as late as possible INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag)); // guarantee that weight is > 0 weight |= 1; #undef INC_WEIGHT_IF assert(cur_bit >= 0, "too many flags"); assert(weight > 0, "weight cannot become negative"); return weight; } bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) { // Discount the edge just traveled. // When the number drops to zero, all forward branches were processed if (dec_forward_branches(cur) != 0) { return false; } assert(_linear_scan_order->index_of(cur) == -1, "block already processed (block can be ready only once)"); assert(_work_list.index_of(cur) == -1, "block already in work-list (block can be ready only once)"); return true; } void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) { assert(_work_list.index_of(cur) == -1, "block already in work list"); int cur_weight = compute_weight(cur); // the linear_scan_number is used to cache the weight of a block cur->set_linear_scan_number(cur_weight); #ifndef PRODUCT if (StressLinearScan) { _work_list.insert_before(0, cur); return; } #endif _work_list.append(NULL); // provide space for new element int insert_idx = _work_list.length() - 1; while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) { _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1)); insert_idx--; } _work_list.at_put(insert_idx, cur); TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id())); TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number())); #ifdef ASSERT for (int i = 0; i < _work_list.length(); i++) { assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set"); assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist"); } #endif } void ComputeLinearScanOrder::append_block(BlockBegin* cur) { TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number())); assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice"); // currently, the linear scan order and code emit order are equal. // therefore the linear_scan_number and the weight of a block must also // be equal. cur->set_linear_scan_number(_linear_scan_order->length()); _linear_scan_order->append(cur); } void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) { TRACE_LINEAR_SCAN(3, "----- computing final block order"); // the start block is always the first block in the linear scan order _linear_scan_order = new BlockList(_num_blocks); append_block(start_block); assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction"); BlockBegin* std_entry = ((Base*)start_block->end())->std_entry(); BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry(); BlockBegin* sux_of_osr_entry = NULL; if (osr_entry != NULL) { // special handling for osr entry: // ignore the edge between the osr entry and its successor for processing // the osr entry block is added manually below assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor"); assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow"); sux_of_osr_entry = osr_entry->sux_at(0); dec_forward_branches(sux_of_osr_entry); compute_dominator(osr_entry, start_block); _iterative_dominators = true; } compute_dominator(std_entry, start_block); // start processing with standard entry block assert(_work_list.is_empty(), "list must be empty before processing"); if (ready_for_processing(std_entry)) { sort_into_work_list(std_entry); } else { assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)"); } do { BlockBegin* cur = _work_list.pop(); if (cur == sux_of_osr_entry) { // the osr entry block is ignored in normal processing, it is never added to the // work list. Instead, it is added as late as possible manually here. append_block(osr_entry); compute_dominator(cur, osr_entry); } append_block(cur); int i; int num_sux = cur->number_of_sux(); // changed loop order to get "intuitive" order of if- and else-blocks for (i = 0; i < num_sux; i++) { BlockBegin* sux = cur->sux_at(i); compute_dominator(sux, cur); if (ready_for_processing(sux)) { sort_into_work_list(sux); } } num_sux = cur->number_of_exception_handlers(); for (i = 0; i < num_sux; i++) { BlockBegin* sux = cur->exception_handler_at(i); compute_dominator(sux, cur); if (ready_for_processing(sux)) { sort_into_work_list(sux); } } } while (_work_list.length() > 0); } bool ComputeLinearScanOrder::compute_dominators_iter() { bool changed = false; int num_blocks = _linear_scan_order->length(); assert(_linear_scan_order->at(0)->dominator() == NULL, "must not have dominator"); assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors"); for (int i = 1; i < num_blocks; i++) { BlockBegin* block = _linear_scan_order->at(i); BlockBegin* dominator = block->pred_at(0); int num_preds = block->number_of_preds(); for (int i = 1; i < num_preds; i++) { dominator = common_dominator(dominator, block->pred_at(i)); } if (dominator != block->dominator()) { TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: updating dominator of B%d from B%d to B%d", block->block_id(), block->dominator()->block_id(), dominator->block_id())); block->set_dominator(dominator); changed = true; } } return changed; } void ComputeLinearScanOrder::compute_dominators() { TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators)); // iterative computation of dominators is only required for methods with non-natural loops // and OSR-methods. For all other methods, the dominators computed when generating the // linear scan block order are correct. if (_iterative_dominators) { do { TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation")); } while (compute_dominators_iter()); } // check that dominators are correct assert(!compute_dominators_iter(), "fix point not reached"); } #ifndef PRODUCT void ComputeLinearScanOrder::print_blocks() { if (TraceLinearScanLevel >= 2) { tty->print_cr("----- loop information:"); for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { BlockBegin* cur = _linear_scan_order->at(block_idx); tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id()); for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { tty->print ("%d ", is_block_in_loop(loop_idx, cur)); } tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth()); } } if (TraceLinearScanLevel >= 1) { tty->print_cr("----- linear-scan block order:"); for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { BlockBegin* cur = _linear_scan_order->at(block_idx); tty->print("%4d: B%2d loop: %2d depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth()); tty->print(cur->is_set(BlockBegin::exception_entry_flag) ? " ex" : " "); tty->print(cur->is_set(BlockBegin::critical_edge_split_flag) ? " ce" : " "); tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : " "); tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag) ? " le" : " "); if (cur->dominator() != NULL) { tty->print(" dom: B%d ", cur->dominator()->block_id()); } else { tty->print(" dom: NULL "); } if (cur->number_of_preds() > 0) { tty->print(" preds: "); for (int j = 0; j < cur->number_of_preds(); j++) { BlockBegin* pred = cur->pred_at(j); tty->print("B%d ", pred->block_id()); } } if (cur->number_of_sux() > 0) { tty->print(" sux: "); for (int j = 0; j < cur->number_of_sux(); j++) { BlockBegin* sux = cur->sux_at(j); tty->print("B%d ", sux->block_id()); } } if (cur->number_of_exception_handlers() > 0) { tty->print(" ex: "); for (int j = 0; j < cur->number_of_exception_handlers(); j++) { BlockBegin* ex = cur->exception_handler_at(j); tty->print("B%d ", ex->block_id()); } } tty->cr(); } } } #endif #ifdef ASSERT void ComputeLinearScanOrder::verify() { assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list"); if (StressLinearScan) { // blocks are scrambled when StressLinearScan is used return; } // check that all successors of a block have a higher linear-scan-number // and that all predecessors of a block have a lower linear-scan-number // (only backward branches of loops are ignored) int i; for (i = 0; i < _linear_scan_order->length(); i++) { BlockBegin* cur = _linear_scan_order->at(i); assert(cur->linear_scan_number() == i, "incorrect linear_scan_number"); assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->index_of(cur), "incorrect linear_scan_number"); int j; for (j = cur->number_of_sux() - 1; j >= 0; j--) { BlockBegin* sux = cur->sux_at(j); assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number"); if (!cur->is_set(BlockBegin::linear_scan_loop_end_flag)) { assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order"); } if (cur->loop_depth() == sux->loop_depth()) { assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); } } for (j = cur->number_of_preds() - 1; j >= 0; j--) { BlockBegin* pred = cur->pred_at(j); assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number"); if (!cur->is_set(BlockBegin::linear_scan_loop_header_flag)) { assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order"); } if (cur->loop_depth() == pred->loop_depth()) { assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); } assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors"); } // check dominator if (i == 0) { assert(cur->dominator() == NULL, "first block has no dominator"); } else { assert(cur->dominator() != NULL, "all but first block must have dominator"); } assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0), "Single predecessor must also be dominator"); } // check that all loops are continuous for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { int block_idx = 0; assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop"); // skip blocks before the loop while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { block_idx++; } // skip blocks of loop while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { block_idx++; } // after the first non-loop block, there must not be another loop-block while (block_idx < _num_blocks) { assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order"); block_idx++; } } } #endif void IR::compute_code() { assert(is_valid(), "IR must be valid"); ComputeLinearScanOrder compute_order(compilation(), start()); _num_loops = compute_order.num_loops(); _code = compute_order.linear_scan_order(); } void IR::compute_use_counts() { // make sure all values coming out of this block get evaluated. int num_blocks = _code->length(); for (int i = 0; i < num_blocks; i++) { _code->at(i)->end()->state()->pin_stack_for_linear_scan(); } // compute use counts UseCountComputer::compute(_code); } void IR::iterate_preorder(BlockClosure* closure) { assert(is_valid(), "IR must be valid"); start()->iterate_preorder(closure); } void IR::iterate_postorder(BlockClosure* closure) { assert(is_valid(), "IR must be valid"); start()->iterate_postorder(closure); } void IR::iterate_linear_scan_order(BlockClosure* closure) { linear_scan_order()->iterate_forward(closure); } #ifndef PRODUCT class BlockPrinter: public BlockClosure { private: InstructionPrinter* _ip; bool _cfg_only; bool _live_only; public: BlockPrinter(InstructionPrinter* ip, bool cfg_only, bool live_only = false) { _ip = ip; _cfg_only = cfg_only; _live_only = live_only; } virtual void block_do(BlockBegin* block) { if (_cfg_only) { _ip->print_instr(block); tty->cr(); } else { block->print_block(*_ip, _live_only); } } }; void IR::print(BlockBegin* start, bool cfg_only, bool live_only) { ttyLocker ttyl; InstructionPrinter ip(!cfg_only); BlockPrinter bp(&ip, cfg_only, live_only); start->iterate_preorder(&bp); tty->cr(); } void IR::print(bool cfg_only, bool live_only) { if (is_valid()) { print(start(), cfg_only, live_only); } else { tty->print_cr("invalid IR"); } } define_array(BlockListArray, BlockList*) define_stack(BlockListList, BlockListArray) class PredecessorValidator : public BlockClosure { private: BlockListList* _predecessors; BlockList* _blocks; static int cmp(BlockBegin** a, BlockBegin** b) { return (*a)->block_id() - (*b)->block_id(); } public: PredecessorValidator(IR* hir) { ResourceMark rm; _predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL); _blocks = new BlockList(); int i; hir->start()->iterate_preorder(this); if (hir->code() != NULL) { assert(hir->code()->length() == _blocks->length(), "must match"); for (i = 0; i < _blocks->length(); i++) { assert(hir->code()->contains(_blocks->at(i)), "should be in both lists"); } } for (i = 0; i < _blocks->length(); i++) { BlockBegin* block = _blocks->at(i); BlockList* preds = _predecessors->at(block->block_id()); if (preds == NULL) { assert(block->number_of_preds() == 0, "should be the same"); continue; } // clone the pred list so we can mutate it BlockList* pred_copy = new BlockList(); int j; for (j = 0; j < block->number_of_preds(); j++) { pred_copy->append(block->pred_at(j)); } // sort them in the same order preds->sort(cmp); pred_copy->sort(cmp); int length = MIN2(preds->length(), block->number_of_preds()); for (j = 0; j < block->number_of_preds(); j++) { assert(preds->at(j) == pred_copy->at(j), "must match"); } assert(preds->length() == block->number_of_preds(), "should be the same"); } } virtual void block_do(BlockBegin* block) { _blocks->append(block); BlockEnd* be = block->end(); int n = be->number_of_sux(); int i; for (i = 0; i < n; i++) { BlockBegin* sux = be->sux_at(i); assert(!sux->is_set(BlockBegin::exception_entry_flag), "must not be xhandler"); BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL); if (preds == NULL) { preds = new BlockList(); _predecessors->at_put(sux->block_id(), preds); } preds->append(block); } n = block->number_of_exception_handlers(); for (i = 0; i < n; i++) { BlockBegin* sux = block->exception_handler_at(i); assert(sux->is_set(BlockBegin::exception_entry_flag), "must be xhandler"); BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL); if (preds == NULL) { preds = new BlockList(); _predecessors->at_put(sux->block_id(), preds); } preds->append(block); } } }; void IR::verify() { #ifdef ASSERT PredecessorValidator pv(this); #endif } #endif // PRODUCT void SubstitutionResolver::visit(Value* v) { Value v0 = *v; if (v0) { Value vs = v0->subst(); if (vs != v0) { *v = v0->subst(); } } } #ifdef ASSERT class SubstitutionChecker: public ValueVisitor { void visit(Value* v) { Value v0 = *v; if (v0) { Value vs = v0->subst(); assert(vs == v0, "missed substitution"); } } }; #endif void SubstitutionResolver::block_do(BlockBegin* block) { Instruction* last = NULL; for (Instruction* n = block; n != NULL;) { n->values_do(this); // need to remove this instruction from the instruction stream if (n->subst() != n) { assert(last != NULL, "must have last"); last->set_next(n->next()); } else { last = n; } n = last->next(); } #ifdef ASSERT SubstitutionChecker check_substitute; if (block->state()) block->state()->values_do(&check_substitute); block->block_values_do(&check_substitute); if (block->end() && block->end()->state()) block->end()->state()->values_do(&check_substitute); #endif }