Mercurial > hg > truffle
annotate src/share/vm/opto/chaitin.hpp @ 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 | 55fb97c4c58d |
| children | c84312468f5c |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
17467
55fb97c4c58d
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
mikael
parents:
12877
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:
923
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
923
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:
923
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_OPTO_CHAITIN_HPP |
| 26 #define SHARE_VM_OPTO_CHAITIN_HPP | |
| 27 | |
| 28 #include "code/vmreg.hpp" | |
| 29 #include "libadt/port.hpp" | |
| 30 #include "memory/resourceArea.hpp" | |
| 31 #include "opto/connode.hpp" | |
| 32 #include "opto/live.hpp" | |
| 33 #include "opto/matcher.hpp" | |
| 34 #include "opto/phase.hpp" | |
| 35 #include "opto/regalloc.hpp" | |
| 36 #include "opto/regmask.hpp" | |
| 37 | |
| 0 | 38 class LoopTree; |
| 39 class MachCallNode; | |
| 40 class MachSafePointNode; | |
| 41 class Matcher; | |
| 42 class PhaseCFG; | |
| 43 class PhaseLive; | |
| 44 class PhaseRegAlloc; | |
| 45 class PhaseChaitin; | |
| 46 | |
| 47 #define OPTO_DEBUG_SPLIT_FREQ BLOCK_FREQUENCY(0.001) | |
| 48 #define OPTO_LRG_HIGH_FREQ BLOCK_FREQUENCY(0.25) | |
| 49 | |
| 50 //------------------------------LRG-------------------------------------------- | |
| 51 // Live-RanGe structure. | |
| 52 class LRG : public ResourceObj { | |
| 3939 | 53 friend class VMStructs; |
| 0 | 54 public: |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
55 static const uint AllStack_size = 0xFFFFF; // This mask size is used to tell that the mask of this LRG supports stack positions |
| 0 | 56 enum { SPILL_REG=29999 }; // Register number of a spilled LRG |
| 57 | |
| 58 double _cost; // 2 for loads/1 for stores times block freq | |
| 59 double _area; // Sum of all simultaneously live values | |
| 60 double score() const; // Compute score from cost and area | |
| 61 double _maxfreq; // Maximum frequency of any def or use | |
| 62 | |
| 63 Node *_def; // Check for multi-def live ranges | |
| 64 #ifndef PRODUCT | |
| 65 GrowableArray<Node*>* _defs; | |
| 66 #endif | |
| 67 | |
| 68 uint _risk_bias; // Index of LRG which we want to avoid color | |
| 69 uint _copy_bias; // Index of LRG which we want to share color | |
| 70 | |
| 71 uint _next; // Index of next LRG in linked list | |
| 72 uint _prev; // Index of prev LRG in linked list | |
| 73 private: | |
| 74 uint _reg; // Chosen register; undefined if mask is plural | |
| 75 public: | |
| 76 // Return chosen register for this LRG. Error if the LRG is not bound to | |
| 77 // a single register. | |
| 78 OptoReg::Name reg() const { return OptoReg::Name(_reg); } | |
| 79 void set_reg( OptoReg::Name r ) { _reg = r; } | |
| 80 | |
| 81 private: | |
| 82 uint _eff_degree; // Effective degree: Sum of neighbors _num_regs | |
| 83 public: | |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
84 int degree() const { assert( _degree_valid , "" ); return _eff_degree; } |
| 0 | 85 // Degree starts not valid and any change to the IFG neighbor |
| 86 // set makes it not valid. | |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
87 void set_degree( uint degree ) { |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
88 _eff_degree = degree; |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
89 debug_only(_degree_valid = 1;) |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
90 assert(!_mask.is_AllStack() || (_mask.is_AllStack() && lo_degree()), "_eff_degree can't be bigger than AllStack_size - _num_regs if the mask supports stack registers"); |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
91 } |
| 0 | 92 // Made a change that hammered degree |
| 93 void invalid_degree() { debug_only(_degree_valid=0;) } | |
| 94 // Incrementally modify degree. If it was correct, it should remain correct | |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
95 void inc_degree( uint mod ) { |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
96 _eff_degree += mod; |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
97 assert(!_mask.is_AllStack() || (_mask.is_AllStack() && lo_degree()), "_eff_degree can't be bigger than AllStack_size - _num_regs if the mask supports stack registers"); |
|
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
98 } |
| 0 | 99 // Compute the degree between 2 live ranges |
| 100 int compute_degree( LRG &l ) const; | |
| 101 | |
| 102 private: | |
| 103 RegMask _mask; // Allowed registers for this LRG | |
| 104 uint _mask_size; // cache of _mask.Size(); | |
| 105 public: | |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
106 int compute_mask_size() const { return _mask.is_AllStack() ? AllStack_size : _mask.Size(); } |
| 0 | 107 void set_mask_size( int size ) { |
|
12877
d8a449d2f5b2
8011415: CTW on Sparc: assert(lrg.lo_degree()) failed:
adlertz
parents:
12254
diff
changeset
|
108 assert((size == (int)AllStack_size) || (size == (int)_mask.Size()), ""); |
| 0 | 109 _mask_size = size; |
|
6179
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
110 #ifdef ASSERT |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
111 _msize_valid=1; |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
112 if (_is_vector) { |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
113 assert(!_fat_proj, "sanity"); |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
114 _mask.verify_sets(_num_regs); |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
115 } else if (_num_regs == 2 && !_fat_proj) { |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
116 _mask.verify_pairs(); |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
117 } |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
118 #endif |
| 0 | 119 } |
| 120 void compute_set_mask_size() { set_mask_size(compute_mask_size()); } | |
| 121 int mask_size() const { assert( _msize_valid, "mask size not valid" ); | |
| 122 return _mask_size; } | |
| 123 // Get the last mask size computed, even if it does not match the | |
| 124 // count of bits in the current mask. | |
| 125 int get_invalid_mask_size() const { return _mask_size; } | |
| 126 const RegMask &mask() const { return _mask; } | |
| 127 void set_mask( const RegMask &rm ) { _mask = rm; debug_only(_msize_valid=0;)} | |
| 128 void AND( const RegMask &rm ) { _mask.AND(rm); debug_only(_msize_valid=0;)} | |
| 129 void SUBTRACT( const RegMask &rm ) { _mask.SUBTRACT(rm); debug_only(_msize_valid=0;)} | |
| 130 void Clear() { _mask.Clear() ; debug_only(_msize_valid=1); _mask_size = 0; } | |
| 131 void Set_All() { _mask.Set_All(); debug_only(_msize_valid=1); _mask_size = RegMask::CHUNK_SIZE; } | |
| 132 void Insert( OptoReg::Name reg ) { _mask.Insert(reg); debug_only(_msize_valid=0;) } | |
| 133 void Remove( OptoReg::Name reg ) { _mask.Remove(reg); debug_only(_msize_valid=0;) } | |
|
6179
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
134 void clear_to_pairs() { _mask.clear_to_pairs(); debug_only(_msize_valid=0;) } |
|
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
135 void clear_to_sets() { _mask.clear_to_sets(_num_regs); debug_only(_msize_valid=0;) } |
| 0 | 136 |
| 137 // Number of registers this live range uses when it colors | |
| 138 private: | |
| 139 uint8 _num_regs; // 2 for Longs and Doubles, 1 for all else | |
| 140 // except _num_regs is kill count for fat_proj | |
| 141 public: | |
| 142 int num_regs() const { return _num_regs; } | |
| 143 void set_num_regs( int reg ) { assert( _num_regs == reg || !_num_regs, "" ); _num_regs = reg; } | |
| 144 | |
| 145 private: | |
| 146 // Number of physical registers this live range uses when it colors | |
| 147 // Architecture and register-set dependent | |
| 148 uint8 _reg_pressure; | |
| 149 public: | |
| 150 void set_reg_pressure(int i) { _reg_pressure = i; } | |
| 151 int reg_pressure() const { return _reg_pressure; } | |
| 152 | |
| 153 // How much 'wiggle room' does this live range have? | |
| 154 // How many color choices can it make (scaled by _num_regs)? | |
| 155 int degrees_of_freedom() const { return mask_size() - _num_regs; } | |
| 156 // Bound LRGs have ZERO degrees of freedom. We also count | |
| 157 // must_spill as bound. | |
| 158 bool is_bound () const { return _is_bound; } | |
| 159 // Negative degrees-of-freedom; even with no neighbors this | |
| 160 // live range must spill. | |
| 161 bool not_free() const { return degrees_of_freedom() < 0; } | |
| 162 // Is this live range of "low-degree"? Trivially colorable? | |
| 163 bool lo_degree () const { return degree() <= degrees_of_freedom(); } | |
| 164 // Is this live range just barely "low-degree"? Trivially colorable? | |
| 165 bool just_lo_degree () const { return degree() == degrees_of_freedom(); } | |
| 166 | |
| 167 uint _is_oop:1, // Live-range holds an oop | |
| 168 _is_float:1, // True if in float registers | |
|
6179
8c92982cbbc4
7119644: Increase superword's vector size up to 256 bits
kvn
parents:
4776
diff
changeset
|
169 _is_vector:1, // True if in vector registers |
| 0 | 170 _was_spilled1:1, // True if prior spilling on def |
| 171 _was_spilled2:1, // True if twice prior spilling on def | |
| 172 _is_bound:1, // live range starts life with no | |
| 173 // degrees of freedom. | |
| 174 _direct_conflict:1, // True if def and use registers in conflict | |
| 175 _must_spill:1, // live range has lost all degrees of freedom | |
| 176 // If _fat_proj is set, live range does NOT require aligned, adjacent | |
| 177 // registers and has NO interferences. | |
| 178 // If _fat_proj is clear, live range requires num_regs() to be a power of | |
| 179 // 2, and it requires registers to form an aligned, adjacent set. | |
| 180 _fat_proj:1, // | |
| 181 _was_lo:1, // Was lo-degree prior to coalesce | |
| 182 _msize_valid:1, // _mask_size cache valid | |
| 183 _degree_valid:1, // _degree cache valid | |
| 184 _has_copy:1, // Adjacent to some copy instruction | |
| 185 _at_risk:1; // Simplify says this guy is at risk to spill | |
| 186 | |
| 187 | |
| 188 // Alive if non-zero, dead if zero | |
| 189 bool alive() const { return _def != NULL; } | |
|
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
196
diff
changeset
|
190 bool is_multidef() const { return _def == NodeSentinel; } |
|
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
196
diff
changeset
|
191 bool is_singledef() const { return _def != NodeSentinel; } |
| 0 | 192 |
| 193 #ifndef PRODUCT | |
| 194 void dump( ) const; | |
| 195 #endif | |
| 196 }; | |
| 197 | |
| 198 //------------------------------IFG-------------------------------------------- | |
| 199 // InterFerence Graph | |
| 200 // An undirected graph implementation. Created with a fixed number of | |
| 201 // vertices. Edges can be added & tested. Vertices can be removed, then | |
| 202 // added back later with all edges intact. Can add edges between one vertex | |
| 203 // and a list of other vertices. Can union vertices (and their edges) | |
| 204 // together. The IFG needs to be really really fast, and also fairly | |
| 205 // abstract! It needs abstraction so I can fiddle with the implementation to | |
| 206 // get even more speed. | |
| 207 class PhaseIFG : public Phase { | |
| 3939 | 208 friend class VMStructs; |
| 0 | 209 // Current implementation: a triangular adjacency list. |
| 210 | |
| 211 // Array of adjacency-lists, indexed by live-range number | |
| 212 IndexSet *_adjs; | |
| 213 | |
| 214 // Assertion bit for proper use of Squaring | |
| 215 bool _is_square; | |
| 216 | |
| 217 // Live range structure goes here | |
| 218 LRG *_lrgs; // Array of LRG structures | |
| 219 | |
| 220 public: | |
| 221 // Largest live-range number | |
| 222 uint _maxlrg; | |
| 223 | |
| 224 Arena *_arena; | |
| 225 | |
| 226 // Keep track of inserted and deleted Nodes | |
| 227 VectorSet *_yanked; | |
| 228 | |
| 229 PhaseIFG( Arena *arena ); | |
| 230 void init( uint maxlrg ); | |
| 231 | |
| 232 // Add edge between a and b. Returns true if actually addded. | |
| 233 int add_edge( uint a, uint b ); | |
| 234 | |
| 235 // Add edge between a and everything in the vector | |
| 236 void add_vector( uint a, IndexSet *vec ); | |
| 237 | |
| 238 // Test for edge existance | |
| 239 int test_edge( uint a, uint b ) const; | |
| 240 | |
| 241 // Square-up matrix for faster Union | |
| 242 void SquareUp(); | |
| 243 | |
| 244 // Return number of LRG neighbors | |
| 245 uint neighbor_cnt( uint a ) const { return _adjs[a].count(); } | |
| 246 // Union edges of b into a on Squared-up matrix | |
| 247 void Union( uint a, uint b ); | |
| 248 // Test for edge in Squared-up matrix | |
| 249 int test_edge_sq( uint a, uint b ) const; | |
| 250 // Yank a Node and all connected edges from the IFG. Be prepared to | |
| 251 // re-insert the yanked Node in reverse order of yanking. Return a | |
| 252 // list of neighbors (edges) yanked. | |
| 253 IndexSet *remove_node( uint a ); | |
| 254 // Reinsert a yanked Node | |
| 255 void re_insert( uint a ); | |
| 256 // Return set of neighbors | |
| 257 IndexSet *neighbors( uint a ) const { return &_adjs[a]; } | |
| 258 | |
| 259 #ifndef PRODUCT | |
| 260 // Dump the IFG | |
| 261 void dump() const; | |
| 262 void stats() const; | |
| 263 void verify( const PhaseChaitin * ) const; | |
| 264 #endif | |
| 265 | |
| 266 //--------------- Live Range Accessors | |
| 267 LRG &lrgs(uint idx) const { assert(idx < _maxlrg, "oob"); return _lrgs[idx]; } | |
| 268 | |
| 269 // Compute and set effective degree. Might be folded into SquareUp(). | |
| 270 void Compute_Effective_Degree(); | |
| 271 | |
| 272 // Compute effective degree as the sum of neighbors' _sizes. | |
| 273 int effective_degree( uint lidx ) const; | |
| 274 }; | |
| 275 | |
| 10111 | 276 // The LiveRangeMap class is responsible for storing node to live range id mapping. |
| 277 // Each node is mapped to a live range id (a virtual register). Nodes that are | |
| 278 // not considered for register allocation are given live range id 0. | |
| 279 class LiveRangeMap VALUE_OBJ_CLASS_SPEC { | |
| 280 | |
| 281 private: | |
| 282 | |
| 283 uint _max_lrg_id; | |
| 284 | |
| 285 // Union-find map. Declared as a short for speed. | |
| 286 // Indexed by live-range number, it returns the compacted live-range number | |
| 287 LRG_List _uf_map; | |
| 288 | |
| 289 // Map from Nodes to live ranges | |
| 290 LRG_List _names; | |
| 291 | |
| 292 // Straight out of Tarjan's union-find algorithm | |
| 293 uint find_compress(const Node *node) { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
294 uint lrg_id = find_compress(_names.at(node->_idx)); |
|
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
295 _names.at_put(node->_idx, lrg_id); |
| 10111 | 296 return lrg_id; |
| 297 } | |
| 298 | |
| 299 uint find_compress(uint lrg); | |
| 300 | |
| 301 public: | |
| 302 | |
| 303 const LRG_List& names() { | |
| 304 return _names; | |
| 305 } | |
| 306 | |
| 307 uint max_lrg_id() const { | |
| 308 return _max_lrg_id; | |
| 309 } | |
| 310 | |
| 311 void set_max_lrg_id(uint max_lrg_id) { | |
| 312 _max_lrg_id = max_lrg_id; | |
| 313 } | |
| 314 | |
| 315 uint size() const { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
316 return _names.length(); |
| 10111 | 317 } |
| 318 | |
| 319 uint live_range_id(uint idx) const { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
320 return _names.at(idx); |
| 10111 | 321 } |
| 322 | |
| 323 uint live_range_id(const Node *node) const { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
324 return _names.at(node->_idx); |
| 10111 | 325 } |
| 326 | |
| 327 uint uf_live_range_id(uint lrg_id) const { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
328 return _uf_map.at(lrg_id); |
| 10111 | 329 } |
| 0 | 330 |
| 10111 | 331 void map(uint idx, uint lrg_id) { |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
332 _names.at_put(idx, lrg_id); |
| 10111 | 333 } |
| 334 | |
| 335 void uf_map(uint dst_lrg_id, uint src_lrg_id) { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
336 _uf_map.at_put(dst_lrg_id, src_lrg_id); |
| 10111 | 337 } |
| 338 | |
| 339 void extend(uint idx, uint lrg_id) { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
340 _names.at_put_grow(idx, lrg_id); |
| 10111 | 341 } |
| 342 | |
| 343 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
344 _uf_map.at_put_grow(dst_lrg_id, src_lrg_id); |
| 10111 | 345 } |
| 346 | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
347 LiveRangeMap(Arena* arena, uint unique) |
|
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
348 : _names(arena, unique, unique, 0) |
|
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
349 , _uf_map(arena, unique, unique, 0) |
| 10111 | 350 , _max_lrg_id(0) {} |
| 351 | |
| 352 uint find_id( const Node *n ) { | |
| 353 uint retval = live_range_id(n); | |
| 354 assert(retval == find(n),"Invalid node to lidx mapping"); | |
| 355 return retval; | |
| 356 } | |
| 357 | |
| 358 // Reset the Union-Find map to identity | |
| 359 void reset_uf_map(uint max_lrg_id); | |
| 360 | |
| 361 // Make all Nodes map directly to their final live range; no need for | |
| 362 // the Union-Find mapping after this call. | |
| 363 void compress_uf_map_for_nodes(); | |
| 364 | |
| 365 uint find(uint lidx) { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
366 uint uf_lidx = _uf_map.at(lidx); |
| 10111 | 367 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); |
| 368 } | |
| 369 | |
| 370 // Convert a Node into a Live Range Index - a lidx | |
| 371 uint find(const Node *node) { | |
| 372 uint lidx = live_range_id(node); | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
373 uint uf_lidx = _uf_map.at(lidx); |
| 10111 | 374 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); |
| 375 } | |
| 376 | |
| 377 // Like Find above, but no path compress, so bad asymptotic behavior | |
| 378 uint find_const(uint lrg) const; | |
| 379 | |
| 380 // Like Find above, but no path compress, so bad asymptotic behavior | |
| 381 uint find_const(const Node *node) const { | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
382 if(node->_idx >= (uint)_names.length()) { |
| 10111 | 383 return 0; // not mapped, usual for debug dump |
| 384 } | |
|
12254
8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
adlertz
parents:
12075
diff
changeset
|
385 return find_const(_names.at(node->_idx)); |
| 10111 | 386 } |
| 387 }; | |
| 0 | 388 |
| 389 //------------------------------Chaitin---------------------------------------- | |
| 390 // Briggs-Chaitin style allocation, mostly. | |
| 391 class PhaseChaitin : public PhaseRegAlloc { | |
| 3939 | 392 friend class VMStructs; |
| 0 | 393 |
| 394 int _trip_cnt; | |
| 395 int _alternate; | |
| 396 | |
| 397 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); } | |
| 398 PhaseLive *_live; // Liveness, used in the interference graph | |
| 399 PhaseIFG *_ifg; // Interference graph (for original chunk) | |
| 400 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill | |
| 401 VectorSet _spilled_once; // Nodes that have been spilled | |
| 402 VectorSet _spilled_twice; // Nodes that have been spilled twice | |
| 403 | |
| 404 // Combine the Live Range Indices for these 2 Nodes into a single live | |
| 405 // range. Future requests for any Node in either live range will | |
| 406 // return the live range index for the combined live range. | |
| 407 void Union( const Node *src, const Node *dst ); | |
| 408 | |
| 409 void new_lrg( const Node *x, uint lrg ); | |
| 410 | |
| 411 // Compact live ranges, removing unused ones. Return new maxlrg. | |
| 412 void compact(); | |
| 413 | |
| 414 uint _lo_degree; // Head of lo-degree LRGs list | |
| 415 uint _lo_stk_degree; // Head of lo-stk-degree LRGs list | |
| 416 uint _hi_degree; // Head of hi-degree LRGs list | |
| 417 uint _simplified; // Linked list head of simplified LRGs | |
| 418 | |
| 419 // Helper functions for Split() | |
| 420 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); | |
| 421 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); | |
| 10111 | 422 |
| 423 //------------------------------clone_projs------------------------------------ | |
| 424 // After cloning some rematerialized instruction, clone any MachProj's that | |
| 425 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants | |
| 426 // use G3 as an address temp. | |
|
12075
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
427 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, uint& max_lrg_id); |
| 10111 | 428 |
|
12075
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
429 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, LiveRangeMap& lrg_map) { |
|
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
430 uint max_lrg_id = lrg_map.max_lrg_id(); |
|
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
431 int found_projs = clone_projs(b, idx, orig, copy, max_lrg_id); |
|
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
432 if (found_projs > 0) { |
|
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
433 // max_lrg_id is updated during call above |
|
4b2838704fd5
8021898: Broken JIT compiler optimization for loop unswitching
kvn
parents:
10111
diff
changeset
|
434 lrg_map.set_max_lrg_id(max_lrg_id); |
| 10111 | 435 } |
| 436 return found_projs; | |
| 437 } | |
| 438 | |
|
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
196
diff
changeset
|
439 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, |
|
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
196
diff
changeset
|
440 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); |
| 0 | 441 // True if lidx is used before any real register is def'd in the block |
| 442 bool prompt_use( Block *b, uint lidx ); | |
| 443 Node *get_spillcopy_wide( Node *def, Node *use, uint uidx ); | |
| 605 | 444 // Insert the spill at chosen location. Skip over any intervening Proj's or |
| 0 | 445 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block |
| 446 // instead. Update high-pressure indices. Create a new live range. | |
| 447 void insert_proj( Block *b, uint i, Node *spill, uint maxlrg ); | |
| 448 | |
| 449 bool is_high_pressure( Block *b, LRG *lrg, uint insidx ); | |
| 450 | |
| 451 uint _oldphi; // Node index which separates pre-allocation nodes | |
| 452 | |
| 453 Block **_blks; // Array of blocks sorted by frequency for coalescing | |
| 454 | |
| 673 | 455 float _high_frequency_lrg; // Frequency at which LRG will be spilled for debug info |
| 456 | |
| 0 | 457 #ifndef PRODUCT |
| 458 bool _trace_spilling; | |
| 459 #endif | |
| 460 | |
| 461 public: | |
| 462 PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher ); | |
| 463 ~PhaseChaitin() {} | |
| 464 | |
| 10111 | 465 LiveRangeMap _lrg_map; |
| 0 | 466 |
| 467 // Do all the real work of allocate | |
| 468 void Register_Allocate(); | |
| 469 | |
| 673 | 470 float high_frequency_lrg() const { return _high_frequency_lrg; } |
| 471 | |
| 0 | 472 #ifndef PRODUCT |
| 473 bool trace_spilling() const { return _trace_spilling; } | |
| 474 #endif | |
| 475 | |
| 476 private: | |
| 477 // De-SSA the world. Assign registers to Nodes. Use the same register for | |
| 478 // all inputs to a PhiNode, effectively coalescing live ranges. Insert | |
| 479 // copies as needed. | |
| 480 void de_ssa(); | |
| 481 | |
| 482 // Add edge between reg and everything in the vector. | |
| 483 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask | |
| 484 // information to trim the set of interferences. Return the | |
| 485 // count of edges added. | |
| 486 void interfere_with_live( uint reg, IndexSet *live ); | |
| 487 // Count register pressure for asserts | |
| 488 uint count_int_pressure( IndexSet *liveout ); | |
| 489 uint count_float_pressure( IndexSet *liveout ); | |
| 490 | |
| 491 // Build the interference graph using virtual registers only. | |
| 492 // Used for aggressive coalescing. | |
| 493 void build_ifg_virtual( ); | |
| 494 | |
| 495 // Build the interference graph using physical registers when available. | |
| 496 // That is, if 2 live ranges are simultaneously alive but in their | |
| 497 // acceptable register sets do not overlap, then they do not interfere. | |
| 498 uint build_ifg_physical( ResourceArea *a ); | |
| 499 | |
| 500 // Gather LiveRanGe information, including register masks and base pointer/ | |
| 501 // derived pointer relationships. | |
| 502 void gather_lrg_masks( bool mod_cisc_masks ); | |
| 503 | |
| 504 // Force the bases of derived pointers to be alive at GC points. | |
| 505 bool stretch_base_pointer_live_ranges( ResourceArea *a ); | |
| 506 // Helper to stretch above; recursively discover the base Node for | |
| 507 // a given derived Node. Easy for AddP-related machine nodes, but | |
| 508 // needs to be recursive for derived Phis. | |
| 509 Node *find_base_for_derived( Node **derived_base_map, Node *derived, uint &maxlrg ); | |
| 510 | |
| 511 // Set the was-lo-degree bit. Conservative coalescing should not change the | |
| 512 // colorability of the graph. If any live range was of low-degree before | |
| 513 // coalescing, it should Simplify. This call sets the was-lo-degree bit. | |
| 514 void set_was_low(); | |
| 515 | |
| 516 // Split live-ranges that must spill due to register conflicts (as opposed | |
| 517 // to capacity spills). Typically these are things def'd in a register | |
| 518 // and used on the stack or vice-versa. | |
| 519 void pre_spill(); | |
| 520 | |
| 521 // Init LRG caching of degree, numregs. Init lo_degree list. | |
| 522 void cache_lrg_info( ); | |
| 523 | |
| 524 // Simplify the IFG by removing LRGs of low degree with no copies | |
| 525 void Pre_Simplify(); | |
| 526 | |
| 527 // Simplify the IFG by removing LRGs of low degree | |
| 528 void Simplify(); | |
| 529 | |
| 530 // Select colors by re-inserting edges into the IFG. | |
| 605 | 531 // Return TRUE if any spills occurred. |
| 0 | 532 uint Select( ); |
| 533 // Helper function for select which allows biased coloring | |
| 534 OptoReg::Name choose_color( LRG &lrg, int chunk ); | |
| 535 // Helper function which implements biasing heuristic | |
| 536 OptoReg::Name bias_color( LRG &lrg, int chunk ); | |
| 537 | |
| 538 // Split uncolorable live ranges | |
| 539 // Return new number of live ranges | |
| 6632 | 540 uint Split(uint maxlrg, ResourceArea* split_arena); |
| 0 | 541 |
| 542 // Copy 'was_spilled'-edness from one Node to another. | |
| 543 void copy_was_spilled( Node *src, Node *dst ); | |
| 544 // Set the 'spilled_once' or 'spilled_twice' flag on a node. | |
| 545 void set_was_spilled( Node *n ); | |
| 546 | |
| 547 // Convert ideal spill-nodes into machine loads & stores | |
| 548 // Set C->failing when fixup spills could not complete, node limit exceeded. | |
| 549 void fixup_spills(); | |
| 550 | |
| 551 // Post-Allocation peephole copy removal | |
| 552 void post_allocate_copy_removal(); | |
| 553 Node *skip_copies( Node *c ); | |
| 923 | 554 // Replace the old node with the current live version of that value |
| 555 // and yank the old value if it's dead. | |
| 556 int replace_and_yank_if_dead( Node *old, OptoReg::Name nreg, | |
| 557 Block *current_block, Node_List& value, Node_List& regnd ) { | |
| 558 Node* v = regnd[nreg]; | |
| 559 assert(v->outcnt() != 0, "no dead values"); | |
| 560 old->replace_by(v); | |
| 561 return yank_if_dead(old, current_block, &value, ®nd); | |
| 562 } | |
| 563 | |
|
4776
5da7201222d5
7110824: ctw/jarfiles/GUI3rdParty_jar/ob_mask_DateField crashes VM
kvn
parents:
3939
diff
changeset
|
564 int yank_if_dead( Node *old, Block *current_block, Node_List *value, Node_List *regnd ) { |
|
5da7201222d5
7110824: ctw/jarfiles/GUI3rdParty_jar/ob_mask_DateField crashes VM
kvn
parents:
3939
diff
changeset
|
565 return yank_if_dead_recurse(old, old, current_block, value, regnd); |
|
5da7201222d5
7110824: ctw/jarfiles/GUI3rdParty_jar/ob_mask_DateField crashes VM
kvn
parents:
3939
diff
changeset
|
566 } |
|
5da7201222d5
7110824: ctw/jarfiles/GUI3rdParty_jar/ob_mask_DateField crashes VM
kvn
parents:
3939
diff
changeset
|
567 int yank_if_dead_recurse(Node *old, Node *orig_old, Block *current_block, |
|
5da7201222d5
7110824: ctw/jarfiles/GUI3rdParty_jar/ob_mask_DateField crashes VM
kvn
parents:
3939
diff
changeset
|
568 Node_List *value, Node_List *regnd); |
|
3934
8f47d8870d9a
7087453: PhaseChaitin::yank_if_dead() should handle MachTemp inputs
roland
parents:
2016
diff
changeset
|
569 int yank( Node *old, Block *current_block, Node_List *value, Node_List *regnd ); |
| 0 | 570 int elide_copy( Node *n, int k, Block *current_block, Node_List &value, Node_List ®nd, bool can_change_regs ); |
| 571 int use_prior_register( Node *copy, uint idx, Node *def, Block *current_block, Node_List &value, Node_List ®nd ); | |
| 572 bool may_be_copy_of_callee( Node *def ) const; | |
| 573 | |
| 574 // If nreg already contains the same constant as val then eliminate it | |
|
70
b683f557224b
6661247: Internal bug in 32-bit HotSpot optimizer while bit manipulations
never
parents:
0
diff
changeset
|
575 bool eliminate_copy_of_constant(Node* val, Node* n, |
|
b683f557224b
6661247: Internal bug in 32-bit HotSpot optimizer while bit manipulations
never
parents:
0
diff
changeset
|
576 Block *current_block, Node_List& value, Node_List ®nd, |
| 0 | 577 OptoReg::Name nreg, OptoReg::Name nreg2); |
| 578 // Extend the node to LRG mapping | |
| 579 void add_reference( const Node *node, const Node *old_node); | |
| 580 | |
| 581 private: | |
| 582 | |
| 583 static int _final_loads, _final_stores, _final_copies, _final_memoves; | |
| 584 static double _final_load_cost, _final_store_cost, _final_copy_cost, _final_memove_cost; | |
| 585 static int _conserv_coalesce, _conserv_coalesce_pair; | |
| 586 static int _conserv_coalesce_trie, _conserv_coalesce_quad; | |
| 587 static int _post_alloc; | |
| 588 static int _lost_opp_pp_coalesce, _lost_opp_cflow_coalesce; | |
| 589 static int _used_cisc_instructions, _unused_cisc_instructions; | |
| 590 static int _allocator_attempts, _allocator_successes; | |
| 591 | |
| 592 #ifndef PRODUCT | |
| 593 static uint _high_pressure, _low_pressure; | |
| 594 | |
| 595 void dump() const; | |
| 596 void dump( const Node *n ) const; | |
| 597 void dump( const Block * b ) const; | |
| 598 void dump_degree_lists() const; | |
| 599 void dump_simplified() const; | |
|
2016
361783318e7e
7004940: CTW: assert(!def_outside->member(r)) failed: Use of external LRG overlaps the same LRG
never
parents:
1972
diff
changeset
|
600 void dump_lrg( uint lidx, bool defs_only) const; |
|
361783318e7e
7004940: CTW: assert(!def_outside->member(r)) failed: Use of external LRG overlaps the same LRG
never
parents:
1972
diff
changeset
|
601 void dump_lrg( uint lidx) const { |
|
361783318e7e
7004940: CTW: assert(!def_outside->member(r)) failed: Use of external LRG overlaps the same LRG
never
parents:
1972
diff
changeset
|
602 // dump defs and uses by default |
|
361783318e7e
7004940: CTW: assert(!def_outside->member(r)) failed: Use of external LRG overlaps the same LRG
never
parents:
1972
diff
changeset
|
603 dump_lrg(lidx, false); |
|
361783318e7e
7004940: CTW: assert(!def_outside->member(r)) failed: Use of external LRG overlaps the same LRG
never
parents:
1972
diff
changeset
|
604 } |
| 0 | 605 void dump_bb( uint pre_order ) const; |
| 606 | |
| 607 // Verify that base pointers and derived pointers are still sane | |
| 608 void verify_base_ptrs( ResourceArea *a ) const; | |
| 609 | |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
295
diff
changeset
|
610 void verify( ResourceArea *a, bool verify_ifg = false ) const; |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
295
diff
changeset
|
611 |
| 0 | 612 void dump_for_spill_split_recycle() const; |
| 613 | |
| 614 public: | |
| 615 void dump_frame() const; | |
| 616 char *dump_register( const Node *n, char *buf ) const; | |
| 617 private: | |
| 618 static void print_chaitin_statistics(); | |
| 619 #endif | |
| 620 friend class PhaseCoalesce; | |
| 621 friend class PhaseAggressiveCoalesce; | |
| 622 friend class PhaseConservativeCoalesce; | |
| 623 }; | |
| 1972 | 624 |
| 625 #endif // SHARE_VM_OPTO_CHAITIN_HPP |