phaseX.hpp revision 1409
893N/A * Copyright 1997-2009 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//----------------------------------------------------------------------------- 0N/A// Expandable closed hash-table of nodes, initialized to NULL. 0N/A// Note that the constructor just zeros things 0N/A// Storage is reclaimed when the Arena's lifetime is over. uint _max;
// Size of table (power of 2) ~
NodeHash();
// Unlock all nodes upon destruction of table. void operator=(
const NodeHash&);
// Unlock all nodes upon replacement of table. void grow();
// Grow _table to next power of 2 and rehash // Return 75% of _max, rounded up. void clear();
// Set all entries to NULL, keep storage. // Return Node* at index in table void dump();
// For debugging, dump statistics uint _grows;
// For debugging, count of table grow()s //----------------------------------------------------------------------------- // Map dense integer indices to Types. Uses classic doubling-array trick. // Abstractly provides an infinite array of Type*'s, initialized to NULL. // Note that the constructor just zeros things, and since I use Arena // allocation I do not need a destructor to reclaim storage. // Despite the general name, this class is customized for use by PhaseTransform. void grow(
uint i );
// Grow array node to fit const Type *
operator[] (
uint i )
const // Lookup, or NULL for not mapped // Extend the mapping: index i maps to Type *n. //------------------------------PhaseRemoveUseless----------------------------- // Remove useless nodes from GVN hash-table, worklist, and graph // list is allocated from current resource area //------------------------------PhaseTransform--------------------------------- // Phases that analyze, then transform. Constructing the Phase object does any // global or slow analysis. The results are cached later for a fast // transformation pass. When the Phase object is deleted the cached analysis // Support both int and long caches because either might be an intptr_t, // so they show up frequently in address computations. // _nodes is used in varying ways by subclasses, which define local accessors // Get a previously recorded type for the node n. // This type must already have been recorded. // If you want the type of a very new (untransformed) node, // you must use type_or_null, and test the result for NULL. // Get a previously recorded type for the node n, // or else return NULL if there is none. // Record a type for a node. // Record an initial type for a node, the node's bottom type. // Use this for initialization when bottom_type() (or better) is not handy. // Usually the initialization shoudl be to n->Value(this) instead, // or a hand-optimized value like Type::MEMORY or Type::CONTROL. // Make sure the types array is big enough to record a size for the node n. // (In product builds, we never want to do range checks on the types array!) // Make an idealized constant, i.e., one of ConINode, ConPNode, ConFNode, etc. // Same as transform(ConNode::make(t)). // Fast int or long constant. Same as TypeInt::make(i) or TypeLong::make(l). // Fast zero or null constant. Same as makecon(Type::get_zero_type(bt)). // Return a node which computes the same function as this node, but // in a faster or cheaper fashion. // Return whether two Nodes are equivalent. // Must not be recursive, since the recursive version is built from this. // For pessimistic optimizations this is simply pointer equivalence. // Return whether two Nodes are equivalent, after stripping casting. // For pessimistic passes, the return type must monotonically narrow. // For optimistic passes, the return type must monotonically widen. // It is possible to get into a "death march" in either type of pass, // where the types are continually moving but it will take 2**31 or // more steps to converge. This doesn't happen on most normal loops. // Here is an example of a deadly loop for an optimistic pass, along // with a partial trace of inferred types: // x = phi(0,x'); L: x' = x+1; if (x' >= 0) goto L; // [0..1] [1..2] join([0..max], [1..2]) // [0..2] [1..3] join([0..max], [1..3]) // [0..max] [min]u[1..max] join([0..max], [min..max]) // We would have proven, the hard way, that the iteration space is all // non-negative ints, with the loop terminating due to 32-bit overflow. // Here is the corresponding example for a pessimistic pass: // x = phi(0,x'); L: x' = x-1; if (x' >= 0) goto L; // int int join([0..max], int) // [0..max] [-1..max-1] join([0..max], [-1..max-1]) // [0..max-1] [-1..max-2] join([0..max], [-1..max-2]) // [0..1] [-1..0] join([0..max], [-1..0]) // 0 -1 join([0..max], -1) // We would have proven, the hard way, that the iteration space is {0}. // (Usually, other optimizations will make the "if (x >= 0)" fold up // before we get into trouble. But not always.) // It's a pleasant thing to observe that the pessimistic pass // will make short work of the optimistic pass's deadly loop, // and vice versa. That is a good example of the complementary // purposes of the CCP (optimistic) vs. GVN (pessimistic) phases. // In any case, only widen or narrow a few times before going to the // correct flavor of top or bottom. // This call only needs to be made once as the data flows around any // given cycle. We do it at Phis, and nowhere else. // The types presented are the new type of a phi (computed by PhiNode::Value) // and the previously computed type, last time the phi was visited. // The third argument is upper limit for the saturated value, // if the phase wishes to widen the new_type. // If the phase is narrowing, the old type provides a lower limit. // Caller guarantees that old_type and new_type are no higher than limit_type. //------------------------------PhaseValues------------------------------------ // Phase infrastructure to support values // Some Ideal and other transforms delete --> modify --> insert values // Used after parsing to eliminate values that are no longer in program // this may invalidate cached cons so reset the cache //------------------------------PhaseGVN--------------------------------------- // Phase for performing local, pessimistic GVN-style optimizations. // Return a node which computes the same function as this node, but // in a faster or cheaper fashion. // Check for a simple dead loop when a data node references itself. //------------------------------PhaseIterGVN----------------------------------- // Phase for iteratively performing local, pessimistic GVN-style optimizations. // and ideal transformations on the graph. bool _delay_transform;
// When true simply register the node when calling transform // instead of actually optimizing it // Idealize old Node 'n' with respect to its inputs and its value // Idealize new Node 'n' with respect to its inputs and its value // Warm up hash table, type table and initial worklist // Usually returns new_type. Returns old_type if new_type is only a slight // improvement, such that it would take many (>>10) steps to reach 2**32. // Given def-use info and an initial worklist, apply Node::Ideal, // Node::Value, Node::Identity, hash-based value numbering, Node::Ideal_DU // and dominator info to a fixed point. // Register a new node with the iter GVN pass without transforming it. // Used when we need to restructure a Region/Phi area and all the Regions // and Phis need to complete this one big transform before any other // transforms can be triggered on the region. // Optional 'orig' is an earlier version of this node. // It is significant only for debugging and profiling. // Kill a globally dead Node. It is allowed to have uses which are // assumed dead and left 'in limbo'. // Kill all inputs to a dead node, recursively making more dead nodes. // The Node must be dead locally, i.e., have no uses. // Subsume users of node 'old' into node 'nn' // If no Def-Use info existed for 'nn' it will after call. // Add users of 'n' to worklist // Replace old node with new one. // Sub-quadratic implementation of VerifyIterativeGVN. //------------------------------PhaseCCP--------------------------------------- // Phase for performing global Conditional Constant Propagation. // Should be replaced with combined CCP & GVN someday. // Non-recursive. Use analysis to transform single Node. // Worklist algorithm identifies constants // Recursive traversal of program. Used analysis to modify program. // Do any transformation after analysis // Returns new_type->widen(old_type), which increments the widen bits until // giving up with TypeInt::INT or TypeLong::LONG. // Result is clipped to limit_type if necessary. //------------------------------PhasePeephole---------------------------------- // Phase for performing peephole optimizations on register allocated basic blocks. // Recursive traversal of program. Pure function is unused in this phase // Do any transformation after analysis