Mercurial > hg > graal-compiler

comparison graal/Compiler/src/com/sun/c1x/opt/LivenessMarker.java @ 2507:9ec15d6914ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }