# HG changeset patch # User Thomas Wuerthinger # Date 1309981239 -7200 # Node ID 2de2bff9dba6a99809ae32e5b39d8c215731a398 # Parent bef7921f8247ed07aa6e49c01d938437bb35ade1 decoupled code emitting order from linear scan order. align loops. reorder short loops. fixed linear scan order. diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Wed Jul 06 21:40:39 2011 +0200 @@ -35,6 +35,7 @@ import com.oracle.max.graal.compiler.lir.*; import com.oracle.max.graal.compiler.observer.*; import com.oracle.max.graal.compiler.value.*; +import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -239,8 +240,10 @@ lirGenerator = compiler.backend.newLIRGenerator(this); - for (LIRBlock begin : hir.linearScanOrder()) { - lirGenerator.doBlock(begin); + BitMap blockVisited = new BitMap(hir.linearScanOrder().size()); + for (LIRBlock b : hir.linearScanOrder()) { + lirGenerator.doBlock(b); +// iterateBlocks(b, blockVisited); } if (GraalOptions.Time) { @@ -255,10 +258,28 @@ } } + private void iterateBlocks(LIRBlock b, BitMap blockVisited) { + if (blockVisited.get(b.blockID())) { + return; + } +// TTY.println("visit B" + b.blockID() + "(" + b.isLinearScanLoopHeader() + ")"); +// TTY.println("predecessors: " + b.blockPredecessors()); + blockVisited.set(b.blockID()); + if (!b.isLinearScanLoopHeader()) { + for (LIRBlock pred : b.blockPredecessors()) { +// TTY.println("iterate " + pred + " " + blockVisited.get(pred.blockID())); + iterateBlocks(pred, blockVisited); + } + } else { + iterateBlocks(b.blockPredecessors().get(0), blockVisited); + } + lirGenerator.doBlock(b); + } + private CiTargetMethod emitCode() { if (GraalOptions.GenLIR && GraalOptions.GenCode) { final LIRAssembler lirAssembler = compiler.backend.newLIRAssembler(this); - lirAssembler.emitCode(hir.linearScanOrder()); + lirAssembler.emitCode(hir.codeEmittingOrder()); // generate code for slow cases lirAssembler.emitLocalStubs(); diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Jul 06 21:40:39 2011 +0200 @@ -159,5 +159,6 @@ public static boolean OptCanonicalizer = true; public static boolean OptLoops = ____; public static boolean OptOptimisticSchedule = ____; + public static boolean OptReorderLoops = ____; public static boolean LoopPeeling = ____; } diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ControlFlowOptimizer.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ControlFlowOptimizer.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ControlFlowOptimizer.java Wed Jul 06 21:40:39 2011 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.graph.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.lir.*; @@ -42,7 +43,7 @@ */ public static void optimize(IR ir) { ControlFlowOptimizer optimizer = new ControlFlowOptimizer(ir); - List code = ir.linearScanOrder(); + List code = ir.codeEmittingOrder(); optimizer.reorderShortLoops(code); optimizer.deleteEmptyBlocks(code); optimizer.deleteUnnecessaryJumps(code); diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Wed Jul 06 21:40:39 2011 +0200 @@ -636,6 +636,7 @@ // Add uses of live locals from interpreter's point of view for proper debug information generation LIRDebugInfo info = op.info; if (info != null) { + assert info.state != null; info.state.forEachLiveStateValue(new ValueProcedure() { public void doValue(Value value) { CiValue operand = value.operand(); diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jul 06 21:40:39 2011 +0200 @@ -241,11 +241,35 @@ TTY.println("BEGIN Generating LIR for block B" + block.blockID()); } - if (block.blockPredecessors().size() > 1) { + if (block == ir.startBlock) { + XirSnippet prologue = xir.genPrologue(null, compilation.method); + if (prologue != null) { + emitXir(prologue, null, null, null, false); + } + FrameState fs = setOperandsForLocals(); + if (GraalOptions.TraceLIRGeneratorLevel >= 2) { + TTY.println("STATE CHANGE (setOperandsForLocals)"); + if (GraalOptions.TraceLIRGeneratorLevel >= 3) { + TTY.println(fs.toString()); + } + } + lastState = fs; + } else if (block.blockPredecessors().size() > 1) { if (GraalOptions.TraceLIRGeneratorLevel >= 2) { TTY.println("STATE RESET"); } lastState = null; + } else if (block.blockPredecessors().size() == 1) { + LIRBlock pred = block.blockPredecessors().get(0); + FrameState fs = pred.lastState(); + assert fs != null : "block B" + block.blockID() + " pred block B" + pred.blockID(); + if (GraalOptions.TraceLIRGeneratorLevel >= 2) { + TTY.println("STATE CHANGE (singlePred)"); + if (GraalOptions.TraceLIRGeneratorLevel >= 3) { + TTY.println(fs.toString()); + } + } + lastState = fs; } for (Node instr : block.getInstructions()) { @@ -444,13 +468,13 @@ public void visitExceptionObject(ExceptionObject x) { XirSnippet snippet = xir.genExceptionObject(site(x)); emitXir(snippet, x, null, null, true); - lastState = lastState.duplicateWithException(lastState.bci, x); - if (GraalOptions.TraceLIRGeneratorLevel >= 2) { - TTY.println("STATE CHANGE (visitExceptionObject)"); - if (GraalOptions.TraceLIRGeneratorLevel >= 3) { - TTY.println(lastState.toString()); - } - } +// lastState = lastState.duplicateWithException(lastState.bci, x); +// if (GraalOptions.TraceLIRGeneratorLevel >= 2) { +// TTY.println("STATE CHANGE (visitExceptionObject)"); +// if (GraalOptions.TraceLIRGeneratorLevel >= 3) { +// TTY.println(lastState.toString()); +// } +// } } @Override @@ -1080,30 +1104,6 @@ block.setLir(lir); lir.branchDestination(block.label()); - if (block == ir.startBlock) { - XirSnippet prologue = xir.genPrologue(null, compilation.method); - if (prologue != null) { - emitXir(prologue, null, null, null, false); - } - FrameState fs = setOperandsForLocals(); - if (GraalOptions.TraceLIRGeneratorLevel >= 2) { - TTY.println("STATE CHANGE (setOperandsForLocals)"); - if (GraalOptions.TraceLIRGeneratorLevel >= 3) { - TTY.println(fs.toString()); - } - } - lastState = fs; - } else if (block.blockPredecessors().size() == 1) { - FrameState fs = block.blockPredecessors().get(0).lastState(); - //assert fs != null; - if (GraalOptions.TraceLIRGeneratorLevel >= 2) { - TTY.println("STATE CHANGE (singlePred)"); - if (GraalOptions.TraceLIRGeneratorLevel >= 3) { - TTY.println(fs.toString()); - } - } - lastState = fs; - } } /** diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jul 06 21:40:39 2011 +0200 @@ -52,7 +52,12 @@ /** * The linear-scan ordered list of blocks. */ - private List orderedBlocks; + private List linearScanOrder; + + /** + * The order in which the code is emitted. + */ + private List codeEmittingOrder; /** * Creates a new IR instance for the specified compilation. @@ -138,6 +143,14 @@ block.setLoopDepth(b.loopDepth()); block.setLoopIndex(b.loopIndex()); + if (b.isLoopEnd()) { + block.setLinearScanLoopEnd(); + } + + if (b.isLoopHeader()) { + block.setLinearScanLoopHeader(); + } + block.setFirstInstruction(b.firstNode()); block.setLastInstruction(b.lastNode()); lirBlocks.add(block); @@ -153,9 +166,8 @@ } } - orderedBlocks = lirBlocks; valueToBlock = new HashMap(); - for (LIRBlock b : orderedBlocks) { + for (LIRBlock b : lirBlocks) { for (Node i : b.getInstructions()) { valueToBlock.put(i, b); } @@ -169,11 +181,12 @@ GraalTimers.COMPUTE_LINEAR_SCAN_ORDER.start(); } - ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock); - orderedBlocks = clso.linearScanOrder(); + ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), compilation.stats.loopCount, startBlock); + linearScanOrder = clso.linearScanOrder(); + codeEmittingOrder = clso.codeEmittingOrder(); int z = 0; - for (LIRBlock b : orderedBlocks) { + for (LIRBlock b : linearScanOrder) { b.setLinearScanNumber(z++); } @@ -190,7 +203,11 @@ * @return the blocks in linear scan order */ public List linearScanOrder() { - return orderedBlocks; + return linearScanOrder; + } + + public List codeEmittingOrder() { + return codeEmittingOrder; } public void printGraph(String phase, Graph graph) { diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java Wed Jul 06 21:40:39 2011 +0200 @@ -36,12 +36,14 @@ private int numBlocks; // total number of blocks (smaller than maxBlockId) List linearScanOrder; // the resulting list of blocks in correct order + List codeEmittingOrder; final BitMap visitedBlocks; // used for recursive processing of blocks final BitMap activeBlocks; // used for recursive processing of blocks final BitMap dominatorBlocks; // temporary BitMap used for computation of dominator final int[] forwardBranches; // number of incoming forward branches for each block final List workList; // temporary list (used in markLoops and computeOrder) + final LIRBlock[] loopHeaders; // accessors for visitedBlocks and activeBlocks void initVisited() { @@ -86,7 +88,8 @@ return linearScanOrder; } - public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) { + public ComputeLinearScanOrder(int maxBlockId, int loopCount, LIRBlock startBlock) { + loopHeaders = new LIRBlock[loopCount]; this.maxBlockId = maxBlockId; visitedBlocks = new BitMap(maxBlockId); @@ -257,6 +260,24 @@ // be equal. cur.setLinearScanNumber(linearScanOrder.size()); linearScanOrder.add(cur); + + if (!cur.isLinearScanLoopHeader() || !GraalOptions.OptReorderLoops) { + codeEmittingOrder.add(cur); + + if (cur.isLinearScanLoopEnd() && GraalOptions.OptReorderLoops) { + LIRBlock loopHeader = loopHeaders[cur.loopIndex()]; + assert loopHeader != null; + codeEmittingOrder.add(loopHeader); + + for (LIRBlock succ : loopHeader.blockSuccessors()) { + if (succ.loopDepth() == loopHeader.loopDepth()) { + succ.setAlign(true); + } + } + } + } else { + loopHeaders[cur.loopIndex()] = cur; + } } private void computeOrder(LIRBlock startBlock) { @@ -267,6 +288,8 @@ // the start block is always the first block in the linear scan order linearScanOrder = new ArrayList(numBlocks); + codeEmittingOrder = new ArrayList(numBlocks); + // start processing with standard entry block assert workList.isEmpty() : "list must be empty before processing"; @@ -327,4 +350,8 @@ } } } + + public List codeEmittingOrder() { + return codeEmittingOrder; + } } diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/CreateVectorNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/CreateVectorNode.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/CreateVectorNode.java Wed Jul 06 21:40:39 2011 +0200 @@ -113,6 +113,7 @@ LoopEnd loopEnd = new LoopEnd(graph()); loopEnd.setLoopBegin(loopBegin); + loopBegin.setStateAfter(stateAfter()); Compare condition; if (reversed) { condition = new Compare(loopVariable, Condition.GE, Constant.forInt(0, graph()), graph()); diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRAssembler.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRAssembler.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRAssembler.java Wed Jul 06 21:40:39 2011 +0200 @@ -108,7 +108,7 @@ void emitBlock(LIRBlock block) { - if (block.isLinearScanLoopHeader()) { + if (block.align()) { emitAlignment(); } diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Wed Jul 06 21:40:39 2011 +0200 @@ -45,6 +45,7 @@ private List predecessors = new ArrayList(4); private List successors = new ArrayList(4); private LIRDebugInfo debugInfo; + private boolean align; /** * Bit map specifying which {@linkplain OperandPool operands} are live upon entry to this block. @@ -107,6 +108,14 @@ return firstLirInstructionID; } + public boolean align() { + return align; + } + + public void setAlign(boolean b) { + align = b; + } + public void setFirstLirInstructionId(int firstLirInstructionId) { this.firstLirInstructionID = firstLirInstructionId; } diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Jul 06 21:40:39 2011 +0200 @@ -194,6 +194,7 @@ block.addSuccessor(loopBeginBlock); BitMap map = new BitMap(blocks.size()); markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth()); + assert loopBeginBlock.loopDepth() == block.loopDepth() && loopBeginBlock.loopIndex() == block.loopIndex(); } } @@ -221,6 +222,10 @@ for (Block pred : block.getPredecessors()) { markBlocks(pred, endBlock, map, loopIndex, initialDepth); } + + if (block.isLoopHeader()) { + markBlocks(nodeToBlock.get(((LoopBegin) block.firstNode()).loopEnd()), endBlock, map, loopIndex, initialDepth); + } } private void computeJavaBlocks() { diff -r bef7921f8247 -r 2de2bff9dba6 graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java --- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Wed Jul 06 18:59:55 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Wed Jul 06 21:40:39 2011 +0200 @@ -394,6 +394,9 @@ } CiKind componentType = src.declaredType().componentType().kind(); + if (componentType == CiKind.Object) { + return null; + } FrameState stateBefore = new FrameState(method, FrameState.BEFORE_BCI, 0, 0, 0, false, graph); FrameState stateAfter = new FrameState(method, FrameState.AFTER_BCI, 0, 0, 0, false, graph); diff -r bef7921f8247 -r 2de2bff9dba6 runscimark.sh --- a/runscimark.sh Wed Jul 06 18:59:55 2011 +0200 +++ b/runscimark.sh Wed Jul 06 21:40:39 2011 +0200 @@ -12,16 +12,7 @@ exit 1; fi if [ -z "${SCIMARK}" ]; then - echo "SCIMARK is not defined. It must point to a SciMark benchmark jar." + echo "SCIMARK is not defined. It must point to a directory with the SciMark benchmark jar." exit 1; fi -COUNT=$1 -shift -if [ -z "${COUNT}" ]; then - COUNT=5000 -fi -for (( i = 1; i <= ${COUNT}; i++ )) ### Outer for loop ### -do - echo "$i " - ${JDK7}/jre/bin/java -client -d64 -graal -esa -ea -Xms32m -Xmx100m -Xbootclasspath/a:${SCIMARK} -G:+Time $@ jnt.scimark2.commandline -done +${JDK7}/jre/bin/java -client -d64 -graal -Xms256m -Xmx512m -Xbootclasspath/a:${SCIMARK}/scimark2lib.jar $@ jnt.scimark2.commandline