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.stackslotalloc;
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.cfg.*;
034import com.oracle.graal.lir.*;
035import com.oracle.graal.lir.LIRInstruction.OperandFlag;
036import com.oracle.graal.lir.LIRInstruction.OperandMode;
037
038/**
039 * Calculates the stack intervals using a worklist-based backwards data-flow analysis.
040 */
041final class FixPointIntervalBuilder {
042    private final BlockMap<BitSet> liveInMap;
043    private final BlockMap<BitSet> liveOutMap;
044    private final LIR lir;
045    private final int maxOpId;
046    private final StackInterval[] stackSlotMap;
047    private final HashSet<LIRInstruction> usePos;
048
049    /**
050     * The number of allocated stack slots.
051     */
052    private static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]");
053
054    FixPointIntervalBuilder(LIR lir, StackInterval[] stackSlotMap, int maxOpId) {
055        this.lir = lir;
056        this.stackSlotMap = stackSlotMap;
057        this.maxOpId = maxOpId;
058        liveInMap = new BlockMap<>(lir.getControlFlowGraph());
059        liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
060        this.usePos = new HashSet<>();
061    }
062
063    /**
064     * Builds the lifetime intervals for {@link VirtualStackSlot virtual stack slots}, sets up
065     * {@link #stackSlotMap} and returns a set of use positions, i.e. instructions that contain
066     * virtual stack slots.
067     */
068    Set<LIRInstruction> build() {
069        Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
070        for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
071            worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
072        }
073        for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
074            liveInMap.put(block, new BitSet(stackSlotMap.length));
075        }
076        while (!worklist.isEmpty()) {
077            AbstractBlockBase<?> block = worklist.poll();
078            processBlock(block, worklist);
079        }
080        return usePos;
081    }
082
083    /**
084     * Merge outSet with in-set of successors.
085     */
086    private boolean updateOutBlock(AbstractBlockBase<?> block) {
087        BitSet union = new BitSet(stackSlotMap.length);
088        block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ)));
089        BitSet outSet = liveOutMap.get(block);
090        // check if changed
091        if (outSet == null || !union.equals(outSet)) {
092            liveOutMap.put(block, union);
093            return true;
094        }
095        return false;
096    }
097
098    private void processBlock(AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) {
099        if (updateOutBlock(block)) {
100            try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
101                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
102                // get out set and mark intervals
103                BitSet outSet = liveOutMap.get(block);
104                markOutInterval(outSet, getBlockEnd(instructions));
105                printLiveSet("liveOut", outSet);
106
107                // process instructions
108                BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
109                for (int i = instructions.size() - 1; i >= 0; i--) {
110                    LIRInstruction inst = instructions.get(i);
111                    closure.processInstructionBottomUp(inst);
112                }
113
114                // add predecessors to work list
115                worklist.addAll(block.getPredecessors());
116                // set in set and mark intervals
117                BitSet inSet = closure.getCurrentSet();
118                liveInMap.put(block, inSet);
119                markInInterval(inSet, getBlockBegin(instructions));
120                printLiveSet("liveIn", inSet);
121            }
122        }
123    }
124
125    private void printLiveSet(String label, BitSet liveSet) {
126        if (Debug.isLogEnabled()) {
127            try (Indent indent = Debug.logAndIndent(label)) {
128                Debug.log("%s", liveSetToString(liveSet));
129            }
130        }
131    }
132
133    private String liveSetToString(BitSet liveSet) {
134        StringBuilder sb = new StringBuilder();
135        for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
136            StackInterval interval = getIntervalFromStackId(i);
137            sb.append(interval.getOperand()).append(" ");
138        }
139        return sb.toString();
140    }
141
142    private void markOutInterval(BitSet outSet, int blockEndOpId) {
143        for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
144            StackInterval interval = getIntervalFromStackId(i);
145            Debug.log("mark live operand: %s", interval.getOperand());
146            interval.addTo(blockEndOpId);
147        }
148    }
149
150    private void markInInterval(BitSet inSet, int blockFirstOpId) {
151        for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
152            StackInterval interval = getIntervalFromStackId(i);
153            Debug.log("mark live operand: %s", interval.getOperand());
154            interval.addFrom(blockFirstOpId);
155        }
156    }
157
158    private final class BlockClosure {
159        private final BitSet currentSet;
160
161        private BlockClosure(BitSet set) {
162            currentSet = set;
163        }
164
165        private BitSet getCurrentSet() {
166            return currentSet;
167        }
168
169        /**
170         * Process all values of an instruction bottom-up, i.e. definitions before usages. Values
171         * that start or end at the current operation are not included.
172         */
173        private void processInstructionBottomUp(LIRInstruction op) {
174            try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
175                // kills
176                op.visitEachTemp(defConsumer);
177                op.visitEachOutput(defConsumer);
178
179                // gen - values that are considered alive for this state
180                op.visitEachAlive(useConsumer);
181                op.visitEachState(useConsumer);
182                // mark locations
183                // gen
184                op.visitEachInput(useConsumer);
185            }
186        }
187
188        InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
189            public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
190                if (isVirtualStackSlot(operand)) {
191                    VirtualStackSlot vslot = asVirtualStackSlot(operand);
192                    addUse(vslot, inst, flags);
193                    addRegisterHint(inst, vslot, mode, flags, false);
194                    usePos.add(inst);
195                    Debug.log("set operand: %s", operand);
196                    currentSet.set(vslot.getId());
197                }
198            }
199        };
200
201        InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
202            public void visitValue(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
203                if (isVirtualStackSlot(operand)) {
204                    VirtualStackSlot vslot = asVirtualStackSlot(operand);
205                    addDef(vslot, inst);
206                    addRegisterHint(inst, vslot, mode, flags, true);
207                    usePos.add(inst);
208                    Debug.log("clear operand: %s", operand);
209                    currentSet.clear(vslot.getId());
210                }
211
212            }
213        };
214
215        private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
216            StackInterval interval = getOrCreateInterval(stackSlot);
217            if (flags.contains(OperandFlag.UNINITIALIZED)) {
218                // Stack slot is marked uninitialized so we have to assume it is live all
219                // the time.
220                if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId)) {
221                    uninitializedSlots.increment();
222                }
223                interval.addFrom(0);
224                interval.addTo(maxOpId);
225            } else {
226                interval.addTo(inst.id());
227            }
228        }
229
230        private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
231            StackInterval interval = getOrCreateInterval(stackSlot);
232            interval.addFrom(inst.id());
233        }
234
235        void addRegisterHint(final LIRInstruction op, VirtualStackSlot targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
236            if (flags.contains(OperandFlag.HINT)) {
237
238                op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
239                    if (isVirtualStackSlot(registerHint)) {
240                        StackInterval from = getOrCreateInterval((VirtualStackSlot) registerHint);
241                        StackInterval to = getOrCreateInterval(targetValue);
242
243                        /* hints always point from def to use */
244                        if (hintAtDef) {
245                            to.setLocationHint(from);
246                        } else {
247                            from.setLocationHint(to);
248                        }
249                        if (Debug.isLogEnabled()) {
250                            Debug.log("operation %s at opId %d: added hint from interval %d to %d", op, op.id(), from, to);
251                        }
252
253                        return registerHint;
254                    }
255                    return null;
256                });
257            }
258        }
259
260    }
261
262    private StackInterval get(VirtualStackSlot stackSlot) {
263        return stackSlotMap[stackSlot.getId()];
264    }
265
266    private void put(VirtualStackSlot stackSlot, StackInterval interval) {
267        stackSlotMap[stackSlot.getId()] = interval;
268    }
269
270    private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
271        StackInterval interval = get(stackSlot);
272        if (interval == null) {
273            interval = new StackInterval(stackSlot, stackSlot.getLIRKind());
274            put(stackSlot, interval);
275        }
276        return interval;
277    }
278
279    private StackInterval getIntervalFromStackId(int id) {
280        return stackSlotMap[id];
281    }
282
283    private static int getBlockBegin(List<LIRInstruction> instructions) {
284        return instructions.get(0).id();
285    }
286
287    private static int getBlockEnd(List<LIRInstruction> instructions) {
288        return instructions.get(instructions.size() - 1).id() + 1;
289    }
290
291}