Mercurial > hg > truffle
changeset 21732:bc2ec35a7189
Use dense index when possible for location marker
| author | Tom Rodriguez <tom.rodriguez@oracle.com> |
|---|---|
| date | Thu, 04 Jun 2015 10:46:23 -0700 |
| parents | df9d2375512a |
| children | 27943aac2e3c |
| files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java |
| diffstat | 1 files changed, 237 insertions(+), 95 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java Wed Jun 03 20:24:05 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java Thu Jun 04 10:46:23 2015 -0700 @@ -25,6 +25,7 @@ import static com.oracle.jvmci.code.ValueUtil.*; import java.util.*; +import java.util.function.*; import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.cfg.*; @@ -104,51 +105,203 @@ } } - private static final class LiveValueSet implements Iterable<Value> { - private static final Object MARKER = new Object(); + private static final class ValueSet { + private Value[] values; - private final HashMap<Value, Object> map; - - public LiveValueSet() { - map = new HashMap<>(); + ValueSet() { + values = Value.NO_VALUES; } - public LiveValueSet(LiveValueSet s) { - map = new HashMap<>(s.map); + ValueSet(ValueSet other) { + int limit = other.values.length; + while (limit > 0) { + if (other.values[limit - 1] == null) { + limit--; + continue; + } + break; + } + values = new Value[limit]; + System.arraycopy(other.values, 0, values, 0, values.length); } - public void put(Value v) { - map.put(v, MARKER); + void put(int index, Value value) { + if (value != null && value.getLIRKind().isValue()) { + return; + } + if (values.length <= index) { + if (value == null) { + return; + } + Value[] newValues = new Value[index + 1]; + System.arraycopy(values, 0, newValues, 0, values.length); + values = newValues; + values[index] = value; + } else { + values[index] = value; + } } - public void putAll(LiveValueSet v) { - map.putAll(v.map); - } - - public void remove(Value v) { - map.remove(v); - } - - public Iterator<Value> iterator() { - return map.keySet().iterator(); + public void putAll(ValueSet stack) { + Value[] otherValues = stack.values; + int limit = otherValues.length; + if (limit > values.length) { + while (limit > 0) { + if (otherValues[limit - 1] == null) { + limit--; + continue; + } + break; + } + if (limit > values.length) { + Value[] newValues = new Value[limit]; + System.arraycopy(values, 0, newValues, 0, values.length); + values = newValues; + } + } + for (int i = 0; i < limit; i++) { + Value value = otherValues[i]; + if (value != null) { + values[i] = value; + } + } } @Override - public boolean equals(Object obj) { - if (obj instanceof LiveValueSet) { - return map.equals(((LiveValueSet) obj).map); - } else { - return false; + public boolean equals(Object other) { + if (other instanceof ValueSet) { + ValueSet that = (ValueSet) other; + int limit = Math.min(values.length, that.values.length); + for (int i = 0; i < limit; i++) { + if (!Objects.equals(values[i], that.values[i])) { + return false; + } + } + for (int i = limit; i < values.length; i++) { + if (values[i] != null) { + return false; + } + } + for (int i = limit; i < that.values.length; i++) { + if (that.values[i] != null) { + return false; + } + } + return true; + } + return false; + } + + public void addLiveValues(ReferenceMap refMap) { + for (Value v : values) { + if (v != null) { + refMap.addLiveValue(v); + } } } @Override public int hashCode() { - return map.hashCode(); + throw new UnsupportedOperationException(); } } private static final class Marker<T extends AbstractBlockBase<T>> { + + private final class LiveValueSet implements Consumer<AbstractBlockBase<T>> { + + public void accept(AbstractBlockBase<T> succ) { + putAll(liveInMap.get(succ)); + } + + private final ValueSet registers; + private final ValueSet stack; + private Set<Value> extraStack; + + public LiveValueSet() { + registers = new ValueSet(); + stack = new ValueSet(); + } + + public LiveValueSet(LiveValueSet s) { + registers = new ValueSet(s.registers); + stack = new ValueSet(s.stack); + if (s.extraStack != null) { + extraStack = new HashSet<>(s.extraStack); + } + } + + public void put(Value v) { + if (isRegister(v)) { + int index = asRegister(v).getReferenceMapIndex(); + registers.put(index, v); + } else if (isStackSlot(v)) { + int index = frameMap.offsetForStackSlot(asStackSlot(v)); + assert index >= 0; + if (index % 4 == 0) { + stack.put(index / 4, v); + } else { + if (extraStack == null) { + extraStack = new HashSet<>(); + } + extraStack.add(v); + } + } + } + + public void putAll(LiveValueSet v) { + registers.putAll(v.registers); + stack.putAll(v.stack); + if (v.extraStack != null) { + if (extraStack == null) { + extraStack = new HashSet<>(); + } + extraStack.addAll(v.extraStack); + } + } + + public void remove(Value v) { + if (isRegister(v)) { + int index = asRegister(v).getReferenceMapIndex(); + registers.put(index, null); + } else if (isStackSlot(v)) { + int index = frameMap.offsetForStackSlot(asStackSlot(v)); + assert index >= 0; + if (index % 4 == 0) { + stack.put(index / 4, null); + } else { + extraStack.remove(v); + } + } + } + + @SuppressWarnings("unchecked") + @Override + public boolean equals(Object obj) { + if (obj instanceof Marker.LiveValueSet) { + LiveValueSet other = (LiveValueSet) obj; + return registers.equals(other.registers) && stack.equals(other.stack) && Objects.equals(extraStack, other.extraStack); + } else { + return false; + } + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException(); + } + + public void addLiveValues(ReferenceMap refMap) { + registers.addLiveValues(refMap); + stack.addLiveValues(refMap); + if (extraStack != null) { + for (Value v : extraStack) { + refMap.addLiveValue(v); + } + } + } + } + private final LIR lir; private final FrameMap frameMap; private final RegisterAttributes[] registerAttributes; @@ -181,9 +334,9 @@ /** * Merge outSet with in-set of successors. */ - private boolean updateOutBlock(AbstractBlockBase<?> block) { + private boolean updateOutBlock(AbstractBlockBase<T> block) { LiveValueSet union = new LiveValueSet(); - block.getSuccessors().forEach(succ -> union.putAll(liveInMap.get(succ))); + block.getSuccessors().forEach(union); LiveValueSet outSet = liveOutMap.get(block); // check if changed if (outSet == null || !union.equals(outSet)) { @@ -196,13 +349,14 @@ private void processBlock(AbstractBlockBase<T> block, UniqueWorkList<T> worklist) { if (updateOutBlock(block)) { try (Indent indent = Debug.logAndIndent("handle block %s", block)) { - BlockClosure closure = new BlockClosure(new LiveValueSet(liveOutMap.get(block))); + currentSet = new LiveValueSet(liveOutMap.get(block)); List<LIRInstruction> instructions = lir.getLIRforBlock(block); for (int i = instructions.size() - 1; i >= 0; i--) { LIRInstruction inst = instructions.get(i); - closure.processInstructionBottomUp(inst); + processInstructionBottomUp(inst); } - liveInMap.put(block, closure.getCurrentSet()); + liveInMap.put(block, currentSet); + currentSet = null; worklist.addAll(block.getPredecessors()); } } @@ -211,78 +365,68 @@ private static final EnumSet<OperandFlag> REGISTER_FLAG_SET = EnumSet.of(OperandFlag.REG); private static final LIRKind REFERENCE_KIND = LIRKind.reference(Kind.Object); - private final class BlockClosure { - private final LiveValueSet currentSet; + private LiveValueSet currentSet; - private BlockClosure(LiveValueSet set) { - currentSet = set; - } + /** + * Process all values of an instruction bottom-up, i.e. definitions before usages. Values + * that start or end at the current operation are not included. + */ + private void processInstructionBottomUp(LIRInstruction op) { + try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) { + // kills - private LiveValueSet getCurrentSet() { - return currentSet; - } + op.visitEachTemp(defConsumer); + op.visitEachOutput(defConsumer); + if (op.destroysCallerSavedRegisters()) { + for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) { + defConsumer.visitValue(reg.asValue(REFERENCE_KIND), OperandMode.TEMP, REGISTER_FLAG_SET); + } + } - /** - * Process all values of an instruction bottom-up, i.e. definitions before usages. - * Values that start or end at the current operation are not included. - */ - private void processInstructionBottomUp(LIRInstruction op) { - try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) { - // kills + // gen - values that are considered alive for this state + op.visitEachAlive(useConsumer); + op.visitEachState(useConsumer); + // mark locations + op.forEachState(stateConsumer); + // gen + op.visitEachInput(useConsumer); + } + } - op.visitEachTemp(defConsumer); - op.visitEachOutput(defConsumer); - if (op.destroysCallerSavedRegisters()) { - for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) { - defConsumer.visitValue(reg.asValue(REFERENCE_KIND), OperandMode.TEMP, REGISTER_FLAG_SET); - } - } + InstructionStateProcedure stateConsumer = new InstructionStateProcedure() { + public void doState(LIRInstruction inst, LIRFrameState info) { + markLocation(inst, info, currentSet); + } + }; - // gen - values that are considered alive for this state - op.visitEachAlive(useConsumer); - op.visitEachState(useConsumer); - // mark locations - op.forEachState(stateConsumer); - // gen - op.visitEachInput(useConsumer); + ValueConsumer useConsumer = new ValueConsumer() { + public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { + if (shouldProcessValue(operand)) { + // no need to insert values and derived reference + if (Debug.isLogEnabled()) { + Debug.log("set operand: %s", operand); + } + currentSet.put(operand); } } - - InstructionStateProcedure stateConsumer = new InstructionStateProcedure() { - public void doState(LIRInstruction inst, LIRFrameState info) { - markLocation(inst, info, getCurrentSet()); - } - }; + }; - ValueConsumer useConsumer = new ValueConsumer() { - public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { - if (shouldProcessValue(operand)) { - // no need to insert values and derived reference - if (Debug.isLogEnabled()) { - Debug.log("set operand: %s", operand); - } - currentSet.put(operand); + ValueConsumer defConsumer = new ValueConsumer() { + public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { + if (shouldProcessValue(operand)) { + if (Debug.isLogEnabled()) { + Debug.log("clear operand: %s", operand); } + currentSet.remove(operand); + } else { + assert isIllegal(operand) || operand.getPlatformKind() != Kind.Illegal || mode == OperandMode.TEMP : String.format("Illegal PlatformKind is only allowed for TEMP mode: %s, %s", + operand, mode); } - }; + } + }; - ValueConsumer defConsumer = new ValueConsumer() { - public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { - if (shouldProcessValue(operand)) { - if (Debug.isLogEnabled()) { - Debug.log("clear operand: %s", operand); - } - currentSet.remove(operand); - } else { - assert isIllegal(operand) || operand.getPlatformKind() != Kind.Illegal || mode == OperandMode.TEMP : String.format( - "Illegal PlatformKind is only allowed for TEMP mode: %s, %s", operand, mode); - } - } - }; - - protected boolean shouldProcessValue(Value operand) { - return (isRegister(operand) && attributes(asRegister(operand)).isAllocatable() || isStackSlot(operand)) && operand.getPlatformKind() != Kind.Illegal; - } + protected boolean shouldProcessValue(Value operand) { + return (isRegister(operand) && attributes(asRegister(operand)).isAllocatable() || isStackSlot(operand)) && operand.getPlatformKind() != Kind.Illegal; } /** @@ -296,9 +440,7 @@ ReferenceMap refMap = info.debugInfo().getReferenceMap(); refMap.reset(); frameMap.addLiveValues(refMap); - for (Value v : values) { - refMap.addLiveValue(v); - } + values.addLiveValues(refMap); refMap.finish(); }