Source code

001/*
002 * Copyright (c) 2009, 2012, 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.lsra;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import jdk.internal.jvmci.common.*;
031import com.oracle.graal.debug.*;
032import com.oracle.graal.debug.Debug.Scope;
033import jdk.internal.jvmci.meta.*;
034
035import com.oracle.graal.compiler.common.cfg.*;
036import com.oracle.graal.compiler.common.util.*;
037import com.oracle.graal.lir.*;
038import com.oracle.graal.lir.LIRInstruction.OperandFlag;
039import com.oracle.graal.lir.LIRInstruction.OperandMode;
040
041/**
042 */
043final class RegisterVerifier {
044
045    LinearScan allocator;
046    List<AbstractBlockBase<?>> workList; // all blocks that must be processed
047    ArrayMap<Interval[]> savedStates; // saved information of previous check
048
049    // simplified access to methods of LinearScan
050    Interval intervalAt(Value operand) {
051        return allocator.intervalFor(operand);
052    }
053
054    // currently, only registers are processed
055    int stateSize() {
056        return allocator.maxRegisterNumber() + 1;
057    }
058
059    // accessors
060    Interval[] stateForBlock(AbstractBlockBase<?> block) {
061        return savedStates.get(block.getId());
062    }
063
064    void setStateForBlock(AbstractBlockBase<?> block, Interval[] savedState) {
065        savedStates.put(block.getId(), savedState);
066    }
067
068    void addToWorkList(AbstractBlockBase<?> block) {
069        if (!workList.contains(block)) {
070            workList.add(block);
071        }
072    }
073
074    RegisterVerifier(LinearScan allocator) {
075        this.allocator = allocator;
076        workList = new ArrayList<>(16);
077        this.savedStates = new ArrayMap<>();
078
079    }
080
081    void verify(AbstractBlockBase<?> start) {
082        try (Scope s = Debug.scope("RegisterVerifier")) {
083            // setup input registers (method arguments) for first block
084            Interval[] inputState = new Interval[stateSize()];
085            setStateForBlock(start, inputState);
086            addToWorkList(start);
087
088            // main loop for verification
089            do {
090                AbstractBlockBase<?> block = workList.get(0);
091                workList.remove(0);
092
093                processBlock(block);
094            } while (!workList.isEmpty());
095        }
096    }
097
098    private void processBlock(AbstractBlockBase<?> block) {
099        try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) {
100            // must copy state because it is modified
101            Interval[] inputState = copy(stateForBlock(block));
102
103            try (Indent indent2 = Debug.logAndIndent("Input-State of intervals:")) {
104                printState(inputState);
105            }
106
107            // process all operations of the block
108            processOperations(block, inputState);
109
110            try (Indent indent2 = Debug.logAndIndent("Output-State of intervals:")) {
111                printState(inputState);
112            }
113
114            // iterate all successors
115            for (AbstractBlockBase<?> succ : block.getSuccessors()) {
116                processSuccessor(succ, inputState);
117            }
118        }
119    }
120
121    protected void printState(Interval[] inputState) {
122        for (int i = 0; i < stateSize(); i++) {
123            Register reg = allocator.getRegisters()[i];
124            assert reg.number == i;
125            if (inputState[i] != null) {
126                Debug.log(" %6s %4d  --  %s", reg, inputState[i].operandNumber, inputState[i]);
127            } else {
128                Debug.log(" %6s   __", reg);
129            }
130        }
131    }
132
133    private void processSuccessor(AbstractBlockBase<?> block, Interval[] inputState) {
134        Interval[] savedState = stateForBlock(block);
135
136        if (savedState != null) {
137            // this block was already processed before.
138            // check if new inputState is consistent with savedState
139
140            boolean savedStateCorrect = true;
141            for (int i = 0; i < stateSize(); i++) {
142                if (inputState[i] != savedState[i]) {
143                    // current inputState and previous savedState assume a different
144                    // interval in this register . assume that this register is invalid
145                    if (savedState[i] != null) {
146                        // invalidate old calculation only if it assumed that
147                        // register was valid. when the register was already invalid,
148                        // then the old calculation was correct.
149                        savedStateCorrect = false;
150                        savedState[i] = null;
151
152                        Debug.log("processSuccessor B%d: invalidating slot %d", block.getId(), i);
153                    }
154                }
155            }
156
157            if (savedStateCorrect) {
158                // already processed block with correct inputState
159                Debug.log("processSuccessor B%d: previous visit already correct", block.getId());
160            } else {
161                // must re-visit this block
162                Debug.log("processSuccessor B%d: must re-visit because input state changed", block.getId());
163                addToWorkList(block);
164            }
165
166        } else {
167            // block was not processed before, so set initial inputState
168            Debug.log("processSuccessor B%d: initial visit", block.getId());
169
170            setStateForBlock(block, copy(inputState));
171            addToWorkList(block);
172        }
173    }
174
175    static Interval[] copy(Interval[] inputState) {
176        return inputState.clone();
177    }
178
179    static void statePut(Interval[] inputState, Value location, Interval interval) {
180        if (location != null && isRegister(location)) {
181            Register reg = asRegister(location);
182            int regNum = reg.number;
183            if (interval != null) {
184                Debug.log("%s = %s", reg, interval.operand);
185            } else if (inputState[regNum] != null) {
186                Debug.log("%s = null", reg);
187            }
188
189            inputState[regNum] = interval;
190        }
191    }
192
193    static boolean checkState(AbstractBlockBase<?> block, LIRInstruction op, Interval[] inputState, Value operand, Value reg, Interval interval) {
194        if (reg != null && isRegister(reg)) {
195            if (inputState[asRegister(reg).number] != interval) {
196                throw new JVMCIError(
197                                "Error in register allocation: operation (%s) in block %s expected register %s (operand %s) to contain the value of interval %s but data-flow says it contains interval %s",
198                                op, block, reg, operand, interval, inputState[asRegister(reg).number]);
199            }
200        }
201        return true;
202    }
203
204    void processOperations(AbstractBlockBase<?> block, final Interval[] inputState) {
205        List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block);
206        InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
207
208            @Override
209            public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
210                // we skip spill moves inserted by the spill position optimization
211                if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != LinearScan.DOMINATOR_SPILL_MOVE_ID) {
212                    Interval interval = intervalAt(operand);
213                    if (op.id() != -1) {
214                        interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
215                    }
216
217                    assert checkState(block, op, inputState, interval.operand, interval.location(), interval.splitParent());
218                }
219            }
220        };
221
222        InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> {
223            if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) {
224                Interval interval = intervalAt(operand);
225                if (op.id() != -1) {
226                    interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
227                }
228
229                statePut(inputState, interval.location(), interval.splitParent());
230            }
231        };
232
233        // visit all instructions of the block
234        for (int i = 0; i < ops.size(); i++) {
235            final LIRInstruction op = ops.get(i);
236
237            if (Debug.isLogEnabled()) {
238                Debug.log("%s", op.toStringWithIdPrefix());
239            }
240
241            // check if input operands are correct
242            op.visitEachInput(useConsumer);
243            // invalidate all caller save registers at calls
244            if (op.destroysCallerSavedRegisters()) {
245                for (Register r : allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters()) {
246                    statePut(inputState, r.asValue(), null);
247                }
248            }
249            op.visitEachAlive(useConsumer);
250            // set temp operands (some operations use temp operands also as output operands, so
251            // can't set them null)
252            op.visitEachTemp(defConsumer);
253            // set output operands
254            op.visitEachOutput(defConsumer);
255        }
256    }
257}