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

Delay Slot Filling

Delay Slot Filling
The Interface


Superscalar architectures such as the Sparc, MIPS, and PA-RISC contain delayed branch and/or load instructions. Delay slot filling is necessary task of the back end to keep the instruction pipelines busy. To accomodate the intricate semantics of branch delay slot in various architectures, MLRISC uses the following very general framework for dealing with delayed instructions.

Instruction representation
To make it easy to deal with instruction with delay slot, MLRISC allow the following extensions to instruction representations.
  • Instructions with delay slot may have a nop flag. When this flag is true the delay slot is assumed to be filled with a NOP instruction.
  • Instructions with delay slots that can be nullified may have a nullified flag. When this flag is true the branch delay slot is assumed to be nullified.
Nullification semantics
Unfortunately, nullification semantics in architectures vary. In general, MLRISC allows the following additional nullification characteristics to be specified.
  • Nullification can be specified as illegal; this is needed because some instructions can not be nullified
  • When nullification is enabled, the semantics of the delay slot instruction may depend on the direction of the branch, and whether a conditional test succeeds.
  • Certain class of instructions may be declared to be illegal to fit into certain class of delay slots.

For example, conditional branch instructions on the Sparc are defined as follows:

    Bicc of {b:branch, a:bool, label:Label.label, nop:bool}
      asm: ``b<b><a>\t<label><nop>''
      padding: nop = true
      nullified: a = true and (case b of I.BA => false | _ => true)
      delayslot candidate: false
where a is annul flag and nop is the nop flag (see the Sparc machine description). A constructor term
    Bicc{b=BE, a=true, label=label, nop=true}
denotes the instruction sequence
    be,a label
    Bicc{b=BE, a=false, label=label, nop=false}
    be label

The Interface

Architecture information about how delay slot filling is to be performed is described in the signature DELAY_SLOT_PROPERTIES.
    structure I : INSTRUCTIONS
    datatype delay_slot = 
      D_NONE   | D_ERROR   | D_ALWAYS  
    val delaySlotSize : int 
    val delaySlot : { instr : I.instruction, backward : bool } -> 
 		   { n    : bool,      
 		     nOn  : delay_slot,
 		     nOff : delay_slot,
 		     nop  : bool      
    val enableDelaySlot : 
 	 {instr : I.instruction, n:bool, nop:bool} -> I.instruction
    val conflict : 
          {regmap:int->int,src:I.instruction,dst:I.instruction} -> bool
    val delaySlotCandidate : 
          { jmp : I.instruction, delaySlot : I.instruction } -> bool
    val setTarget : I.instruction * Label.label -> I.instruction
The components of this signature are:
This datatype describes properties related to a delay slot.
This indicates that no delay slot is possible.
This indicates that it is an error
This indicates that the delay slot is always active
This indicates that the delay slot is only active when branch is taken
This indicates that the delay slot is only active when branch is not taken
This is size of delay slot in bytes.

This method takes an instruction instr and a flag indicating whether the branch is backward, and returns the delay slot properties of an instruction. The properties is described by four fields.
n : bool
This bit is if the nullified bit in the instruction is currently set.
nOn : delay_slot
This field indicates the delay slot type when the instruction is nullified.
nOff : delay_slot
This field indiciates the delay slot type when the instruction is not nullified.
nop : bool
This bit indicates whether there is an implicit padded nop.

This method set the nullification and nop flags of an instruction.

This method checks whether there are any conflicts between instruction src and dst.
This method checks whether instruction delaySlot is within the class of instructions that can fit within the delay slot of instruction jmp.

This method changes the branch target of an instruction.


For example,
     delaySlot{instr=instr, backward=true} =
     {n=true, nOn=D_ERROR, nOff=D_ALWAYS, nop=true}
means that the instruction nullification bit is on, the the nullification cannot be turned off, delay slot is always active (when not nullified), and there is currently an implicit padded nop.

    delaySlot{instr=instr, backward=false} =
   {n=false, nOn=D_NONE, nOff=D_TAKEN, nop=false}
means that the nullification bit is off, the delay slot is inactive when the nullification bit is off, the delay slot is only active when the (forward) branch is taken when instr is not-nullified, and there is no implicitly padded nop.

    delaySlot{instr=instr, backward=true} =
   {n=true, nOn=D_TAKEN, nOff=D_ALWAYS, nop=true}
means that the nullification bit is on, the delay slot is active on a taken (backward) branch when the nullification bit is off, the delay slot is always active when instr is not-nullified, and there is currently an implicitly padded nop.

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