Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/README
ViewVC logotype

View of /sml/trunk/src/MLRISC/README

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (download) (annotate)
Thu Jun 1 18:34:03 2000 UTC (19 years ago) by monnier
File size: 12310 byte(s)
bring revisions from the vendor branch to the trunk
Changes in MLRISC++ 
-------------------
June 26, 1999
============
   Changed 

       BOOL of ty * ccexp 

   to the more general

       COND of ty * ccexp * rexp * rexp

   The semantics of COND(ty,cc,e1,e2) is

       if cc then e1 else e2

   except that the code generator has the freedom to eagerly evaluate both
   e1 and e2.

   For example,

       COND(ty,cc,LI 1,LI 0) means the same as BOOL(ty,cc)

       COND(ty,LT,x,y) computes the minimum of x and y
       COND(ty,GT,x,y) computes the maximum of x and y
    
       MV(ty,x,COND(ty,cc,y,REG(ty,x))) means the same as

           if cc then x <- y.
    
June 23, 1999
============

   Added

       BOOL of ty * ccexp

   to mltree.

   This operator converts a comparison into a zero/one boolean value.
   It should be useful for C.

June 21, 1999
============
   Added a new points-to analysis module.

June 20, 1999
============
   Added BLOCK_ANNOTATION of annotation to MLTREE.  This changes the
stream interface.

June 14, 1999
============
   Fixed up the ppc instruction set a bit.  Still not finished.

June 12, 1999
============
   Added the group mechanism for all instruction set.
   Extended INSN_PROPERTIES to include

   datatype instrKind = ...
       IK_GROUP | IK_PHI | IK_SOURCE | IK_SINK
   

June 9, 1999
============
   Renamed MOD? -> REM? in MLTREE
   Added rounding mode to CVTF2F

June 8, 1999
============

   Removed LOADCC/STORECC from MLTREE.
   Renamed ROUND and TRUNC to CVTF2I 

   Improved the delay slot filling module (spanDep.sml) so that it works
   with the HPPA instruction set.  Added delay slot filling to HPPA.

June 3, 1999
============

   Fixed up the x86 stuff so that it'll bootstrap on the new MLTREE stuff.
   
   In Cells, created a new regmap now adds the default bindings for 
   physical registers.  The x86 seems to depend on this to work properly.

May 24, 1999
============

   I've added the functions 

    val getCell : cellkind -> cellset -> register list
    val updateCell : cellkind -> cellset * register list -> cellset

   into the cellset interface.   This way, the cellset can now be
   manipulated as an abstract datatype. 
   

May 20, 1999
============

   Converted the PPC instruction selection module to use the new MLTREE.

   Added V9 support for Sparc


May 19, 1999
============
   Replaced 
   
     LIinf of IntInf.int

   by
 
     LI64 of Word64.word

   Make Alpha recognize the RET instruction.
   Fixed a few assembly bugs on the Alpha.

May 18, 1999
============
   Added the interface FREQUENCY_PROPERTIES for extracting frequency 
information, like branch probability, from the instruction sets.
 
May 16, 1999
============
   Added numerous improvements to the modular RA.

   Added IK_CALL to insnProps

Apr 29, 1999
============
   The new hppa backend now works great.  Please see README.hppa for details.

Apr 27, 1999
============
   Fixed up the hppa backend in a major way.  I'm hoping it'll now bootstrap.

Apr 24, 1999
============
   Added frequency information to cluster.  
   The weight type in CFG and the freq cluster in cluster are now
   the same type.

Apr 20, 1999
============

   Added more MLTREE and annotations stuff.  We can now annotate
mltree.  What to do with this?

   Added Regions to the x86 instruction set.
   Displacement and indexing effect addresses and the CALL instruction
   carries around a Region.
  
   Fixed up the x86 instruction selection to use the new interface 
     (not entirely satisfactory)

   Migrating the SSA to use MLTREE as semantics description (LOTS of WORK!)

Apr 19, 1999
============

   The directory x86 contains x86 sources from version 110.16.

