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

Generated by mltex2html
Last modified: Fri Oct 11 18:19:52 UTC 2019 by buildd@x86-grnet-02