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 */
23package org.graalvm.compiler.lir;
24
25import static org.graalvm.compiler.lir.LIR.verifyBlocks;
26
27import java.util.ArrayList;
28
29import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30import org.graalvm.compiler.debug.CounterKey;
31import org.graalvm.compiler.debug.DebugContext;
32import org.graalvm.compiler.lir.gen.LIRGenerationResult;
33import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase;
34
35import jdk.vm.ci.code.TargetDescription;
36
37/**
38 * This class performs basic optimizations on the control flow graph after LIR generation.
39 */
40public final class ControlFlowOptimizer extends PostAllocationOptimizationPhase {
41
42    /**
43     * Performs control flow optimizations on the given LIR graph.
44     */
45    @Override
46    protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PostAllocationOptimizationContext context) {
47        LIR lir = lirGenRes.getLIR();
48        new Optimizer(lir).deleteEmptyBlocks(lir.codeEmittingOrder());
49    }
50
51    private static final class Optimizer {
52
53        private final LIR lir;
54
55        private Optimizer(LIR lir) {
56            this.lir = lir;
57        }
58
59        private static final CounterKey BLOCKS_DELETED = DebugContext.counter("BlocksDeleted");
60
61        /**
62         * Checks whether a block can be deleted. Only blocks with exactly one successor and an
63         * unconditional branch to this successor are eligable.
64         *
65         * @param block the block checked for deletion
66         * @return whether the block can be deleted
67         */
68        private boolean canDeleteBlock(AbstractBlockBase<?> block) {
69            if (block == null || block.getSuccessorCount() != 1 || block.getPredecessorCount() == 0 || block.getSuccessors()[0] == block) {
70                return false;
71            }
72
73            ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
74
75            assert instructions.size() >= 2 : "block must have label and branch";
76            assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
77            assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "last instruction must always be a branch";
78            assert ((StandardOp.JumpOp) instructions.get(instructions.size() - 1)).destination().label() == ((StandardOp.LabelOp) lir.getLIRforBlock(block.getSuccessors()[0]).get(
79                            0)).getLabel() : "branch target must be the successor";
80
81            // Block must have exactly one successor.
82            return instructions.size() == 2 && !instructions.get(instructions.size() - 1).hasState() && !block.isExceptionEntry();
83        }
84
85        private void alignBlock(AbstractBlockBase<?> block) {
86            if (!block.isAligned()) {
87                block.setAlign(true);
88                ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
89                assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
90                StandardOp.LabelOp label = (StandardOp.LabelOp) instructions.get(0);
91                instructions.set(0, new StandardOp.LabelOp(label.getLabel(), true));
92            }
93        }
94
95        private void deleteEmptyBlocks(AbstractBlockBase<?>[] blocks) {
96            assert verifyBlocks(lir, blocks);
97            for (int i = 0; i < blocks.length; i++) {
98                AbstractBlockBase<?> block = blocks[i];
99                if (canDeleteBlock(block)) {
100
101                    block.delete();
102                    // adjust successor and predecessor lists
103                    AbstractBlockBase<?> other = block.getSuccessors()[0];
104                    if (block.isAligned()) {
105                        alignBlock(other);
106                    }
107
108                    BLOCKS_DELETED.increment(lir.getDebug());
109                    blocks[i] = null;
110                }
111            }
112            assert verifyBlocks(lir, blocks);
113        }
114    }
115}
116