Mercurial > hg > truffle
view 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 |
line wrap: on
line source
/* * Copyright (c) 2009, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package com.sun.c1x.opt; import static com.sun.c1x.ir.Value.Flag.*; import com.sun.c1x.*; import com.sun.c1x.graph.*; import com.sun.c1x.ir.*; import com.sun.c1x.value.*; /** * The {@code LivenessMarker} class walks over an IR graph and marks instructions * whose values are live, either because they are needed to compute the method's result, * may produce a side-effect, or are needed for deoptimization. * * @author Ben L. Titzer */ public final class LivenessMarker { final IR ir; final InstructionMarker deoptMarker = new InstructionMarker(LiveDeopt); final InstructionMarker valueMarker = new InstructionMarker(LiveValue); int count; /** * Creates a new liveness marking instance and marks live instructions. * @param ir the IR to mark */ public LivenessMarker(IR ir) { this.ir = ir; markRoots(); } private void markRoots() { // first pass: mark root instructions and their inputs ir.startBlock.iteratePreOrder(new BlockClosure() { public void apply(BlockBegin block) { block.stateBefore().valuesDo(deoptMarker); if (block.stateAfter() != null) { block.stateAfter().valuesDo(deoptMarker); } Instruction i = block; while ((i = i.next()) != null) { // visit all instructions first, marking control dependent and side-effects markRootInstr(i); } } }); // propagate liveness flags to inputs of instructions valueMarker.markAll(); deoptMarker.markAll(); } public int liveCount() { return count; } public void removeDeadCode() { // second pass: remove dead instructions from blocks ir.startBlock.iteratePreOrder(new BlockClosure() { public void apply(BlockBegin block) { Instruction prev = block; Instruction i = block.next(); while (i != null) { if (i.isLive()) { prev.resetNext(i); // skip any previous dead instructions prev = i; } else { C1XMetrics.DeadCodeEliminated++; } i = i.next(); } } }); // clear all marks on all instructions valueMarker.clearAll(); deoptMarker.clearAll(); } private static class Link { final Value value; Link next; Link(Value v) { this.value = v; } } private final class InstructionMarker implements ValueClosure { final Value.Flag reason; Link head; Link tail; public InstructionMarker(Value.Flag reason) { this.reason = reason; } public Value apply(Value i) { if (!i.checkFlag(reason) && !i.isDeadPhi()) { // set the flag and add to the queue setFlag(i, reason); if (head == null) { head = tail = new Link(i); } else { tail.next = new Link(i); tail = tail.next; } } return i; } private void markAll() { Link cursor = head; while (cursor != null) { markInputs(cursor.value); cursor = cursor.next; } } private void clearAll() { Link cursor = head; while (cursor != null) { cursor.value.clearLive(); cursor = cursor.next; } } private void markInputs(Value i) { if (!i.isDeadPhi()) { i.inputValuesDo(this); if (i instanceof Phi) { // phis are special Phi phi = (Phi) i; int max = phi.inputCount(); for (int j = 0; j < max; j++) { apply(phi.inputAt(j)); } } } } } void markRootInstr(Instruction i) { FrameState stateBefore = i.stateBefore(); if (stateBefore != null) { // stateBefore != null implies that this instruction may have side effects stateBefore.valuesDo(deoptMarker); i.inputValuesDo(valueMarker); setFlag(i, LiveSideEffect); } else if (i.checkFlag(LiveStore)) { // instruction is a store that cannot be eliminated i.inputValuesDo(valueMarker); setFlag(i, LiveSideEffect); } else if (i.checkFlag(LiveSideEffect)) { // instruction has a side effect i.inputValuesDo(valueMarker); } if (i instanceof BlockEnd) { // input values to block ends are control dependencies i.inputValuesDo(valueMarker); setFlag(i, LiveControl); } FrameState stateAfter = i.stateAfter(); if (stateAfter != null) { stateAfter.valuesDo(deoptMarker); } } void setFlag(Value i, Value.Flag flag) { if (!i.isLive()) { count++; } i.setFlag(flag); } }