Fri, 12 Feb 2010 15:27:36 -0800
Merge
duke@435 | 1 | /* |
xdono@631 | 2 | * Copyright 2006-2008 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | #include "incls/_precompiled.incl" |
duke@435 | 26 | #include "incls/_loopUnswitch.cpp.incl" |
duke@435 | 27 | |
duke@435 | 28 | //================= Loop Unswitching ===================== |
duke@435 | 29 | // |
duke@435 | 30 | // orig: transformed: |
duke@435 | 31 | // if (invariant-test) then |
duke@435 | 32 | // loop loop |
duke@435 | 33 | // stmt1 stmt1 |
duke@435 | 34 | // if (invariant-test) then stmt2 |
duke@435 | 35 | // stmt2 stmt4 |
duke@435 | 36 | // else endloop |
duke@435 | 37 | // stmt3 else |
duke@435 | 38 | // endif loop [clone] |
duke@435 | 39 | // stmt4 stmt1 [clone] |
duke@435 | 40 | // endloop stmt3 |
duke@435 | 41 | // stmt4 [clone] |
duke@435 | 42 | // endloop |
duke@435 | 43 | // endif |
duke@435 | 44 | // |
duke@435 | 45 | // Note: the "else" clause may be empty |
duke@435 | 46 | |
duke@435 | 47 | //------------------------------policy_unswitching----------------------------- |
duke@435 | 48 | // Return TRUE or FALSE if the loop should be unswitched |
duke@435 | 49 | // (ie. clone loop with an invariant test that does not exit the loop) |
duke@435 | 50 | bool IdealLoopTree::policy_unswitching( PhaseIdealLoop *phase ) const { |
duke@435 | 51 | if( !LoopUnswitching ) { |
duke@435 | 52 | return false; |
duke@435 | 53 | } |
rasbold@543 | 54 | if (!_head->is_Loop()) { |
rasbold@543 | 55 | return false; |
rasbold@543 | 56 | } |
duke@435 | 57 | uint nodes_left = MaxNodeLimit - phase->C->unique(); |
duke@435 | 58 | if (2 * _body.size() > nodes_left) { |
duke@435 | 59 | return false; // Too speculative if running low on nodes. |
duke@435 | 60 | } |
duke@435 | 61 | LoopNode* head = _head->as_Loop(); |
duke@435 | 62 | if (head->unswitch_count() + 1 > head->unswitch_max()) { |
duke@435 | 63 | return false; |
duke@435 | 64 | } |
duke@435 | 65 | return phase->find_unswitching_candidate(this) != NULL; |
duke@435 | 66 | } |
duke@435 | 67 | |
duke@435 | 68 | //------------------------------find_unswitching_candidate----------------------------- |
duke@435 | 69 | // Find candidate "if" for unswitching |
duke@435 | 70 | IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop) const { |
duke@435 | 71 | |
duke@435 | 72 | // Find first invariant test that doesn't exit the loop |
duke@435 | 73 | LoopNode *head = loop->_head->as_Loop(); |
duke@435 | 74 | IfNode* unswitch_iff = NULL; |
duke@435 | 75 | Node* n = head->in(LoopNode::LoopBackControl); |
duke@435 | 76 | while (n != head) { |
duke@435 | 77 | Node* n_dom = idom(n); |
duke@435 | 78 | if (n->is_Region()) { |
duke@435 | 79 | if (n_dom->is_If()) { |
duke@435 | 80 | IfNode* iff = n_dom->as_If(); |
duke@435 | 81 | if (iff->in(1)->is_Bool()) { |
duke@435 | 82 | BoolNode* bol = iff->in(1)->as_Bool(); |
duke@435 | 83 | if (bol->in(1)->is_Cmp()) { |
duke@435 | 84 | // If condition is invariant and not a loop exit, |
duke@435 | 85 | // then found reason to unswitch. |
duke@435 | 86 | if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) { |
duke@435 | 87 | unswitch_iff = iff; |
duke@435 | 88 | } |
duke@435 | 89 | } |
duke@435 | 90 | } |
duke@435 | 91 | } |
duke@435 | 92 | } |
duke@435 | 93 | n = n_dom; |
duke@435 | 94 | } |
duke@435 | 95 | return unswitch_iff; |
duke@435 | 96 | } |
duke@435 | 97 | |
duke@435 | 98 | //------------------------------do_unswitching----------------------------- |
duke@435 | 99 | // Clone loop with an invariant test (that does not exit) and |
duke@435 | 100 | // insert a clone of the test that selects which version to |
duke@435 | 101 | // execute. |
duke@435 | 102 | void PhaseIdealLoop::do_unswitching (IdealLoopTree *loop, Node_List &old_new) { |
duke@435 | 103 | |
duke@435 | 104 | // Find first invariant test that doesn't exit the loop |
duke@435 | 105 | LoopNode *head = loop->_head->as_Loop(); |
duke@435 | 106 | |
duke@435 | 107 | IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop); |
duke@435 | 108 | assert(unswitch_iff != NULL, "should be at least one"); |
duke@435 | 109 | |
duke@435 | 110 | // Need to revert back to normal loop |
duke@435 | 111 | if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) { |
duke@435 | 112 | head->as_CountedLoop()->set_normal_loop(); |
duke@435 | 113 | } |
duke@435 | 114 | |
duke@435 | 115 | ProjNode* proj_true = create_slow_version_of_loop(loop, old_new); |
duke@435 | 116 | |
duke@435 | 117 | assert(proj_true->is_IfTrue() && proj_true->unique_ctrl_out() == head, "by construction"); |
duke@435 | 118 | |
duke@435 | 119 | // Increment unswitch count |
duke@435 | 120 | LoopNode* head_clone = old_new[head->_idx]->as_Loop(); |
duke@435 | 121 | int nct = head->unswitch_count() + 1; |
duke@435 | 122 | head->set_unswitch_count(nct); |
duke@435 | 123 | head_clone->set_unswitch_count(nct); |
duke@435 | 124 | |
duke@435 | 125 | // Add test to new "if" outside of loop |
duke@435 | 126 | IfNode* invar_iff = proj_true->in(0)->as_If(); |
duke@435 | 127 | Node* invar_iff_c = invar_iff->in(0); |
duke@435 | 128 | BoolNode* bol = unswitch_iff->in(1)->as_Bool(); |
duke@435 | 129 | invar_iff->set_req(1, bol); |
duke@435 | 130 | invar_iff->_prob = unswitch_iff->_prob; |
duke@435 | 131 | |
duke@435 | 132 | ProjNode* proj_false = invar_iff->proj_out(0)->as_Proj(); |
duke@435 | 133 | |
twisti@1040 | 134 | // Hoist invariant casts out of each loop to the appropriate |
duke@435 | 135 | // control projection. |
duke@435 | 136 | |
duke@435 | 137 | Node_List worklist; |
duke@435 | 138 | |
duke@435 | 139 | for (DUIterator_Fast imax, i = unswitch_iff->fast_outs(imax); i < imax; i++) { |
duke@435 | 140 | ProjNode* proj= unswitch_iff->fast_out(i)->as_Proj(); |
duke@435 | 141 | // Copy to a worklist for easier manipulation |
duke@435 | 142 | for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) { |
duke@435 | 143 | Node* use = proj->fast_out(j); |
duke@435 | 144 | if (use->Opcode() == Op_CheckCastPP && loop->is_invariant(use->in(1))) { |
duke@435 | 145 | worklist.push(use); |
duke@435 | 146 | } |
duke@435 | 147 | } |
duke@435 | 148 | ProjNode* invar_proj = invar_iff->proj_out(proj->_con)->as_Proj(); |
duke@435 | 149 | while (worklist.size() > 0) { |
duke@435 | 150 | Node* use = worklist.pop(); |
duke@435 | 151 | Node* nuse = use->clone(); |
duke@435 | 152 | nuse->set_req(0, invar_proj); |
duke@435 | 153 | _igvn.hash_delete(use); |
duke@435 | 154 | use->set_req(1, nuse); |
duke@435 | 155 | _igvn._worklist.push(use); |
duke@435 | 156 | register_new_node(nuse, invar_proj); |
duke@435 | 157 | // Same for the clone |
duke@435 | 158 | Node* use_clone = old_new[use->_idx]; |
duke@435 | 159 | _igvn.hash_delete(use_clone); |
duke@435 | 160 | use_clone->set_req(1, nuse); |
duke@435 | 161 | _igvn._worklist.push(use_clone); |
duke@435 | 162 | } |
duke@435 | 163 | } |
duke@435 | 164 | |
duke@435 | 165 | // Hardwire the control paths in the loops into if(true) and if(false) |
duke@435 | 166 | _igvn.hash_delete(unswitch_iff); |
duke@435 | 167 | short_circuit_if(unswitch_iff, proj_true); |
duke@435 | 168 | _igvn._worklist.push(unswitch_iff); |
duke@435 | 169 | |
duke@435 | 170 | IfNode* unswitch_iff_clone = old_new[unswitch_iff->_idx]->as_If(); |
duke@435 | 171 | _igvn.hash_delete(unswitch_iff_clone); |
duke@435 | 172 | short_circuit_if(unswitch_iff_clone, proj_false); |
duke@435 | 173 | _igvn._worklist.push(unswitch_iff_clone); |
duke@435 | 174 | |
duke@435 | 175 | // Reoptimize loops |
duke@435 | 176 | loop->record_for_igvn(); |
duke@435 | 177 | for(int i = loop->_body.size() - 1; i >= 0 ; i--) { |
duke@435 | 178 | Node *n = loop->_body[i]; |
duke@435 | 179 | Node *n_clone = old_new[n->_idx]; |
duke@435 | 180 | _igvn._worklist.push(n_clone); |
duke@435 | 181 | } |
duke@435 | 182 | |
duke@435 | 183 | #ifndef PRODUCT |
duke@435 | 184 | if (TraceLoopUnswitching) { |
duke@435 | 185 | tty->print_cr("Loop unswitching orig: %d @ %d new: %d @ %d", |
duke@435 | 186 | head->_idx, unswitch_iff->_idx, |
duke@435 | 187 | old_new[head->_idx]->_idx, unswitch_iff_clone->_idx); |
duke@435 | 188 | } |
duke@435 | 189 | #endif |
duke@435 | 190 | |
duke@435 | 191 | C->set_major_progress(); |
duke@435 | 192 | } |
duke@435 | 193 | |
duke@435 | 194 | //-------------------------create_slow_version_of_loop------------------------ |
duke@435 | 195 | // Create a slow version of the loop by cloning the loop |
duke@435 | 196 | // and inserting an if to select fast-slow versions. |
duke@435 | 197 | // Return control projection of the entry to the fast version. |
duke@435 | 198 | ProjNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop, |
duke@435 | 199 | Node_List &old_new) { |
duke@435 | 200 | LoopNode* head = loop->_head->as_Loop(); |
duke@435 | 201 | Node* entry = head->in(LoopNode::EntryControl); |
duke@435 | 202 | _igvn.hash_delete(entry); |
duke@435 | 203 | _igvn._worklist.push(entry); |
duke@435 | 204 | IdealLoopTree* outer_loop = loop->_parent; |
duke@435 | 205 | |
duke@435 | 206 | Node *cont = _igvn.intcon(1); |
duke@435 | 207 | set_ctrl(cont, C->root()); |
kvn@651 | 208 | Node* opq = new (C, 2) Opaque1Node(C, cont); |
duke@435 | 209 | register_node(opq, outer_loop, entry, dom_depth(entry)); |
duke@435 | 210 | Node *bol = new (C, 2) Conv2BNode(opq); |
duke@435 | 211 | register_node(bol, outer_loop, entry, dom_depth(entry)); |
duke@435 | 212 | IfNode* iff = new (C, 2) IfNode(entry, bol, PROB_MAX, COUNT_UNKNOWN); |
duke@435 | 213 | register_node(iff, outer_loop, entry, dom_depth(entry)); |
duke@435 | 214 | ProjNode* iffast = new (C, 1) IfTrueNode(iff); |
duke@435 | 215 | register_node(iffast, outer_loop, iff, dom_depth(iff)); |
duke@435 | 216 | ProjNode* ifslow = new (C, 1) IfFalseNode(iff); |
duke@435 | 217 | register_node(ifslow, outer_loop, iff, dom_depth(iff)); |
duke@435 | 218 | |
duke@435 | 219 | // Clone the loop body. The clone becomes the fast loop. The |
duke@435 | 220 | // original pre-header will (illegally) have 2 control users (old & new loops). |
duke@435 | 221 | clone_loop(loop, old_new, dom_depth(head), iff); |
duke@435 | 222 | assert(old_new[head->_idx]->is_Loop(), "" ); |
duke@435 | 223 | |
duke@435 | 224 | // Fast (true) control |
duke@435 | 225 | _igvn.hash_delete(head); |
duke@435 | 226 | head->set_req(LoopNode::EntryControl, iffast); |
duke@435 | 227 | set_idom(head, iffast, dom_depth(head)); |
duke@435 | 228 | _igvn._worklist.push(head); |
duke@435 | 229 | |
duke@435 | 230 | // Slow (false) control |
duke@435 | 231 | LoopNode* slow_head = old_new[head->_idx]->as_Loop(); |
duke@435 | 232 | _igvn.hash_delete(slow_head); |
duke@435 | 233 | slow_head->set_req(LoopNode::EntryControl, ifslow); |
duke@435 | 234 | set_idom(slow_head, ifslow, dom_depth(slow_head)); |
duke@435 | 235 | _igvn._worklist.push(slow_head); |
duke@435 | 236 | |
duke@435 | 237 | recompute_dom_depth(); |
duke@435 | 238 | |
duke@435 | 239 | return iffast; |
duke@435 | 240 | } |