• file
• revisions
• annotate
• diff
• comparison
• raw

src/share/vm/compiler/methodLiveness.hpp@a9becfeecd1b (annotated)

src/share/vm/compiler/methodLiveness.hpp

Wed, 22 Jan 2014 17:42:23 -0800

author

kvn

date

Wed, 22 Jan 2014 17:42:23 -0800

changeset 6503

a9becfeecd1b

parent 2314

f95d63e2154a

child 6876

710a3c8b516e

permissions

-rw-r--r--

Merge

duke@435	1	/*
stefank@2314	2	* Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
duke@435	3	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435	4	*
duke@435	5	* This code is free software; you can redistribute it and/or modify it
duke@435	6	* under the terms of the GNU General Public License version 2 only, as
duke@435	7	* published by the Free Software Foundation.
duke@435	8	*
duke@435	9	* This code is distributed in the hope that it will be useful, but WITHOUT
duke@435	10	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435	11	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@435	12	* version 2 for more details (a copy is included in the LICENSE file that
duke@435	13	* accompanied this code).
duke@435	14	*
duke@435	15	* You should have received a copy of the GNU General Public License version
duke@435	16	* 2 along with this work; if not, write to the Free Software Foundation,
duke@435	17	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435	18	*
trims@1907	19	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@1907	20	* or visit www.oracle.com if you need additional information or have any
trims@1907	21	* questions.
duke@435	22	*
duke@435	23	*/
duke@435	24
stefank@2314	25	#ifndef SHARE_VM_COMPILER_METHODLIVENESS_HPP
stefank@2314	26	#define SHARE_VM_COMPILER_METHODLIVENESS_HPP
stefank@2314	27
stefank@2314	28	#include "utilities/bitMap.hpp"
stefank@2314	29	#include "utilities/growableArray.hpp"
stefank@2314	30
duke@435	31	class ciMethod;
duke@435	32
duke@435	33	class MethodLivenessResult : public BitMap {
duke@435	34	private:
duke@435	35	bool _is_valid;
duke@435	36
duke@435	37	public:
ysr@777	38	MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)
duke@435	39	: BitMap(map, size_in_bits)
duke@435	40	, _is_valid(false)
duke@435	41	{}
duke@435	42
duke@435	43	MethodLivenessResult(idx_t size_in_bits)
duke@435	44	: BitMap(size_in_bits)
duke@435	45	, _is_valid(false)
duke@435	46	{}
duke@435	47
duke@435	48	void set_is_valid() { _is_valid = true; }
duke@435	49	bool is_valid() { return _is_valid; }
duke@435	50	};
duke@435	51
duke@435	52	class MethodLiveness : public ResourceObj {
duke@435	53	public:
duke@435	54	// The BasicBlock class is used to represent a basic block in the
duke@435	55	// liveness analysis.
duke@435	56	class BasicBlock : public ResourceObj {
duke@435	57	private:
duke@435	58	// This class is only used by the MethodLiveness class.
duke@435	59	friend class MethodLiveness;
duke@435	60
duke@435	61	// The analyzer which created this basic block.
duke@435	62	MethodLiveness* _analyzer;
duke@435	63
duke@435	64	// The range of this basic block is [start_bci,limit_bci)
duke@435	65	int _start_bci;
duke@435	66	int _limit_bci;
duke@435	67
duke@435	68	// The liveness at the start of the block;
duke@435	69	BitMap _entry;
duke@435	70
duke@435	71	// The summarized liveness effects of our direct successors reached
duke@435	72	// by normal control flow
duke@435	73	BitMap _normal_exit;
duke@435	74
duke@435	75	// The summarized liveness effects of our direct successors reached
duke@435	76	// by exceptional control flow
duke@435	77	BitMap _exception_exit;
duke@435	78
duke@435	79	// These members hold the results of the last call to
duke@435	80	// compute_gen_kill_range(). _gen is the set of locals
duke@435	81	// used before they are defined in the range. _kill is the
duke@435	82	// set of locals defined before they are used.
duke@435	83	BitMap _gen;
duke@435	84	BitMap _kill;
duke@435	85	int _last_bci;
duke@435	86
duke@435	87	// A list of all blocks which could come directly before this one
duke@435	88	// in normal (non-exceptional) control flow. We propagate liveness
duke@435	89	// information to these blocks.
duke@435	90	GrowableArray<BasicBlock*>* _normal_predecessors;
duke@435	91
duke@435	92	// A list of all blocks which could come directly before this one
duke@435	93	// in exceptional control flow.
duke@435	94	GrowableArray<BasicBlock*>* _exception_predecessors;
duke@435	95
duke@435	96	// The following fields are used to manage a work list used in the
duke@435	97	// dataflow.
duke@435	98	BasicBlock *_next;
duke@435	99	bool _on_work_list;
duke@435	100
duke@435	101	// Our successors call this method to merge liveness information into
duke@435	102	// our _normal_exit member.
duke@435	103	bool merge_normal(BitMap other);
duke@435	104
duke@435	105	// Our successors call this method to merge liveness information into
duke@435	106	// our _exception_exit member.
duke@435	107	bool merge_exception(BitMap other);
duke@435	108
duke@435	109	// This helper routine is used to help compute the gen/kill pair for
duke@435	110	// the block. It is also used to answer queries.
duke@435	111	void compute_gen_kill_range(ciBytecodeStream *bytes);
duke@435	112
duke@435	113	// Compute the gen/kill effect of a single instruction.
duke@435	114	void compute_gen_kill_single(ciBytecodeStream *instruction);
duke@435	115
duke@435	116	// Helpers for compute_gen_kill_single.
duke@435	117	void load_one(int local);
duke@435	118	void load_two(int local);
duke@435	119	void store_one(int local);
duke@435	120	void store_two(int local);
duke@435	121
duke@435	122	BasicBlock(MethodLiveness *analyzer, int start, int limit);
duke@435	123
duke@435	124	// -- Accessors
duke@435	125
duke@435	126	int start_bci() const { return _start_bci; }
duke@435	127
duke@435	128	int limit_bci() const { return _limit_bci; }
duke@435	129	void set_limit_bci(int limit) { _limit_bci = limit; }
duke@435	130
duke@435	131	BasicBlock *next() const { return _next; }
duke@435	132	void set_next(BasicBlock *next) { _next = next; }
duke@435	133
duke@435	134	bool on_work_list() const { return _on_work_list; }
duke@435	135	void set_on_work_list(bool val) { _on_work_list = val; }
duke@435	136
duke@435	137	// -- Flow graph construction.
duke@435	138
duke@435	139	// Add a basic block to our list of normal predecessors.
duke@435	140	void add_normal_predecessor(BasicBlock *pred) {
duke@435	141	_normal_predecessors->append_if_missing(pred);
duke@435	142	}
duke@435	143
duke@435	144	// Add a basic block to our list of exceptional predecessors
duke@435	145	void add_exception_predecessor(BasicBlock *pred) {
duke@435	146	_exception_predecessors->append_if_missing(pred);
duke@435	147	}
duke@435	148
duke@435	149	// Split the basic block at splitBci. This basic block
duke@435	150	// becomes the second half. The first half is newly created.
duke@435	151	BasicBlock *split(int splitBci);
duke@435	152
duke@435	153	// -- Dataflow.
duke@435	154
duke@435	155	void compute_gen_kill(ciMethod* method);
duke@435	156
duke@435	157	// Propagate changes from this basic block
duke@435	158	void propagate(MethodLiveness *ml);
duke@435	159
duke@435	160	// -- Query.
duke@435	161
duke@435	162	MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
duke@435	163
duke@435	164	// -- Debugging.
duke@435	165
duke@435	166	void print_on(outputStream *os) const PRODUCT_RETURN;
duke@435	167
duke@435	168	}; // End of MethodLiveness::BasicBlock
duke@435	169
duke@435	170	private:
duke@435	171	// The method we are analyzing.
duke@435	172	ciMethod* _method;
duke@435	173	ciMethod* method() const { return _method; }
duke@435	174
duke@435	175	// The arena for storing structures...
duke@435	176	Arena* _arena;
duke@435	177	Arena* arena() const { return _arena; }
duke@435	178
duke@435	179	// We cache the length of the method.
duke@435	180	int _code_size;
duke@435	181
duke@435	182	// The size of a BitMap.
duke@435	183	int _bit_map_size_bits;
duke@435	184	int _bit_map_size_words;
duke@435	185
duke@435	186	// A list of all BasicBlocks.
duke@435	187	BasicBlock **_block_list;
duke@435	188
duke@435	189	// number of blocks
duke@435	190	int _block_count;
duke@435	191
duke@435	192	// Keeps track of bci->block mapping. One entry for each bci. Only block starts are
duke@435	193	// recorded.
duke@435	194	GrowableArray<BasicBlock*>* _block_map;
duke@435	195
duke@435	196	// Our work list.
duke@435	197	BasicBlock *_work_list;
duke@435	198
duke@435	199	#ifdef COMPILER1
duke@435	200	// bcis where blocks start are marked
duke@435	201	BitMap _bci_block_start;
duke@435	202	#endif // COMPILER1
duke@435	203
duke@435	204	// -- Graph construction & Analysis
duke@435	205
duke@435	206	// Compute ranges and predecessors for basic blocks.
duke@435	207	void init_basic_blocks();
duke@435	208
duke@435	209	// Compute gen/kill information for all basic blocks.
duke@435	210	void init_gen_kill();
duke@435	211
duke@435	212	// Perform the dataflow.
duke@435	213	void propagate_liveness();
duke@435	214
duke@435	215	// The class MethodLiveness::BasicBlock needs special access to some
duke@435	216	// of our members.
duke@435	217	friend class MethodLiveness::BasicBlock;
duke@435	218
duke@435	219	// And accessors.
duke@435	220	int bit_map_size_bits() const { return _bit_map_size_bits; }
duke@435	221	int bit_map_size_words() const { return _bit_map_size_words; }
duke@435	222
duke@435	223	// Work list manipulation routines. Called internally by BasicBlock.
duke@435	224	BasicBlock *work_list_get();
duke@435	225	void work_list_add(BasicBlock *block);
duke@435	226
duke@435	227	// -- Timing and Statistics.
duke@435	228
duke@435	229
duke@435	230	// Timers
duke@435	231	static elapsedTimer _time_build_graph;
duke@435	232	static elapsedTimer _time_gen_kill;
duke@435	233	static elapsedTimer _time_flow;
duke@435	234	static elapsedTimer _time_query;
duke@435	235	static elapsedTimer _time_total;
duke@435	236
duke@435	237	#ifndef PRODUCT
duke@435	238
duke@435	239	// Counts
duke@435	240	static long _total_bytes;
duke@435	241	static int _total_methods;
duke@435	242
duke@435	243	static long _total_blocks;
duke@435	244	static int _max_method_blocks;
duke@435	245
duke@435	246	static long _total_edges;
duke@435	247	static int _max_block_edges;
duke@435	248
duke@435	249	static long _total_exc_edges;
duke@435	250	static int _max_block_exc_edges;
duke@435	251
duke@435	252	static long _total_method_locals;
duke@435	253	static int _max_method_locals;
duke@435	254
duke@435	255	static long _total_locals_queried;
duke@435	256	static long _total_live_locals_queried;
duke@435	257
duke@435	258	static long _total_visits;
duke@435	259
duke@435	260	#endif
duke@435	261
duke@435	262	public:
duke@435	263	// Create a liveness analyzer for a method
duke@435	264	MethodLiveness(Arena* arena, ciMethod* method);
duke@435	265
duke@435	266	// Compute liveness information for the method
duke@435	267	void compute_liveness();
duke@435	268
duke@435	269	// Find out which locals are live at a specific bci.
duke@435	270	MethodLivenessResult get_liveness_at(int bci);
duke@435	271
duke@435	272	#ifdef COMPILER1
duke@435	273	const BitMap get_bci_block_start() const { return _bci_block_start; }
duke@435	274	#endif // COMPILER1
duke@435	275
duke@435	276	static void print_times() PRODUCT_RETURN;
duke@435	277	};
stefank@2314	278
stefank@2314	279	#endif // SHARE_VM_COMPILER_METHODLIVENESS_HPP