How to Obtain MLRISC
Problem Statement
MLRISC Based Compiler
MLRISC Intermediate Representation
MLRisc Generation
Back End Optimizations
Register Allocation
Machine Description
Garbage Collection Safety
System Integration
Graphical Interface
Line Counts
Systems Using MLRISC
Future Work
Architecture of MLRISC
The MLTREE Language
MLTree Extensions
MLTree Utilities
Instruction Selection
Machine Code Emitters
Delay Slot Filling
Span Dependency Resolution
The Graph Library
The Graph Visualization Library
Basic Compiler Graphs
SSA Optimizations
ILP Optimizations
Optimizations for VLIW/EPIC Architectur...
Register Allocator
Back Ends
The Alpha Back End
The PA RISC Back End
The Sparc Back End
The Intel x86 Back End
The PowerPC Back End
The MIPS Back End
The TI C6x Back End
Basic Types
Client Defined Constants
Client Defined Pseudo Ops
Instruction Streams
Label Expressions

Span Dependency Resolution

Span Dependency Resolution
-The Interface
-The Modules
The span dependency resolution phase is used to resolve the values of client defined constants and labels in a program. An instruction whose immediate operand field contains a constant or label expression which is too large is rewritten into a sequence of instructions to compute the same result. Similarly, short branches referencing labels that are too far are rewritten into the long form. For architectures that require the filling of delay slots, this is performed at the same time as span depedency resolution, to ensure maximum benefit results.

The Interface

The signature SDI_JUMPS describes architectural information about span dependence resolution.

 signature SDI_JUMPS = sig
   structure I : INSTRUCTIONS
   structure C : CELLS
     sharing I.C = C
   val branchDelayedArch : bool
   val isSdi : I.instruction -> bool
   val minSize : I.instruction -> int
   val maxSize : I.instruction -> int
   val sdiSize : I.instruction * (C.cell -> C.cell)
                               * (Label.label -> int) * int -> int
   val expand : I.instruction * int * int -> I.instruction list
The components in this interface are:
A flag indicating whether the architecture contains delay slots. For example, this would be true on the MIPS, Sparc, PA RISC; but would be false on the x86 and on the Alpha.
This function returns true if the instruction is span dependent, i.e.~its size depends either on some unresolved constants, or on its position in the code stream.
This function takes a span dependent instruction, a regmap, a mapping from labels to code stream position, and its current code stream position and returns the size of its expansion in bytes.
This function takes a span dependent instruction, its size, and its location and return its expansion.

The signature BBSCHED is the signature of the phase that performs span depedennce resolution and code generation.

 signature BBSCHED = sig
   structure F : FLOWGRAPH
   val bbsched : F.cluster -> unit
   val finish : unit -> unit
   val cleanUp : unit -> unit

The Modules

Three different functors are present in the MLRISC system for performing span dependence resolution and code generator. Functor BBSched2 is the simplest one, which does not perform delay slot filling.
 functor BBSched2
   (structure Flowgraph : FLOWGRAPH
    structure Jumps : SDI_JUMPS
    structure Emitter : INSTRUCTION_EMITTER
      sharing Emitter.P = Flowgraph.P
      sharing Flowgraph.I = Jumps.I = Emitter.I
   ): BBSCHED 
Functor SpanDependencyResolution performs both span dependence resolution and delay slot filling at the same time.
 functor SpanDependencyResolution
   (structure Flowgraph : FLOWGRAPH
    structure Emitter : INSTRUCTION_EMITTER
    structure Jumps : SDI_JUMPS
    structure DelaySlot : DELAY_SLOT_PROPERTIES
    structure Props : INSN_PROPERTIES
      sharing Flowgraph.P = Emitter.P
      sharing Flowgraph.I = Jumps.I = DelaySlot.I = Props.I = Emitter.I
   ) : BBSCHED 
Finally, functor BackPatch is a span dependency resolution module specially written for the x86 architecture.
 functor BackPatch
   (structure CodeString : CODE_STRING
    structure Jumps: SDI_JUMPS
    structure Props : INSN_PROPERTIES
    structure Emitter : MC_EMIT
    structure Flowgraph : FLOWGRAPH
    structure Asm : INSTRUCTION_EMITTER
       sharing Emitter.I = Jumps.I = Flowgraph.I = Props.I = Asm.I) : BBSCHED 

Lal George
Allen Leung
SML/NJ Validate this page
Generated by mltex2html
Last modified: Thu Jan 9 19:38:15 EST 2003 by leunga@slinky