1 /*
   2  * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "memory/resourceArea.hpp"
  27 #include "opto/cfgnode.hpp"
  28 #include "opto/phaseX.hpp"
  29 #include "opto/replacednodes.hpp"
  30 
  31 void ReplacedNodes::allocate_if_necessary() {
  32   if (_replaced_nodes == NULL) {
  33     _replaced_nodes = new GrowableArray<ReplacedNode>();
  34   }
  35 }
  36 
  37 bool ReplacedNodes::is_empty() const {
  38   return _replaced_nodes == NULL || _replaced_nodes->length() == 0;
  39 }
  40 
  41 bool ReplacedNodes::has_node(const ReplacedNode& r) const {
  42   return _replaced_nodes->find(r) != -1;
  43 }
  44 
  45 bool ReplacedNodes::has_target_node(Node* n) const {
  46   for (int i = 0; i < _replaced_nodes->length(); i++) {
  47     if (_replaced_nodes->at(i).improved() == n) {
  48       return true;
  49     }
  50   }
  51   return false;
  52 }
  53 
  54 // Record replaced node if not seen before
  55 void ReplacedNodes::record(Node* initial, Node* improved) {
  56   allocate_if_necessary();
  57   ReplacedNode r(initial, improved);
  58   if (!has_node(r)) {
  59     _replaced_nodes->push(r);
  60   }
  61 }
  62 
  63 // Copy replaced nodes from one map to another. idx is used to
  64 // identify nodes that are too new to be of interest in the target
  65 // node list.
  66 void ReplacedNodes::transfer_from(const ReplacedNodes& other, uint idx) {
  67   if (other.is_empty()) {
  68     return;
  69   }
  70   allocate_if_necessary();
  71   for (int i = 0; i < other._replaced_nodes->length(); i++) {
  72     ReplacedNode replaced = other._replaced_nodes->at(i);
  73     // Only transfer the nodes that can actually be useful
  74     if (!has_node(replaced) && (replaced.initial()->_idx < idx || has_target_node(replaced.initial()))) {
  75       _replaced_nodes->push(replaced);
  76     }
  77   }
  78 }
  79 
  80 void ReplacedNodes::clone() {
  81   if (_replaced_nodes != NULL) {
  82     GrowableArray<ReplacedNode>* replaced_nodes_clone = new GrowableArray<ReplacedNode>();
  83     replaced_nodes_clone->appendAll(_replaced_nodes);
  84     _replaced_nodes = replaced_nodes_clone;
  85   }
  86 }
  87 
  88 void ReplacedNodes::reset() {
  89   if (_replaced_nodes != NULL) {
  90     _replaced_nodes->clear();
  91   }
  92 }
  93 
  94 // Perfom node replacement (used when returning to caller)
  95 void ReplacedNodes::apply(Node* n) {
  96   if (is_empty()) {
  97     return;
  98   }
  99   for (int i = 0; i < _replaced_nodes->length(); i++) {
 100     ReplacedNode replaced = _replaced_nodes->at(i);
 101     n->replace_edge(replaced.initial(), replaced.improved());
 102   }
 103 }
 104 
 105 static void enqueue_use(Node* n, Node* use, Unique_Node_List& work) {
 106   if (use->is_Phi()) {
 107     Node* r = use->in(0);
 108     assert(r->is_Region(), "Phi should have Region");
 109     for (uint i = 1; i < use->req(); i++) {
 110       if (use->in(i) == n) {
 111         work.push(r->in(i));
 112       }
 113     }
 114   } else {
 115     work.push(use);
 116   }
 117 }
 118 
 119 // Perfom node replacement following late inlining
 120 void ReplacedNodes::apply(Compile* C, Node* ctl) {
 121   // ctl is the control on exit of the method that was late inlined
 122   if (is_empty()) {
 123     return;
 124   }
 125   for (int i = 0; i < _replaced_nodes->length(); i++) {
 126     ReplacedNode replaced = _replaced_nodes->at(i);
 127     Node* initial = replaced.initial();
 128     Node* improved = replaced.improved();
 129     assert (ctl != NULL && !ctl->is_top(), "replaced node should have actual control");
 130 
 131     ResourceMark rm;
 132     Unique_Node_List work;
 133     // Go over all the uses of the node that is considered for replacement...
 134     for (DUIterator j = initial->outs(); initial->has_out(j); j++) {
 135       Node* use = initial->out(j);
 136 
 137       if (use == improved || use->outcnt() == 0) {
 138         continue;
 139       }
 140       work.clear();
 141       enqueue_use(initial, use, work);
 142       bool replace = true;
 143       // Check that this use is dominated by ctl. Go ahead with the
 144       // replacement if it is.
 145       while (work.size() != 0 && replace) {
 146         Node* n = work.pop();
 147         if (use->outcnt() == 0) {
 148           continue;
 149         }
 150         if (n->is_CFG() || (n->in(0) != NULL && !n->in(0)->is_top())) {
 151           int depth = 0;
 152           Node *m = n;
 153           if (!n->is_CFG()) {
 154             n = n->in(0);
 155           }
 156           assert(n->is_CFG(), "should be CFG now");
 157           while(n != ctl) {
 158             n = IfNode::up_one_dom(n);
 159             depth++;
 160             // limit search depth
 161             if (depth >= 100 || n == NULL) {
 162               replace = false;
 163               break;
 164             }
 165           }
 166         } else {
 167           for (DUIterator k = n->outs(); n->has_out(k); k++) {
 168             enqueue_use(n, n->out(k), work);
 169           }
 170         }
 171       }
 172       if (replace) {
 173         bool is_in_table = C->initial_gvn()->hash_delete(use);
 174         int replaced = use->replace_edge(initial, improved);
 175         if (is_in_table) {
 176           C->initial_gvn()->hash_find_insert(use);
 177         }
 178         C->record_for_igvn(use);
 179 
 180         assert(replaced > 0, "inconsistent");
 181         --j;
 182       }
 183     }
 184   }
 185 }
 186 
 187 void ReplacedNodes::dump(outputStream *st) const {
 188   if (!is_empty()) {
 189     st->print("replaced nodes: ");
 190     for (int i = 0; i < _replaced_nodes->length(); i++) {
 191       st->print("%d->%d", _replaced_nodes->at(i).initial()->_idx, _replaced_nodes->at(i).improved()->_idx);
 192       if (i < _replaced_nodes->length()-1) {
 193         st->print(",");
 194       }
 195     }
 196   }
 197 }
 198 
 199 // Merge 2 list of replaced node at a point where control flow paths merge
 200 void ReplacedNodes::merge_with(const ReplacedNodes& other) {
 201   if (is_empty()) {
 202     return;
 203   }
 204   if (other.is_empty()) {
 205     reset();
 206     return;
 207   }
 208   int shift = 0;
 209   int len = _replaced_nodes->length();
 210   for (int i = 0; i < len; i++) {
 211     if (!other.has_node(_replaced_nodes->at(i))) {
 212       shift++;
 213     } else if (shift > 0) {
 214       _replaced_nodes->at_put(i-shift, _replaced_nodes->at(i));
 215     }
 216   }
 217   if (shift > 0) {
 218     _replaced_nodes->trunc_to(len - shift);
 219   }
 220 }