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, uint idx) {
  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     // Only apply if improved node was created in a callee to avoid
 102     // issues with irreducible loops in the caller
 103     if (replaced.improved()->_idx >= idx) {
 104       n->replace_edge(replaced.initial(), replaced.improved());
 105     }
 106   }
 107 }
 108 
 109 static void enqueue_use(Node* n, Node* use, Unique_Node_List& work) {
 110   if (use->is_Phi()) {
 111     Node* r = use->in(0);
 112     assert(r->is_Region(), "Phi should have Region");
 113     for (uint i = 1; i < use->req(); i++) {
 114       if (use->in(i) == n) {
 115         work.push(r->in(i));
 116       }
 117     }
 118   } else {
 119     work.push(use);
 120   }
 121 }
 122 
 123 // Perfom node replacement following late inlining
 124 void ReplacedNodes::apply(Compile* C, Node* ctl) {
 125   // ctl is the control on exit of the method that was late inlined
 126   if (is_empty()) {
 127     return;
 128   }
 129   for (int i = 0; i < _replaced_nodes->length(); i++) {
 130     ReplacedNode replaced = _replaced_nodes->at(i);
 131     Node* initial = replaced.initial();
 132     Node* improved = replaced.improved();
 133     assert (ctl != NULL && !ctl->is_top(), "replaced node should have actual control");
 134 
 135     ResourceMark rm;
 136     Unique_Node_List work;
 137     // Go over all the uses of the node that is considered for replacement...
 138     for (DUIterator j = initial->outs(); initial->has_out(j); j++) {
 139       Node* use = initial->out(j);
 140 
 141       if (use == improved || use->outcnt() == 0) {
 142         continue;
 143       }
 144       work.clear();
 145       enqueue_use(initial, use, work);
 146       bool replace = true;
 147       // Check that this use is dominated by ctl. Go ahead with the
 148       // replacement if it is.
 149       while (work.size() != 0 && replace) {
 150         Node* n = work.pop();
 151         if (use->outcnt() == 0) {
 152           continue;
 153         }
 154         if (n->is_CFG() || (n->in(0) != NULL && !n->in(0)->is_top())) {
 155           int depth = 0;
 156           Node *m = n;
 157           if (!n->is_CFG()) {
 158             n = n->in(0);
 159           }
 160           assert(n->is_CFG(), "should be CFG now");
 161           while(n != ctl) {
 162             n = IfNode::up_one_dom(n);
 163             depth++;
 164             // limit search depth
 165             if (depth >= 100 || n == NULL) {
 166               replace = false;
 167               break;
 168             }
 169           }
 170         } else {
 171           for (DUIterator k = n->outs(); n->has_out(k); k++) {
 172             enqueue_use(n, n->out(k), work);
 173           }
 174         }
 175       }
 176       if (replace) {
 177         bool is_in_table = C->initial_gvn()->hash_delete(use);
 178         int replaced = use->replace_edge(initial, improved);
 179         if (is_in_table) {
 180           C->initial_gvn()->hash_find_insert(use);
 181         }
 182         C->record_for_igvn(use);
 183 
 184         assert(replaced > 0, "inconsistent");
 185         --j;
 186       }
 187     }
 188   }
 189 }
 190 
 191 void ReplacedNodes::dump(outputStream *st) const {
 192   if (!is_empty()) {
 193     st->print("replaced nodes: ");
 194     for (int i = 0; i < _replaced_nodes->length(); i++) {
 195       st->print("%d->%d", _replaced_nodes->at(i).initial()->_idx, _replaced_nodes->at(i).improved()->_idx);
 196       if (i < _replaced_nodes->length()-1) {
 197         st->print(",");
 198       }
 199     }
 200   }
 201 }
 202 
 203 // Merge 2 list of replaced node at a point where control flow paths merge
 204 void ReplacedNodes::merge_with(const ReplacedNodes& other) {
 205   if (is_empty()) {
 206     return;
 207   }
 208   if (other.is_empty()) {
 209     reset();
 210     return;
 211   }
 212   int shift = 0;
 213   int len = _replaced_nodes->length();
 214   for (int i = 0; i < len; i++) {
 215     if (!other.has_node(_replaced_nodes->at(i))) {
 216       shift++;
 217     } else if (shift > 0) {
 218       _replaced_nodes->at_put(i-shift, _replaced_nodes->at(i));
 219     }
 220   }
 221   if (shift > 0) {
 222     _replaced_nodes->trunc_to(len - shift);
 223   }
 224 }