001/*
002 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir;
024
025import static com.oracle.graal.lir.LIR.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import com.oracle.graal.debug.*;
031
032import com.oracle.graal.compiler.common.cfg.*;
033import com.oracle.graal.lir.gen.*;
034import com.oracle.graal.lir.phases.*;
035
036/**
037 * This class performs basic optimizations on the control flow graph after LIR generation.
038 */
039public final class ControlFlowOptimizer extends PostAllocationOptimizationPhase {
040
041    /**
042     * Performs control flow optimizations on the given LIR graph.
043     */
044    @Override
045    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
046                    BenchmarkCounterFactory counterFactory) {
047        LIR lir = lirGenRes.getLIR();
048        new Optimizer<B>(lir).deleteEmptyBlocks(codeEmittingOrder);
049    }
050
051    private static final class Optimizer<B extends AbstractBlockBase<B>> {
052
053        private final LIR lir;
054
055        private Optimizer(LIR lir) {
056            this.lir = lir;
057        }
058
059        private static final DebugMetric BLOCKS_DELETED = Debug.metric("BlocksDeleted");
060
061        /**
062         * Checks whether a block can be deleted. Only blocks with exactly one successor and an
063         * unconditional branch to this successor are eligable.
064         *
065         * @param block the block checked for deletion
066         * @return whether the block can be deleted
067         */
068        private boolean canDeleteBlock(B block) {
069            if (block.getSuccessorCount() != 1 || block.getPredecessorCount() == 0 || block.getSuccessors().iterator().next() == block) {
070                return false;
071            }
072
073            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
074
075            assert instructions.size() >= 2 : "block must have label and branch";
076            assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
077            assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "last instruction must always be a branch";
078            assert ((StandardOp.JumpOp) instructions.get(instructions.size() - 1)).destination().label() == ((StandardOp.LabelOp) lir.getLIRforBlock(block.getSuccessors().iterator().next()).get(0)).getLabel() : "branch target must be the successor";
079
080            // Block must have exactly one successor.
081            return instructions.size() == 2 && !instructions.get(instructions.size() - 1).hasState() && !block.isExceptionEntry();
082        }
083
084        private void alignBlock(B block) {
085            if (!block.isAligned()) {
086                block.setAlign(true);
087                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
088                assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
089                StandardOp.LabelOp label = (StandardOp.LabelOp) instructions.get(0);
090                instructions.set(0, new StandardOp.LabelOp(label.getLabel(), true));
091            }
092        }
093
094        private void deleteEmptyBlocks(List<B> blocks) {
095            assert verifyBlocks(lir, blocks);
096            Iterator<B> iterator = blocks.iterator();
097            while (iterator.hasNext()) {
098                B block = iterator.next();
099                if (canDeleteBlock(block)) {
100                    // adjust successor and predecessor lists
101                    B other = block.getSuccessors().iterator().next();
102                    for (AbstractBlockBase<B> pred : block.getPredecessors()) {
103                        Collections.replaceAll(pred.getSuccessors(), block, other);
104                    }
105                    for (int i = 0; i < other.getPredecessorCount(); i++) {
106                        if (other.getPredecessors().get(i) == block) {
107                            other.getPredecessors().remove(i);
108                            other.getPredecessors().addAll(i, block.getPredecessors());
109                        }
110                    }
111                    block.getSuccessors().clear();
112                    block.getPredecessors().clear();
113
114                    if (block.isAligned()) {
115                        alignBlock(other);
116                    }
117
118                    BLOCKS_DELETED.increment();
119                    iterator.remove();
120                }
121            }
122            assert verifyBlocks(lir, blocks);
123        }
124    }
125}