ifg.cpp revision 566
337N/A * Copyright 1998-2008 Sun Microsystems, Inc. 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. 0N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 0N/A * CA 95054 USA or visit www.sun.com if you need additional information or 0N/A * have any questions. 0N/A#
include "incls/_precompiled.incl" 0N/A//============================================================================= 0N/A//------------------------------IFG-------------------------------------------- 0N/A//------------------------------init------------------------------------------- 0N/A // Make uninitialized adjacency lists 0N/A // Also make empty live range structures 0N/A // Init all to empty 0N/A//------------------------------add-------------------------------------------- 0N/A// Add edge between vertices a & b. These are sorted (triangular matrix), 0N/A// then the smaller number is inserted in the larger numbered array. 0N/A // Sort a and b, so that a is bigger 0N/A//------------------------------add_vector------------------------------------- 0N/A// Add an edge between 'a' and everything in the vector. 0N/A // IFG is triangular, so do the inserts where 'a' < 'b'. 0N/A//------------------------------test------------------------------------------- 0N/A// Is there an edge between a and b? 0N/A // Sort a and b, so that a is larger 0N/A//------------------------------SquareUp--------------------------------------- 0N/A// Convert triangular matrix to square matrix 0N/A//------------------------------Compute_Effective_Degree----------------------- 0N/A// Compute effective degree in bulk 0N/A//------------------------------test_edge_sq----------------------------------- 0N/A // Swap, so that 'a' has the lesser count. Then binary search is on 0N/A // the smaller of a's list and b's list. 0N/A //return _adjs[a].unordered_member(b); 0N/A//------------------------------Union------------------------------------------ 0N/A// Union edges of B into A 0N/A//------------------------------remove_node------------------------------------ 0N/A// Yank a Node and all connected edges from the IFG. Return a 0N/A// list of neighbors (edges) yanked. 0N/A // I remove the LRG from all neighbors. 0N/A//------------------------------re_insert-------------------------------------- 0N/A// Re-insert a yanked Node. 0N/A//------------------------------compute_degree--------------------------------- 0N/A// Compute the degree between 2 live ranges. If both live ranges are 0N/A// aligned-adjacent powers-of-2 then we use the MAX size. If either is 0N/A// mis-aligned (or for Fat-Projections, not-adjacent) then we have to 0N/A// MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 0N/A//------------------------------effective_degree------------------------------- 0N/A// Compute effective degree for this live range. If both live ranges are 0N/A// aligned-adjacent powers-of-2 then we use the MAX size. If either is 0N/A// mis-aligned (or for Fat-Projections, not-adjacent) then we have to 0N/A// MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 0N/A//------------------------------dump------------------------------------------- 0N/A//------------------------------stats------------------------------------------ 0N/A//------------------------------verify----------------------------------------- 0N/A // IFG is square, sorted and no need for Find 0N/A//------------------------------interfere_with_live---------------------------- 0N/A// Interfere this register with everything currently live. Use the RegMasks 0N/A// to trim the set of possible interferences. Return a count of register-only 0N/A// inteferences as an estimate of register pressure. 0N/A // Interfere with everything live. 0N/A // Check for interference by checking overlap of regmasks. 0N/A // Only interfere if acceptable register masks overlap. 0N/A//------------------------------build_ifg_virtual------------------------------ 0N/A// Actually build the interference graph. Uses virtual registers only, no 0N/A// physical register masks. This allows me to be very aggressive when 0N/A// coalescing copies. Some of this aggressiveness will have to be undone 0N/A// later, but I'd rather get all the copies I can now (since unremoved copies 0N/A// at this point can end up in bad places). Copies I re-insert later I have 0N/A// more opportunity to insert them in low-frequency locations. 0N/A // For all blocks (in any order) do... 0N/A // The IFG is built by a single reverse pass over each basic block. 0N/A // Starting with the known live-out set, we remove things that get 0N/A // defined and add things that become live (essentially executing one 0N/A // pass of a standard LIVE analysis). Just before a Node defines a value 0N/A // (and removes it from the live-ness set) that value is certainly live. 0N/A // The defined value interferes with everything currently live. The 0N/A // value is then removed from the live-ness set and it's inputs are 0N/A // added to the live-ness set. 0N/A // Get value being defined 0N/A // Some special values do not allocate 0N/A // Remove from live-out set 0N/A // Copies do not define a new value and so do not interfere. 0N/A // Remove the copies source from the liveout set before interfering. 0N/A // Interfere with everything live 0N/A // Make all inputs live 0N/A if( !n->
is_Phi() ) {
// Phi function uses come from prior block 0N/A // 2-address instructions always have the defined value live 0N/A // on entry to the instruction, even though it is being defined 0N/A // by the instruction. We pretend a virtual copy sits just prior 0N/A // to the instruction and kills the src-def'd register. 0N/A // In other words, for 2-address instructions the defined value 0N/A // interferes with all inputs. 0N/A // Sometimes my 2-address ADDs are commuted in a bad way. 0N/A // We generally want the USE-DEF register to refer to the 0N/A // loop-varying quantity, to avoid a copy. 0N/A // Check that mach->num_opnds() == 3 to ensure instruction is 0N/A // not subsuming constants, effectively excludes addI_cin_imm 0N/A // Can NOT swap for instructions like addI_cin_imm since it 0N/A // is adding zero to yhi + carry and the second ideal-input 0N/A // points to the result of adding low-halves. 0N/A // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm 0N/A // See if the ADD is involved in a tight data loop the wrong way 0N/A // Defined value interferes with all inputs 0N/A }
// End of forall instructions in block 0N/A }
// End of forall blocks 0N/A//------------------------------count_int_pressure----------------------------- 0N/A//------------------------------count_float_pressure--------------------------- 0N/A//------------------------------lower_pressure--------------------------------- 0N/A// Adjust register pressure down by 1. Capture last hi-to-low transition, 0N/A//------------------------------build_ifg_physical----------------------------- 0N/A// Build the interference graph using physical registers when available. 0N/A// That is, if 2 live ranges are simultaneously alive but in their acceptable 0N/A// register sets do not overlap, then they do not interfere. 0N/A // For all blocks (in any order) do... 0N/A // Clone (rather than smash in place) the liveout info, so it is alive 0N/A // for the "collect_gc_info" phase later. 566N/A // Compute first nonphi node index 566N/A // Spills could be inserted before CreateEx node which should be 566N/A // first instruction in block after Phis. Move CreateEx up. 566N/A // If the CreateEx isn't above all the MachSpillCopies 566N/A // then move it to the top. 566N/A // Stop once a CreateEx or any other node is found 0N/A // Reset block's register pressure values for each ifg construction 0N/A // Liveout things are presumed live for the whole block. We accumulate 0N/A // 'area' accordingly. If they get killed in the block, we'll subtract 0N/A // the unused part of the block from the area. 0N/A // Compute initial register pressure 0N/A // Count int pressure, but do not count the SP, flags 0N/A // The IFG is built by a single reverse pass over each basic block. 0N/A // Starting with the known live-out set, we remove things that get 0N/A // defined and add things that become live (essentially executing one 0N/A // pass of a standard LIVE analysis). Just before a Node defines a value 0N/A // (and removes it from the live-ness set) that value is certainly live. 0N/A // The defined value interferes with everything currently live. The 0N/A // value is then removed from the live-ness set and it's inputs are added 0N/A // to the live-ness set. 0N/A // Get value being defined 0N/A // Some special values do not allocate 0N/A // A DEF normally costs block frequency; rematerialized values are 0N/A // removed from the DEF sight, so LOWER costs here. 0N/A // If it is not live, then this instruction is dead. Probably caused 0N/A // by spilling and rematerialization. Who cares why, yank this baby. 0N/A // Could also be a flags-projection of a dead ADD or such. 0N/A // Since yanking a Node from block, high pressure moves up one 0N/A // Fat-projections kill many registers which cannot be used to 0N/A // hold live ranges. 0N/A // Count the int-only registers 0N/A // Count the float-only registers 0N/A }
else {
// Else it is live 0N/A // A DEF also ends 'area' partway through the block. 0N/A // Insure high score for immediate-use spill copies so they get a color 0N/A && n->
outcnt() ==
1 // and use must be in this block 0N/A // All single-use MachSpillCopy(s) that immediately precede their 0N/A // use must color early. If a longer live range steals their 0N/A // color, the spill copy will split and may push another spill copy 0N/A // further away resulting in an infinite spill-split-retry cycle. 0N/A // Assigning a zero area results in a high score() and a good 0N/A // location in the simplify list. 0N/A // Use can be earlier in block if it is a Phi, but then I should be a MultiDef 0N/A // Find first non SpillCopy 'm' that follows the current instruction 0N/A // (j - 1) is index for current instruction 'n' 0N/A // Remove from live-out set 0N/A // Adjust register pressure. 0N/A // Capture last hi-to-lo pressure transition 0N/A // Copies do not define a new value and so do not interfere. 0N/A // Remove the copies source from the liveout set before interfering. 0N/A // Adjust register pressure. 0N/A }
// End of if live or not 0N/A // Interfere with everything live. If the defined value must 0N/A // go in a particular register, just remove that register from 0N/A // all conflicting parties and avoid the interference. 0N/A // Make exclusions for rematerializable defs. Since rematerializable 0N/A // DEFs are not bound but the live range is, some uses must be bound. 0N/A // If we spill live range 'r', it can rematerialize at each use site 0N/A // according to its bindings. 0N/A // Smear odd bits; leave only aligned pairs of bits. 0N/A // Check for common case 0N/A // If 'l' must spill already, do not further hack his bits. 0N/A // He'll get some interferences and be forced to spill later. 0N/A // Remove bound register(s) from 'l's choices 0N/A // Remove the bits from LRG 'r' from LRG 'l' so 'l' no 0N/A // longer interferes with 'r'. If 'l' requires aligned 0N/A // adjacent pairs, subtract out bit pairs. 0N/A }
else {
// Common case: size 1 bound removal 0N/A // If 'l' goes completely dry, it must spill. 0N/A // Give 'l' some kind of reasonable mask, so he picks up 0N/A // interferences (and will spill later). 0N/A }
// End of if bound 0N/A // Now interference with everything that is live and has 0N/A // compatible register sets. 0N/A }
// End of if normal register-allocated value 369N/A // Area remaining in the block 0N/A // Make all inputs live 0N/A if( !n->
is_Phi() ) {
// Phi function uses come from prior block 0N/A // Start loop at 1 (skip control edge) for most Nodes. 0N/A // SCMemProj's might be the sole use of a StoreLConditional. 0N/A // While StoreLConditionals set memory (the SCMemProj use) 0N/A // they also def flags; if that flag def is unused the 0N/A // allocator sees a flag-setting instruction with no use of 0N/A // the flags and assumes it's dead. This keeps the (useless) 0N/A // flag-setting behavior alive while also keeping the (useful) 0N/A // memory update effect. 0N/A // No use-side cost for spilling debug info 0N/A // A USE costs twice block frequency (once for the Load, once 0N/A // for a Load-delay). Rematerialized uses only cost once. 0N/A // Newly live things assumed live from here to top of block 0N/A // Adjust register pressure 0N/A }
// End of reverse pass over all instructions in block 0N/A // If we run off the top of the block with high pressure and 0N/A // never see a hi-to-low pressure transition, just record that 0N/A // the whole block is high pressure. 0N/A // Compute high pressure indice; avoid landing in the middle of projnodes 0N/A // Gather Register Pressure Statistics 0N/A }
// End of for all blocks