MLRISC
MLRISC
Contributors
Requirements
How to Obtain MLRISC
Overview
Problem Statement
Contributions
MLRISC Based Compiler
MLRISC Intermediate Representation
MLRisc Generation
Back End Optimizations
Register Allocation
Machine Description
Garbage Collection Safety
System Integration
Optimizations
Graphical Interface
Line Counts
Systems Using MLRISC
Future Work
System
Architecture of MLRISC
The MLTREE Language
MLTree Extensions
MLTree Utilities
Instruction Selection
Assemblers
Machine Code Emitters
Delay Slot Filling
Span Dependency Resolution
The Graph Library
The Graph Visualization Library
Basic Compiler Graphs
The MLRISC IR
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
Annotations
Cells
Cluster
Client Defined Constants
Client Defined Pseudo Ops
Instructions
Instruction Streams
Label Expressions
Labels
Regions
Regmap

Delay Slot Filling


Delay Slot Filling
Overview
The Interface
-Examples

Overview

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
    nop
 
while
    Bicc{b=BE, a=false, label=label, nop=false}
 
denotes
    be label
 

The Interface

Architecture information about how delay slot filling is to be performed is described in the signature DELAY_SLOT_PROPERTIES.
 signature DELAY_SLOT_PROPERTIES =
 sig
    structure I : INSTRUCTIONS
 
    datatype delay_slot = 
      D_NONE   | D_ERROR   | D_ALWAYS  
    | D_TAKEN  | D_FALLTHRU 
 
    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
 end
 
The components of this signature are:
delay_slot
This datatype describes properties related to a delay slot.
D_NONE
This indicates that no delay slot is possible.
D_ERROR
This indicates that it is an error
D_ALWAYS
This indicates that the delay slot is always active
D_TAKEN
This indicates that the delay slot is only active when branch is taken
D_FALLTHRU
This indicates that the delay slot is only active when branch is not taken
delaySlotSize
This is size of delay slot in bytes.

delaySlot
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.

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

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

setTarget
This method changes the branch target of an instruction.

Examples

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