truffle: src/share/vm/opto/node.cpp comparison

comparison src/share/vm/opto/node.cpp @ 193:44a553b2809d

6714406: Node::dominates() does not always check for TOP Summary: Add missed checks for TOP and missed checks for non-dominating cases Reviewed-by: rasbold, jrose, never

author	kvn
date	Fri, 13 Jun 2008 15:08:56 -0700
parents	885ed790ecf0
children	d1605aabd0a1 2a1a77d3458f

comparison

equal deleted inserted replaced

-:6d13fcb3663f
+:44a553b2809d
 }
 //--------------------------dominates------------------------------------------
 // Helper function for MemNode::all_controls_dominate().
 // Check if 'this' control node dominates or equal to 'sub' control node.
+// We already know that if any path back to Root or Start reaches 'this',
+// then all paths so, so this is a simple search for one example,
+// not an exhaustive search for a counterexample.
 bool Node::dominates(Node* sub, Node_List &nlist) {
 assert(this->is_CFG(), "expecting control");
 assert(sub != NULL && sub->is_CFG(), "expecting control");
 // detect dead cycle without regions
 int iterations_without_region_limit = DominatorSearchLimit;
 Node* orig_sub = sub;
+Node* dom      = this;
+bool  met_dom  = false;
 nlist.clear();
-bool this_dominates = false;
-bool result = false; // Conservative answer
+// Walk 'sub' backward up the chain to 'dom', watching for regions.
+// After seeing 'dom', continue up to Root or Start.
-while (sub != NULL) {        // walk 'sub' up the chain to 'this'
+// If we hit a region (backward split point), it may be a loop head.
-if (sub == this) {
+// Keep going through one of the region's inputs.  If we reach the
+// same region again, go through a different input.  Eventually we
+// will either exit through the loop head, or give up.
+// (If we get confused, break out and return a conservative 'false'.)
+while (sub != NULL) {
+if (sub->is_top())  break; // Conservative answer for dead code.
+if (sub == dom) {
 if (nlist.size() == 0) {
 // No Region nodes except loops were visited before and the EntryControl
 // path was taken for loops: it did not walk in a cycle.
-result = true;
+return true;
-break;
+} else if (met_dom) {
-} else if (this_dominates) {
+break;          // already met before: walk in a cycle
-result = false;          // already met before: walk in a cycle
-break;
 } else {
 // Region nodes were visited. Continue walk up to Start or Root
 // to make sure that it did not walk in a cycle.
-this_dominates = true; // first time meet
+met_dom = true; // first time meet
 iterations_without_region_limit = DominatorSearchLimit; // Reset
 }
 }
 if (sub->is_Start() || sub->is_Root()) {
-result = this_dominates;
+// Success if we met 'dom' along a path to Start or Root.
-break;
+// We assume there are no alternative paths that avoid 'dom'.
-}
+// (This assumption is up to the caller to ensure!)
-Node* up = sub->find_exact_control(sub->in(0));
+return met_dom;
-if (up == NULL || up->is_top()) {
+}
-result = false; // Conservative answer for dead code
+Node* up = sub->in(0);
-break;
+// Normalize simple pass-through regions and projections:
-}
+up = sub->find_exact_control(up);
-if (sub == up && (sub->is_Loop() || sub->is_Region() && sub->req() != 3)) {
+// If sub == up, we found a self-loop.  Try to push past it.
-// Take first valid path on the way up to 'this'.
+if (sub == up && sub->is_Loop()) {
+// Take loop entry path on the way up to 'dom'.
 up = sub->in(1); // in(LoopNode::EntryControl);
+} else if (sub == up && sub->is_Region() && sub->req() != 3) {
+// Always take in(1) path on the way up to 'dom' for clone regions
+// (with only one input) or regions which merge > 2 paths
+// (usually used to merge fast/slow paths).
+up = sub->in(1);
 } else if (sub == up && sub->is_Region()) {
-assert(sub->req() == 3, "sanity");
+// Try both paths for Regions with 2 input paths (it may be a loop head).
+// It could give conservative 'false' answer without information
+// which region's input is the entry path.
 iterations_without_region_limit = DominatorSearchLimit; // Reset
-// Try both paths for such Regions.
-// It is not accurate without regions dominating information.
-// With such information the other path should be checked for
-// the most dominating Region which was visited before.
 bool region_was_visited_before = false;
-uint i = 1;
+// Was this Region node visited before?
-uint size = nlist.size();
+// If so, we have reached it because we accidentally took a
-if (size == 0) {
+// loop-back edge from 'sub' back into the body of the loop,
-// No such Region nodes were visited before.
+// and worked our way up again to the loop header 'sub'.
-// Take first valid path on the way up to 'this'.
+// So, take the first unexplored path on the way up to 'dom'.
-} else {
+for (int j = nlist.size() - 1; j >= 0; j--) {
-// Was this Region node visited before?
+intptr_t ni = (intptr_t)nlist.at(j);
-intptr_t ni;
+Node* visited = (Node*)(ni & ~1);
-int j = size - 1;
+bool  visited_twice_already = ((ni & 1) != 0);
-for (; j >= 0; j--) {
+if (visited == sub) {
-ni = (intptr_t)nlist.at(j);
+if (visited_twice_already) {
-if ((Node*)(ni & ~1) == sub) {
+// Visited 2 paths, but still stuck in loop body.  Give up.
-if ((ni & 1) != 0) {
+return false;
-break; // Visited 2 paths. Give up.
-} else {
-// The Region node was visited before only once.
-nlist.remove(j);
-region_was_visited_before = true;
-for (; i < sub->req(); i++) {
-Node* in = sub->in(i);
-if (in != NULL && !in->is_top() && in != sub) {
-break;
-}
-}
-i++; // Take other path.
-break;
-}
 }
-}
+// The Region node was visited before only once.
-if (j >= 0 && (ni & 1) != 0) {
+// (We will repush with the low bit set, below.)
-result = false; // Visited 2 paths. Give up.
+nlist.remove(j);
-break;
+// We will find a new edge and re-insert.
-}
+region_was_visited_before = true;
-// The Region node was not visited before.
-}
-for (; i < sub->req(); i++) {
-Node* in = sub->in(i);
-if (in != NULL && !in->is_top() && in != sub) {
 break;
 }
 }
-if (i < sub->req()) {
-up = sub->in(i);
+// Find an incoming edge which has not been seen yet; walk through it.
-if (region_was_visited_before && sub != up) {
+assert(up == sub, "");
-// Set 0 bit to indicate that both paths were taken.
+uint skip = region_was_visited_before ? 1 : 0;
-nlist.push((Node*)((intptr_t)sub + 1));
+for (uint i = 1; i < sub->req(); i++) {
-} else {
+Node* in = sub->in(i);
-nlist.push(sub);
+if (in != NULL && !in->is_top() && in != sub) {
+if (skip == 0) {
+up = in;
+break;
+}
+--skip;               // skip this nontrivial input
 }
 }
-}
-if (sub == up) {
+// Set 0 bit to indicate that both paths were taken.
-result = false;    // some kind of tight cycle
+nlist.push((Node*)((intptr_t)sub + (region_was_visited_before ? 1 : 0)));
-break;
+}
+if (up == sub) {
+break;    // some kind of tight cycle
+}
+if (up == orig_sub && met_dom) {
+// returned back after visiting 'dom'
+break;    // some kind of cycle
 }
 if (--iterations_without_region_limit < 0) {
-result = false;    // dead cycle
+break;    // dead cycle
-break;
 }
 sub = up;
 }
-return result;
+// Did not meet Root or Start node in pred. chain.
+// Conservative answer for dead code.
+return false;
 }
 //------------------------------remove_dead_region-----------------------------
 // This control node is dead.  Follow the subgraph below it making everything
 // using it dead as well.  This will happen normally via the usual IterGVN

Mercurial > hg > truffle

comparison src/share/vm/opto/node.cpp @ 193:44a553b2809d