1 /*
2 * Copyright (c) 1998, 2014, 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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "ci/ciMethod.hpp"
27 #include "ci/ciMethodBlocks.hpp"
28 #include "ci/ciStreams.hpp"
29 #include "compiler/methodLiveness.hpp"
30 #include "interpreter/bytecode.hpp"
31 #include "interpreter/bytecodes.hpp"
32 #include "memory/allocation.inline.hpp"
33 #include "utilities/bitMap.inline.hpp"
34
35 // The MethodLiveness class performs a simple liveness analysis on a method
36 // in order to decide which locals are live (that is, will be used again) at
37 // a particular bytecode index (bci).
38 //
39 // The algorithm goes:
40 //
41 // 1. Break the method into a set of basic blocks. For each basic block we
42 // also keep track of its set of predecessors through normal control flow
43 // and predecessors through exceptional control flow.
44 //
45 // 2. For each basic block, compute two sets, gen (the set of values used before
46 // they are defined) and kill (the set of values defined before they are used)
47 // in the basic block. A basic block "needs" the locals in its gen set to
48 // perform its computation. A basic block "provides" values for the locals in
49 // its kill set, allowing a need from a successor to be ignored.
50 //
51 // 3. Liveness information (the set of locals which are needed) is pushed backwards through
52 // the program, from blocks to their predecessors. We compute and store liveness
|
1 /*
2 * Copyright (c) 1998, 2016, 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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "ci/ciMethod.hpp"
27 #include "ci/ciMethodBlocks.hpp"
28 #include "ci/ciStreams.hpp"
29 #include "compiler/methodLiveness.hpp"
30 #include "interpreter/bytecode.hpp"
31 #include "interpreter/bytecodes.hpp"
32 #include "memory/allocation.inline.hpp"
33 #include "memory/resourceArea.hpp"
34 #include "utilities/bitMap.inline.hpp"
35
36 // The MethodLiveness class performs a simple liveness analysis on a method
37 // in order to decide which locals are live (that is, will be used again) at
38 // a particular bytecode index (bci).
39 //
40 // The algorithm goes:
41 //
42 // 1. Break the method into a set of basic blocks. For each basic block we
43 // also keep track of its set of predecessors through normal control flow
44 // and predecessors through exceptional control flow.
45 //
46 // 2. For each basic block, compute two sets, gen (the set of values used before
47 // they are defined) and kill (the set of values defined before they are used)
48 // in the basic block. A basic block "needs" the locals in its gen set to
49 // perform its computation. A basic block "provides" values for the locals in
50 // its kill set, allowing a need from a successor to be ignored.
51 //
52 // 3. Liveness information (the set of locals which are needed) is pushed backwards through
53 // the program, from blocks to their predecessors. We compute and store liveness
|