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