spiglet.translate.graph
Class LinearScanAlloc<T,R>

java.lang.Object
  spiglet.translate.graph.RegisterAlloc<T,R>
      spiglet.translate.graph.LinearScanAlloc<T,R>

Type Parameters:

T - the type of the variable in an interference graph

R - the type of the register that variables are allocated to

public final class LinearScanAlloc<T,R>
extends RegisterAlloc<T,R>

This class uses the information gathered in a liveness analysis of a control flow graph to allocate variables to registers. The algorithm employed is linear scan (Poletto and Sarkar, MIT, Linear Scan Register Allocation, p 899).

Author:

Santoso Wijaya

See Also:

Liveness

Field Summary

Fields inherited from class spiglet.translate.graph.RegisterAlloc

registers

Constructor Summary

LinearScanAlloc(java.util.Set<R> pool)
Construct a register allocator given the set of general registers, using liveness analysis and linear scan algorithm.

Method Summary

java.util.Map<T,R>	getAllocation(FlowGraph<T> graph, java.util.Map<T,R> preAlloc) Returns the mapping of all variables to their allocated registers, given a control flow graph from which to infer.
java.util.Map<T,R>	getRegAllocation(FlowGraph<T> graph, java.util.Map<T,R> preAlloc) Returns the mapping of only those variables that are mapped to registers, given a control flow graph from which to infer.
java.lang.String	toString()

Methods inherited from class spiglet.translate.graph.RegisterAlloc

getAllocation, getRegAllocation

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinearScanAlloc

public LinearScanAlloc(java.util.Set<R> pool)

Construct a register allocator given the set of general registers, using liveness analysis and linear scan algorithm. The returned object can be queried to return a mapping of variables to registers.

Parameters:

pool - the set of registers to allocate

Method Detail

getAllocation

public java.util.Map<T,R> getAllocation(FlowGraph<T> graph,
                                        java.util.Map<T,R> preAlloc)

Description copied from class: RegisterAlloc

Returns the mapping of all variables to their allocated registers, given a control flow graph from which to infer. If a variable is mapped to null, that means the variable is spilled. A pre-allocation of variables to registers is also given, to indicate to the allocator that such a mapping must remain in the final allocation result. The returned allocation mapping also includes the mapping in preAlloc.

Specified by:

getAllocation in class RegisterAlloc<T,R>

Parameters:

graph - the control flow graph

preAlloc - the pre-allocation mapping

Returns:

the mapping of variables to their allocated registers (null if spilled)

getRegAllocation

public java.util.Map<T,R> getRegAllocation(FlowGraph<T> graph,
                                           java.util.Map<T,R> preAlloc)

Description copied from class: RegisterAlloc

Returns the mapping of only those variables that are mapped to registers, given a control flow graph from which to infer. Spilled variables do not appear in the key set of the returned map. A pre-allocation of variables to registers is also given, to indicate to the allocator that such a mapping must remain in the final allocation result. The returned allocation mapping also includes the mapping in preAlloc.

Specified by:

getRegAllocation in class RegisterAlloc<T,R>

Parameters:

graph - the control flow graph

preAlloc - the pre-allocation mapping

Returns:

the mapping of variables to their allocated registers; no variable is mapped to null

toString

public java.lang.String toString()

Specified by:

toString in class RegisterAlloc<T,R>