Source code

001/*
002 * Copyright (c) 2015, 2015, 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.alloc.trace;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import jdk.internal.jvmci.meta.*;
031
032import com.oracle.graal.compiler.common.alloc.*;
033import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
034import com.oracle.graal.compiler.common.cfg.*;
035import com.oracle.graal.debug.*;
036import com.oracle.graal.lir.*;
037import com.oracle.graal.lir.alloc.lsra.*;
038import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
039import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
040import com.oracle.graal.lir.gen.*;
041import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
042
043public class TraceSimpleLifetimeAnalysisPhase extends TraceLinearScanLifetimeAnalysisPhase {
044
045    public TraceSimpleLifetimeAnalysisPhase(LinearScan allocator, TraceBuilderResult<?> traceBuilderResult) {
046        super(allocator, traceBuilderResult);
047    }
048
049    @Override
050    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
051                    RegisterAllocationConfig registerAllocationConfig) {
052        numberInstructions();
053        allocator.printLir("Before register allocation", true);
054        buildIntervals();
055    }
056
057    @Override
058    protected void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) {
059        if (!allocator.isProcessed(operand)) {
060            return;
061        }
062        if (isRegister(operand)) {
063            super.addUse(operand, from, to, registerPriority, kind);
064            return;
065        }
066
067        Interval interval = allocator.getOrCreateInterval(operand);
068        if (!kind.equals(LIRKind.Illegal)) {
069            interval.setKind(kind);
070        }
071
072        Range r = interval.first();
073        if (r == Range.EndMarker) {
074            interval.addRange(from, to);
075        } else if (r.from > from) {
076            r.from = from;
077        }
078
079        // Register use position at even instruction id.
080        interval.addUsePos(to & ~1, registerPriority);
081
082        if (Debug.isLogEnabled()) {
083            Debug.log("add use: %s, at %d (%s)", interval, to, registerPriority.name());
084        }
085    }
086
087    @Override
088    protected void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) {
089        if (!allocator.isProcessed(operand)) {
090            return;
091        }
092        if (isRegister(operand)) {
093            super.addTemp(operand, tempPos, registerPriority, kind);
094            return;
095        }
096
097        Interval interval = allocator.getOrCreateInterval(operand);
098        if (!kind.equals(LIRKind.Illegal)) {
099            interval.setKind(kind);
100        }
101
102        Range r = interval.first();
103        if (r == Range.EndMarker) {
104            interval.addRange(tempPos, tempPos + 1);
105        } else if (r.from > tempPos) {
106            r.from = tempPos;
107        }
108        interval.addUsePos(tempPos, registerPriority);
109        interval.addMaterializationValue(null);
110
111        if (Debug.isLogEnabled()) {
112            Debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name());
113        }
114    }
115
116    @Override
117    protected void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) {
118        if (!allocator.isProcessed(operand)) {
119            return;
120        }
121        if (isRegister(operand)) {
122            super.addDef(operand, op, registerPriority, kind);
123            return;
124        }
125        int defPos = op.id();
126
127        Interval interval = allocator.getOrCreateInterval(operand);
128        if (!kind.equals(LIRKind.Illegal)) {
129            interval.setKind(kind);
130        }
131
132        Range r = interval.first();
133        if (r == Range.EndMarker) {
134            /*
135             * Dead value - make vacuous interval also add register priority for dead intervals
136             */
137            interval.addRange(defPos, defPos + 1);
138            interval.addUsePos(defPos, registerPriority);
139            if (Debug.isLogEnabled()) {
140                Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
141            }
142        } else {
143            /*
144             * Update the starting point (when a range is first created for a use, its start is the
145             * beginning of the current block until a def is encountered).
146             */
147            r.from = defPos;
148            interval.addUsePos(defPos, registerPriority);
149
150        }
151
152        changeSpillDefinitionPos(op, operand, interval, defPos);
153        if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) {
154            // detection of method-parameters and roundfp-results
155            interval.setSpillState(SpillState.StartInMemory);
156        }
157        interval.addMaterializationValue(getMaterializedValue(op, operand, interval));
158
159        if (Debug.isLogEnabled()) {
160            Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
161        }
162    }
163
164    @Override
165    protected void buildIntervals() {
166
167        try (Indent indent = Debug.logAndIndent("build intervals")) {
168            InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
169                if (LinearScan.isVariableOrRegister(operand)) {
170                    addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind());
171                    addRegisterHint(op, operand, mode, flags, true);
172                }
173            };
174
175            InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> {
176                if (LinearScan.isVariableOrRegister(operand)) {
177                    addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind());
178                    addRegisterHint(op, operand, mode, flags, false);
179                }
180            };
181
182            InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> {
183                if (LinearScan.isVariableOrRegister(operand)) {
184                    RegisterPriority p = registerPriorityOfInputOperand(flags);
185                    int opId = op.id();
186                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
187                    addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getLIRKind());
188                    addRegisterHint(op, operand, mode, flags, false);
189                }
190            };
191
192            InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
193                if (LinearScan.isVariableOrRegister(operand)) {
194                    int opId = op.id();
195                    RegisterPriority p = registerPriorityOfInputOperand(flags);
196                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
197                    addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind());
198                    addRegisterHint(op, operand, mode, flags, false);
199                }
200            };
201
202            InstructionValueConsumer stateProc = (op, operand, mode, flags) -> {
203                if (LinearScan.isVariableOrRegister(operand)) {
204                    int opId = op.id();
205                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
206                    addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());
207                }
208            };
209
210            // create a list with all caller-save registers (cpu, fpu, xmm)
211            Register[] callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters();
212
213            // iterate all blocks in reverse order
214            for (int i = allocator.blockCount() - 1; i >= 0; i--) {
215
216                AbstractBlockBase<?> block = allocator.blockAt(i);
217                // TODO (je) make empty bitset - remove
218                allocator.getBlockData(block).liveIn = new BitSet();
219                allocator.getBlockData(block).liveOut = new BitSet();
220                try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
221
222                    List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
223
224                    /*
225                     * Iterate all instructions of the block in reverse order. definitions of
226                     * intervals are processed before uses.
227                     */
228                    for (int j = instructions.size() - 1; j >= 0; j--) {
229                        final LIRInstruction op = instructions.get(j);
230                        final int opId = op.id();
231
232                        try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) {
233
234                            // add a temp range for each register if operation destroys
235                            // caller-save registers
236                            if (op.destroysCallerSavedRegisters()) {
237                                for (Register r : callerSaveRegs) {
238                                    if (allocator.attributes(r).isAllocatable()) {
239                                        addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal);
240                                    }
241                                }
242                                if (Debug.isLogEnabled()) {
243                                    Debug.log("operation destroys all caller-save registers");
244                                }
245                            }
246
247                            op.visitEachOutput(outputConsumer);
248                            op.visitEachTemp(tempConsumer);
249                            op.visitEachAlive(aliveConsumer);
250                            op.visitEachInput(inputConsumer);
251
252                            /*
253                             * Add uses of live locals from interpreter's point of view for proper
254                             * debug information generation. Treat these operands as temp values (if
255                             * the live range is extended to a call site, the value would be in a
256                             * register at the call otherwise).
257                             */
258                            op.visitEachState(stateProc);
259
260                            // special steps for some instructions (especially moves)
261                            handleMethodArguments(op);
262
263                        }
264
265                    } // end of instruction iteration
266                }
267                allocator.printIntervals("After Block " + block);
268            } // end of block iteration
269
270            /*
271             * Add the range [0, 1] to all fixed intervals. the register allocator need not handle
272             * unhandled fixed intervals.
273             */
274            for (Interval interval : allocator.intervals()) {
275                if (interval != null && isRegister(interval.operand)) {
276                    interval.addRange(0, 1);
277                }
278            }
279        }
280        postBuildIntervals();
281    }
282}