1/*
2 * Copyright (c) 2015, 2015, 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.amd64.phases;
24
25import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
26
27import java.util.ArrayList;
28import java.util.Collections;
29import java.util.List;
30
31import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32import org.graalvm.compiler.debug.Debug;
33import org.graalvm.compiler.debug.DebugCounter;
34import org.graalvm.compiler.lir.LIR;
35import org.graalvm.compiler.lir.LIRInstruction;
36import org.graalvm.compiler.lir.RedundantMoveElimination;
37import org.graalvm.compiler.lir.amd64.AMD64Move.AMD64MultiStackMove;
38import org.graalvm.compiler.lir.amd64.AMD64Move.AMD64StackMove;
39import org.graalvm.compiler.lir.gen.LIRGenerationResult;
40import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase;
41import org.graalvm.compiler.options.NestedBooleanOptionValue;
42import org.graalvm.compiler.options.Option;
43import org.graalvm.compiler.options.OptionType;
44
45import jdk.vm.ci.code.Register;
46import jdk.vm.ci.code.TargetDescription;
47import jdk.vm.ci.meta.AllocatableValue;
48import jdk.vm.ci.meta.Value;
49
50/**
51 * Replaces sequential {@link AMD64StackMove}s of the same type with a single
52 * {@link AMD64MultiStackMove} to avoid storing/restoring the scratch register multiple times.
53 *
54 * Note: this phase must be inserted <b>after</b> {@link RedundantMoveElimination} phase because
55 * {@link AMD64MultiStackMove} are not probably detected.
56 */
57public class StackMoveOptimizationPhase extends PostAllocationOptimizationPhase {
58    public static class Options {
59        // @formatter:off
60        @Option(help = "", type = OptionType.Debug)
61        public static final NestedBooleanOptionValue LIROptStackMoveOptimizer = new NestedBooleanOptionValue(LIROptimization, true);
62        // @formatter:on
63    }
64
65    private static final DebugCounter eliminatedBackup = Debug.counter("StackMoveOptimizer[EliminatedScratchBackupRestore]");
66
67    @Override
68    protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PostAllocationOptimizationContext context) {
69        LIR lir = lirGenRes.getLIR();
70        for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
71            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
72            new Closure().process(instructions);
73        }
74    }
75
76    private static class Closure {
77        private static final int NONE = -1;
78
79        private int begin = NONE;
80        private Register reg = null;
81        private List<AllocatableValue> dst;
82        private List<Value> src;
83        private AllocatableValue slot;
84        private boolean removed = false;
85
86        public void process(List<LIRInstruction> instructions) {
87            for (int i = 0; i < instructions.size(); i++) {
88                LIRInstruction inst = instructions.get(i);
89
90                if (isStackMove(inst)) {
91                    AMD64StackMove move = asStackMove(inst);
92
93                    if (reg != null && !reg.equals(move.getScratchRegister())) {
94                        // end of trace & start of new
95                        replaceStackMoves(instructions);
96                    }
97
98                    // lazy initialize
99                    if (dst == null) {
100                        assert src == null;
101                        dst = new ArrayList<>();
102                        src = new ArrayList<>();
103                    }
104
105                    dst.add(move.getResult());
106                    src.add(move.getInput());
107
108                    if (begin == NONE) {
109                        // trace begin
110                        begin = i;
111                        reg = move.getScratchRegister();
112                        slot = move.getBackupSlot();
113                    }
114
115                } else if (begin != NONE) {
116                    // end of trace
117                    replaceStackMoves(instructions);
118                }
119            }
120            // remove instructions
121            if (removed) {
122                instructions.removeAll(Collections.singleton(null));
123            }
124
125        }
126
127        private void replaceStackMoves(List<LIRInstruction> instructions) {
128            int size = dst.size();
129            if (size > 1) {
130                AMD64MultiStackMove multiMove = new AMD64MultiStackMove(dst.toArray(new AllocatableValue[size]), src.toArray(new AllocatableValue[size]), reg, slot);
131                // replace first instruction
132                instructions.set(begin, multiMove);
133                // and null out others
134                Collections.fill(instructions.subList(begin + 1, begin + size), null);
135                // removed
136                removed = true;
137                eliminatedBackup.add(size - 1);
138            }
139            // reset
140            dst.clear();
141            src.clear();
142            begin = NONE;
143            reg = null;
144            slot = null;
145        }
146    }
147
148    private static AMD64StackMove asStackMove(LIRInstruction inst) {
149        assert isStackMove(inst);
150        return (AMD64StackMove) inst;
151    }
152
153    private static boolean isStackMove(LIRInstruction inst) {
154        return inst instanceof AMD64StackMove;
155    }
156
157}
158