Mercurial > hg > graal-compiler
diff src/share/vm/compiler/methodLiveness.hpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 37f87013dfd8 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/compiler/methodLiveness.hpp Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,271 @@ +/* + * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + * + */ + +class ciMethod; + +class MethodLivenessResult : public BitMap { + private: + bool _is_valid; + + public: + MethodLivenessResult(uintptr_t* map, idx_t size_in_bits) + : BitMap(map, size_in_bits) + , _is_valid(false) + {} + + MethodLivenessResult(idx_t size_in_bits) + : BitMap(size_in_bits) + , _is_valid(false) + {} + + void set_is_valid() { _is_valid = true; } + bool is_valid() { return _is_valid; } +}; + +class MethodLiveness : public ResourceObj { + public: + // The BasicBlock class is used to represent a basic block in the + // liveness analysis. + class BasicBlock : public ResourceObj { + private: + // This class is only used by the MethodLiveness class. + friend class MethodLiveness; + + // The analyzer which created this basic block. + MethodLiveness* _analyzer; + + // The range of this basic block is [start_bci,limit_bci) + int _start_bci; + int _limit_bci; + + // The liveness at the start of the block; + BitMap _entry; + + // The summarized liveness effects of our direct successors reached + // by normal control flow + BitMap _normal_exit; + + // The summarized liveness effects of our direct successors reached + // by exceptional control flow + BitMap _exception_exit; + + // These members hold the results of the last call to + // compute_gen_kill_range(). _gen is the set of locals + // used before they are defined in the range. _kill is the + // set of locals defined before they are used. + BitMap _gen; + BitMap _kill; + int _last_bci; + + // A list of all blocks which could come directly before this one + // in normal (non-exceptional) control flow. We propagate liveness + // information to these blocks. + GrowableArray<BasicBlock*>* _normal_predecessors; + + // A list of all blocks which could come directly before this one + // in exceptional control flow. + GrowableArray<BasicBlock*>* _exception_predecessors; + + // The following fields are used to manage a work list used in the + // dataflow. + BasicBlock *_next; + bool _on_work_list; + + // Our successors call this method to merge liveness information into + // our _normal_exit member. + bool merge_normal(BitMap other); + + // Our successors call this method to merge liveness information into + // our _exception_exit member. + bool merge_exception(BitMap other); + + // This helper routine is used to help compute the gen/kill pair for + // the block. It is also used to answer queries. + void compute_gen_kill_range(ciBytecodeStream *bytes); + + // Compute the gen/kill effect of a single instruction. + void compute_gen_kill_single(ciBytecodeStream *instruction); + + // Helpers for compute_gen_kill_single. + void load_one(int local); + void load_two(int local); + void store_one(int local); + void store_two(int local); + + BasicBlock(MethodLiveness *analyzer, int start, int limit); + + // -- Accessors + + int start_bci() const { return _start_bci; } + + int limit_bci() const { return _limit_bci; } + void set_limit_bci(int limit) { _limit_bci = limit; } + + BasicBlock *next() const { return _next; } + void set_next(BasicBlock *next) { _next = next; } + + bool on_work_list() const { return _on_work_list; } + void set_on_work_list(bool val) { _on_work_list = val; } + + // -- Flow graph construction. + + // Add a basic block to our list of normal predecessors. + void add_normal_predecessor(BasicBlock *pred) { + _normal_predecessors->append_if_missing(pred); + } + + // Add a basic block to our list of exceptional predecessors + void add_exception_predecessor(BasicBlock *pred) { + _exception_predecessors->append_if_missing(pred); + } + + // Split the basic block at splitBci. This basic block + // becomes the second half. The first half is newly created. + BasicBlock *split(int splitBci); + + // -- Dataflow. + + void compute_gen_kill(ciMethod* method); + + // Propagate changes from this basic block + void propagate(MethodLiveness *ml); + + // -- Query. + + MethodLivenessResult get_liveness_at(ciMethod* method, int bci); + + // -- Debugging. + + void print_on(outputStream *os) const PRODUCT_RETURN; + + }; // End of MethodLiveness::BasicBlock + + private: + // The method we are analyzing. + ciMethod* _method; + ciMethod* method() const { return _method; } + + // The arena for storing structures... + Arena* _arena; + Arena* arena() const { return _arena; } + + // We cache the length of the method. + int _code_size; + + // The size of a BitMap. + int _bit_map_size_bits; + int _bit_map_size_words; + + // A list of all BasicBlocks. + BasicBlock **_block_list; + + // number of blocks + int _block_count; + + // Keeps track of bci->block mapping. One entry for each bci. Only block starts are + // recorded. + GrowableArray<BasicBlock*>* _block_map; + + // Our work list. + BasicBlock *_work_list; + +#ifdef COMPILER1 + // bcis where blocks start are marked + BitMap _bci_block_start; +#endif // COMPILER1 + + // -- Graph construction & Analysis + + // Compute ranges and predecessors for basic blocks. + void init_basic_blocks(); + + // Compute gen/kill information for all basic blocks. + void init_gen_kill(); + + // Perform the dataflow. + void propagate_liveness(); + + // The class MethodLiveness::BasicBlock needs special access to some + // of our members. + friend class MethodLiveness::BasicBlock; + + // And accessors. + int bit_map_size_bits() const { return _bit_map_size_bits; } + int bit_map_size_words() const { return _bit_map_size_words; } + + // Work list manipulation routines. Called internally by BasicBlock. + BasicBlock *work_list_get(); + void work_list_add(BasicBlock *block); + + // -- Timing and Statistics. + + + // Timers + static elapsedTimer _time_build_graph; + static elapsedTimer _time_gen_kill; + static elapsedTimer _time_flow; + static elapsedTimer _time_query; + static elapsedTimer _time_total; + +#ifndef PRODUCT + + // Counts + static long _total_bytes; + static int _total_methods; + + static long _total_blocks; + static int _max_method_blocks; + + static long _total_edges; + static int _max_block_edges; + + static long _total_exc_edges; + static int _max_block_exc_edges; + + static long _total_method_locals; + static int _max_method_locals; + + static long _total_locals_queried; + static long _total_live_locals_queried; + + static long _total_visits; + +#endif + + public: + // Create a liveness analyzer for a method + MethodLiveness(Arena* arena, ciMethod* method); + + // Compute liveness information for the method + void compute_liveness(); + + // Find out which locals are live at a specific bci. + MethodLivenessResult get_liveness_at(int bci); + +#ifdef COMPILER1 + const BitMap get_bci_block_start() const { return _bci_block_start; } +#endif // COMPILER1 + + static void print_times() PRODUCT_RETURN; +};