Apr 13, 1999
============

Instruction sets
----------------

   I've added annotations to all the instruction sets.  Each instruction
set now contains a constructor:

    ANNOTATION of {i:instruction, a:Annotations.annotation}

which allows the client to attach arbitrary information to an instruction.

Alpha and Hppa
--------------
   Fixed up the instruction selection modules somewhat.

RA
--
   There is now a new RA using a more modular implementation.
See ra/ra-iteratedCoalescing.sml for details.  
There is also an improvement to the function isDedicated, 
which may improve the performance of RA a little bit.

Instruction Properties
----------------------

   Added the functions immedRange and loadImmed.  This used to be
in SSA_PROPERTIES.

   Also added the functions

      hashOpn : operand -> word
      eqOpn   : operand * operand -> word

   These are useful for building hash tables on operands.

Apr 8, 1999
============


    I've renamed MLRISC to MLRISC++ temporarily since there are lots and
    lots of changes.  

Library
-------

    Added and changed a few interfaces.  Added a merge sort using the algorithm
seen in the last NJPLS.

CELLS
-----

    The cells interface has been changed as follows:

  1. Type cellclass is renamed cellkind.  

  2. All physical registers must now have unique ids.  For example,
     on the Alpha integer registers are numbered as 0 .. 31, and floating
     point registers are numbered as 32 .. 63.   This affects all clients
     that uses these functions.
   
  3. The Cells functors are now generated from the new MDGen tool.

Instruction Stream
------------------

   There is now an ``instruction stream'' concept, with the following
signature:

