1 /*

     2  * Copyright (c) 2014, 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 "opto/cfgnode.hpp"

    27 #include "opto/phaseX.hpp"

    28 #include "opto/replacednodes.hpp"

    29 

    30 void ReplacedNodes::allocate_if_necessary() {

    31   if (_replaced_nodes == NULL) {

    32     _replaced_nodes = new GrowableArray<ReplacedNode>();

    33   }

    34 }

    35 

    36 bool ReplacedNodes::is_empty() const {

    37   return _replaced_nodes == NULL || _replaced_nodes->length() == 0;

    38 }

    39 

    40 bool ReplacedNodes::has_node(const ReplacedNode& r) const {

    41   return _replaced_nodes->find(r) != -1;

    42 }

    43 

    44 bool ReplacedNodes::has_target_node(Node* n) const {

    45   for (int i = 0; i < _replaced_nodes->length(); i++) {

    46     if (_replaced_nodes->at(i).improved() == n) {

    47       return true;

    48     }

    49   }

    50   return false;

    51 }

    52 

    53 // Record replaced node if not seen before

    54 void ReplacedNodes::record(Node* initial, Node* improved) {

    55   allocate_if_necessary();

    56   ReplacedNode r(initial, improved);

    57   if (!has_node(r)) {

    58     _replaced_nodes->push(r);

    59   }

    60 }

    61 

    62 // Copy replaced nodes from one map to another. idx is used to

    63 // identify nodes that are too new to be of interest in the target

    64 // node list.

    65 void ReplacedNodes::transfer_from(const ReplacedNodes& other, uint idx) {

    66   if (other.is_empty()) {

    67     return;

    68   }

    69   allocate_if_necessary();

    70   for (int i = 0; i < other._replaced_nodes->length(); i++) {

    71     ReplacedNode replaced = other._replaced_nodes->at(i);

    72     // Only transfer the nodes that can actually be useful

    73     if (!has_node(replaced) && (replaced.initial()->_idx < idx || has_target_node(replaced.initial()))) {

    74       _replaced_nodes->push(replaced);

    75     }

    76   }

    77 }

    78 

    79 void ReplacedNodes::clone() {

    80   if (_replaced_nodes != NULL) {

    81     GrowableArray<ReplacedNode>* replaced_nodes_clone = new GrowableArray<ReplacedNode>();

    82     replaced_nodes_clone->appendAll(_replaced_nodes);

    83     _replaced_nodes = replaced_nodes_clone;

    84   }

    85 }

    86 

    87 void ReplacedNodes::reset() {

    88   if (_replaced_nodes != NULL) {

    89     _replaced_nodes->clear();

    90   }

    91 }

    92 

    93 // Perfom node replacement (used when returning to caller)

    94 void ReplacedNodes::apply(Node* n) {

    95   if (is_empty()) {

    96     return;

    97   }

    98   for (int i = 0; i < _replaced_nodes->length(); i++) {

    99     ReplacedNode replaced = _replaced_nodes->at(i);

   100     n->replace_edge(replaced.initial(), replaced.improved());

   101   }

   102 }

   103 

   104 static void enqueue_use(Node* n, Node* use, Unique_Node_List& work) {

   105   if (use->is_Phi()) {

   106     Node* r = use->in(0);

   107     assert(r->is_Region(), "Phi should have Region");

   108     for (uint i = 1; i < use->req(); i++) {

   109       if (use->in(i) == n) {

   110         work.push(r->in(i));

   111       }

   112     }

   113   } else {

   114     work.push(use);

   115   }

   116 }

   117 

   118 // Perfom node replacement following late inlining

   119 void ReplacedNodes::apply(Compile* C, Node* ctl) {

   120   // ctl is the control on exit of the method that was late inlined

   121   if (is_empty()) {

   122     return;

   123   }

   124   for (int i = 0; i < _replaced_nodes->length(); i++) {

   125     ReplacedNode replaced = _replaced_nodes->at(i);

   126     Node* initial = replaced.initial();

   127     Node* improved = replaced.improved();

   128     assert (ctl != NULL && !ctl->is_top(), "replaced node should have actual control");

   129 

   130     ResourceMark rm;

   131     Unique_Node_List work;

   132     // Go over all the uses of the node that is considered for replacement...

   133     for (DUIterator j = initial->outs(); initial->has_out(j); j++) {

   134       Node* use = initial->out(j);

   135 

   136       if (use == improved || use->outcnt() == 0) {

   137         continue;

   138       }

   139       work.clear();

   140       enqueue_use(initial, use, work);

   141       bool replace = true;

   142       // Check that this use is dominated by ctl. Go ahead with the

   143       // replacement if it is.

   144       while (work.size() != 0 && replace) {

   145         Node* n = work.pop();

   146         if (use->outcnt() == 0) {

   147           continue;

   148         }

   149         if (n->is_CFG() || (n->in(0) != NULL && !n->in(0)->is_top())) {

   150           int depth = 0;

   151           Node *m = n;

   152           if (!n->is_CFG()) {

   153             n = n->in(0);

   154           }

   155           assert(n->is_CFG(), "should be CFG now");

   156           while(n != ctl) {

   157             n = IfNode::up_one_dom(n);

   158             depth++;

   159             // limit search depth

   160             if (depth >= 100 || n == NULL) {

   161               replace = false;

   162               break;

   163             }

   164           }

   165         } else {

   166           for (DUIterator k = n->outs(); n->has_out(k); k++) {

   167             enqueue_use(n, n->out(k), work);

   168           }

   169         }

   170       }

   171       if (replace) {

   172         bool is_in_table = C->initial_gvn()->hash_delete(use);

   173         int replaced = use->replace_edge(initial, improved);

   174         if (is_in_table) {

   175           C->initial_gvn()->hash_find_insert(use);

   176         }

   177         C->record_for_igvn(use);

   178 

   179         assert(replaced > 0, "inconsistent");

   180         --j;

   181       }

   182     }

   183   }

   184 }

   185 

   186 void ReplacedNodes::dump(outputStream *st) const {

   187   if (!is_empty()) {

   188     tty->print("replaced nodes: ");

   189     for (int i = 0; i < _replaced_nodes->length(); i++) {

   190       tty->print("%d->%d", _replaced_nodes->at(i).initial()->_idx, _replaced_nodes->at(i).improved()->_idx);

   191       if (i < _replaced_nodes->length()-1) {

   192         tty->print(",");

   193       }

   194     }

   195   }

   196 }

   197 

   198 // Merge 2 list of replaced node at a point where control flow paths merge

   199 void ReplacedNodes::merge_with(const ReplacedNodes& other) {

   200   if (is_empty()) {

   201     return;

   202   }

   203   if (other.is_empty()) {

   204     reset();

   205     return;

   206   }

   207   int shift = 0;

   208   int len = _replaced_nodes->length();

   209   for (int i = 0; i < len; i++) {

   210     if (!other.has_node(_replaced_nodes->at(i))) {

   211       shift++;

   212     } else if (shift > 0) {

   213       _replaced_nodes->at_put(i-shift, _replaced_nodes->at(i));

   214     }

   215   }

   216   if (shift > 0) {

   217     _replaced_nodes->trunc_to(len - shift);

   218   }

   219 }