From: <jik...@li...> - 2014-05-23 14:32:38
|
details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/009af8a1cc71 changeset: 10752:009af8a1cc71 user: Erik Brangs <eri...@gm...> date: Fri May 23 15:27:00 2014 +0200 description: Correct Javadoc for markDirty in ScratchMap. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/acf2e8f7c2fb changeset: 10753:acf2e8f7c2fb user: Erik Brangs <eri...@gm...> date: Fri May 23 15:28:39 2014 +0200 description: RVM-1077 : Add a unit test for org.jikesrvm.compilers.opt.regalloc.ScratchMap. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/b095895ef5a7 changeset: 10754:b095895ef5a7 user: Erik Brangs <eri...@gm...> date: Fri May 23 15:52:13 2014 +0200 description: Fix a bug that prevented removal of SymbolInterval instances in endSymbolicInterval(). This bug was revealed by FindBugs. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/4874964faa69 changeset: 10755:4874964faa69 user: Erik Brangs <eri...@gm...> date: Fri May 23 15:56:36 2014 +0200 description: Change toString() in ScratchMap to use StringBuilder. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/60aacb09bcdf changeset: 10756:60aacb09bcdf user: Erik Brangs <eri...@gm...> date: Fri May 23 16:02:32 2014 +0200 description: Change visibility in the Interval classes in ScratchMap to reflect current use of the classes. diffstat: rvm/src/org/jikesrvm/compilers/opt/regalloc/ScratchMap.java | 33 +- rvm/test-src/org/jikesrvm/compilers/opt/regalloc/ScratchMapTest.java | 176 ++++++++++ 2 files changed, 195 insertions(+), 14 deletions(-) diffs (282 lines): diff --git a/rvm/src/org/jikesrvm/compilers/opt/regalloc/ScratchMap.java b/rvm/src/org/jikesrvm/compilers/opt/regalloc/ScratchMap.java --- a/rvm/src/org/jikesrvm/compilers/opt/regalloc/ScratchMap.java +++ b/rvm/src/org/jikesrvm/compilers/opt/regalloc/ScratchMap.java @@ -77,7 +77,7 @@ SymbolicInterval i = (SymbolicInterval) pending.get(r); i.end = end; - pending.remove(i); + pending.remove(r); } /** @@ -165,8 +165,12 @@ } /** - * Note that at GC point s, the real value of register symb is cached in - * a dirty scratch register. + * Records that the real value of a symbolic register is cached in + * a dirty scratch register at a given instruction that is a GC point. + * + * @param s an instruction that is a GC point. Note: it is the caller's + * responsibility to check this + * @param symb the symbolic register */ public void markDirty(Instruction s, Register symb) { HashSet<Register> set = dirtyMap.get(s); @@ -195,13 +199,14 @@ */ @Override public String toString() { - String result = ""; + StringBuilder result = new StringBuilder(); for (ArrayList<Interval> v : map.values()) { for (Interval i : v) { - result += i + "\n"; + result.append(i); + result.append("\n"); } } - return result; + return result.toString(); } /** @@ -211,27 +216,27 @@ /** * The instruction before which the scratch range begins. */ - Instruction begin; + protected Instruction begin; /** * The instruction before which the scratch range ends. */ - Instruction end; + protected Instruction end; /** * The physical scratch register or register evicted. */ - final Register scratch; + protected final Register scratch; /** * Initialize scratch register */ - Interval(Register scratch) { + protected Interval(Register scratch) { this.scratch = scratch; } /** * Does this interval contain the instruction numbered n? */ - final boolean contains(int n) { + protected final boolean contains(int n) { return (begin.scratch <= n && end.scratch > n); } } @@ -242,11 +247,11 @@ * * Note that this interval must not span a basic block. */ - static final class SymbolicInterval extends Interval { + private static final class SymbolicInterval extends Interval { /** * The symbolic register */ - final Register symbolic; + private final Register symbolic; SymbolicInterval(Register symbolic, Register scratch) { super(scratch); @@ -270,7 +275,7 @@ * * Note that this interval must not span a basic block. */ - static final class PhysicalInterval extends Interval { + private static final class PhysicalInterval extends Interval { PhysicalInterval(Register scratch) { super(scratch); } diff --git a/rvm/test-src/org/jikesrvm/compilers/opt/regalloc/ScratchMapTest.java b/rvm/test-src/org/jikesrvm/compilers/opt/regalloc/ScratchMapTest.java new file mode 100644 --- /dev/null +++ b/rvm/test-src/org/jikesrvm/compilers/opt/regalloc/ScratchMapTest.java @@ -0,0 +1,176 @@ +/* + * This file is part of the Jikes RVM project (http://jikesrvm.org). + * + * This file is licensed to You under the Eclipse Public License (EPL); + * You may not use this file except in compliance with the License. You + * may obtain a copy of the License at + * + * http://www.opensource.org/licenses/eclipse-1.0.php + * + * See the COPYRIGHT.txt file distributed with this work for information + * regarding copyright ownership. + */ +package org.jikesrvm.compilers.opt.regalloc; + +import static org.junit.Assert.*; +import static org.hamcrest.CoreMatchers.*; +import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD; +import static org.jikesrvm.compilers.opt.ir.Operators.FENCE; + +import org.jikesrvm.classloader.TypeReference; +import org.jikesrvm.compilers.opt.ir.Binary; +import org.jikesrvm.compilers.opt.ir.Empty; +import org.jikesrvm.compilers.opt.ir.Instruction; +import org.jikesrvm.compilers.opt.ir.Register; +import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand; +import org.jikesrvm.junit.runners.RequiresJikesRVM; +import org.jikesrvm.junit.runners.VMRequirements; +import org.junit.Before; +import org.junit.Test; +import org.junit.experimental.categories.Category; +import org.junit.runner.RunWith; + + +@RunWith(VMRequirements.class) +public class ScratchMapTest { + + private ScratchMap scratchMap; + + @Before + public void createNewScratchMap() { + scratchMap = new ScratchMap(); + } + + @Test + public void newMapIsEmpty() { + ScratchMap scratchMap = new ScratchMap(); + assertThat(scratchMap.isEmpty(), is(true)); + } + + @Category(RequiresJikesRVM.class) // because of TypeReference + @Test + public void markDirtyMarksRegistersAsDirty() { + Register resultReg = createRegister(0); + RegisterOperand result = new RegisterOperand(resultReg, TypeReference.Int); + Register op1Reg = new Register(1); + Register op2Reg = new Register(2); + RegisterOperand op1 = new RegisterOperand(op1Reg, TypeReference.Int); + RegisterOperand op2 = new RegisterOperand(op2Reg, TypeReference.Int); + Instruction add = Binary.create(INT_ADD, result, op1, op2); + + scratchMap.markDirty(add, op2Reg); + assertThat(scratchMap.isDirty(add, op2Reg), is(true)); + } + + @Category(RequiresJikesRVM.class) // because of TypeReference + @Test + public void markingRegistersAsDirtyMoreThanOnceIsHarmless() { + Register resultReg = createRegister(0); + RegisterOperand result = new RegisterOperand(resultReg, TypeReference.Int); + Register op1Reg = new Register(1); + Register op2Reg = new Register(2); + RegisterOperand op1 = new RegisterOperand(op1Reg, TypeReference.Int); + RegisterOperand op2 = new RegisterOperand(op2Reg, TypeReference.Int); + Instruction add = Binary.create(INT_ADD, result, op1, op2); + + scratchMap.markDirty(add, op2Reg); + scratchMap.markDirty(add, op2Reg); + assertThat(scratchMap.isDirty(add, op2Reg), is(true)); + } + + @Test + public void markDirtyDoesNotCheckThatRegisterIsUsedInInstruction() { + Register symb = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.markDirty(inst, symb); + assertThat(scratchMap.isDirty(inst, symb), is(true)); + } + + @Test + public void beginSymbolicIntervalCreatesANewInterval() { + Register symb = createRegister(0); + Register scratch = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.beginSymbolicInterval(symb, scratch, inst); + assertThat(scratchMap.isEmpty(), is(false)); + } + + @Test(expected = NullPointerException.class) + public void endSymbolicIntervalRemovesInformationAboutScratchRegisterFromPendingMap() { + Register symb = createRegister(0); + Register scratch = createRegister(1); + Instruction begin = createInstruction(); + scratchMap.beginSymbolicInterval(symb, scratch, begin); + Instruction end = createInstruction(); + scratchMap.endSymbolicInterval(symb, end); + + scratchMap.endSymbolicInterval(symb, end); + } + + private Register createRegister(int regNum) { + return new Register(regNum); + } + + @Test + public void beginSymbolicIntervalAllowsRegisterAndItsScratchRegisterToBeTheSame() { + Register symb = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.beginSymbolicInterval(symb, symb, inst); + } + + @Test(expected = NullPointerException.class) + public void endSymbolicIntervalForNotStartedIntervalCausesNPE() { + Register symb = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.endSymbolicInterval(symb, inst); + } + + private Instruction createInstruction() { + Instruction fence = Empty.create(FENCE); + return fence; + } + + @Test + public void beginScratchIntervalCreatesANewInterval() { + Register scratch = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.beginScratchInterval(scratch, inst); + assertThat(scratchMap.isEmpty(), is(false)); + } + + @Test + public void beginScratchIntervalSavesInformationAboutScratchRegister() { + Register scratch = createRegister(0); + Instruction begin = createInstruction(); + int instNumber = 2; + begin.scratch = instNumber; + scratchMap.beginScratchInterval(scratch, begin); + Instruction end = createInstruction(); + end.scratch = instNumber + 1; + scratchMap.endScratchInterval(scratch, end); + + Register scratchReg = scratchMap.getScratch(scratch, instNumber); + assertThat(scratchReg, is(scratch)); + assertThat(scratchMap.isScratch(scratchReg, instNumber), is(true)); + } + + @Test(expected = NullPointerException.class) + public void endScratchIntervalRemovesInformationAboutScratchRegisterFromPendingMap() { + Register scratch = createRegister(0); + Instruction begin = createInstruction(); + scratchMap.beginScratchInterval(scratch, begin); + Instruction end = createInstruction(); + scratchMap.endScratchInterval(scratch, end); + + scratchMap.endScratchInterval(scratch, end); + } + + @Test(expected = NullPointerException.class) + public void endScratchIntervalForNotStartedIntervalCausesNPE() { + Register scratch = createRegister(0); + Instruction inst = createInstruction(); + scratchMap.endScratchInterval(scratch, inst); + } + + +} |
From: <jik...@li...> - 2014-09-10 17:14:49
|
details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/950a5b3f9b24 changeset: 10900:950a5b3f9b24 user: Erik Brangs <eri...@gm...> date: Wed Sep 10 15:49:43 2014 +0200 description: Add equals() and hashCode() to ReorderingPhase.Edge to fix FindBugs warnings and ensure that (x.compareTo(y)==0) == (x.equals(y)). details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/befb820917d6 changeset: 10901:befb820917d6 user: Erik Brangs <eri...@gm...> date: Wed Sep 10 16:11:25 2014 +0200 description: Remove unnecessary calls to toString() from ReorderingPhase. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/c60863fb8921 changeset: 10902:c60863fb8921 user: Erik Brangs <eri...@gm...> date: Wed Sep 10 16:38:35 2014 +0200 description: Improve readability of chain handling in ReorderingPhase. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/b8d5d35ba702 changeset: 10903:b8d5d35ba702 user: Erik Brangs <eri...@gm...> date: Wed Sep 10 16:44:58 2014 +0200 description: RVM-1083 : Use a HashMap instead of scratch fields to keep track of chains in ReorderingPhase. details: http://hg.code.sourceforge.net/p/jikesrvm/code/rev/f4412dd19ed4 changeset: 10904:f4412dd19ed4 user: Erik Brangs <eri...@gm...> date: Wed Sep 10 16:47:44 2014 +0200 description: Improve typing of outWeights map in ReorderingPhase.ChainInfo. diffstat: rvm/src/org/jikesrvm/compilers/opt/controlflow/ReorderingPhase.java | 62 ++++++++- 1 files changed, 50 insertions(+), 12 deletions(-) diffs (133 lines): diff --git a/rvm/src/org/jikesrvm/compilers/opt/controlflow/ReorderingPhase.java b/rvm/src/org/jikesrvm/compilers/opt/controlflow/ReorderingPhase.java --- a/rvm/src/org/jikesrvm/compilers/opt/controlflow/ReorderingPhase.java +++ b/rvm/src/org/jikesrvm/compilers/opt/controlflow/ReorderingPhase.java @@ -181,13 +181,14 @@ int numBlocks = 0; TreeSet<Edge> edges = new TreeSet<Edge>(); LinkedHashSet<BasicBlock> chainHeads = new LinkedHashSet<BasicBlock>(); + HashMap<BasicBlock, BasicBlock> associatedChain = new HashMap<BasicBlock, BasicBlock>(); BasicBlock entry = ir.cfg.entry(); if (VM.VerifyAssertions) VM._assert(ir.cfg.entry() == ir.cfg.firstInCodeOrder()); for (BasicBlock bb = entry; bb != null; bb = bb.nextBasicBlockInCodeOrder()) { numBlocks++; chainHeads.add(bb); - bb.setScratchObject(bb); + associatedChain.put(bb, bb); BasicBlock ft = bb.getFallThroughBlock(); if (ft != null) { bb.appendInstruction(Goto.create(GOTO, ft.makeJumpTarget())); @@ -219,7 +220,9 @@ if (DEBUG) VM.sysWriteln("\tTarget is not at start of a chain"); continue; } - if (e.source.getScratchObject() == e.target.getScratchObject()) { + BasicBlock sourceChain = associatedChain.get(e.source); + BasicBlock targetChain = associatedChain.get(e.target); + if (sourceChain == targetChain) { if (DEBUG) VM.sysWriteln("\tSource and target are in same chain"); continue; } @@ -228,9 +231,9 @@ ir.cfg.linkInCodeOrder(e.source, e.target); // Yuck....we should really use near-linear time union find here // Doing this crappy thing makes us O(N^2) in the worst case. - BasicBlock newChain = (BasicBlock) e.source.getScratchObject(); + BasicBlock newChain = sourceChain; for (BasicBlock ptr = e.target; ptr != null; ptr = ptr.nextBasicBlockInCodeOrder()) { - ptr.setScratchObject(newChain); + associatedChain.put(ptr, newChain); } } @@ -243,16 +246,16 @@ // (3) Summarize inter-chain edges. for (Edge e : edges) { - if (e.source.getScratchObject() != e.target.getScratchObject()) { - Object sourceChain = e.source.getScratchObject(); - Object targetChain = e.target.getScratchObject(); + BasicBlock sourceChain = associatedChain.get(e.source); + BasicBlock targetChain = associatedChain.get(e.target); + if (sourceChain != targetChain) { ChainInfo sourceInfo = chainInfo.get(sourceChain); ChainInfo targetInfo = chainInfo.get(targetChain); if (DEBUG) VM.sysWriteln("Inter-chain edge " + sourceChain + "->" + targetChain + " (" + e.weight + ")"); - Object value = sourceInfo.outWeights.get(targetInfo); + Float value = sourceInfo.outWeights.get(targetInfo); float weight = e.weight; if (value != null) { - weight += (Float) value; + weight += value; } sourceInfo.outWeights.put(targetInfo, weight); targetInfo.inWeight += e.weight; @@ -287,7 +290,7 @@ if (chainInfo.isEmpty()) break; // no chains left to place. for (ChainInfo target : nextChoice.outWeights.keySet()) { if (DEBUG) VM.sysWrite("\toutedge " + target); - float weight = (Float) nextChoice.outWeights.get(target); + float weight = nextChoice.outWeights.get(target); if (DEBUG) VM.sysWriteln(" = " + weight); target.placedWeight += weight; target.inWeight -= weight; @@ -341,7 +344,7 @@ final BasicBlock head; float placedWeight; float inWeight; - final HashMap<ChainInfo, Object> outWeights = new HashMap<ChainInfo, Object>(); + final HashMap<ChainInfo, Float> outWeights = new HashMap<ChainInfo, Float>(); ChainInfo(BasicBlock h) { head = h; @@ -354,6 +357,7 @@ } private static final class Edge implements Comparable<Edge> { + final BasicBlock source; final BasicBlock target; final float weight; @@ -366,7 +370,41 @@ @Override public String toString() { - return weight + ": " + source.toString() + " -> " + target.toString(); + return weight + ": " + source + " -> " + target; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((source == null) ? 0 : source.hashCode()); + result = prime * result + ((target == null) ? 0 : target.hashCode()); + result = prime * result + Float.floatToIntBits(weight); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + Edge other = (Edge) obj; + if (source == null) { + if (other.source != null) + return false; + } else if (!source.equals(other.source)) + return false; + if (target == null) { + if (other.target != null) + return false; + } else if (!target.equals(other.target)) + return false; + if (Float.floatToIntBits(weight) != Float.floatToIntBits(other.weight)) + return false; + return true; } @Override |