Mercurial > jdk8-mips64-public > hotspot / changeset

     1.1 --- a/src/share/vm/opto/memnode.cpp	Fri Jun 13 14:49:07 2008 -0700
     1.2 +++ b/src/share/vm/opto/memnode.cpp	Fri Jun 13 15:08:56 2008 -0700
     1.3 @@ -253,11 +253,17 @@
     1.4    if (dom == NULL || dom->is_top() || sub == NULL || sub->is_top())
     1.5      return false; // Conservative answer for dead code
     1.6  
     1.7 -  // Check 'dom'.
     1.8 +  // Check 'dom'. Skip Proj and CatchProj nodes.
     1.9    dom = dom->find_exact_control(dom);
    1.10    if (dom == NULL || dom->is_top())
    1.11      return false; // Conservative answer for dead code
    1.12  
    1.13 +  if (dom == sub) {
    1.14 +    // For the case when, for example, 'sub' is Initialize and the original
    1.15 +    // 'dom' is Proj node of the 'sub'.
    1.16 +    return false;
    1.17 +  }
    1.18 +
    1.19    if (dom->is_Con() || dom->is_Start() || dom->is_Root() || dom == sub)
    1.20      return true;
    1.21  
    1.22 @@ -271,6 +277,7 @@
    1.23           sub->is_Region(), "expecting only these nodes");
    1.24  
    1.25    // Get control edge of 'sub'.
    1.26 +  Node* orig_sub = sub;
    1.27    sub = sub->find_exact_control(sub->in(0));
    1.28    if (sub == NULL || sub->is_top())
    1.29      return false; // Conservative answer for dead code
    1.30 @@ -296,14 +303,16 @@
    1.31  
    1.32      for (uint next = 0; next < dom_list.size(); next++) {
    1.33        Node* n = dom_list.at(next);
    1.34 +      if (n == orig_sub)
    1.35 +        return false; // One of dom's inputs dominated by sub.
    1.36        if (!n->is_CFG() && n->pinned()) {
    1.37          // Check only own control edge for pinned non-control nodes.
    1.38          n = n->find_exact_control(n->in(0));
    1.39          if (n == NULL || n->is_top())
    1.40            return false; // Conservative answer for dead code
    1.41          assert(n->is_CFG(), "expecting control");
    1.42 -      }
    1.43 -      if (n->is_Con() || n->is_Start() || n->is_Root()) {
    1.44 +        dom_list.push(n);
    1.45 +      } else if (n->is_Con() || n->is_Start() || n->is_Root()) {
    1.46          only_dominating_controls = true;
    1.47        } else if (n->is_CFG()) {
    1.48          if (n->dominates(sub, nlist))

     2.1 --- a/src/share/vm/opto/node.cpp	Fri Jun 13 14:49:07 2008 -0700
     2.2 +++ b/src/share/vm/opto/node.cpp	Fri Jun 13 15:08:56 2008 -0700
     2.3 @@ -1039,6 +1039,9 @@
     2.4  //--------------------------dominates------------------------------------------
     2.5  // Helper function for MemNode::all_controls_dominate().
     2.6  // Check if 'this' control node dominates or equal to 'sub' control node.
     2.7 +// We already know that if any path back to Root or Start reaches 'this',
     2.8 +// then all paths so, so this is a simple search for one example,
     2.9 +// not an exhaustive search for a counterexample.
    2.10  bool Node::dominates(Node* sub, Node_List &nlist) {
    2.11    assert(this->is_CFG(), "expecting control");
    2.12    assert(sub != NULL && sub->is_CFG(), "expecting control");
    2.13 @@ -1047,110 +1050,115 @@
    2.14    int iterations_without_region_limit = DominatorSearchLimit;
    2.15  
    2.16    Node* orig_sub = sub;
    2.17 +  Node* dom      = this;
    2.18 +  bool  met_dom  = false;
    2.19    nlist.clear();
    2.20 -  bool this_dominates = false;
    2.21 -  bool result = false; // Conservative answer
    2.22  
    2.23 -  while (sub != NULL) {        // walk 'sub' up the chain to 'this'
    2.24 -    if (sub == this) {
    2.25 +  // Walk 'sub' backward up the chain to 'dom', watching for regions.
    2.26 +  // After seeing 'dom', continue up to Root or Start.
    2.27 +  // If we hit a region (backward split point), it may be a loop head.
    2.28 +  // Keep going through one of the region's inputs.  If we reach the
    2.29 +  // same region again, go through a different input.  Eventually we
    2.30 +  // will either exit through the loop head, or give up.
    2.31 +  // (If we get confused, break out and return a conservative 'false'.)
    2.32 +  while (sub != NULL) {
    2.33 +    if (sub->is_top())  break; // Conservative answer for dead code.
    2.34 +    if (sub == dom) {
    2.35        if (nlist.size() == 0) {
    2.36          // No Region nodes except loops were visited before and the EntryControl
    2.37          // path was taken for loops: it did not walk in a cycle.
    2.38 -        result = true;
    2.39 -        break;
    2.40 -      } else if (this_dominates) {
    2.41 -        result = false;          // already met before: walk in a cycle
    2.42 -        break;
    2.43 +        return true;
    2.44 +      } else if (met_dom) {
    2.45 +        break;          // already met before: walk in a cycle
    2.46        } else {
    2.47          // Region nodes were visited. Continue walk up to Start or Root
    2.48          // to make sure that it did not walk in a cycle.
    2.49 -        this_dominates = true; // first time meet
    2.50 +        met_dom = true; // first time meet
    2.51          iterations_without_region_limit = DominatorSearchLimit; // Reset
    2.52       }
    2.53      }
    2.54      if (sub->is_Start() || sub->is_Root()) {
    2.55 -      result = this_dominates;
    2.56 -      break;
    2.57 +      // Success if we met 'dom' along a path to Start or Root.
    2.58 +      // We assume there are no alternative paths that avoid 'dom'.
    2.59 +      // (This assumption is up to the caller to ensure!)
    2.60 +      return met_dom;
    2.61      }
    2.62 -    Node* up = sub->find_exact_control(sub->in(0));
    2.63 -    if (up == NULL || up->is_top()) {
    2.64 -      result = false; // Conservative answer for dead code
    2.65 -      break;
    2.66 -    }
    2.67 -    if (sub == up && (sub->is_Loop() || sub->is_Region() && sub->req() != 3)) {
    2.68 -      // Take first valid path on the way up to 'this'.
    2.69 +    Node* up = sub->in(0);
    2.70 +    // Normalize simple pass-through regions and projections:
    2.71 +    up = sub->find_exact_control(up);
    2.72 +    // If sub == up, we found a self-loop.  Try to push past it.
    2.73 +    if (sub == up && sub->is_Loop()) {
    2.74 +      // Take loop entry path on the way up to 'dom'.
    2.75        up = sub->in(1); // in(LoopNode::EntryControl);
    2.76 +    } else if (sub == up && sub->is_Region() && sub->req() != 3) {
    2.77 +      // Always take in(1) path on the way up to 'dom' for clone regions
    2.78 +      // (with only one input) or regions which merge > 2 paths
    2.79 +      // (usually used to merge fast/slow paths).
    2.80 +      up = sub->in(1);
    2.81      } else if (sub == up && sub->is_Region()) {
    2.82 -      assert(sub->req() == 3, "sanity");
    2.83 +      // Try both paths for Regions with 2 input paths (it may be a loop head).
    2.84 +      // It could give conservative 'false' answer without information
    2.85 +      // which region's input is the entry path.
    2.86        iterations_without_region_limit = DominatorSearchLimit; // Reset
    2.87  
    2.88 -      // Try both paths for such Regions.
    2.89 -      // It is not accurate without regions dominating information.
    2.90 -      // With such information the other path should be checked for
    2.91 -      // the most dominating Region which was visited before.
    2.92        bool region_was_visited_before = false;
    2.93 -      uint i = 1;
    2.94 -      uint size = nlist.size();
    2.95 -      if (size == 0) {
    2.96 -        // No such Region nodes were visited before.
    2.97 -        // Take first valid path on the way up to 'this'.
    2.98 -      } else {
    2.99 -        // Was this Region node visited before?
   2.100 -        intptr_t ni;
   2.101 -        int j = size - 1;
   2.102 -        for (; j >= 0; j--) {
   2.103 -          ni = (intptr_t)nlist.at(j);
   2.104 -          if ((Node*)(ni & ~1) == sub) {
   2.105 -            if ((ni & 1) != 0) {
   2.106 -              break; // Visited 2 paths. Give up.
   2.107 -            } else {
   2.108 -              // The Region node was visited before only once.
   2.109 -              nlist.remove(j);
   2.110 -              region_was_visited_before = true;
   2.111 -              for (; i < sub->req(); i++) {
   2.112 -                Node* in = sub->in(i);
   2.113 -                if (in != NULL && !in->is_top() && in != sub) {
   2.114 -                  break;
   2.115 -                }
   2.116 -              }
   2.117 -              i++; // Take other path.
   2.118 -              break;
   2.119 -            }
   2.120 +      // Was this Region node visited before?
   2.121 +      // If so, we have reached it because we accidentally took a
   2.122 +      // loop-back edge from 'sub' back into the body of the loop,
   2.123 +      // and worked our way up again to the loop header 'sub'.
   2.124 +      // So, take the first unexplored path on the way up to 'dom'.
   2.125 +      for (int j = nlist.size() - 1; j >= 0; j--) {
   2.126 +        intptr_t ni = (intptr_t)nlist.at(j);
   2.127 +        Node* visited = (Node*)(ni & ~1);
   2.128 +        bool  visited_twice_already = ((ni & 1) != 0);
   2.129 +        if (visited == sub) {
   2.130 +          if (visited_twice_already) {
   2.131 +            // Visited 2 paths, but still stuck in loop body.  Give up.
   2.132 +            return false;
   2.133            }
   2.134 -        }
   2.135 -        if (j >= 0 && (ni & 1) != 0) {
   2.136 -          result = false; // Visited 2 paths. Give up.
   2.137 -          break;
   2.138 -        }
   2.139 -        // The Region node was not visited before.
   2.140 -      }
   2.141 -      for (; i < sub->req(); i++) {
   2.142 -        Node* in = sub->in(i);
   2.143 -        if (in != NULL && !in->is_top() && in != sub) {
   2.144 +          // The Region node was visited before only once.
   2.145 +          // (We will repush with the low bit set, below.)
   2.146 +          nlist.remove(j);
   2.147 +          // We will find a new edge and re-insert.
   2.148 +          region_was_visited_before = true;
   2.149            break;
   2.150          }
   2.151        }
   2.152 -      if (i < sub->req()) {
   2.153 -        up = sub->in(i);
   2.154 -        if (region_was_visited_before && sub != up) {
   2.155 -          // Set 0 bit to indicate that both paths were taken.
   2.156 -          nlist.push((Node*)((intptr_t)sub + 1));
   2.157 -        } else {
   2.158 -          nlist.push(sub);
   2.159 +
   2.160 +      // Find an incoming edge which has not been seen yet; walk through it.
   2.161 +      assert(up == sub, "");
   2.162 +      uint skip = region_was_visited_before ? 1 : 0;
   2.163 +      for (uint i = 1; i < sub->req(); i++) {
   2.164 +        Node* in = sub->in(i);
   2.165 +        if (in != NULL && !in->is_top() && in != sub) {
   2.166 +          if (skip == 0) {
   2.167 +            up = in;
   2.168 +            break;
   2.169 +          }
   2.170 +          --skip;               // skip this nontrivial input
   2.171          }
   2.172        }
   2.173 +
   2.174 +      // Set 0 bit to indicate that both paths were taken.
   2.175 +      nlist.push((Node*)((intptr_t)sub + (region_was_visited_before ? 1 : 0)));
   2.176      }
   2.177 -    if (sub == up) {
   2.178 -      result = false;    // some kind of tight cycle
   2.179 -      break;
   2.180 +
   2.181 +    if (up == sub) {
   2.182 +      break;    // some kind of tight cycle
   2.183 +    }
   2.184 +    if (up == orig_sub && met_dom) {
   2.185 +      // returned back after visiting 'dom'
   2.186 +      break;    // some kind of cycle
   2.187      }
   2.188      if (--iterations_without_region_limit < 0) {
   2.189 -      result = false;    // dead cycle
   2.190 -      break;
   2.191 +      break;    // dead cycle
   2.192      }
   2.193      sub = up;
   2.194    }
   2.195 -  return result;
   2.196 +
   2.197 +  // Did not meet Root or Start node in pred. chain.
   2.198 +  // Conservative answer for dead code.
   2.199 +  return false;
   2.200  }
   2.201  
   2.202  //------------------------------remove_dead_region-----------------------------