1 /*
2 * Copyright (c) 1997, 2010, 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 *
33 #include "opto/matcher.hpp"
34 #include "opto/phase.hpp"
35 #include "opto/regalloc.hpp"
36 #include "opto/regmask.hpp"
37
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 {
53 public:
54 enum { SPILL_REG=29999 }; // Register number of a spilled LRG
55
56 double _cost; // 2 for loads/1 for stores times block freq
57 double _area; // Sum of all simultaneously live values
58 double score() const; // Compute score from cost and area
59 double _maxfreq; // Maximum frequency of any def or use
60
61 Node *_def; // Check for multi-def live ranges
62 #ifndef PRODUCT
63 GrowableArray<Node*>* _defs;
64 #endif
65
66 uint _risk_bias; // Index of LRG which we want to avoid color
67 uint _copy_bias; // Index of LRG which we want to share color
68
69 uint _next; // Index of next LRG in linked list
70 uint _prev; // Index of prev LRG in linked list
71 private:
72 uint _reg; // Chosen register; undefined if mask is plural
164 _msize_valid:1, // _mask_size cache valid
165 _degree_valid:1, // _degree cache valid
166 _has_copy:1, // Adjacent to some copy instruction
167 _at_risk:1; // Simplify says this guy is at risk to spill
168
169
170 // Alive if non-zero, dead if zero
171 bool alive() const { return _def != NULL; }
172 bool is_multidef() const { return _def == NodeSentinel; }
173 bool is_singledef() const { return _def != NodeSentinel; }
174
175 #ifndef PRODUCT
176 void dump( ) const;
177 #endif
178 };
179
180 //------------------------------LRG_List---------------------------------------
181 // Map Node indices to Live RanGe indices.
182 // Array lookup in the optimized case.
183 class LRG_List : public ResourceObj {
184 uint _cnt, _max;
185 uint* _lidxs;
186 ReallocMark _nesting; // assertion check for reallocations
187 public:
188 LRG_List( uint max );
189
190 uint lookup( uint nidx ) const {
191 return _lidxs[nidx];
192 }
193 uint operator[] (uint nidx) const { return lookup(nidx); }
194
195 void map( uint nidx, uint lidx ) {
196 assert( nidx < _cnt, "oob" );
197 _lidxs[nidx] = lidx;
198 }
199 void extend( uint nidx, uint lidx );
200
201 uint Size() const { return _cnt; }
202 };
203
204 //------------------------------IFG--------------------------------------------
205 // InterFerence Graph
206 // An undirected graph implementation. Created with a fixed number of
207 // vertices. Edges can be added & tested. Vertices can be removed, then
208 // added back later with all edges intact. Can add edges between one vertex
209 // and a list of other vertices. Can union vertices (and their edges)
210 // together. The IFG needs to be really really fast, and also fairly
211 // abstract! It needs abstraction so I can fiddle with the implementation to
212 // get even more speed.
213 class PhaseIFG : public Phase {
214 // Current implementation: a triangular adjacency list.
215
216 // Array of adjacency-lists, indexed by live-range number
217 IndexSet *_adjs;
218
219 // Assertion bit for proper use of Squaring
220 bool _is_square;
221
222 // Live range structure goes here
223 LRG *_lrgs; // Array of LRG structures
224
225 public:
226 // Largest live-range number
227 uint _maxlrg;
228
229 Arena *_arena;
230
231 // Keep track of inserted and deleted Nodes
232 VectorSet *_yanked;
233
277 // Compute effective degree as the sum of neighbors' _sizes.
278 int effective_degree( uint lidx ) const;
279 };
280
281 // TEMPORARILY REPLACED WITH COMMAND LINE FLAG
282
283 //// !!!!! Magic Constants need to move into ad file
284 #ifdef SPARC
285 //#define FLOAT_PRESSURE 30 /* SFLT_REG_mask.Size() - 1 */
286 //#define INT_PRESSURE 23 /* NOTEMP_I_REG_mask.Size() - 1 */
287 #define FLOAT_INCREMENT(regs) regs
288 #else
289 //#define FLOAT_PRESSURE 6
290 //#define INT_PRESSURE 6
291 #define FLOAT_INCREMENT(regs) 1
292 #endif
293
294 //------------------------------Chaitin----------------------------------------
295 // Briggs-Chaitin style allocation, mostly.
296 class PhaseChaitin : public PhaseRegAlloc {
297
298 int _trip_cnt;
299 int _alternate;
300
301 uint _maxlrg; // Max live range number
302 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); }
303 PhaseLive *_live; // Liveness, used in the interference graph
304 PhaseIFG *_ifg; // Interference graph (for original chunk)
305 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill
306 VectorSet _spilled_once; // Nodes that have been spilled
307 VectorSet _spilled_twice; // Nodes that have been spilled twice
308
309 LRG_List _names; // Map from Nodes to Live RanGes
310
311 // Union-find map. Declared as a short for speed.
312 // Indexed by live-range number, it returns the compacted live-range number
313 LRG_List _uf_map;
314 // Reset the Union-Find map to identity
315 void reset_uf_map( uint maxlrg );
316 // Remove the need for the Union-Find mapping
|
1 /*
2 * Copyright (c) 1997, 2011, 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 *
33 #include "opto/matcher.hpp"
34 #include "opto/phase.hpp"
35 #include "opto/regalloc.hpp"
36 #include "opto/regmask.hpp"
37
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 {
53 friend class VMStructs;
54 public:
55 enum { SPILL_REG=29999 }; // Register number of a spilled LRG
56
57 double _cost; // 2 for loads/1 for stores times block freq
58 double _area; // Sum of all simultaneously live values
59 double score() const; // Compute score from cost and area
60 double _maxfreq; // Maximum frequency of any def or use
61
62 Node *_def; // Check for multi-def live ranges
63 #ifndef PRODUCT
64 GrowableArray<Node*>* _defs;
65 #endif
66
67 uint _risk_bias; // Index of LRG which we want to avoid color
68 uint _copy_bias; // Index of LRG which we want to share color
69
70 uint _next; // Index of next LRG in linked list
71 uint _prev; // Index of prev LRG in linked list
72 private:
73 uint _reg; // Chosen register; undefined if mask is plural
165 _msize_valid:1, // _mask_size cache valid
166 _degree_valid:1, // _degree cache valid
167 _has_copy:1, // Adjacent to some copy instruction
168 _at_risk:1; // Simplify says this guy is at risk to spill
169
170
171 // Alive if non-zero, dead if zero
172 bool alive() const { return _def != NULL; }
173 bool is_multidef() const { return _def == NodeSentinel; }
174 bool is_singledef() const { return _def != NodeSentinel; }
175
176 #ifndef PRODUCT
177 void dump( ) const;
178 #endif
179 };
180
181 //------------------------------LRG_List---------------------------------------
182 // Map Node indices to Live RanGe indices.
183 // Array lookup in the optimized case.
184 class LRG_List : public ResourceObj {
185 friend class VMStructs;
186 uint _cnt, _max;
187 uint* _lidxs;
188 ReallocMark _nesting; // assertion check for reallocations
189 public:
190 LRG_List( uint max );
191
192 uint lookup( uint nidx ) const {
193 return _lidxs[nidx];
194 }
195 uint operator[] (uint nidx) const { return lookup(nidx); }
196
197 void map( uint nidx, uint lidx ) {
198 assert( nidx < _cnt, "oob" );
199 _lidxs[nidx] = lidx;
200 }
201 void extend( uint nidx, uint lidx );
202
203 uint Size() const { return _cnt; }
204 };
205
206 //------------------------------IFG--------------------------------------------
207 // InterFerence Graph
208 // An undirected graph implementation. Created with a fixed number of
209 // vertices. Edges can be added & tested. Vertices can be removed, then
210 // added back later with all edges intact. Can add edges between one vertex
211 // and a list of other vertices. Can union vertices (and their edges)
212 // together. The IFG needs to be really really fast, and also fairly
213 // abstract! It needs abstraction so I can fiddle with the implementation to
214 // get even more speed.
215 class PhaseIFG : public Phase {
216 friend class VMStructs;
217 // Current implementation: a triangular adjacency list.
218
219 // Array of adjacency-lists, indexed by live-range number
220 IndexSet *_adjs;
221
222 // Assertion bit for proper use of Squaring
223 bool _is_square;
224
225 // Live range structure goes here
226 LRG *_lrgs; // Array of LRG structures
227
228 public:
229 // Largest live-range number
230 uint _maxlrg;
231
232 Arena *_arena;
233
234 // Keep track of inserted and deleted Nodes
235 VectorSet *_yanked;
236
280 // Compute effective degree as the sum of neighbors' _sizes.
281 int effective_degree( uint lidx ) const;
282 };
283
284 // TEMPORARILY REPLACED WITH COMMAND LINE FLAG
285
286 //// !!!!! Magic Constants need to move into ad file
287 #ifdef SPARC
288 //#define FLOAT_PRESSURE 30 /* SFLT_REG_mask.Size() - 1 */
289 //#define INT_PRESSURE 23 /* NOTEMP_I_REG_mask.Size() - 1 */
290 #define FLOAT_INCREMENT(regs) regs
291 #else
292 //#define FLOAT_PRESSURE 6
293 //#define INT_PRESSURE 6
294 #define FLOAT_INCREMENT(regs) 1
295 #endif
296
297 //------------------------------Chaitin----------------------------------------
298 // Briggs-Chaitin style allocation, mostly.
299 class PhaseChaitin : public PhaseRegAlloc {
300 friend class VMStructs;
301
302 int _trip_cnt;
303 int _alternate;
304
305 uint _maxlrg; // Max live range number
306 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); }
307 PhaseLive *_live; // Liveness, used in the interference graph
308 PhaseIFG *_ifg; // Interference graph (for original chunk)
309 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill
310 VectorSet _spilled_once; // Nodes that have been spilled
311 VectorSet _spilled_twice; // Nodes that have been spilled twice
312
313 LRG_List _names; // Map from Nodes to Live RanGes
314
315 // Union-find map. Declared as a short for speed.
316 // Indexed by live-range number, it returns the compacted live-range number
317 LRG_List _uf_map;
318 // Reset the Union-Find map to identity
319 void reset_uf_map( uint maxlrg );
320 // Remove the need for the Union-Find mapping
|