Mercurial > hg > truffle
annotate src/share/vm/opto/coalesce.cpp @ 17716:cdb71841f4bc
6498581: ThreadInterruptTest3 produces wrong output on Windows
Summary: There is race condition between os::interrupt and os::is_interrupted on Windows. In JVM_Sleep(Thread.sleep), check if thread gets interrupted, it may see interrupted but not really interrupted so cause spurious waking up (early return from sleep). Fix by checking if interrupt event really gets set thus prevent false return. For intrinsic of _isInterrupted, on Windows, go fastpath only on bit not set.
Reviewed-by: acorn, kvn
Contributed-by: david.holmes@oracle.com, yumin.qi@oracle.com
author | minqi |
---|---|
date | Wed, 26 Feb 2014 15:20:41 -0800 |
parents | 4b078f877b56 |
children | 04e7587c97dc b8e2e616c1e9 |
rev | line source |
---|---|
0 | 1 /* |
10999
693e4d04fd09
8014959: assert(Compile::current()->live_nodes() < (uint)MaxNodeLimit) failed: Live Node limit exceeded limit
drchase
parents:
10111
diff
changeset
|
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 25 #include "precompiled.hpp" |
26 #include "memory/allocation.inline.hpp" | |
27 #include "opto/block.hpp" | |
28 #include "opto/cfgnode.hpp" | |
29 #include "opto/chaitin.hpp" | |
30 #include "opto/coalesce.hpp" | |
31 #include "opto/connode.hpp" | |
32 #include "opto/indexSet.hpp" | |
33 #include "opto/machnode.hpp" | |
34 #include "opto/matcher.hpp" | |
35 #include "opto/regmask.hpp" | |
0 | 36 |
37 #ifndef PRODUCT | |
10111 | 38 void PhaseCoalesce::dump(Node *n) const { |
0 | 39 // Being a const function means I cannot use 'Find' |
10111 | 40 uint r = _phc._lrg_map.find(n); |
0 | 41 tty->print("L%d/N%d ",r,n->_idx); |
42 } | |
43 | |
44 void PhaseCoalesce::dump() const { | |
45 // I know I have a block layout now, so I can print blocks in a loop | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
46 for( uint i=0; i<_phc._cfg.number_of_blocks(); i++ ) { |
0 | 47 uint j; |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
48 Block* b = _phc._cfg.get_block(i); |
0 | 49 // Print a nice block header |
50 tty->print("B%d: ",b->_pre_order); | |
51 for( j=1; j<b->num_preds(); j++ ) | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
52 tty->print("B%d ", _phc._cfg.get_block_for_node(b->pred(j))->_pre_order); |
0 | 53 tty->print("-> "); |
54 for( j=0; j<b->_num_succs; j++ ) | |
55 tty->print("B%d ",b->_succs[j]->_pre_order); | |
56 tty->print(" IDom: B%d/#%d\n", b->_idom ? b->_idom->_pre_order : 0, b->_dom_depth); | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
57 uint cnt = b->number_of_nodes(); |
0 | 58 for( j=0; j<cnt; j++ ) { |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
59 Node *n = b->get_node(j); |
0 | 60 dump( n ); |
61 tty->print("\t%s\t",n->Name()); | |
62 | |
63 // Dump the inputs | |
64 uint k; // Exit value of loop | |
65 for( k=0; k<n->req(); k++ ) // For all required inputs | |
66 if( n->in(k) ) dump( n->in(k) ); | |
67 else tty->print("_ "); | |
68 int any_prec = 0; | |
69 for( ; k<n->len(); k++ ) // For all precedence inputs | |
70 if( n->in(k) ) { | |
71 if( !any_prec++ ) tty->print(" |"); | |
72 dump( n->in(k) ); | |
73 } | |
74 | |
75 // Dump node-specific info | |
76 n->dump_spec(tty); | |
77 tty->print("\n"); | |
78 | |
79 } | |
80 tty->print("\n"); | |
81 } | |
82 } | |
83 #endif | |
84 | |
85 // Combine the live ranges def'd by these 2 Nodes. N2 is an input to N1. | |
10111 | 86 void PhaseCoalesce::combine_these_two(Node *n1, Node *n2) { |
87 uint lr1 = _phc._lrg_map.find(n1); | |
88 uint lr2 = _phc._lrg_map.find(n2); | |
0 | 89 if( lr1 != lr2 && // Different live ranges already AND |
90 !_phc._ifg->test_edge_sq( lr1, lr2 ) ) { // Do not interfere | |
91 LRG *lrg1 = &_phc.lrgs(lr1); | |
92 LRG *lrg2 = &_phc.lrgs(lr2); | |
93 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK. | |
94 | |
95 // Now, why is int->oop OK? We end up declaring a raw-pointer as an oop | |
96 // and in general that's a bad thing. However, int->oop conversions only | |
97 // happen at GC points, so the lifetime of the misclassified raw-pointer | |
98 // is from the CheckCastPP (that converts it to an oop) backwards up | |
99 // through a merge point and into the slow-path call, and around the | |
100 // diamond up to the heap-top check and back down into the slow-path call. | |
101 // The misclassified raw pointer is NOT live across the slow-path call, | |
102 // and so does not appear in any GC info, so the fact that it is | |
103 // misclassified is OK. | |
104 | |
105 if( (lrg1->_is_oop || !lrg2->_is_oop) && // not an oop->int cast AND | |
106 // Compatible final mask | |
107 lrg1->mask().overlap( lrg2->mask() ) ) { | |
108 // Merge larger into smaller. | |
109 if( lr1 > lr2 ) { | |
110 uint tmp = lr1; lr1 = lr2; lr2 = tmp; | |
111 Node *n = n1; n1 = n2; n2 = n; | |
112 LRG *ltmp = lrg1; lrg1 = lrg2; lrg2 = ltmp; | |
113 } | |
114 // Union lr2 into lr1 | |
115 _phc.Union( n1, n2 ); | |
116 if (lrg1->_maxfreq < lrg2->_maxfreq) | |
117 lrg1->_maxfreq = lrg2->_maxfreq; | |
118 // Merge in the IFG | |
119 _phc._ifg->Union( lr1, lr2 ); | |
120 // Combine register restrictions | |
121 lrg1->AND(lrg2->mask()); | |
122 } | |
123 } | |
124 } | |
125 | |
126 // Copy coalescing | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
127 void PhaseCoalesce::coalesce_driver() { |
0 | 128 verify(); |
129 // Coalesce from high frequency to low | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
130 for (uint i = 0; i < _phc._cfg.number_of_blocks(); i++) { |
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
131 coalesce(_phc._blks[i]); |
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
132 } |
0 | 133 } |
134 | |
135 // I am inserting copies to come out of SSA form. In the general case, I am | |
136 // doing a parallel renaming. I'm in the Named world now, so I can't do a | |
137 // general parallel renaming. All the copies now use "names" (live-ranges) | |
138 // to carry values instead of the explicit use-def chains. Suppose I need to | |
139 // insert 2 copies into the same block. They copy L161->L128 and L128->L132. | |
140 // If I insert them in the wrong order then L128 will get clobbered before it | |
141 // can get used by the second copy. This cannot happen in the SSA model; | |
142 // direct use-def chains get me the right value. It DOES happen in the named | |
143 // model so I have to handle the reordering of copies. | |
144 // | |
145 // In general, I need to topo-sort the placed copies to avoid conflicts. | |
146 // Its possible to have a closed cycle of copies (e.g., recirculating the same | |
147 // values around a loop). In this case I need a temp to break the cycle. | |
148 void PhaseAggressiveCoalesce::insert_copy_with_overlap( Block *b, Node *copy, uint dst_name, uint src_name ) { | |
149 | |
150 // Scan backwards for the locations of the last use of the dst_name. | |
151 // I am about to clobber the dst_name, so the copy must be inserted | |
152 // after the last use. Last use is really first-use on a backwards scan. | |
153 uint i = b->end_idx()-1; | |
10111 | 154 while(1) { |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
155 Node *n = b->get_node(i); |
0 | 156 // Check for end of virtual copies; this is also the end of the |
157 // parallel renaming effort. | |
10111 | 158 if (n->_idx < _unique) { |
159 break; | |
160 } | |
0 | 161 uint idx = n->is_Copy(); |
3842 | 162 assert( idx || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); |
10111 | 163 if (idx && _phc._lrg_map.find(n->in(idx)) == dst_name) { |
164 break; | |
165 } | |
0 | 166 i--; |
167 } | |
168 uint last_use_idx = i; | |
169 | |
170 // Also search for any kill of src_name that exits the block. | |
171 // Since the copy uses src_name, I have to come before any kill. | |
172 uint kill_src_idx = b->end_idx(); | |
173 // There can be only 1 kill that exits any block and that is | |
174 // the last kill. Thus it is the first kill on a backwards scan. | |
175 i = b->end_idx()-1; | |
10111 | 176 while (1) { |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
177 Node *n = b->get_node(i); |
0 | 178 // Check for end of virtual copies; this is also the end of the |
179 // parallel renaming effort. | |
10111 | 180 if (n->_idx < _unique) { |
181 break; | |
182 } | |
3842 | 183 assert( n->is_Copy() || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); |
10111 | 184 if (_phc._lrg_map.find(n) == src_name) { |
0 | 185 kill_src_idx = i; |
186 break; | |
187 } | |
188 i--; | |
189 } | |
190 // Need a temp? Last use of dst comes after the kill of src? | |
10111 | 191 if (last_use_idx >= kill_src_idx) { |
0 | 192 // Need to break a cycle with a temp |
193 uint idx = copy->is_Copy(); | |
194 Node *tmp = copy->clone(); | |
10111 | 195 uint max_lrg_id = _phc._lrg_map.max_lrg_id(); |
196 _phc.new_lrg(tmp, max_lrg_id); | |
197 _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1); | |
198 | |
0 | 199 // Insert new temp between copy and source |
200 tmp ->set_req(idx,copy->in(idx)); | |
201 copy->set_req(idx,tmp); | |
202 // Save source in temp early, before source is killed | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
203 b->insert_node(tmp, kill_src_idx); |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
204 _phc._cfg.map_node_to_block(tmp, b); |
0 | 205 last_use_idx++; |
206 } | |
207 | |
208 // Insert just after last use | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
209 b->insert_node(copy, last_use_idx + 1); |
0 | 210 } |
211 | |
212 void PhaseAggressiveCoalesce::insert_copies( Matcher &matcher ) { | |
213 // We do LRGs compressing and fix a liveout data only here since the other | |
214 // place in Split() is guarded by the assert which we never hit. | |
10111 | 215 _phc._lrg_map.compress_uf_map_for_nodes(); |
0 | 216 // Fix block's liveout data for compressed live ranges. |
10111 | 217 for (uint lrg = 1; lrg < _phc._lrg_map.max_lrg_id(); lrg++) { |
218 uint compressed_lrg = _phc._lrg_map.find(lrg); | |
219 if (lrg != compressed_lrg) { | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
220 for (uint bidx = 0; bidx < _phc._cfg.number_of_blocks(); bidx++) { |
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
221 IndexSet *liveout = _phc._live->live(_phc._cfg.get_block(bidx)); |
10111 | 222 if (liveout->member(lrg)) { |
0 | 223 liveout->remove(lrg); |
224 liveout->insert(compressed_lrg); | |
225 } | |
226 } | |
227 } | |
228 } | |
229 | |
230 // All new nodes added are actual copies to replace virtual copies. | |
231 // Nodes with index less than '_unique' are original, non-virtual Nodes. | |
232 _unique = C->unique(); | |
233 | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
234 for (uint i = 0; i < _phc._cfg.number_of_blocks(); i++) { |
10999
693e4d04fd09
8014959: assert(Compile::current()->live_nodes() < (uint)MaxNodeLimit) failed: Live Node limit exceeded limit
drchase
parents:
10111
diff
changeset
|
235 C->check_node_count(NodeLimitFudgeFactor, "out of nodes in coalesce"); |
693e4d04fd09
8014959: assert(Compile::current()->live_nodes() < (uint)MaxNodeLimit) failed: Live Node limit exceeded limit
drchase
parents:
10111
diff
changeset
|
236 if (C->failing()) return; |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
237 Block *b = _phc._cfg.get_block(i); |
0 | 238 uint cnt = b->num_preds(); // Number of inputs to the Phi |
239 | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
240 for( uint l = 1; l<b->number_of_nodes(); l++ ) { |
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
241 Node *n = b->get_node(l); |
0 | 242 |
243 // Do not use removed-copies, use copied value instead | |
244 uint ncnt = n->req(); | |
245 for( uint k = 1; k<ncnt; k++ ) { | |
246 Node *copy = n->in(k); | |
247 uint cidx = copy->is_Copy(); | |
248 if( cidx ) { | |
249 Node *def = copy->in(cidx); | |
10111 | 250 if (_phc._lrg_map.find(copy) == _phc._lrg_map.find(def)) { |
251 n->set_req(k, def); | |
252 } | |
0 | 253 } |
254 } | |
255 | |
256 // Remove any explicit copies that get coalesced. | |
257 uint cidx = n->is_Copy(); | |
258 if( cidx ) { | |
259 Node *def = n->in(cidx); | |
10111 | 260 if (_phc._lrg_map.find(n) == _phc._lrg_map.find(def)) { |
0 | 261 n->replace_by(def); |
262 n->set_req(cidx,NULL); | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
263 b->remove_node(l); |
0 | 264 l--; |
265 continue; | |
266 } | |
267 } | |
268 | |
10111 | 269 if (n->is_Phi()) { |
0 | 270 // Get the chosen name for the Phi |
10111 | 271 uint phi_name = _phc._lrg_map.find(n); |
0 | 272 // Ignore the pre-allocated specials |
10111 | 273 if (!phi_name) { |
274 continue; | |
275 } | |
0 | 276 // Check for mismatch inputs to Phi |
10111 | 277 for (uint j = 1; j < cnt; j++) { |
0 | 278 Node *m = n->in(j); |
10111 | 279 uint src_name = _phc._lrg_map.find(m); |
280 if (src_name != phi_name) { | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
281 Block *pred = _phc._cfg.get_block_for_node(b->pred(j)); |
0 | 282 Node *copy; |
283 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); | |
284 // Rematerialize constants instead of copying them | |
285 if( m->is_Mach() && m->as_Mach()->is_Con() && | |
286 m->as_Mach()->rematerialize() ) { | |
287 copy = m->clone(); | |
288 // Insert the copy in the predecessor basic block | |
289 pred->add_inst(copy); | |
290 // Copy any flags as well | |
10111 | 291 _phc.clone_projs(pred, pred->end_idx(), m, copy, _phc._lrg_map); |
0 | 292 } else { |
293 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; | |
10111 | 294 copy = new (C) MachSpillCopyNode(m, *rm, *rm); |
0 | 295 // Find a good place to insert. Kinda tricky, use a subroutine |
296 insert_copy_with_overlap(pred,copy,phi_name,src_name); | |
297 } | |
298 // Insert the copy in the use-def chain | |
10111 | 299 n->set_req(j, copy); |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
300 _phc._cfg.map_node_to_block(copy, pred); |
0 | 301 // Extend ("register allocate") the names array for the copy. |
10111 | 302 _phc._lrg_map.extend(copy->_idx, phi_name); |
0 | 303 } // End of if Phi names do not match |
304 } // End of for all inputs to Phi | |
305 } else { // End of if Phi | |
306 | |
307 // Now check for 2-address instructions | |
308 uint idx; | |
309 if( n->is_Mach() && (idx=n->as_Mach()->two_adr()) ) { | |
310 // Get the chosen name for the Node | |
10111 | 311 uint name = _phc._lrg_map.find(n); |
312 assert (name, "no 2-address specials"); | |
0 | 313 // Check for name mis-match on the 2-address input |
314 Node *m = n->in(idx); | |
10111 | 315 if (_phc._lrg_map.find(m) != name) { |
0 | 316 Node *copy; |
317 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); | |
318 // At this point it is unsafe to extend live ranges (6550579). | |
319 // Rematerialize only constants as we do for Phi above. | |
10111 | 320 if(m->is_Mach() && m->as_Mach()->is_Con() && |
321 m->as_Mach()->rematerialize()) { | |
0 | 322 copy = m->clone(); |
323 // Insert the copy in the basic block, just before us | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
324 b->insert_node(copy, l++); |
12075
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
12071
diff
changeset
|
325 l += _phc.clone_projs(b, l, m, copy, _phc._lrg_map); |
0 | 326 } else { |
327 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; | |
10111 | 328 copy = new (C) MachSpillCopyNode(m, *rm, *rm); |
0 | 329 // Insert the copy in the basic block, just before us |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
330 b->insert_node(copy, l++); |
0 | 331 } |
332 // Insert the copy in the use-def chain | |
10111 | 333 n->set_req(idx, copy); |
0 | 334 // Extend ("register allocate") the names array for the copy. |
10111 | 335 _phc._lrg_map.extend(copy->_idx, name); |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
336 _phc._cfg.map_node_to_block(copy, b); |
0 | 337 } |
338 | |
339 } // End of is two-adr | |
340 | |
341 // Insert a copy at a debug use for a lrg which has high frequency | |
12171
4b078f877b56
8023988: Move local scheduling of nodes to the CFG creation and code motion phase (PhaseCFG)
adlertz
parents:
12167
diff
changeset
|
342 if (b->_freq < OPTO_DEBUG_SPLIT_FREQ || _phc._cfg.is_uncommon(b)) { |
0 | 343 // Walk the debug inputs to the node and check for lrg freq |
344 JVMState* jvms = n->jvms(); | |
345 uint debug_start = jvms ? jvms->debug_start() : 999999; | |
346 uint debug_end = jvms ? jvms->debug_end() : 999999; | |
347 for(uint inpidx = debug_start; inpidx < debug_end; inpidx++) { | |
348 // Do not split monitors; they are only needed for debug table | |
349 // entries and need no code. | |
10111 | 350 if (jvms->is_monitor_use(inpidx)) { |
351 continue; | |
352 } | |
0 | 353 Node *inp = n->in(inpidx); |
10111 | 354 uint nidx = _phc._lrg_map.live_range_id(inp); |
0 | 355 LRG &lrg = lrgs(nidx); |
356 | |
357 // If this lrg has a high frequency use/def | |
673 | 358 if( lrg._maxfreq >= _phc.high_frequency_lrg() ) { |
0 | 359 // If the live range is also live out of this block (like it |
360 // would be for a fast/slow idiom), the normal spill mechanism | |
361 // does an excellent job. If it is not live out of this block | |
362 // (like it would be for debug info to uncommon trap) splitting | |
363 // the live range now allows a better allocation in the high | |
364 // frequency blocks. | |
365 // Build_IFG_virtual has converted the live sets to | |
366 // live-IN info, not live-OUT info. | |
367 uint k; | |
368 for( k=0; k < b->_num_succs; k++ ) | |
369 if( _phc._live->live(b->_succs[k])->member( nidx ) ) | |
370 break; // Live in to some successor block? | |
371 if( k < b->_num_succs ) | |
372 continue; // Live out; do not pre-split | |
373 // Split the lrg at this use | |
374 const RegMask *rm = C->matcher()->idealreg2spillmask[inp->ideal_reg()]; | |
375 Node *copy = new (C) MachSpillCopyNode( inp, *rm, *rm ); | |
376 // Insert the copy in the use-def chain | |
377 n->set_req(inpidx, copy ); | |
378 // Insert the copy in the basic block, just before us | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
379 b->insert_node(copy, l++); |
0 | 380 // Extend ("register allocate") the names array for the copy. |
10111 | 381 uint max_lrg_id = _phc._lrg_map.max_lrg_id(); |
382 _phc.new_lrg(copy, max_lrg_id); | |
383 _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1); | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
384 _phc._cfg.map_node_to_block(copy, b); |
0 | 385 //tty->print_cr("Split a debug use in Aggressive Coalesce"); |
386 } // End of if high frequency use/def | |
387 } // End of for all debug inputs | |
388 } // End of if low frequency safepoint | |
389 | |
390 } // End of if Phi | |
391 | |
392 } // End of for all instructions | |
393 } // End of for all blocks | |
394 } | |
395 | |
12071
adb9a7d94cb5
8023003: Cleanup the public interface to PhaseCFG
adlertz
parents:
12023
diff
changeset
|
396 |
0 | 397 // Aggressive (but pessimistic) copy coalescing of a single block |
398 | |
399 // The following coalesce pass represents a single round of aggressive | |
400 // pessimistic coalesce. "Aggressive" means no attempt to preserve | |
401 // colorability when coalescing. This occasionally means more spills, but | |
402 // it also means fewer rounds of coalescing for better code - and that means | |
403 // faster compiles. | |
404 | |
405 // "Pessimistic" means we do not hit the fixed point in one pass (and we are | |
406 // reaching for the least fixed point to boot). This is typically solved | |
407 // with a few more rounds of coalescing, but the compiler must run fast. We | |
408 // could optimistically coalescing everything touching PhiNodes together | |
409 // into one big live range, then check for self-interference. Everywhere | |
410 // the live range interferes with self it would have to be split. Finding | |
411 // the right split points can be done with some heuristics (based on | |
412 // expected frequency of edges in the live range). In short, it's a real | |
413 // research problem and the timeline is too short to allow such research. | |
414 // Further thoughts: (1) build the LR in a pass, (2) find self-interference | |
415 // in another pass, (3) per each self-conflict, split, (4) split by finding | |
416 // the low-cost cut (min-cut) of the LR, (5) edges in the LR are weighted | |
417 // according to the GCM algorithm (or just exec freq on CFG edges). | |
418 | |
419 void PhaseAggressiveCoalesce::coalesce( Block *b ) { | |
420 // Copies are still "virtual" - meaning we have not made them explicitly | |
421 // copies. Instead, Phi functions of successor blocks have mis-matched | |
422 // live-ranges. If I fail to coalesce, I'll have to insert a copy to line | |
423 // up the live-ranges. Check for Phis in successor blocks. | |
424 uint i; | |
425 for( i=0; i<b->_num_succs; i++ ) { | |
426 Block *bs = b->_succs[i]; | |
427 // Find index of 'b' in 'bs' predecessors | |
428 uint j=1; | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
429 while (_phc._cfg.get_block_for_node(bs->pred(j)) != b) { |
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
430 j++; |
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
431 } |
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
432 |
0 | 433 // Visit all the Phis in successor block |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
434 for( uint k = 1; k<bs->number_of_nodes(); k++ ) { |
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
435 Node *n = bs->get_node(k); |
0 | 436 if( !n->is_Phi() ) break; |
437 combine_these_two( n, n->in(j) ); | |
438 } | |
439 } // End of for all successor blocks | |
440 | |
441 | |
442 // Check _this_ block for 2-address instructions and copies. | |
443 uint cnt = b->end_idx(); | |
444 for( i = 1; i<cnt; i++ ) { | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
445 Node *n = b->get_node(i); |
0 | 446 uint idx; |
447 // 2-address instructions have a virtual Copy matching their input | |
448 // to their output | |
10111 | 449 if (n->is_Mach() && (idx = n->as_Mach()->two_adr())) { |
0 | 450 MachNode *mach = n->as_Mach(); |
10111 | 451 combine_these_two(mach, mach->in(idx)); |
0 | 452 } |
453 } // End of for all instructions in block | |
454 } | |
455 | |
10111 | 456 PhaseConservativeCoalesce::PhaseConservativeCoalesce(PhaseChaitin &chaitin) : PhaseCoalesce(chaitin) { |
457 _ulr.initialize(_phc._lrg_map.max_lrg_id()); | |
0 | 458 } |
459 | |
460 void PhaseConservativeCoalesce::verify() { | |
461 #ifdef ASSERT | |
462 _phc.set_was_low(); | |
463 #endif | |
464 } | |
465 | |
466 void PhaseConservativeCoalesce::union_helper( Node *lr1_node, Node *lr2_node, uint lr1, uint lr2, Node *src_def, Node *dst_copy, Node *src_copy, Block *b, uint bindex ) { | |
467 // Join live ranges. Merge larger into smaller. Union lr2 into lr1 in the | |
468 // union-find tree | |
469 _phc.Union( lr1_node, lr2_node ); | |
470 | |
471 // Single-def live range ONLY if both live ranges are single-def. | |
472 // If both are single def, then src_def powers one live range | |
473 // and def_copy powers the other. After merging, src_def powers | |
474 // the combined live range. | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
475 lrgs(lr1)._def = (lrgs(lr1).is_multidef() || |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
476 lrgs(lr2).is_multidef() ) |
0 | 477 ? NodeSentinel : src_def; |
478 lrgs(lr2)._def = NULL; // No def for lrg 2 | |
479 lrgs(lr2).Clear(); // Force empty mask for LRG 2 | |
480 //lrgs(lr2)._size = 0; // Live-range 2 goes dead | |
481 lrgs(lr1)._is_oop |= lrgs(lr2)._is_oop; | |
482 lrgs(lr2)._is_oop = 0; // In particular, not an oop for GC info | |
483 | |
484 if (lrgs(lr1)._maxfreq < lrgs(lr2)._maxfreq) | |
485 lrgs(lr1)._maxfreq = lrgs(lr2)._maxfreq; | |
486 | |
487 // Copy original value instead. Intermediate copies go dead, and | |
488 // the dst_copy becomes useless. | |
489 int didx = dst_copy->is_Copy(); | |
490 dst_copy->set_req( didx, src_def ); | |
491 // Add copy to free list | |
492 // _phc.free_spillcopy(b->_nodes[bindex]); | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
493 assert( b->get_node(bindex) == dst_copy, "" ); |
0 | 494 dst_copy->replace_by( dst_copy->in(didx) ); |
495 dst_copy->set_req( didx, NULL); | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
496 b->remove_node(bindex); |
0 | 497 if( bindex < b->_ihrp_index ) b->_ihrp_index--; |
498 if( bindex < b->_fhrp_index ) b->_fhrp_index--; | |
499 | |
500 // Stretched lr1; add it to liveness of intermediate blocks | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
501 Block *b2 = _phc._cfg.get_block_for_node(src_copy); |
0 | 502 while( b != b2 ) { |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
503 b = _phc._cfg.get_block_for_node(b->pred(1)); |
0 | 504 _phc._live->live(b)->insert(lr1); |
505 } | |
506 } | |
507 | |
508 // Factored code from copy_copy that computes extra interferences from | |
509 // lengthening a live range by double-coalescing. | |
510 uint PhaseConservativeCoalesce::compute_separating_interferences(Node *dst_copy, Node *src_copy, Block *b, uint bindex, RegMask &rm, uint reg_degree, uint rm_size, uint lr1, uint lr2 ) { | |
511 | |
512 assert(!lrgs(lr1)._fat_proj, "cannot coalesce fat_proj"); | |
513 assert(!lrgs(lr2)._fat_proj, "cannot coalesce fat_proj"); | |
514 Node *prev_copy = dst_copy->in(dst_copy->is_Copy()); | |
515 Block *b2 = b; | |
516 uint bindex2 = bindex; | |
517 while( 1 ) { | |
518 // Find previous instruction | |
519 bindex2--; // Chain backwards 1 instruction | |
520 while( bindex2 == 0 ) { // At block start, find prior block | |
521 assert( b2->num_preds() == 2, "cannot double coalesce across c-flow" ); | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
522 b2 = _phc._cfg.get_block_for_node(b2->pred(1)); |
0 | 523 bindex2 = b2->end_idx()-1; |
524 } | |
525 // Get prior instruction | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
526 assert(bindex2 < b2->number_of_nodes(), "index out of bounds"); |
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
527 Node *x = b2->get_node(bindex2); |
0 | 528 if( x == prev_copy ) { // Previous copy in copy chain? |
529 if( prev_copy == src_copy)// Found end of chain and all interferences | |
530 break; // So break out of loop | |
531 // Else work back one in copy chain | |
532 prev_copy = prev_copy->in(prev_copy->is_Copy()); | |
533 } else { // Else collect interferences | |
10111 | 534 uint lidx = _phc._lrg_map.find(x); |
0 | 535 // Found another def of live-range being stretched? |
10111 | 536 if(lidx == lr1) { |
537 return max_juint; | |
538 } | |
539 if(lidx == lr2) { | |
540 return max_juint; | |
541 } | |
0 | 542 |
543 // If we attempt to coalesce across a bound def | |
544 if( lrgs(lidx).is_bound() ) { | |
545 // Do not let the coalesced LRG expect to get the bound color | |
546 rm.SUBTRACT( lrgs(lidx).mask() ); | |
547 // Recompute rm_size | |
548 rm_size = rm.Size(); | |
549 //if( rm._flags ) rm_size += 1000000; | |
550 if( reg_degree >= rm_size ) return max_juint; | |
551 } | |
552 if( rm.overlap(lrgs(lidx).mask()) ) { | |
553 // Insert lidx into union LRG; returns TRUE if actually inserted | |
554 if( _ulr.insert(lidx) ) { | |
555 // Infinite-stack neighbors do not alter colorability, as they | |
556 // can always color to some other color. | |
557 if( !lrgs(lidx).mask().is_AllStack() ) { | |
558 // If this coalesce will make any new neighbor uncolorable, | |
559 // do not coalesce. | |
560 if( lrgs(lidx).just_lo_degree() ) | |
561 return max_juint; | |
562 // Bump our degree | |
563 if( ++reg_degree >= rm_size ) | |
564 return max_juint; | |
565 } // End of if not infinite-stack neighbor | |
566 } // End of if actually inserted | |
567 } // End of if live range overlaps | |
605 | 568 } // End of else collect interferences for 1 node |
569 } // End of while forever, scan back for interferences | |
0 | 570 return reg_degree; |
571 } | |
572 | |
573 void PhaseConservativeCoalesce::update_ifg(uint lr1, uint lr2, IndexSet *n_lr1, IndexSet *n_lr2) { | |
574 // Some original neighbors of lr1 might have gone away | |
575 // because the constrained register mask prevented them. | |
576 // Remove lr1 from such neighbors. | |
577 IndexSetIterator one(n_lr1); | |
578 uint neighbor; | |
579 LRG &lrg1 = lrgs(lr1); | |
580 while ((neighbor = one.next()) != 0) | |
581 if( !_ulr.member(neighbor) ) | |
582 if( _phc._ifg->neighbors(neighbor)->remove(lr1) ) | |
583 lrgs(neighbor).inc_degree( -lrg1.compute_degree(lrgs(neighbor)) ); | |
584 | |
585 | |
586 // lr2 is now called (coalesced into) lr1. | |
587 // Remove lr2 from the IFG. | |
588 IndexSetIterator two(n_lr2); | |
589 LRG &lrg2 = lrgs(lr2); | |
590 while ((neighbor = two.next()) != 0) | |
591 if( _phc._ifg->neighbors(neighbor)->remove(lr2) ) | |
592 lrgs(neighbor).inc_degree( -lrg2.compute_degree(lrgs(neighbor)) ); | |
593 | |
594 // Some neighbors of intermediate copies now interfere with the | |
595 // combined live range. | |
596 IndexSetIterator three(&_ulr); | |
597 while ((neighbor = three.next()) != 0) | |
598 if( _phc._ifg->neighbors(neighbor)->insert(lr1) ) | |
599 lrgs(neighbor).inc_degree( lrg1.compute_degree(lrgs(neighbor)) ); | |
600 } | |
601 | |
602 static void record_bias( const PhaseIFG *ifg, int lr1, int lr2 ) { | |
603 // Tag copy bias here | |
604 if( !ifg->lrgs(lr1)._copy_bias ) | |
605 ifg->lrgs(lr1)._copy_bias = lr2; | |
606 if( !ifg->lrgs(lr2)._copy_bias ) | |
607 ifg->lrgs(lr2)._copy_bias = lr1; | |
608 } | |
609 | |
610 // See if I can coalesce a series of multiple copies together. I need the | |
611 // final dest copy and the original src copy. They can be the same Node. | |
612 // Compute the compatible register masks. | |
10111 | 613 bool PhaseConservativeCoalesce::copy_copy(Node *dst_copy, Node *src_copy, Block *b, uint bindex) { |
0 | 614 |
10111 | 615 if (!dst_copy->is_SpillCopy()) { |
616 return false; | |
617 } | |
618 if (!src_copy->is_SpillCopy()) { | |
619 return false; | |
620 } | |
0 | 621 Node *src_def = src_copy->in(src_copy->is_Copy()); |
10111 | 622 uint lr1 = _phc._lrg_map.find(dst_copy); |
623 uint lr2 = _phc._lrg_map.find(src_def); | |
0 | 624 |
625 // Same live ranges already? | |
10111 | 626 if (lr1 == lr2) { |
627 return false; | |
628 } | |
0 | 629 |
630 // Interfere? | |
10111 | 631 if (_phc._ifg->test_edge_sq(lr1, lr2)) { |
632 return false; | |
633 } | |
0 | 634 |
635 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK. | |
10111 | 636 if (!lrgs(lr1)._is_oop && lrgs(lr2)._is_oop) { // not an oop->int cast |
0 | 637 return false; |
10111 | 638 } |
0 | 639 |
640 // Coalescing between an aligned live range and a mis-aligned live range? | |
641 // No, no! Alignment changes how we count degree. | |
10111 | 642 if (lrgs(lr1)._fat_proj != lrgs(lr2)._fat_proj) { |
0 | 643 return false; |
10111 | 644 } |
0 | 645 |
646 // Sort; use smaller live-range number | |
647 Node *lr1_node = dst_copy; | |
648 Node *lr2_node = src_def; | |
10111 | 649 if (lr1 > lr2) { |
0 | 650 uint tmp = lr1; lr1 = lr2; lr2 = tmp; |
651 lr1_node = src_def; lr2_node = dst_copy; | |
652 } | |
653 | |
654 // Check for compatibility of the 2 live ranges by | |
655 // intersecting their allowed register sets. | |
656 RegMask rm = lrgs(lr1).mask(); | |
657 rm.AND(lrgs(lr2).mask()); | |
658 // Number of bits free | |
659 uint rm_size = rm.Size(); | |
660 | |
1730
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
661 if (UseFPUForSpilling && rm.is_AllStack() ) { |
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
662 // Don't coalesce when frequency difference is large |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
663 Block *dst_b = _phc._cfg.get_block_for_node(dst_copy); |
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
664 Block *src_def_b = _phc._cfg.get_block_for_node(src_def); |
1730
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
665 if (src_def_b->_freq > 10*dst_b->_freq ) |
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
666 return false; |
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
667 } |
f55c4f82ab9d
6978249: spill between cpu and fpu registers when those moves are fast
never
parents:
1552
diff
changeset
|
668 |
0 | 669 // If we can use any stack slot, then effective size is infinite |
670 if( rm.is_AllStack() ) rm_size += 1000000; | |
671 // Incompatible masks, no way to coalesce | |
672 if( rm_size == 0 ) return false; | |
673 | |
674 // Another early bail-out test is when we are double-coalescing and the | |
605 | 675 // 2 copies are separated by some control flow. |
0 | 676 if( dst_copy != src_copy ) { |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
677 Block *src_b = _phc._cfg.get_block_for_node(src_copy); |
0 | 678 Block *b2 = b; |
679 while( b2 != src_b ) { | |
680 if( b2->num_preds() > 2 ){// Found merge-point | |
681 _phc._lost_opp_cflow_coalesce++; | |
682 // extra record_bias commented out because Chris believes it is not | |
683 // productive. Since we can record only 1 bias, we want to choose one | |
684 // that stands a chance of working and this one probably does not. | |
685 //record_bias( _phc._lrgs, lr1, lr2 ); | |
686 return false; // To hard to find all interferences | |
687 } | |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
688 b2 = _phc._cfg.get_block_for_node(b2->pred(1)); |
0 | 689 } |
690 } | |
691 | |
692 // Union the two interference sets together into '_ulr' | |
693 uint reg_degree = _ulr.lrg_union( lr1, lr2, rm_size, _phc._ifg, rm ); | |
694 | |
695 if( reg_degree >= rm_size ) { | |
696 record_bias( _phc._ifg, lr1, lr2 ); | |
697 return false; | |
698 } | |
699 | |
700 // Now I need to compute all the interferences between dst_copy and | |
701 // src_copy. I'm not willing visit the entire interference graph, so | |
702 // I limit my search to things in dst_copy's block or in a straight | |
703 // line of previous blocks. I give up at merge points or when I get | |
704 // more interferences than my degree. I can stop when I find src_copy. | |
705 if( dst_copy != src_copy ) { | |
706 reg_degree = compute_separating_interferences(dst_copy, src_copy, b, bindex, rm, rm_size, reg_degree, lr1, lr2 ); | |
707 if( reg_degree == max_juint ) { | |
708 record_bias( _phc._ifg, lr1, lr2 ); | |
709 return false; | |
710 } | |
711 } // End of if dst_copy & src_copy are different | |
712 | |
713 | |
714 // ---- THE COMBINED LRG IS COLORABLE ---- | |
715 | |
716 // YEAH - Now coalesce this copy away | |
717 assert( lrgs(lr1).num_regs() == lrgs(lr2).num_regs(), "" ); | |
718 | |
719 IndexSet *n_lr1 = _phc._ifg->neighbors(lr1); | |
720 IndexSet *n_lr2 = _phc._ifg->neighbors(lr2); | |
721 | |
722 // Update the interference graph | |
723 update_ifg(lr1, lr2, n_lr1, n_lr2); | |
724 | |
725 _ulr.remove(lr1); | |
726 | |
727 // Uncomment the following code to trace Coalescing in great detail. | |
728 // | |
729 //if (false) { | |
730 // tty->cr(); | |
731 // tty->print_cr("#######################################"); | |
732 // tty->print_cr("union %d and %d", lr1, lr2); | |
733 // n_lr1->dump(); | |
734 // n_lr2->dump(); | |
735 // tty->print_cr("resulting set is"); | |
736 // _ulr.dump(); | |
737 //} | |
738 | |
739 // Replace n_lr1 with the new combined live range. _ulr will use | |
740 // n_lr1's old memory on the next iteration. n_lr2 is cleared to | |
741 // send its internal memory to the free list. | |
742 _ulr.swap(n_lr1); | |
743 _ulr.clear(); | |
744 n_lr2->clear(); | |
745 | |
746 lrgs(lr1).set_degree( _phc._ifg->effective_degree(lr1) ); | |
747 lrgs(lr2).set_degree( 0 ); | |
748 | |
749 // Join live ranges. Merge larger into smaller. Union lr2 into lr1 in the | |
750 // union-find tree | |
751 union_helper( lr1_node, lr2_node, lr1, lr2, src_def, dst_copy, src_copy, b, bindex ); | |
752 // Combine register restrictions | |
753 lrgs(lr1).set_mask(rm); | |
754 lrgs(lr1).compute_set_mask_size(); | |
755 lrgs(lr1)._cost += lrgs(lr2)._cost; | |
756 lrgs(lr1)._area += lrgs(lr2)._area; | |
757 | |
758 // While its uncommon to successfully coalesce live ranges that started out | |
759 // being not-lo-degree, it can happen. In any case the combined coalesced | |
760 // live range better Simplify nicely. | |
761 lrgs(lr1)._was_lo = 1; | |
762 | |
763 // kinda expensive to do all the time | |
764 //tty->print_cr("warning: slow verify happening"); | |
765 //_phc._ifg->verify( &_phc ); | |
766 return true; | |
767 } | |
768 | |
769 // Conservative (but pessimistic) copy coalescing of a single block | |
770 void PhaseConservativeCoalesce::coalesce( Block *b ) { | |
771 // Bail out on infrequent blocks | |
12171
4b078f877b56
8023988: Move local scheduling of nodes to the CFG creation and code motion phase (PhaseCFG)
adlertz
parents:
12167
diff
changeset
|
772 if (_phc._cfg.is_uncommon(b)) { |
0 | 773 return; |
12023
d1034bd8cefc
8022284: Hide internal data structure in PhaseCFG
adlertz
parents:
10999
diff
changeset
|
774 } |
0 | 775 // Check this block for copies. |
776 for( uint i = 1; i<b->end_idx(); i++ ) { | |
777 // Check for actual copies on inputs. Coalesce a copy into its | |
778 // input if use and copy's input are compatible. | |
12167
650868c062a9
8023691: Create interface for nodes in class Block
adlertz
parents:
12075
diff
changeset
|
779 Node *copy1 = b->get_node(i); |
0 | 780 uint idx1 = copy1->is_Copy(); |
781 if( !idx1 ) continue; // Not a copy | |
782 | |
783 if( copy_copy(copy1,copy1,b,i) ) { | |
784 i--; // Retry, same location in block | |
785 PhaseChaitin::_conserv_coalesce++; // Collect stats on success | |
786 continue; | |
787 } | |
788 } | |
789 } |