Mercurial > hg > graal-jvmci-8
comparison graal/Compiler/src/com/sun/c1x/opt/LivenessMarker.java @ 2507:9ec15d6914ca
Pull over of compiler from maxine repository.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:43:22 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
2506:4a3bf8a5bf41 | 2507:9ec15d6914ca |
---|---|
1 /* | |
2 * Copyright (c) 2009, 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 */ | |
23 package com.sun.c1x.opt; | |
24 | |
25 import static com.sun.c1x.ir.Value.Flag.*; | |
26 | |
27 import com.sun.c1x.*; | |
28 import com.sun.c1x.graph.*; | |
29 import com.sun.c1x.ir.*; | |
30 import com.sun.c1x.value.*; | |
31 | |
32 /** | |
33 * The {@code LivenessMarker} class walks over an IR graph and marks instructions | |
34 * whose values are live, either because they are needed to compute the method's result, | |
35 * may produce a side-effect, or are needed for deoptimization. | |
36 * | |
37 * @author Ben L. Titzer | |
38 */ | |
39 public final class LivenessMarker { | |
40 | |
41 final IR ir; | |
42 | |
43 final InstructionMarker deoptMarker = new InstructionMarker(LiveDeopt); | |
44 final InstructionMarker valueMarker = new InstructionMarker(LiveValue); | |
45 | |
46 int count; | |
47 | |
48 /** | |
49 * Creates a new liveness marking instance and marks live instructions. | |
50 * @param ir the IR to mark | |
51 */ | |
52 public LivenessMarker(IR ir) { | |
53 this.ir = ir; | |
54 markRoots(); | |
55 } | |
56 | |
57 private void markRoots() { | |
58 // first pass: mark root instructions and their inputs | |
59 ir.startBlock.iteratePreOrder(new BlockClosure() { | |
60 public void apply(BlockBegin block) { | |
61 block.stateBefore().valuesDo(deoptMarker); | |
62 if (block.stateAfter() != null) { | |
63 block.stateAfter().valuesDo(deoptMarker); | |
64 } | |
65 Instruction i = block; | |
66 while ((i = i.next()) != null) { | |
67 // visit all instructions first, marking control dependent and side-effects | |
68 markRootInstr(i); | |
69 } | |
70 } | |
71 }); | |
72 | |
73 // propagate liveness flags to inputs of instructions | |
74 valueMarker.markAll(); | |
75 deoptMarker.markAll(); | |
76 } | |
77 | |
78 public int liveCount() { | |
79 return count; | |
80 } | |
81 | |
82 public void removeDeadCode() { | |
83 // second pass: remove dead instructions from blocks | |
84 ir.startBlock.iteratePreOrder(new BlockClosure() { | |
85 public void apply(BlockBegin block) { | |
86 Instruction prev = block; | |
87 Instruction i = block.next(); | |
88 while (i != null) { | |
89 if (i.isLive()) { | |
90 prev.resetNext(i); // skip any previous dead instructions | |
91 prev = i; | |
92 } else { | |
93 C1XMetrics.DeadCodeEliminated++; | |
94 } | |
95 i = i.next(); | |
96 } | |
97 } | |
98 }); | |
99 // clear all marks on all instructions | |
100 valueMarker.clearAll(); | |
101 deoptMarker.clearAll(); | |
102 } | |
103 | |
104 private static class Link { | |
105 final Value value; | |
106 Link next; | |
107 | |
108 Link(Value v) { | |
109 this.value = v; | |
110 } | |
111 } | |
112 | |
113 private final class InstructionMarker implements ValueClosure { | |
114 final Value.Flag reason; | |
115 Link head; | |
116 Link tail; | |
117 | |
118 public InstructionMarker(Value.Flag reason) { | |
119 this.reason = reason; | |
120 } | |
121 | |
122 public Value apply(Value i) { | |
123 if (!i.checkFlag(reason) && !i.isDeadPhi()) { | |
124 // set the flag and add to the queue | |
125 setFlag(i, reason); | |
126 if (head == null) { | |
127 head = tail = new Link(i); | |
128 } else { | |
129 tail.next = new Link(i); | |
130 tail = tail.next; | |
131 } | |
132 } | |
133 return i; | |
134 } | |
135 | |
136 private void markAll() { | |
137 Link cursor = head; | |
138 while (cursor != null) { | |
139 markInputs(cursor.value); | |
140 cursor = cursor.next; | |
141 } | |
142 } | |
143 | |
144 private void clearAll() { | |
145 Link cursor = head; | |
146 while (cursor != null) { | |
147 cursor.value.clearLive(); | |
148 cursor = cursor.next; | |
149 } | |
150 } | |
151 | |
152 private void markInputs(Value i) { | |
153 if (!i.isDeadPhi()) { | |
154 i.inputValuesDo(this); | |
155 if (i instanceof Phi) { | |
156 // phis are special | |
157 Phi phi = (Phi) i; | |
158 int max = phi.inputCount(); | |
159 for (int j = 0; j < max; j++) { | |
160 apply(phi.inputAt(j)); | |
161 } | |
162 } | |
163 } | |
164 } | |
165 } | |
166 | |
167 void markRootInstr(Instruction i) { | |
168 FrameState stateBefore = i.stateBefore(); | |
169 if (stateBefore != null) { | |
170 // stateBefore != null implies that this instruction may have side effects | |
171 stateBefore.valuesDo(deoptMarker); | |
172 i.inputValuesDo(valueMarker); | |
173 setFlag(i, LiveSideEffect); | |
174 } else if (i.checkFlag(LiveStore)) { | |
175 // instruction is a store that cannot be eliminated | |
176 i.inputValuesDo(valueMarker); | |
177 setFlag(i, LiveSideEffect); | |
178 } else if (i.checkFlag(LiveSideEffect)) { | |
179 // instruction has a side effect | |
180 i.inputValuesDo(valueMarker); | |
181 } | |
182 if (i instanceof BlockEnd) { | |
183 // input values to block ends are control dependencies | |
184 i.inputValuesDo(valueMarker); | |
185 setFlag(i, LiveControl); | |
186 } | |
187 FrameState stateAfter = i.stateAfter(); | |
188 if (stateAfter != null) { | |
189 stateAfter.valuesDo(deoptMarker); | |
190 } | |
191 } | |
192 | |
193 void setFlag(Value i, Value.Flag flag) { | |
194 if (!i.isLive()) { | |
195 count++; | |
196 } | |
197 i.setFlag(flag); | |
198 } | |
199 } |