2273N/A * Copyright (c) 2002, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A// The functions in this file builds OopMaps after all scheduling is done. 0N/A// OopMaps contain a list of all registers and stack-slots containing oops (so 0N/A// they can be updated by GC). OopMaps also contain a list of derived-pointer 0N/A// base-pointer pairs. When the base is moved, the derived pointer moves to 0N/A// follow it. Finally, any registers holding callee-save values are also 0N/A// recorded. These might contain oops, but only the caller knows. 0N/A// BuildOopMaps implements a simple forward reaching-defs solution. At each 0N/A// GC point we'll have the reaching-def Nodes. If the reaching Nodes are 0N/A// typed as pointers (no offset), then they are oops. Pointers+offsets are 0N/A// derived pointers, and bases can be found from them. Finally, we'll also 0N/A// track reaching callee-save values. Note that a copy of a callee-save value 0N/A// "kills" it's source, so that only 1 copy of a callee-save value is alive at 0N/A// We run a simple bitvector liveness pass to help trim out dead oops. Due to 0N/A// irreducible loops, we can have a reaching def of an oop that only reaches 0N/A// along one path and no way to know if it's valid or not on the other path. 0N/A// The bitvectors are quite dense and the liveness pass is fast. 0N/A// At GC points, we consult this information to build OopMaps. All reaching 0N/A// defs typed as oops are added to the OopMap. Only 1 instance of a 0N/A// callee-save register can be recorded. For derived pointers, we'll have to 0N/A// find and record the register holding the base. 0N/A// The reaching def's is a simple 1-pass worklist approach. I tried a clever 0N/A// breadth-first approach but it was worse (showed O(n^2) in the 0N/A// pick-next-block code). 605N/A// The relevant data is kept in a struct of arrays (it could just as well be 0N/A// an array of structs, but the struct-of-arrays is generally a little more 0N/A// efficient). The arrays are indexed by register number (including 0N/A// stack-slots as registers) and so is bounded by 200 to 300 elements in 0N/A// practice. One array will map to a reaching def Node (or NULL for 0N/A// OptoReg::Bad for not-callee-saved. 0N/A//------------------------------OopFlow---------------------------------------- 0N/A// Structure to pass around 0N/A short *
_callees;
// Array mapping register to callee-saved 0N/A // OopFlow structs, when not being actively modified, describe the _end_ of 0N/A // Given reaching-defs for this block start, compute it for this block end 0N/A // Merge these two OopFlows into the 'this' pointer. 0N/A // Copy a 'flow' over an existing flow 0N/A // Make a new OopFlow from scratch 0N/A // Build an oopmap from the current flow info 0N/A//------------------------------compute_reach---------------------------------- 0N/A// Given reaching-defs for this block start, compute it for this block end 0N/A if( n->
jvms() ) {
// Build an OopMap here? 0N/A // no map needed for leaf calls 0N/A // Assign new reaching def's. 0N/A // Note that I padded the _defs and _callees arrays so it's legal 0N/A // to index at _defs[OptoReg::Bad]. 0N/A // Pass callee-save info around copies 0N/A if(
idx ) {
// Copies move callee-save info 0N/A }
else if( n->
is_Phi() ) {
// Phis do not mod callee-saves 0N/A // Find base case for callee saves 0N/A//------------------------------merge------------------------------------------ 0N/A// Merge the given flow into the 'this' flow 0N/A // Do the merge. If there are any differences, drop to 'bottom' which 0N/A // is OptoReg::Bad or NULL depending. 0N/A // Merge the callee-save's 0N/A // Merge the reaching defs 0N/A//------------------------------clone------------------------------------------ 0N/A//------------------------------make------------------------------------------- 0N/A//------------------------------bit twiddlers---------------------------------- 0N/A//------------------------------build_oop_map---------------------------------- 0N/A// Build an oopmap from the current flow info 0N/A // For all registers do... 0N/A continue;
// Ignore if not live 0N/A // %%% C2 can use 2 OptoRegs when the physical register is only one 64bit 0N/A // register in that case we'll get an non-concrete register for the second 0N/A // half. We only need to tell the map the register once! 0N/A // However for the moment we disable this change and leave things as they 0N/A // See if dead (no reaching def). 0N/A // Classify the reaching def as oop, derived, callee-save, dead, or other 0N/A // 64-bit pointers record oop-ishness on 2 aligned adjacent registers. 0N/A // Make sure both are record from the same reaching def, but do not 0N/A // put both into the oopmap. 0N/A if( (
reg&
1) ==
1 ) {
// High half of oop-pair? 0N/A continue;
// Do not record high parts in oopmap 0N/A // Check for a legal reg name in the oopMap and bailout if it is not. 0N/A // Outgoing argument GC mask responsibility belongs to the callee, 0N/A // not the caller. Inspect the inputs to the call, to see if 0N/A // this live-range is one of them. 0N/A break;
// reaching def is an argument oop 0N/A if( j <
cnt )
// arg oops dont go in GC map 0N/A continue;
// Continue on to the next register 0N/A }
else {
// Else it's derived. 0N/A // Find the base of the derived value. 0N/A // Fast, common case, scan 0N/A if( n->
in(i) ==
def )
break;
// Common case 0N/A if( i == n->
req() ) {
// Missed, try a more generous scan 0N/A // Scan again, but this time peek through copies 0N/A Node *m = n->
in(i);
// Get initial derived value 0N/A while(
1 ) {
// Follow copies of reaching def to end 0N/A if( m == d )
goto found;
// breaks 3 loops 0N/A // I record liveness at safepoints BEFORE I make the inputs 0N/A // live. This is because argument oops are NOT live at a 0N/A // safepoint (or at least they cannot appear in the oopmap). 0N/A // liveness data but they need to appear in the oopmap. 0N/A // Flag it, so next derived pointer won't re-insert into oopmap 0N/A // Already missed our turn? 113N/A // Check for a legal reg name in the oopMap and bailout if it is not. 113N/A // Outgoing argument GC mask responsibility belongs to the callee, 113N/A // not the caller. Inspect the inputs to the call, to see if 113N/A // this live-range is one of them. 113N/A break;
// reaching def is an argument oop 113N/A if( j <
cnt )
// arg oops dont go in GC map 113N/A continue;
// Continue on to the next register 0N/A // It's a callee-save value 0N/A // Other - some reaching non-oop value 833N/A assert(
false,
"there should be a oop in OopMap instead of a live raw oop at safepoint");
0N/A /* Nice, Intel-only assert 0N/A int cnt_callee_saves=0; 0N/A while (OptoReg::is_reg(reg2)) { 0N/A if( dup_check[reg2] != 0) cnt_callee_saves++; 0N/A assert( cnt_callee_saves==3 || cnt_callee_saves==5, "missed some callee-save" ); 0N/A//------------------------------do_liveness------------------------------------ 0N/A// Compute backwards liveness on registers 0N/A // On CISC platforms, get the node representing the stack pointer that regalloc 0N/A // Push preds onto worklist 0N/A // ZKM.jar includes tiny infinite loops which are unreached from below. 0N/A // If we missed any blocks, we'll retry here after pushing all missed 0N/A // blocks on the worklist. Normally this outer loop never trips more 0N/A // Copy first successor into my tmp_live space 0N/A // OR in the remaining live registers 0N/A // Now walk tmp_live up the block backwards, computing live 0N/A // Check if m is potentially a CISC alternate instruction (i.e, possibly 0N/A // synthesized by RegAlloc from a conventional instruction and a 0N/A // If we use the stack pointer in a cisc-alternative instruction, 0N/A // check for use as a memory operand. Then reconstruct the RegName 0N/A // for this stack location, and set the appropriate bit in the 0N/A // live vector 4987749. 0N/A // Machnode has multiple memory inputs. We are unable to reason 0N/A // with these, but are presuming (with trepidation) that not any of 0N/A // them are oops. This can be fixed by making get_base_and_disp() 0N/A // look at a specific input instead of all inputs. 0N/A // Do nothing: the fp operand is either not from a memory use 0N/A // (base == NULL) OR the fp is used in a non-memory context 0N/A // (base is some other register) OR the offset is not constant, 0N/A // so it is not a stack slot. 0N/A if( n->
jvms() ) {
// Record liveness at safepoint 0N/A // This placement of this stanza means inputs to calls are 0N/A // considered live at the callsite's OopMap. Argument oops are 0N/A // hence live, but NOT included in the oopmap. See cutout in 0N/A // build_oop_map. Debug oops are live (and in OopMap). 0N/A // Now at block top, see if we have any changes. If so, propagate 0N/A // Copy in new value 0N/A // Push preds onto worklist 0N/A // Scan for any missing safepoints. Happens to infinite loops 0N/A break;
// Got 'em all 0N/A // Force the issue (expensively): recheck everybody 0N/A//------------------------------BuildOopMaps----------------------------------- 0N/A// Collect GC mask info - where are all the OOPs? 0N/A // Can't resource-mark because I need to leave all those OopMaps around, 0N/A // or else I need to resource-mark some arena other than the default. 0N/A // ResourceMark rm; // Reclaim all OopFlows when done 0N/A // Compute a backwards liveness per register. Needs a bitarray of 0N/A // #blocks x (#registers, rounded up to ints) 0N/A // Array mapping blocks to completed oopflows 0N/A // Do the first block 'by hand' to prime the worklist 0N/A // Initialize to 'bottom' (not 'top') 0N/A // Do the first block 'by hand' to prime the worklist 0N/A // Now worklist contains blocks which have some, but perhaps not all, 0N/A // predecessors visited. 0N/A // Scan for a block with all predecessors visited, or any randoms slob 0N/A // otherwise. All-preds-visited order allows me to recycle OopFlow 0N/A // structures rapidly and cut down on the memory footprint. 0N/A // Note: not all predecessors might be visited yet (must happen for 0N/A // irreducible loops). This is OK, since every live value must have the 0N/A // SAME reaching def for the block, so any reaching def is OK. 0N/A // Ignore root block 0N/A // Block is already done? Happens if block has several predecessors, 0N/A // he can get on the worklist more than once. 0N/A // If this block has a visited predecessor AND that predecessor has this 0N/A // last block as his only undone child, we can move the OopFlow from the 0N/A // pred to this block. Otherwise we have to grab a new OopFlow. 0N/A // Scan this block's preds to find a done predecessor 0N/A pred = p;
// Record some predecessor 0N/A // If all successors of p are done except for 'b', then we can carry 0N/A // p_flow forward to 'b' without copying, otherwise we have to draw 0N/A // from the free_list and clone data. 0N/A // Either carry-forward the now-unused OopFlow for b's use 0N/A // or draw a new one from the free list 0N/A break;
// Found an ideal pred, use him 0N/A // We have an OopFlow that's the last-use of a predecessor. 0N/A // Carry it forward. 0N/A }
else {
// Draw a new OopFlow from the freelist 0N/A // Mark flow for block. Blocks can only be flowed over once, 0N/A // because after the first time they are guarded from entering 0N/A // Now push flow forward 0N/A // Now push children onto worklist