001/*
002 * Copyright (c) 2013, 2014, 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 jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import com.oracle.graal.debug.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.*;
034import com.oracle.graal.compiler.common.cfg.*;
035import com.oracle.graal.lir.LIRInstruction.OperandFlag;
036import com.oracle.graal.lir.LIRInstruction.OperandMode;
037import com.oracle.graal.lir.StandardOp.MoveOp;
038import com.oracle.graal.lir.framemap.*;
039import com.oracle.graal.lir.gen.*;
040import com.oracle.graal.lir.phases.*;
041
042/**
043 * Removes move instructions, where the destination value is already in place.
044 */
045public final class RedundantMoveElimination extends PostAllocationOptimizationPhase {
046
047    @Override
048    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
049                    BenchmarkCounterFactory counterFactory) {
050        Optimization redundantMoveElimination = new Optimization(lirGenRes.getFrameMap());
051        redundantMoveElimination.doOptimize(lirGenRes.getLIR());
052    }
053
054    /**
055     * Holds the entry and exit states for each block for dataflow analysis. The state is an array
056     * with an element for each relevant location (register or stack slot). Each element holds the
057     * global number of the location's definition. A location definition is simply an output of an
058     * instruction. Note that because instructions can have multiple outputs it is not possible to
059     * use the instruction id for value numbering. In addition, the result of merging at block
060     * entries (= phi values) get unique value numbers.
061     *
062     * The value numbers also contain information if it is an object kind value or not: if the
063     * number is negative it is an object kind value.
064     */
065    private static final class BlockData {
066
067        BlockData(int stateSize) {
068            entryState = new int[stateSize];
069            exitState = new int[stateSize];
070        }
071
072        /*
073         * The state at block entry for global dataflow analysis. It contains a global value number
074         * for each location to optimize.
075         */
076        int[] entryState;
077
078        /*
079         * The state at block exit for global dataflow analysis. It contains a global value number
080         * for each location to optimize.
081         */
082        int[] exitState;
083
084        /*
085         * The starting number for global value numbering in this block.
086         */
087        int entryValueNum;
088    }
089
090    private static final class Optimization {
091
092        Map<AbstractBlockBase<?>, BlockData> blockData = CollectionsFactory.newMap();
093
094        Register[] callerSaveRegs;
095
096        /**
097         * Contains the register number for registers which can be optimized and -1 for the others.
098         */
099        int[] eligibleRegs;
100
101        /**
102         * A map from the {@link StackSlot} {@link #getOffset offset} to an index into the state.
103         * StackSlots of different kinds that map to the same location will map to the same index.
104         */
105        Map<Integer, Integer> stackIndices = CollectionsFactory.newMap();
106
107        int numRegs;
108
109        private final FrameMap frameMap;
110
111        /*
112         * Pseudo value for a not yet assigned location.
113         */
114        static final int INIT_VALUE = 0;
115
116        public Optimization(FrameMap frameMap) {
117            this.frameMap = frameMap;
118        }
119
120        /**
121         * The main method doing the elimination of redundant moves.
122         */
123        private void doOptimize(LIR lir) {
124
125            try (Indent indent = Debug.logAndIndent("eliminate redundant moves")) {
126
127                callerSaveRegs = frameMap.getRegisterConfig().getCallerSaveRegisters();
128
129                initBlockData(lir);
130
131                // Compute a table of the registers which are eligible for move optimization.
132                // Unallocatable registers should never be optimized.
133                eligibleRegs = new int[numRegs];
134                Arrays.fill(eligibleRegs, -1);
135                for (Register reg : frameMap.getRegisterConfig().getAllocatableRegisters()) {
136                    if (reg.number < numRegs) {
137                        eligibleRegs[reg.number] = reg.number;
138                    }
139                }
140
141                if (!solveDataFlow(lir)) {
142                    return;
143                }
144
145                eliminateMoves(lir);
146            }
147        }
148
149        /**
150         * The maximum number of locations * blocks. This is a complexity limit for the inner loop
151         * in {@link #mergeState} (assuming a small number of iterations in {@link #solveDataFlow}.
152         */
153        private static final int COMPLEXITY_LIMIT = 30000;
154
155        private void initBlockData(LIR lir) {
156
157            List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder();
158            numRegs = 0;
159
160            int maxStackLocations = COMPLEXITY_LIMIT / blocks.size();
161
162            /*
163             * Search for relevant locations which can be optimized. These are register or stack
164             * slots which occur as destinations of move instructions.
165             */
166            for (AbstractBlockBase<?> block : blocks) {
167                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
168                for (LIRInstruction op : instructions) {
169                    if (isEligibleMove(op)) {
170                        Value dest = ((MoveOp) op).getResult();
171                        if (isRegister(dest)) {
172                            int regNum = ((RegisterValue) dest).getRegister().number;
173                            if (regNum >= numRegs) {
174                                numRegs = regNum + 1;
175                            }
176                        } else if (isStackSlot(dest)) {
177                            StackSlot stackSlot = (StackSlot) dest;
178                            Integer offset = getOffset(stackSlot);
179                            if (!stackIndices.containsKey(offset) && stackIndices.size() < maxStackLocations) {
180                                stackIndices.put(offset, stackIndices.size());
181                            }
182                        }
183                    }
184                }
185            }
186
187            /*
188             * Now we know the number of locations to optimize, so we can allocate the block states.
189             */
190            int numLocations = numRegs + stackIndices.size();
191            Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size());
192            for (AbstractBlockBase<?> block : blocks) {
193                BlockData data = new BlockData(numLocations);
194                blockData.put(block, data);
195            }
196        }
197
198        private int getOffset(StackSlot stackSlot) {
199            return stackSlot.getOffset(frameMap.totalFrameSize());
200        }
201
202        /**
203         * Calculates the entry and exit states for all basic blocks.
204         *
205         * @return Returns true on success and false if the the control flow is too complex.
206         */
207        private boolean solveDataFlow(LIR lir) {
208
209            try (Indent indent = Debug.logAndIndent("solve data flow")) {
210
211                List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder();
212
213                int numIter = 0;
214
215                /*
216                 * Iterate until there are no more changes.
217                 */
218                int currentValueNum = 1;
219                boolean firstRound = true;
220                boolean changed;
221                do {
222                    changed = false;
223                    try (Indent indent2 = Debug.logAndIndent("new iteration")) {
224
225                        for (AbstractBlockBase<?> block : blocks) {
226
227                            BlockData data = blockData.get(block);
228                            /*
229                             * Initialize the number for global value numbering for this block. It
230                             * is essential that the starting number for a block is consistent at
231                             * all iterations and also in eliminateMoves().
232                             */
233                            if (firstRound) {
234                                data.entryValueNum = currentValueNum;
235                            }
236                            int valueNum = data.entryValueNum;
237                            assert valueNum > 0;
238                            boolean newState = false;
239
240                            if (block == blocks.get(0) || block.isExceptionEntry()) {
241                                /*
242                                 * The entry block has undefined values. And also exception handler
243                                 * blocks: the LinearScan can insert moves at the end of an
244                                 * exception handler predecessor block (after the invoke, which
245                                 * throws the exception), and in reality such moves are not in the
246                                 * control flow in case of an exception. So we assume a save default
247                                 * for exception handler blocks.
248                                 */
249                                Debug.log("kill all values at entry of block %d", block.getId());
250                                clearValues(data.entryState, valueNum);
251                            } else {
252                                /*
253                                 * Merge the states of predecessor blocks
254                                 */
255                                for (AbstractBlockBase<?> predecessor : block.getPredecessors()) {
256                                    BlockData predData = blockData.get(predecessor);
257                                    newState |= mergeState(data.entryState, predData.exitState, valueNum);
258                                }
259                            }
260                            // Advance by the value numbers which are "consumed" by
261                            // clearValues and mergeState
262                            valueNum += data.entryState.length;
263
264                            if (newState || firstRound) {
265                                try (Indent indent3 = Debug.logAndIndent("update block %d", block.getId())) {
266
267                                    /*
268                                     * Derive the exit state from the entry state by iterating
269                                     * through all instructions of the block.
270                                     */
271                                    int[] iterState = data.exitState;
272                                    copyState(iterState, data.entryState);
273                                    List<LIRInstruction> instructions = lir.getLIRforBlock(block);
274
275                                    for (LIRInstruction op : instructions) {
276                                        valueNum = updateState(iterState, op, valueNum);
277                                    }
278                                    changed = true;
279                                }
280                            }
281                            if (firstRound) {
282                                currentValueNum = valueNum;
283                            }
284                        }
285                        firstRound = false;
286                    }
287                    numIter++;
288
289                    if (numIter > 5) {
290                        /*
291                         * This is _very_ seldom.
292                         */
293                        return false;
294                    }
295
296                } while (changed);
297
298            }
299
300            return true;
301        }
302
303        /**
304         * Deletes all move instructions where the target location already contains the source
305         * value.
306         */
307        private void eliminateMoves(LIR lir) {
308
309            try (Indent indent = Debug.logAndIndent("eliminate moves")) {
310
311                List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder();
312
313                for (AbstractBlockBase<?> block : blocks) {
314
315                    try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) {
316
317                        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
318                        BlockData data = blockData.get(block);
319                        boolean hasDead = false;
320
321                        // Reuse the entry state for iteration, we don't need it later.
322                        int[] iterState = data.entryState;
323
324                        // Add the values which are "consumed" by clearValues and
325                        // mergeState in solveDataFlow
326                        int valueNum = data.entryValueNum + data.entryState.length;
327
328                        int numInsts = instructions.size();
329                        for (int idx = 0; idx < numInsts; idx++) {
330                            LIRInstruction op = instructions.get(idx);
331                            if (isEligibleMove(op)) {
332                                MoveOp moveOp = (MoveOp) op;
333                                int sourceIdx = getStateIdx(moveOp.getInput());
334                                int destIdx = getStateIdx(moveOp.getResult());
335                                if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
336                                    assert iterState[sourceIdx] != INIT_VALUE;
337                                    Debug.log("delete move %s", op);
338                                    instructions.set(idx, null);
339                                    hasDead = true;
340                                }
341                            }
342                            // It doesn't harm if updateState is also called for a deleted move
343                            valueNum = updateState(iterState, op, valueNum);
344                        }
345                        if (hasDead) {
346                            instructions.removeAll(Collections.singleton(null));
347                        }
348                    }
349                }
350            }
351        }
352
353        /**
354         * Updates the state for one instruction.
355         */
356        private int updateState(final int[] state, LIRInstruction op, int initValueNum) {
357
358            try (final Indent indent = Debug.logAndIndent("update state for op %s, initial value num = %d", op, initValueNum)) {
359                if (isEligibleMove(op)) {
360                    /*
361                     * Handle the special case of a move instruction
362                     */
363                    MoveOp moveOp = (MoveOp) op;
364                    int sourceIdx = getStateIdx(moveOp.getInput());
365                    int destIdx = getStateIdx(moveOp.getResult());
366                    if (sourceIdx >= 0 && destIdx >= 0) {
367                        assert isObjectValue(state[sourceIdx]) || moveOp.getInput().getLIRKind().isValue() : "move op moves object but input is not defined as object";
368                        state[destIdx] = state[sourceIdx];
369                        Debug.log("move value %d from %d to %d", state[sourceIdx], sourceIdx, destIdx);
370                        return initValueNum;
371                    }
372                }
373
374                int valueNum = initValueNum;
375
376                if (op.destroysCallerSavedRegisters()) {
377                    Debug.log("kill all caller save regs");
378
379                    for (Register reg : callerSaveRegs) {
380                        if (reg.number < numRegs) {
381                            // Kind.Object is the save default
382                            state[reg.number] = encodeValueNum(valueNum++, true);
383                        }
384                    }
385                }
386
387                /*
388                 * Value procedure for the instruction's output and temp values
389                 */
390                class OutputValueConsumer implements ValueConsumer {
391
392                    int opValueNum;
393
394                    OutputValueConsumer(int opValueNum) {
395                        this.opValueNum = opValueNum;
396                    }
397
398                    @Override
399                    public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
400                        int stateIdx = getStateIdx(operand);
401                        if (stateIdx >= 0) {
402                            /*
403                             * Assign a unique number to the output or temp location.
404                             */
405                            state[stateIdx] = encodeValueNum(opValueNum++, !operand.getLIRKind().isValue());
406                            Debug.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]);
407                        }
408                    }
409                }
410
411                OutputValueConsumer outputValueConsumer = new OutputValueConsumer(valueNum);
412
413                op.visitEachTemp(outputValueConsumer);
414                /*
415                 * Semantically the output values are written _after_ the temp values
416                 */
417                op.visitEachOutput(outputValueConsumer);
418
419                valueNum = outputValueConsumer.opValueNum;
420
421                if (op.hasState()) {
422                    /*
423                     * All instructions with framestates (mostly method calls), may do garbage
424                     * collection. GC will rewrite all object references which are live at this
425                     * point. So we can't rely on their values. It would be sufficient to just kill
426                     * all values which are referenced in the state (or all values which are not),
427                     * but for simplicity we kill all values.
428                     */
429                    Debug.log("kill all object values");
430                    clearValuesOfKindObject(state, valueNum);
431                    valueNum += state.length;
432                }
433
434                return valueNum;
435            }
436        }
437
438        /**
439         * The state merge function for dataflow joins.
440         */
441        private static boolean mergeState(int[] dest, int[] source, int defNum) {
442            assert dest.length == source.length;
443            boolean changed = false;
444            for (int idx = 0; idx < source.length; idx++) {
445                int phiNum = defNum + idx;
446                int dst = dest[idx];
447                int src = source[idx];
448                if (dst != src && src != INIT_VALUE && dst != encodeValueNum(phiNum, isObjectValue(dst))) {
449                    if (dst != INIT_VALUE) {
450                        dst = encodeValueNum(phiNum, isObjectValue(dst) || isObjectValue(src));
451                    } else {
452                        dst = src;
453                    }
454                    dest[idx] = dst;
455                    changed = true;
456                }
457            }
458            return changed;
459        }
460
461        private static void copyState(int[] dest, int[] source) {
462            assert dest.length == source.length;
463            for (int idx = 0; idx < source.length; idx++) {
464                dest[idx] = source[idx];
465            }
466        }
467
468        private static void clearValues(int[] state, int defNum) {
469            for (int idx = 0; idx < state.length; idx++) {
470                int phiNum = defNum + idx;
471                // Let the killed values assume to be object references: it's the save default.
472                state[idx] = encodeValueNum(phiNum, true);
473            }
474        }
475
476        private static void clearValuesOfKindObject(int[] state, int defNum) {
477            for (int idx = 0; idx < state.length; idx++) {
478                int phiNum = defNum + idx;
479                if (isObjectValue(state[idx])) {
480                    state[idx] = encodeValueNum(phiNum, true);
481                }
482            }
483        }
484
485        /**
486         * Returns the index to the state arrays in BlockData for a specific location.
487         */
488        private int getStateIdx(Value location) {
489            if (isRegister(location)) {
490                int regNum = ((RegisterValue) location).getRegister().number;
491                if (regNum < numRegs) {
492                    return eligibleRegs[regNum];
493                }
494                return -1;
495            }
496            if (isStackSlot(location)) {
497                StackSlot slot = (StackSlot) location;
498                Integer index = stackIndices.get(getOffset(slot));
499                if (index != null) {
500                    return index.intValue() + numRegs;
501                }
502            }
503            return -1;
504        }
505
506        /**
507         * Encodes a value number + the is-object information to a number to be stored in a state.
508         */
509        private static int encodeValueNum(int valueNum, boolean isObjectKind) {
510            assert valueNum > 0;
511            if (isObjectKind) {
512                return -valueNum;
513            }
514            return valueNum;
515        }
516
517        /**
518         * Returns true if an encoded value number (which is stored in a state) refers to an object
519         * reference.
520         */
521        private static boolean isObjectValue(int encodedValueNum) {
522            return encodedValueNum < 0;
523        }
524
525        /**
526         * Returns true for a move instruction which is a candidate for elimination.
527         */
528        private static boolean isEligibleMove(LIRInstruction op) {
529            if (op instanceof MoveOp) {
530                MoveOp moveOp = (MoveOp) op;
531                Value source = moveOp.getInput();
532                Value dest = moveOp.getResult();
533                /*
534                 * Moves with mismatching kinds are not moves, but memory loads/stores!
535                 */
536                return source.getLIRKind().equals(dest.getLIRKind());
537            }
538            return false;
539        }
540    }
541}