Mercurial > hg > truffle
annotate src/share/vm/c1/c1_LinearScan.hpp @ 1721:413ad0331a0c
6977924: Changes for 6975078 produce build error with certain gcc versions
Summary: The changes introduced for 6975078 assign badHeapOopVal to the _allocation field in the ResourceObj class. In 32 bit linux builds with certain versions of gcc this assignment will be flagged as an error while compiling allocation.cpp. In 32 bit builds the constant value badHeapOopVal (which is cast to an intptr_t) is negative. The _allocation field is typed as an unsigned intptr_t and gcc catches this as an error.
Reviewed-by: jcoomes, ysr, phh
author | johnc |
---|---|
date | Wed, 18 Aug 2010 10:59:06 -0700 |
parents | b812ff5abc73 |
children | f02a8bbe6ed4 |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
337
diff
changeset
|
2 * Copyright (c) 2005, 2008, 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:
337
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
337
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:
337
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
25 class DebugInfoCache; | |
26 class FpuStackAllocator; | |
27 class IRScopeDebugInfo; | |
28 class Interval; | |
29 class IntervalWalker; | |
30 class LIRGenerator; | |
31 class LinearScan; | |
32 class MoveResolver; | |
33 class Range; | |
34 | |
35 define_array(IntervalArray, Interval*) | |
36 define_stack(IntervalList, IntervalArray) | |
37 | |
38 define_array(IntervalsArray, IntervalList*) | |
39 define_stack(IntervalsList, IntervalsArray) | |
40 | |
41 define_array(OopMapArray, OopMap*) | |
42 define_stack(OopMapList, OopMapArray) | |
43 | |
44 define_array(ScopeValueArray, ScopeValue*) | |
45 | |
46 define_array(LIR_OpListArray, LIR_OpList*); | |
47 define_stack(LIR_OpListStack, LIR_OpListArray); | |
48 | |
49 | |
50 enum IntervalUseKind { | |
51 // priority of use kinds must be ascending | |
52 noUse = 0, | |
53 loopEndMarker = 1, | |
54 shouldHaveRegister = 2, | |
55 mustHaveRegister = 3, | |
56 | |
57 firstValidKind = 1, | |
58 lastValidKind = 3 | |
59 }; | |
60 define_array(UseKindArray, IntervalUseKind) | |
61 define_stack(UseKindStack, UseKindArray) | |
62 | |
63 | |
64 enum IntervalKind { | |
65 fixedKind = 0, // interval pre-colored by LIR_Generator | |
66 anyKind = 1, // no register/memory allocated by LIR_Generator | |
67 nofKinds, | |
68 firstKind = fixedKind | |
69 }; | |
70 | |
71 | |
72 // during linear scan an interval is in one of four states in | |
73 enum IntervalState { | |
74 unhandledState = 0, // unhandled state (not processed yet) | |
75 activeState = 1, // life and is in a physical register | |
76 inactiveState = 2, // in a life time hole and is in a physical register | |
77 handledState = 3, // spilled or not life again | |
78 invalidState = -1 | |
79 }; | |
80 | |
81 | |
82 enum IntervalSpillState { | |
83 noDefinitionFound, // starting state of calculation: no definition found yet | |
84 oneDefinitionFound, // one definition has already been found. | |
85 // Note: two consecutive definitions are treated as one (e.g. consecutive move and add because of two-operand LIR form) | |
86 // the position of this definition is stored in _definition_pos | |
87 oneMoveInserted, // one spill move has already been inserted. | |
88 storeAtDefinition, // the interval should be stored immediately after its definition because otherwise | |
89 // there would be multiple redundant stores | |
90 startInMemory, // the interval starts in memory (e.g. method parameter), so a store is never necessary | |
91 noOptimization // the interval has more then one definition (e.g. resulting from phi moves), so stores to memory are not optimized | |
92 }; | |
93 | |
94 | |
95 #define for_each_interval_kind(kind) \ | |
96 for (IntervalKind kind = firstKind; kind < nofKinds; kind = (IntervalKind)(kind + 1)) | |
97 | |
98 #define for_each_visitor_mode(mode) \ | |
99 for (LIR_OpVisitState::OprMode mode = LIR_OpVisitState::firstMode; mode < LIR_OpVisitState::numModes; mode = (LIR_OpVisitState::OprMode)(mode + 1)) | |
100 | |
101 | |
102 class LinearScan : public CompilationResourceObj { | |
103 // declare classes used by LinearScan as friends because they | |
104 // need a wide variety of functions declared here | |
105 // | |
106 // Only the small interface to the rest of the compiler is public | |
107 friend class Interval; | |
108 friend class IntervalWalker; | |
109 friend class LinearScanWalker; | |
110 friend class FpuStackAllocator; | |
111 friend class MoveResolver; | |
112 friend class LinearScanStatistic; | |
113 friend class LinearScanTimers; | |
114 friend class RegisterVerifier; | |
115 | |
116 public: | |
117 enum { | |
118 any_reg = -1, | |
119 nof_cpu_regs = pd_nof_cpu_regs_linearscan, | |
120 nof_fpu_regs = pd_nof_fpu_regs_linearscan, | |
121 nof_xmm_regs = pd_nof_xmm_regs_linearscan, | |
122 nof_regs = nof_cpu_regs + nof_fpu_regs + nof_xmm_regs | |
123 }; | |
124 | |
125 private: | |
126 Compilation* _compilation; | |
127 IR* _ir; | |
128 LIRGenerator* _gen; | |
129 FrameMap* _frame_map; | |
130 | |
131 BlockList _cached_blocks; // cached list with all blocks in linear-scan order (only correct if original list keeps unchanged) | |
132 int _num_virtual_regs; // number of virtual registers (without new registers introduced because of splitting intervals) | |
133 bool _has_fpu_registers; // true if this method uses any floating point registers (and so fpu stack allocation is necessary) | |
134 int _num_calls; // total number of calls in this method | |
135 int _max_spills; // number of stack slots used for intervals allocated to memory | |
136 int _unused_spill_slot; // unused spill slot for a single-word value because of alignment of a double-word value | |
137 | |
138 IntervalList _intervals; // mapping from register number to interval | |
139 IntervalList* _new_intervals_from_allocation; // list with all intervals created during allocation when an existing interval is split | |
140 IntervalArray* _sorted_intervals; // intervals sorted by Interval::from() | |
141 | |
142 LIR_OpArray _lir_ops; // mapping from LIR_Op id to LIR_Op node | |
143 BlockBeginArray _block_of_op; // mapping from LIR_Op id to the BlockBegin containing this instruction | |
144 BitMap _has_info; // bit set for each LIR_Op id that has a CodeEmitInfo | |
145 BitMap _has_call; // bit set for each LIR_Op id that destroys all caller save registers | |
146 BitMap2D _interval_in_loop; // bit set for each virtual register that is contained in each loop | |
147 | |
148 // cached debug info to prevent multiple creation of same object | |
149 // TODO: cached scope values for registers could be static | |
150 ScopeValueArray _scope_value_cache; | |
151 | |
152 static ConstantOopWriteValue _oop_null_scope_value; | |
153 static ConstantIntValue _int_m1_scope_value; | |
154 static ConstantIntValue _int_0_scope_value; | |
155 static ConstantIntValue _int_1_scope_value; | |
156 static ConstantIntValue _int_2_scope_value; | |
157 | |
158 // accessors | |
159 IR* ir() const { return _ir; } | |
160 Compilation* compilation() const { return _compilation; } | |
161 LIRGenerator* gen() const { return _gen; } | |
162 FrameMap* frame_map() const { return _frame_map; } | |
163 | |
164 // unified bailout support | |
165 void bailout(const char* msg) const { compilation()->bailout(msg); } | |
166 bool bailed_out() const { return compilation()->bailed_out(); } | |
167 | |
168 // access to block list (sorted in linear scan order) | |
169 int block_count() const { assert(_cached_blocks.length() == ir()->linear_scan_order()->length(), "invalid cached block list"); return _cached_blocks.length(); } | |
170 BlockBegin* block_at(int idx) const { assert(_cached_blocks.at(idx) == ir()->linear_scan_order()->at(idx), "invalid cached block list"); return _cached_blocks.at(idx); } | |
171 | |
172 int num_virtual_regs() const { return _num_virtual_regs; } | |
173 // size of live_in and live_out sets of BasicBlocks (BitMap needs rounded size for iteration) | |
174 int live_set_size() const { return round_to(_num_virtual_regs, BitsPerWord); } | |
175 bool has_fpu_registers() const { return _has_fpu_registers; } | |
176 int num_loops() const { return ir()->num_loops(); } | |
177 bool is_interval_in_loop(int interval, int loop) const { return _interval_in_loop.at(interval, loop); } | |
178 | |
179 // handling of fpu stack allocation (platform dependent, needed for debug information generation) | |
304 | 180 #ifdef X86 |
0 | 181 FpuStackAllocator* _fpu_stack_allocator; |
182 bool use_fpu_stack_allocation() const { return UseSSE < 2 && has_fpu_registers(); } | |
183 #else | |
184 bool use_fpu_stack_allocation() const { return false; } | |
185 #endif | |
186 | |
187 | |
188 // access to interval list | |
189 int interval_count() const { return _intervals.length(); } | |
190 Interval* interval_at(int reg_num) const { return _intervals.at(reg_num); } | |
191 | |
192 IntervalList* new_intervals_from_allocation() const { return _new_intervals_from_allocation; } | |
193 | |
194 // access to LIR_Ops and Blocks indexed by op_id | |
195 int max_lir_op_id() const { assert(_lir_ops.length() > 0, "no operations"); return (_lir_ops.length() - 1) << 1; } | |
196 LIR_Op* lir_op_with_id(int op_id) const { assert(op_id >= 0 && op_id <= max_lir_op_id() && op_id % 2 == 0, "op_id out of range or not even"); return _lir_ops.at(op_id >> 1); } | |
197 BlockBegin* block_of_op_with_id(int op_id) const { assert(_block_of_op.length() > 0 && op_id >= 0 && op_id <= max_lir_op_id() + 1, "op_id out of range"); return _block_of_op.at(op_id >> 1); } | |
198 | |
199 bool is_block_begin(int op_id) { return op_id == 0 || block_of_op_with_id(op_id) != block_of_op_with_id(op_id - 1); } | |
200 bool covers_block_begin(int op_id_1, int op_id_2) { return block_of_op_with_id(op_id_1) != block_of_op_with_id(op_id_2); } | |
201 | |
202 bool has_call(int op_id) { assert(op_id % 2 == 0, "must be even"); return _has_call.at(op_id >> 1); } | |
203 bool has_info(int op_id) { assert(op_id % 2 == 0, "must be even"); return _has_info.at(op_id >> 1); } | |
204 | |
205 | |
206 // functions for converting LIR-Operands to register numbers | |
207 static bool is_valid_reg_num(int reg_num) { return reg_num >= 0; } | |
208 static int reg_num(LIR_Opr opr); | |
209 static int reg_numHi(LIR_Opr opr); | |
210 | |
211 // functions for classification of intervals | |
212 static bool is_precolored_interval(const Interval* i); | |
213 static bool is_virtual_interval(const Interval* i); | |
214 | |
215 static bool is_precolored_cpu_interval(const Interval* i); | |
216 static bool is_virtual_cpu_interval(const Interval* i); | |
217 static bool is_precolored_fpu_interval(const Interval* i); | |
218 static bool is_virtual_fpu_interval(const Interval* i); | |
219 | |
220 static bool is_in_fpu_register(const Interval* i); | |
221 static bool is_oop_interval(const Interval* i); | |
222 | |
223 | |
224 // General helper functions | |
225 int allocate_spill_slot(bool double_word); | |
226 void assign_spill_slot(Interval* it); | |
227 void propagate_spill_slots(); | |
228 | |
229 Interval* create_interval(int reg_num); | |
230 void append_interval(Interval* it); | |
231 void copy_register_flags(Interval* from, Interval* to); | |
232 | |
233 // platform dependent functions | |
234 static bool is_processed_reg_num(int reg_num); | |
235 static int num_physical_regs(BasicType type); | |
236 static bool requires_adjacent_regs(BasicType type); | |
237 static bool is_caller_save(int assigned_reg); | |
238 | |
239 // spill move optimization: eliminate moves from register to stack if | |
240 // stack slot is known to be correct | |
241 void change_spill_definition_pos(Interval* interval, int def_pos); | |
242 void change_spill_state(Interval* interval, int spill_pos); | |
243 static bool must_store_at_definition(const Interval* i); | |
244 void eliminate_spill_moves(); | |
245 | |
246 // Phase 1: number all instructions in all blocks | |
247 void number_instructions(); | |
248 | |
249 // Phase 2: compute local live sets separately for each block | |
250 // (sets live_gen and live_kill for each block) | |
251 // | |
252 // helper methods used by compute_local_live_sets() | |
253 void set_live_gen_kill(Value value, LIR_Op* op, BitMap& live_gen, BitMap& live_kill); | |
254 | |
255 void compute_local_live_sets(); | |
256 | |
257 // Phase 3: perform a backward dataflow analysis to compute global live sets | |
258 // (sets live_in and live_out for each block) | |
259 void compute_global_live_sets(); | |
260 | |
261 | |
262 // Phase 4: build intervals | |
263 // (fills the list _intervals) | |
264 // | |
265 // helper methods used by build_intervals() | |
266 void add_use (Value value, int from, int to, IntervalUseKind use_kind); | |
267 | |
268 void add_def (LIR_Opr opr, int def_pos, IntervalUseKind use_kind); | |
269 void add_use (LIR_Opr opr, int from, int to, IntervalUseKind use_kind); | |
270 void add_temp(LIR_Opr opr, int temp_pos, IntervalUseKind use_kind); | |
271 | |
272 void add_def (int reg_num, int def_pos, IntervalUseKind use_kind, BasicType type); | |
273 void add_use (int reg_num, int from, int to, IntervalUseKind use_kind, BasicType type); | |
274 void add_temp(int reg_num, int temp_pos, IntervalUseKind use_kind, BasicType type); | |
275 | |
276 // Add platform dependent kills for particular LIR ops. Can be used | |
277 // to add platform dependent behaviour for some operations. | |
278 void pd_add_temps(LIR_Op* op); | |
279 | |
280 IntervalUseKind use_kind_of_output_operand(LIR_Op* op, LIR_Opr opr); | |
281 IntervalUseKind use_kind_of_input_operand(LIR_Op* op, LIR_Opr opr); | |
282 void handle_method_arguments(LIR_Op* op); | |
283 void handle_doubleword_moves(LIR_Op* op); | |
284 void add_register_hints(LIR_Op* op); | |
285 | |
286 void build_intervals(); | |
287 | |
288 | |
289 // Phase 5: actual register allocation | |
290 // (Uses LinearScanWalker) | |
291 // | |
292 // helper functions for building a sorted list of intervals | |
293 NOT_PRODUCT(bool is_sorted(IntervalArray* intervals);) | |
294 static int interval_cmp(Interval** a, Interval** b); | |
295 void add_to_list(Interval** first, Interval** prev, Interval* interval); | |
296 void create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)); | |
297 | |
298 void sort_intervals_before_allocation(); | |
299 void sort_intervals_after_allocation(); | |
300 void allocate_registers(); | |
301 | |
302 | |
303 // Phase 6: resolve data flow | |
304 // (insert moves at edges between blocks if intervals have been split) | |
305 // | |
306 // helper functions for resolve_data_flow() | |
307 Interval* split_child_at_op_id(Interval* interval, int op_id, LIR_OpVisitState::OprMode mode); | |
308 Interval* interval_at_block_begin(BlockBegin* block, int reg_num); | |
309 Interval* interval_at_block_end(BlockBegin* block, int reg_num); | |
310 Interval* interval_at_op_id(int reg_num, int op_id); | |
311 void resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver); | |
312 void resolve_find_insert_pos(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver); | |
313 void resolve_data_flow(); | |
314 | |
315 void resolve_exception_entry(BlockBegin* block, int reg_num, MoveResolver &move_resolver); | |
316 void resolve_exception_entry(BlockBegin* block, MoveResolver &move_resolver); | |
317 void resolve_exception_edge(XHandler* handler, int throwing_op_id, int reg_num, Phi* phi, MoveResolver &move_resolver); | |
318 void resolve_exception_edge(XHandler* handler, int throwing_op_id, MoveResolver &move_resolver); | |
319 void resolve_exception_handlers(); | |
320 | |
321 // Phase 7: assign register numbers back to LIR | |
322 // (includes computation of debug information and oop maps) | |
323 // | |
324 // helper functions for assign_reg_num() | |
325 VMReg vm_reg_for_interval(Interval* interval); | |
326 VMReg vm_reg_for_operand(LIR_Opr opr); | |
327 | |
328 static LIR_Opr operand_for_interval(Interval* interval); | |
329 static LIR_Opr calc_operand_for_interval(const Interval* interval); | |
330 LIR_Opr canonical_spill_opr(Interval* interval); | |
331 | |
332 LIR_Opr color_lir_opr(LIR_Opr opr, int id, LIR_OpVisitState::OprMode); | |
333 | |
334 // methods used for oop map computation | |
335 IntervalWalker* init_compute_oop_maps(); | |
336 OopMap* compute_oop_map(IntervalWalker* iw, LIR_Op* op, CodeEmitInfo* info, bool is_call_site); | |
337 void compute_oop_map(IntervalWalker* iw, const LIR_OpVisitState &visitor, LIR_Op* op); | |
338 | |
339 // methods used for debug information computation | |
340 void init_compute_debug_info(); | |
341 | |
342 MonitorValue* location_for_monitor_index(int monitor_index); | |
343 LocationValue* location_for_name(int name, Location::Type loc_type); | |
344 | |
345 int append_scope_value_for_constant(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values); | |
346 int append_scope_value_for_operand(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values); | |
347 int append_scope_value(int op_id, Value value, GrowableArray<ScopeValue*>* scope_values); | |
348 | |
349 IRScopeDebugInfo* compute_debug_info_for_scope(int op_id, IRScope* cur_scope, ValueStack* cur_state, ValueStack* innermost_state, int cur_bci, int stack_end, int locks_end); | |
350 void compute_debug_info(CodeEmitInfo* info, int op_id); | |
351 | |
352 void assign_reg_num(LIR_OpList* instructions, IntervalWalker* iw); | |
353 void assign_reg_num(); | |
354 | |
355 | |
356 // Phase 8: fpu stack allocation | |
357 // (Used only on x86 when fpu operands are present) | |
358 void allocate_fpu_stack(); | |
359 | |
360 | |
361 // helper functions for printing state | |
362 #ifndef PRODUCT | |
363 static void print_bitmap(BitMap& bitmap); | |
364 void print_intervals(const char* label); | |
365 void print_lir(int level, const char* label, bool hir_valid = true); | |
366 #endif | |
367 | |
368 #ifdef ASSERT | |
369 // verification functions for allocation | |
370 // (check that all intervals have a correct register and that no registers are overwritten) | |
371 void verify(); | |
372 void verify_intervals(); | |
373 void verify_no_oops_in_fixed_intervals(); | |
374 void verify_constants(); | |
375 void verify_registers(); | |
376 #endif | |
377 | |
378 public: | |
379 // creation | |
380 LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map); | |
381 | |
382 // main entry function: perform linear scan register allocation | |
383 void do_linear_scan(); | |
384 | |
385 // accessors used by Compilation | |
386 int max_spills() const { return _max_spills; } | |
387 int num_calls() const { assert(_num_calls >= 0, "not set"); return _num_calls; } | |
388 | |
389 // entry functions for printing | |
390 #ifndef PRODUCT | |
391 static void print_statistics(); | |
392 static void print_timers(double total); | |
393 #endif | |
394 }; | |
395 | |
396 | |
397 // Helper class for ordering moves that are inserted at the same position in the LIR | |
398 // When moves between registers are inserted, it is important that the moves are | |
399 // ordered such that no register is overwritten. So moves from register to stack | |
400 // are processed prior to moves from stack to register. When moves have circular | |
401 // dependencies, a temporary stack slot is used to break the circle. | |
402 // The same logic is used in the LinearScanWalker and in LinearScan during resolve_data_flow | |
403 // and therefore factored out in a separate class | |
404 class MoveResolver: public StackObj { | |
405 private: | |
406 LinearScan* _allocator; | |
407 | |
408 LIR_List* _insert_list; | |
409 int _insert_idx; | |
410 LIR_InsertionBuffer _insertion_buffer; // buffer where moves are inserted | |
411 | |
412 IntervalList _mapping_from; | |
413 LIR_OprList _mapping_from_opr; | |
414 IntervalList _mapping_to; | |
415 bool _multiple_reads_allowed; | |
416 int _register_blocked[LinearScan::nof_regs]; | |
417 | |
418 int register_blocked(int reg) { assert(reg >= 0 && reg < LinearScan::nof_regs, "out of bounds"); return _register_blocked[reg]; } | |
419 void set_register_blocked(int reg, int direction) { assert(reg >= 0 && reg < LinearScan::nof_regs, "out of bounds"); assert(direction == 1 || direction == -1, "out of bounds"); _register_blocked[reg] += direction; } | |
420 | |
421 void block_registers(Interval* it); | |
422 void unblock_registers(Interval* it); | |
423 bool save_to_process_move(Interval* from, Interval* to); | |
424 | |
425 void create_insertion_buffer(LIR_List* list); | |
426 void append_insertion_buffer(); | |
427 void insert_move(Interval* from_interval, Interval* to_interval); | |
428 void insert_move(LIR_Opr from_opr, Interval* to_interval); | |
429 | |
430 DEBUG_ONLY(void verify_before_resolve();) | |
431 void resolve_mappings(); | |
432 public: | |
433 MoveResolver(LinearScan* allocator); | |
434 | |
435 DEBUG_ONLY(void check_empty();) | |
436 void set_multiple_reads_allowed() { _multiple_reads_allowed = true; } | |
437 void set_insert_position(LIR_List* insert_list, int insert_idx); | |
438 void move_insert_position(LIR_List* insert_list, int insert_idx); | |
439 void add_mapping(Interval* from, Interval* to); | |
440 void add_mapping(LIR_Opr from, Interval* to); | |
441 void resolve_and_append_moves(); | |
442 | |
443 LinearScan* allocator() { return _allocator; } | |
444 bool has_mappings() { return _mapping_from.length() > 0; } | |
445 }; | |
446 | |
447 | |
448 class Range : public CompilationResourceObj { | |
449 friend class Interval; | |
450 | |
451 private: | |
452 static Range* _end; // sentinel (from == to == max_jint) | |
453 | |
454 int _from; // from (inclusive) | |
455 int _to; // to (exclusive) | |
456 Range* _next; // linear list of Ranges | |
457 | |
458 // used only by class Interval, so hide them | |
459 bool intersects(Range* r) const { return intersects_at(r) != -1; } | |
460 int intersects_at(Range* r) const; | |
461 | |
462 public: | |
463 Range(int from, int to, Range* next); | |
464 | |
1584 | 465 static void initialize(Arena* arena); |
0 | 466 static Range* end() { return _end; } |
467 | |
468 int from() const { return _from; } | |
469 int to() const { return _to; } | |
470 Range* next() const { return _next; } | |
471 void set_from(int from) { _from = from; } | |
472 void set_to(int to) { _to = to; } | |
473 void set_next(Range* next) { _next = next; } | |
474 | |
475 // for testing | |
476 void print(outputStream* out = tty) const PRODUCT_RETURN; | |
477 }; | |
478 | |
479 | |
480 // Interval is an ordered list of disjoint ranges. | |
481 | |
482 // For pre-colored double word LIR_Oprs, one interval is created for | |
483 // the low word register and one is created for the hi word register. | |
484 // On Intel for FPU double registers only one interval is created. At | |
485 // all times assigned_reg contains the reg. number of the physical | |
486 // register. | |
487 | |
488 // For LIR_Opr in virtual registers a single interval can represent | |
489 // single and double word values. When a physical register is | |
490 // assigned to the interval, assigned_reg contains the | |
491 // phys. reg. number and for double word values assigned_regHi the | |
492 // phys. reg. number of the hi word if there is any. For spilled | |
493 // intervals assigned_reg contains the stack index. assigned_regHi is | |
494 // always -1. | |
495 | |
496 class Interval : public CompilationResourceObj { | |
497 private: | |
498 static Interval* _end; // sentinel (interval with only range Range::end()) | |
499 | |
500 int _reg_num; | |
501 BasicType _type; // valid only for virtual registers | |
502 Range* _first; // sorted list of Ranges | |
503 intStack _use_pos_and_kinds; // sorted list of use-positions and their according use-kinds | |
504 | |
505 Range* _current; // interval iteration: the current Range | |
506 Interval* _next; // interval iteration: sorted list of Intervals (ends with sentinel) | |
507 IntervalState _state; // interval iteration: to which set belongs this interval | |
508 | |
509 | |
510 int _assigned_reg; | |
511 int _assigned_regHi; | |
512 | |
513 int _cached_to; // cached value: to of last range (-1: not cached) | |
514 LIR_Opr _cached_opr; | |
515 VMReg _cached_vm_reg; | |
516 | |
517 Interval* _split_parent; // the original interval where this interval is derived from | |
518 IntervalList _split_children; // list of all intervals that are split off from this interval (only available for split parents) | |
519 Interval* _current_split_child; // the current split child that has been active or inactive last (always stored in split parents) | |
520 | |
521 int _canonical_spill_slot; // the stack slot where all split parts of this interval are spilled to (always stored in split parents) | |
522 bool _insert_move_when_activated; // true if move is inserted between _current_split_child and this interval when interval gets active the first time | |
523 IntervalSpillState _spill_state; // for spill move optimization | |
524 int _spill_definition_pos; // position where the interval is defined (if defined only once) | |
525 Interval* _register_hint; // this interval should be in the same register as the hint interval | |
526 | |
527 int calc_to(); | |
528 Interval* new_split_child(); | |
529 public: | |
530 Interval(int reg_num); | |
531 | |
1584 | 532 static void initialize(Arena* arena); |
0 | 533 static Interval* end() { return _end; } |
534 | |
535 // accessors | |
536 int reg_num() const { return _reg_num; } | |
537 void set_reg_num(int r) { assert(_reg_num == -1, "cannot change reg_num"); _reg_num = r; } | |
538 BasicType type() const { assert(_reg_num == -1 || _reg_num >= LIR_OprDesc::vreg_base, "cannot access type for fixed interval"); return _type; } | |
539 void set_type(BasicType type) { assert(_reg_num < LIR_OprDesc::vreg_base || _type == T_ILLEGAL || _type == type, "overwriting existing type"); _type = type; } | |
540 | |
541 Range* first() const { return _first; } | |
542 int from() const { return _first->from(); } | |
543 int to() { if (_cached_to == -1) _cached_to = calc_to(); assert(_cached_to == calc_to(), "invalid cached value"); return _cached_to; } | |
544 int num_use_positions() const { return _use_pos_and_kinds.length() / 2; } | |
545 | |
546 Interval* next() const { return _next; } | |
547 Interval** next_addr() { return &_next; } | |
548 void set_next(Interval* next) { _next = next; } | |
549 | |
550 int assigned_reg() const { return _assigned_reg; } | |
551 int assigned_regHi() const { return _assigned_regHi; } | |
552 void assign_reg(int reg) { _assigned_reg = reg; _assigned_regHi = LinearScan::any_reg; } | |
553 void assign_reg(int reg,int regHi) { _assigned_reg = reg; _assigned_regHi = regHi; } | |
554 | |
555 Interval* register_hint(bool search_split_child = true) const; // calculation needed | |
556 void set_register_hint(Interval* i) { _register_hint = i; } | |
557 | |
558 int state() const { return _state; } | |
559 void set_state(IntervalState s) { _state = s; } | |
560 | |
561 // access to split parent and split children | |
562 bool is_split_parent() const { return _split_parent == this; } | |
563 bool is_split_child() const { return _split_parent != this; } | |
564 Interval* split_parent() const { assert(_split_parent->is_split_parent(), "must be"); return _split_parent; } | |
565 Interval* split_child_at_op_id(int op_id, LIR_OpVisitState::OprMode mode); | |
566 Interval* split_child_before_op_id(int op_id); | |
567 bool split_child_covers(int op_id, LIR_OpVisitState::OprMode mode); | |
568 DEBUG_ONLY(void check_split_children();) | |
569 | |
570 // information stored in split parent, but available for all children | |
571 int canonical_spill_slot() const { return split_parent()->_canonical_spill_slot; } | |
572 void set_canonical_spill_slot(int slot) { assert(split_parent()->_canonical_spill_slot == -1, "overwriting existing value"); split_parent()->_canonical_spill_slot = slot; } | |
573 Interval* current_split_child() const { return split_parent()->_current_split_child; } | |
574 void make_current_split_child() { split_parent()->_current_split_child = this; } | |
575 | |
576 bool insert_move_when_activated() const { return _insert_move_when_activated; } | |
577 void set_insert_move_when_activated(bool b) { _insert_move_when_activated = b; } | |
578 | |
579 // for spill optimization | |
580 IntervalSpillState spill_state() const { return split_parent()->_spill_state; } | |
581 int spill_definition_pos() const { return split_parent()->_spill_definition_pos; } | |
582 void set_spill_state(IntervalSpillState state) { assert(state >= spill_state(), "state cannot decrease"); split_parent()->_spill_state = state; } | |
583 void set_spill_definition_pos(int pos) { assert(spill_definition_pos() == -1, "cannot set the position twice"); split_parent()->_spill_definition_pos = pos; } | |
584 // returns true if this interval has a shadow copy on the stack that is always correct | |
585 bool always_in_memory() const { return split_parent()->_spill_state == storeAtDefinition || split_parent()->_spill_state == startInMemory; } | |
586 | |
587 // caching of values that take time to compute and are used multiple times | |
588 LIR_Opr cached_opr() const { return _cached_opr; } | |
589 VMReg cached_vm_reg() const { return _cached_vm_reg; } | |
590 void set_cached_opr(LIR_Opr opr) { _cached_opr = opr; } | |
591 void set_cached_vm_reg(VMReg reg) { _cached_vm_reg = reg; } | |
592 | |
593 // access to use positions | |
594 int first_usage(IntervalUseKind min_use_kind) const; // id of the first operation requiring this interval in a register | |
595 int next_usage(IntervalUseKind min_use_kind, int from) const; // id of next usage seen from the given position | |
596 int next_usage_exact(IntervalUseKind exact_use_kind, int from) const; | |
597 int previous_usage(IntervalUseKind min_use_kind, int from) const; | |
598 | |
599 // manipulating intervals | |
600 void add_use_pos(int pos, IntervalUseKind use_kind); | |
601 void add_range(int from, int to); | |
602 Interval* split(int split_pos); | |
603 Interval* split_from_start(int split_pos); | |
604 void remove_first_use_pos() { _use_pos_and_kinds.truncate(_use_pos_and_kinds.length() - 2); } | |
605 | |
606 // test intersection | |
607 bool covers(int op_id, LIR_OpVisitState::OprMode mode) const; | |
608 bool has_hole_between(int from, int to); | |
609 bool intersects(Interval* i) const { return _first->intersects(i->_first); } | |
610 int intersects_at(Interval* i) const { return _first->intersects_at(i->_first); } | |
611 | |
612 // range iteration | |
613 void rewind_range() { _current = _first; } | |
614 void next_range() { assert(this != _end, "not allowed on sentinel"); _current = _current->next(); } | |
615 int current_from() const { return _current->from(); } | |
616 int current_to() const { return _current->to(); } | |
617 bool current_at_end() const { return _current == Range::end(); } | |
618 bool current_intersects(Interval* it) { return _current->intersects(it->_current); }; | |
619 int current_intersects_at(Interval* it) { return _current->intersects_at(it->_current); }; | |
620 | |
621 // printing | |
622 void print(outputStream* out = tty) const PRODUCT_RETURN; | |
623 }; | |
624 | |
625 | |
626 class IntervalWalker : public CompilationResourceObj { | |
627 protected: | |
628 Compilation* _compilation; | |
629 LinearScan* _allocator; | |
630 | |
631 Interval* _unhandled_first[nofKinds]; // sorted list of intervals, not life before the current position | |
632 Interval* _active_first [nofKinds]; // sorted list of intervals, life at the current position | |
633 Interval* _inactive_first [nofKinds]; // sorted list of intervals, intervals in a life time hole at the current position | |
634 | |
635 Interval* _current; // the current interval coming from unhandled list | |
636 int _current_position; // the current position (intercept point through the intervals) | |
637 IntervalKind _current_kind; // and whether it is fixed_kind or any_kind. | |
638 | |
639 | |
640 Compilation* compilation() const { return _compilation; } | |
641 LinearScan* allocator() const { return _allocator; } | |
642 | |
643 // unified bailout support | |
644 void bailout(const char* msg) const { compilation()->bailout(msg); } | |
645 bool bailed_out() const { return compilation()->bailed_out(); } | |
646 | |
647 void check_bounds(IntervalKind kind) { assert(kind >= fixedKind && kind <= anyKind, "invalid interval_kind"); } | |
648 | |
649 Interval** unhandled_first_addr(IntervalKind kind) { check_bounds(kind); return &_unhandled_first[kind]; } | |
650 Interval** active_first_addr(IntervalKind kind) { check_bounds(kind); return &_active_first[kind]; } | |
651 Interval** inactive_first_addr(IntervalKind kind) { check_bounds(kind); return &_inactive_first[kind]; } | |
652 | |
653 void append_unsorted(Interval** first, Interval* interval); | |
654 void append_sorted(Interval** first, Interval* interval); | |
655 void append_to_unhandled(Interval** list, Interval* interval); | |
656 | |
657 bool remove_from_list(Interval** list, Interval* i); | |
658 void remove_from_list(Interval* i); | |
659 | |
660 void next_interval(); | |
661 Interval* current() const { return _current; } | |
662 IntervalKind current_kind() const { return _current_kind; } | |
663 | |
664 void walk_to(IntervalState state, int from); | |
665 | |
666 // activate_current() is called when an unhandled interval becomes active (in current(), current_kind()). | |
667 // Return false if current() should not be moved the the active interval list. | |
668 // It is safe to append current to any interval list but the unhandled list. | |
669 virtual bool activate_current() { return true; } | |
670 | |
671 // interval_moved() is called whenever an interval moves from one interval list to another. | |
672 // In the implementation of this method it is prohibited to move the interval to any list. | |
673 virtual void interval_moved(Interval* interval, IntervalKind kind, IntervalState from, IntervalState to); | |
674 | |
675 public: | |
676 IntervalWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first); | |
677 | |
678 Interval* unhandled_first(IntervalKind kind) { check_bounds(kind); return _unhandled_first[kind]; } | |
679 Interval* active_first(IntervalKind kind) { check_bounds(kind); return _active_first[kind]; } | |
680 Interval* inactive_first(IntervalKind kind) { check_bounds(kind); return _inactive_first[kind]; } | |
681 | |
682 // active contains the intervals that are live after the lir_op | |
683 void walk_to(int lir_op_id); | |
684 // active contains the intervals that are live before the lir_op | |
685 void walk_before(int lir_op_id) { walk_to(lir_op_id-1); } | |
686 // walk through all intervals | |
687 void walk() { walk_to(max_jint); } | |
688 | |
689 int current_position() { return _current_position; } | |
690 }; | |
691 | |
692 | |
693 // The actual linear scan register allocator | |
694 class LinearScanWalker : public IntervalWalker { | |
695 enum { | |
696 any_reg = LinearScan::any_reg | |
697 }; | |
698 | |
699 private: | |
700 int _first_reg; // the reg. number of the first phys. register | |
701 int _last_reg; // the reg. nmber of the last phys. register | |
702 int _num_phys_regs; // required by current interval | |
703 bool _adjacent_regs; // have lo/hi words of phys. regs be adjacent | |
704 | |
705 int _use_pos[LinearScan::nof_regs]; | |
706 int _block_pos[LinearScan::nof_regs]; | |
707 IntervalList* _spill_intervals[LinearScan::nof_regs]; | |
708 | |
709 MoveResolver _move_resolver; // for ordering spill moves | |
710 | |
711 // accessors mapped to same functions in class LinearScan | |
712 int block_count() const { return allocator()->block_count(); } | |
713 BlockBegin* block_at(int idx) const { return allocator()->block_at(idx); } | |
714 BlockBegin* block_of_op_with_id(int op_id) const { return allocator()->block_of_op_with_id(op_id); } | |
715 | |
716 void init_use_lists(bool only_process_use_pos); | |
717 void exclude_from_use(int reg); | |
718 void exclude_from_use(Interval* i); | |
719 void set_use_pos(int reg, Interval* i, int use_pos, bool only_process_use_pos); | |
720 void set_use_pos(Interval* i, int use_pos, bool only_process_use_pos); | |
721 void set_block_pos(int reg, Interval* i, int block_pos); | |
722 void set_block_pos(Interval* i, int block_pos); | |
723 | |
724 void free_exclude_active_fixed(); | |
725 void free_exclude_active_any(); | |
726 void free_collect_inactive_fixed(Interval* cur); | |
727 void free_collect_inactive_any(Interval* cur); | |
728 void free_collect_unhandled(IntervalKind kind, Interval* cur); | |
729 void spill_exclude_active_fixed(); | |
730 void spill_block_unhandled_fixed(Interval* cur); | |
731 void spill_block_inactive_fixed(Interval* cur); | |
732 void spill_collect_active_any(); | |
733 void spill_collect_inactive_any(Interval* cur); | |
734 | |
735 void insert_move(int op_id, Interval* src_it, Interval* dst_it); | |
736 int find_optimal_split_pos(BlockBegin* min_block, BlockBegin* max_block, int max_split_pos); | |
737 int find_optimal_split_pos(Interval* it, int min_split_pos, int max_split_pos, bool do_loop_optimization); | |
738 void split_before_usage(Interval* it, int min_split_pos, int max_split_pos); | |
739 void split_for_spilling(Interval* it); | |
740 void split_stack_interval(Interval* it); | |
741 void split_when_partial_register_available(Interval* it, int register_available_until); | |
742 void split_and_spill_interval(Interval* it); | |
743 | |
744 int find_free_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split); | |
745 int find_free_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split); | |
746 bool alloc_free_reg(Interval* cur); | |
747 | |
748 int find_locked_reg(int reg_needed_until, int interval_to, int hint_reg, int ignore_reg, bool* need_split); | |
749 int find_locked_double_reg(int reg_needed_until, int interval_to, int hint_reg, bool* need_split); | |
750 void split_and_spill_intersecting_intervals(int reg, int regHi); | |
751 void alloc_locked_reg(Interval* cur); | |
752 | |
753 bool no_allocation_possible(Interval* cur); | |
754 void update_phys_reg_range(bool requires_cpu_register); | |
755 void init_vars_for_alloc(Interval* cur); | |
756 bool pd_init_regs_for_alloc(Interval* cur); | |
757 | |
758 void combine_spilled_intervals(Interval* cur); | |
759 bool is_move(LIR_Op* op, Interval* from, Interval* to); | |
760 | |
761 bool activate_current(); | |
762 | |
763 public: | |
764 LinearScanWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first); | |
765 | |
766 // must be called when all intervals are allocated | |
767 void finish_allocation() { _move_resolver.resolve_and_append_moves(); } | |
768 }; | |
769 | |
770 | |
771 | |
772 /* | |
773 When a block has more than one predecessor, and all predecessors end with | |
774 the same sequence of move-instructions, than this moves can be placed once | |
775 at the beginning of the block instead of multiple times in the predecessors. | |
776 | |
777 Similarly, when a block has more than one successor, then equal sequences of | |
778 moves at the beginning of the successors can be placed once at the end of | |
779 the block. But because the moves must be inserted before all branch | |
780 instructions, this works only when there is exactly one conditional branch | |
781 at the end of the block (because the moves must be inserted before all | |
782 branches, but after all compares). | |
783 | |
784 This optimization affects all kind of moves (reg->reg, reg->stack and | |
785 stack->reg). Because this optimization works best when a block contains only | |
786 few moves, it has a huge impact on the number of blocks that are totally | |
787 empty. | |
788 */ | |
789 class EdgeMoveOptimizer : public StackObj { | |
790 private: | |
791 // the class maintains a list with all lir-instruction-list of the | |
792 // successors (predecessors) and the current index into the lir-lists | |
793 LIR_OpListStack _edge_instructions; | |
794 intStack _edge_instructions_idx; | |
795 | |
796 void init_instructions(); | |
797 void append_instructions(LIR_OpList* instructions, int instructions_idx); | |
798 LIR_Op* instruction_at(int edge); | |
799 void remove_cur_instruction(int edge, bool decrement_index); | |
800 | |
801 bool operations_different(LIR_Op* op1, LIR_Op* op2); | |
802 | |
803 void optimize_moves_at_block_end(BlockBegin* cur); | |
804 void optimize_moves_at_block_begin(BlockBegin* cur); | |
805 | |
806 EdgeMoveOptimizer(); | |
807 | |
808 public: | |
809 static void optimize(BlockList* code); | |
810 }; | |
811 | |
812 | |
813 | |
814 class ControlFlowOptimizer : public StackObj { | |
815 private: | |
816 BlockList _original_preds; | |
817 | |
818 enum { | |
819 ShortLoopSize = 5 | |
820 }; | |
821 void reorder_short_loop(BlockList* code, BlockBegin* header_block, int header_idx); | |
822 void reorder_short_loops(BlockList* code); | |
823 | |
824 bool can_delete_block(BlockBegin* cur); | |
825 void substitute_branch_target(BlockBegin* cur, BlockBegin* target_from, BlockBegin* target_to); | |
826 void delete_empty_blocks(BlockList* code); | |
827 | |
828 void delete_unnecessary_jumps(BlockList* code); | |
829 void delete_jumps_to_return(BlockList* code); | |
830 | |
831 DEBUG_ONLY(void verify(BlockList* code);) | |
832 | |
833 ControlFlowOptimizer(); | |
834 public: | |
835 static void optimize(BlockList* code); | |
836 }; | |
837 | |
838 | |
839 #ifndef PRODUCT | |
840 | |
841 // Helper class for collecting statistics of LinearScan | |
842 class LinearScanStatistic : public StackObj { | |
843 public: | |
844 enum Counter { | |
845 // general counters | |
846 counter_method, | |
847 counter_fpu_method, | |
848 counter_loop_method, | |
849 counter_exception_method, | |
850 counter_loop, | |
851 counter_block, | |
852 counter_loop_block, | |
853 counter_exception_block, | |
854 counter_interval, | |
855 counter_fixed_interval, | |
856 counter_range, | |
857 counter_fixed_range, | |
858 counter_use_pos, | |
859 counter_fixed_use_pos, | |
860 counter_spill_slots, | |
861 blank_line_1, | |
862 | |
863 // counter for classes of lir instructions | |
864 counter_instruction, | |
865 counter_label, | |
866 counter_entry, | |
867 counter_return, | |
868 counter_call, | |
869 counter_move, | |
870 counter_cmp, | |
871 counter_cond_branch, | |
872 counter_uncond_branch, | |
873 counter_stub_branch, | |
874 counter_alu, | |
875 counter_alloc, | |
876 counter_sync, | |
877 counter_throw, | |
878 counter_unwind, | |
879 counter_typecheck, | |
880 counter_fpu_stack, | |
881 counter_misc_inst, | |
882 counter_other_inst, | |
883 blank_line_2, | |
884 | |
885 // counter for different types of moves | |
886 counter_move_total, | |
887 counter_move_reg_reg, | |
888 counter_move_reg_stack, | |
889 counter_move_stack_reg, | |
890 counter_move_stack_stack, | |
891 counter_move_reg_mem, | |
892 counter_move_mem_reg, | |
893 counter_move_const_any, | |
894 | |
895 number_of_counters, | |
896 invalid_counter = -1 | |
897 }; | |
898 | |
899 private: | |
900 int _counters_sum[number_of_counters]; | |
901 int _counters_max[number_of_counters]; | |
902 | |
903 void inc_counter(Counter idx, int value = 1) { _counters_sum[idx] += value; } | |
904 | |
905 const char* counter_name(int counter_idx); | |
906 Counter base_counter(int counter_idx); | |
907 | |
908 void sum_up(LinearScanStatistic &method_statistic); | |
909 void collect(LinearScan* allocator); | |
910 | |
911 public: | |
912 LinearScanStatistic(); | |
913 void print(const char* title); | |
914 static void compute(LinearScan* allocator, LinearScanStatistic &global_statistic); | |
915 }; | |
916 | |
917 | |
918 // Helper class for collecting compilation time of LinearScan | |
919 class LinearScanTimers : public StackObj { | |
920 public: | |
921 enum Timer { | |
922 timer_do_nothing, | |
923 timer_number_instructions, | |
924 timer_compute_local_live_sets, | |
925 timer_compute_global_live_sets, | |
926 timer_build_intervals, | |
927 timer_sort_intervals_before, | |
928 timer_allocate_registers, | |
929 timer_resolve_data_flow, | |
930 timer_sort_intervals_after, | |
931 timer_eliminate_spill_moves, | |
932 timer_assign_reg_num, | |
933 timer_allocate_fpu_stack, | |
934 timer_optimize_lir, | |
935 | |
936 number_of_timers | |
937 }; | |
938 | |
939 private: | |
940 elapsedTimer _timers[number_of_timers]; | |
941 const char* timer_name(int idx); | |
942 | |
943 public: | |
944 LinearScanTimers(); | |
945 | |
946 void begin_method(); // called for each method when register allocation starts | |
947 void end_method(LinearScan* allocator); // called for each method when register allocation completed | |
948 void print(double total_time); // called before termination of VM to print global summary | |
949 | |
950 elapsedTimer* timer(int idx) { return &(_timers[idx]); } | |
951 }; | |
952 | |
953 | |
954 #endif // ifndef PRODUCT | |
955 | |
956 | |
957 // Pick up platform-dependent implementation details | |
958 # include "incls/_c1_LinearScan_pd.hpp.incl" |