Mercurial > hg > graal-jvmci-8
diff graal/Compiler/src/com/sun/c1x/alloc/RegisterVerifier.java @ 2507:9ec15d6914ca
Pull over of compiler from maxine repository.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:43:22 +0200 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/Compiler/src/com/sun/c1x/alloc/RegisterVerifier.java Wed Apr 27 11:43:22 2011 +0200 @@ -0,0 +1,299 @@ +/* + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.sun.c1x.alloc; + +import java.util.*; + +import com.sun.c1x.*; +import com.sun.c1x.debug.*; +import com.sun.c1x.ir.*; +import com.sun.c1x.lir.*; +import com.sun.c1x.util.*; +import com.sun.cri.ci.*; + +/** + * + * @author Thomas Wuerthinger + */ +final class RegisterVerifier { + + LinearScan allocator; + List<BlockBegin> workList; // all blocks that must be processed + ArrayMap<Interval[]> savedStates; // saved information of previous check + + // simplified access to methods of LinearScan + C1XCompilation compilation() { + return allocator.compilation; + } + + Interval intervalAt(CiValue operand) { + return allocator.intervalFor(operand); + } + + // currently, only registers are processed + int stateSize() { + return allocator.operands.maxRegisterNumber() + 1; + } + + // accessors + Interval[] stateForBlock(BlockBegin block) { + return savedStates.get(block.blockID); + } + + void setStateForBlock(BlockBegin block, Interval[] savedState) { + savedStates.put(block.blockID, savedState); + } + + void addToWorkList(BlockBegin block) { + if (!workList.contains(block)) { + workList.add(block); + } + } + + RegisterVerifier(LinearScan allocator) { + this.allocator = allocator; + workList = new ArrayList<BlockBegin>(16); + this.savedStates = new ArrayMap<Interval[]>(); + + } + + void verify(BlockBegin start) { + // setup input registers (method arguments) for first block + Interval[] inputState = new Interval[stateSize()]; + CiCallingConvention args = compilation().frameMap().incomingArguments(); + for (int n = 0; n < args.locations.length; n++) { + CiValue operand = args.locations[n]; + if (operand.isRegister()) { + CiValue reg = operand; + Interval interval = intervalAt(reg); + inputState[reg.asRegister().number] = interval; + } + } + + setStateForBlock(start, inputState); + addToWorkList(start); + + // main loop for verification + do { + BlockBegin block = workList.get(0); + workList.remove(0); + + processBlock(block); + } while (!workList.isEmpty()); + } + + void processBlock(BlockBegin block) { + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(); + TTY.println("processBlock B%d", block.blockID); + } + + // must copy state because it is modified + Interval[] inputState = copy(stateForBlock(block)); + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("Input-State of intervals:"); + TTY.print(" "); + for (int i = 0; i < stateSize(); i++) { + if (inputState[i] != null) { + TTY.print(" %4d", inputState[i].operandNumber); + } else { + TTY.print(" __"); + } + } + TTY.println(); + TTY.println(); + } + + // process all operations of the block + processOperations(block.lir(), inputState); + + // iterate all successors + for (BlockBegin succ : block.end().successors()) { + processSuccessor(succ, inputState); + } + } + + void processXhandler(ExceptionHandler xhandler, Interval[] inputState) { + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("processXhandler B%d", xhandler.entryBlock().blockID); + } + + // must copy state because it is modified + inputState = copy(inputState); + + if (xhandler.entryCode() != null) { + processOperations(xhandler.entryCode(), inputState); + } + processSuccessor(xhandler.entryBlock(), inputState); + } + + void processSuccessor(BlockBegin block, Interval[] inputState) { + Interval[] savedState = stateForBlock(block); + + if (savedState != null) { + // this block was already processed before. + // check if new inputState is consistent with savedState + + boolean savedStateCorrect = true; + for (int i = 0; i < stateSize(); i++) { + if (inputState[i] != savedState[i]) { + // current inputState and previous savedState assume a different + // interval in this register . assume that this register is invalid + if (savedState[i] != null) { + // invalidate old calculation only if it assumed that + // register was valid. when the register was already invalid, + // then the old calculation was correct. + savedStateCorrect = false; + savedState[i] = null; + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("processSuccessor B%d: invalidating slot %d", block.blockID, i); + } + } + } + } + + if (savedStateCorrect) { + // already processed block with correct inputState + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("processSuccessor B%d: previous visit already correct", block.blockID); + } + } else { + // must re-visit this block + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("processSuccessor B%d: must re-visit because input state changed", block.blockID); + } + addToWorkList(block); + } + + } else { + // block was not processed before, so set initial inputState + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("processSuccessor B%d: initial visit", block.blockID); + } + + setStateForBlock(block, copy(inputState)); + addToWorkList(block); + } + } + + Interval[] copy(Interval[] inputState) { + return inputState.clone(); + } + + void statePut(Interval[] inputState, CiValue location, Interval interval) { + if (location != null && location.isRegister()) { + CiRegister reg = location.asRegister(); + int regNum = reg.number; + if (interval != null) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println(" %s = %s", reg, interval.operand); + } + } else if (inputState[regNum] != null) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println(" %s = null", reg); + } + } + + inputState[regNum] = interval; + } + } + + boolean checkState(Interval[] inputState, CiValue reg, Interval interval) { + if (reg != null && reg.isRegister()) { + if (inputState[reg.asRegister().number] != interval) { + throw new CiBailout("!! Error in register allocation: register " + reg + " does not contain interval " + interval.operand + " but interval " + inputState[reg.asRegister().number]); + } + } + return true; + } + + void processOperations(LIRList ops, Interval[] inputState) { + // visit all instructions of the block + for (int i = 0; i < ops.length(); i++) { + LIRInstruction op = ops.at(i); + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println(op.toStringWithIdPrefix()); + } + + // check if input operands are correct + int n = op.operandCount(LIRInstruction.OperandMode.Input); + for (int j = 0; j < n; j++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, j); + if (allocator.isProcessed(operand)) { + Interval interval = intervalAt(operand); + if (op.id != -1) { + interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Input, allocator); + } + + assert checkState(inputState, interval.location(), interval.splitParent()); + } + } + + // invalidate all caller save registers at calls + if (op.hasCall) { + for (CiRegister r : allocator.compilation.registerConfig.getCallerSaveRegisters()) { + statePut(inputState, r.asValue(), null); + } + } + + // process xhandler before output and temp operands + List<ExceptionHandler> xhandlers = op.exceptionEdges(); + n = xhandlers.size(); + for (int k = 0; k < n; k++) { + processXhandler(xhandlers.get(k), inputState); + } + + // set temp operands (some operations use temp operands also as output operands, so can't set them null) + n = op.operandCount(LIRInstruction.OperandMode.Temp); + for (int j = 0; j < n; j++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, j); + if (allocator.isProcessed(operand)) { + Interval interval = intervalAt(operand); + assert interval != null : "Could not find interval for operand " + operand; + if (op.id != -1) { + interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Temp, allocator); + } + + statePut(inputState, interval.location(), interval.splitParent()); + } + } + + // set output operands + n = op.operandCount(LIRInstruction.OperandMode.Output); + for (int j = 0; j < n; j++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, j); + if (allocator.isProcessed(operand)) { + Interval interval = intervalAt(operand); + if (op.id != -1) { + interval = interval.getSplitChildAtOpId(op.id, LIRInstruction.OperandMode.Output, allocator); + } + + statePut(inputState, interval.location(), interval.splitParent()); + } + } + } + } +}