signature INSTRUCTION_STREAM =
sig

   structure P : PSEUDO_OPS
   structure B : BLOCK_NAMES

   datatype ('a,'b,'c) stream =
      STREAM of
         { init        : int -> unit,
           finish      : 'c -> unit,
           emit        : (int -> int) -> 'a -> unit,
           pseudoOp    : P.pseudo_op -> unit,
           defineLabel : Label.label -> unit, 
           entryLabel  : Label.label -> unit, 
           comment     : string -> unit,
           blockName   : B.name -> unit,
           exitBlock   : 'b -> unit
         }
end

   An instruction stream accepts a sequence of instructions and does stuff 
with it.  Various modules are now expressed as transformations that
operate on instruction streams. 

INSN_PROPERTIES
---------------

   I've added the instr_kind IK_COPY.
   I've removed various functions that dealt with parallel copies.  These
were either not used or inadequate given the new changes.

Regions
-------

   I'm moving towards a new Regions interface as per discussion with Fermin.
This is needed for the new SSA stuff.

MC and Asm
----------

  These modules now uses the instruction stream interface.   These modules
implement the function:

   val makeStream : unit -> (instruction,unit,unit) stream

The state of the stream is hidden within the function.  Each call of
makeStream() creates a new stream instance; you can have multiple streams
active at the same time.   MC and Asm modules are now generated by
the MDGen tool.

MLTREE
------
 
   The mltree signature has been expanded to deal with different
floating point and integer types.  Plus some SSA support has been put
in but these are not currently fully functional.  Some of the MLTREE
stuff have been factored out so that they can be used for the semantics
description language (MLExp) used in SSA.  

   I expect eventually the two will be merged somehow.  This allows us to do 
wonderful things like this: the backend can build up a big MLExp (MLTREE) 
expression by composing the semantics of a sequence of instructions,
and apply simplification on it.  It then creates a new instruction selection 
module (see below) and asks it to give back a new (simplified) 
sequence of instruction that has the same semantics as before.  For this
to work nicely MLExp and MLTREE should be combined.

MLTREECOMP (Instruction Selection Modules)
------------------------------------------

   This interface has been changed as follows:

   signature MLTREECOMP = sig
      structure T : MLTREE
      structure I : INSTRUCTIONS
      structure S : INSTRUCTION_STREAM
        sharing S.B = T.BNames
        sharing S.P = T.PseudoOp

      val selectInstructions : 
        (I.instruction,T.mlrisc list,I.C.regmap) S.stream ->
        {  mltreeComp : T.mltree -> unit,
           mlriscComp : T.stm -> unit,
           emitInstr  : I.instruction -> unit
        }
   end

   Conceptually, an instruction selection module takes a stream
   of mltree ``instructions'' (i.e. stm) and transform it into a stream of 
   actual instructions.  I've rewritten them so that multiple instances 
   of these modules can now be active at the same time.  

   They are also properly detached from the flowgen modules so that 
   they can be more flexibily reused in some other places.    For example,
   the backend can create mltree stms on the fly, pass them to a instruction
   selection module, and get back a stream of instructions.  In the old
   MLRISC this is not possible.

   Also, if we don't care about register allocation, we can be tie
   an instruction selection module directly to an assembly emitter stream. 

   Ideally, selectionInstructions should have signature 

      val selectInstructions : 
        (I.instruction,T.mlrisc list,I.C.regmap) S.stream ->
        (T.stm,T.mlrisc list,I.C.regmap) S.stream

   but for various reasons I'll stick with something closer to the old
   signature for now.

   I've rewritten the ones for Sparc, Hppa and Alpha to take advantage
   of the new MLTREEE.  Only the one on the sparc has been tested.

Alpha
-----

   The alpha instruction set has been drastically expanded to handle 64 bit
quantities.  Lots of floating point ops are still missing though.  They
deal with different types of rounding and trapping modes.  I don't know
how they fit into the picture yet.  Conditional Moves are also added; these
are not used yet.   I have renamed Alpha32 to Alpha.

Hppa and Sparc
--------------

   Some additions to deal with single precision floating points.
I think these are 64 bit processors but I don't have up-to-date manuals.

Flowgen
-------

  The flowgen module is used to build a flowgraph from a stream of 
instructions.  The flowgen interface now makes no mention of flowgraph
representation.  This allows us to use other representations than FLOWGRAPH.
Flowgen has the following interface:

   signature FLOWGRAPH_GEN = 
   sig
  
      structure C : CELLS
      structure I : INSTRUCTIONS
      structure T : MLTREE
      structure B : BLOCK_NAMES
      structure S : INSTRUCTION_STREAM

      sharing I.C = C 
      sharing T.Constant = I.Constant
      sharing T.PseudoOp = S.P
      sharing T.BNames   = B = S.B

      val newStream : unit -> (I.instruction,T.mlrisc list,C.regmap) S.stream
   end

   flowgen.sml has been renamed to clustergen.sml.  The module ClusterGen
serves the same function as FlowgraphGen before: it takes a stream
of instructions, build a cluster, then pass it onto the next phase.

   An alternative module, CFGGen, also exists.  This module builds a CFG
instead.  Eventually, we should have modules that can directly build
an SSA.


SSA, IR, ir
-----------
   Too many changes to list here.  

   The new ssa datatype will have a distinct representation than instructions.
Merging them turned out to be easy on paper but hard in practice.

   However, there is a new way to make ssa_ops behave just like instructions.
See the signature ssa-instructions.sig for details.  So all the machinary 
developed on top of instructions can be reused.

MD++
----

   This directory contains the MDGen tool.  The machine description
files have suffixes md.   To run the MDGen tool, go into SML in directory
MLRISC++.  Type ``use "make.sml"''  This automatically regenerates all
files dependent on the machine description files.

   Currently, only *Cells.sml, *Instr.sml, *MC.sml, *Asm.sml files are
generated from *.md.  Eventually, more things will be automated.

RA
--

   I'm in the process of splitting the RA into more manageable pieces.
See ra/ra-graph.s* ra/ra-core.s* etc.

The idea is that the build/rebuild and spill phases should be split from
the core of the register allocator, so that we can customize them by 
incorporating different heuristics.  This is needed for the coming SSA work.
The core of the register allocator will not reference any flowgraph 
data structures since those can change.

   How about register-pair allocation?

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0