This document describes the Alto scheduler (schedule.c version 1.29)


The scheduler is invoked after the code has been layouted (positioned).
That means that at scheduling time all the basic blocks of the entire
program are accumulated in one function and the order of those
blocks inside the function represents the order in which
they should be inside of the executable.

Some block are marked to be aligned and the scheduler will insert
universal noops to force the alignment.

The scheduler is list based.

Instead of scheduling one basic block at a time the scheduler tries
to schedule a super block at a time.
A superblock is a sequence of basic blocks with the following constraints

o the blocks are  sequential in the layout 
o except for the first bbl they have exactly on incoming edge
o except for the last block their type is either BT_NORMAL (fall through)
  or BT_BRANCH (conditional branch)

The scheduler may move instruction into different basic blocks within
the super block. Moving instructions up (to a prior block) is very common,
moving instruction down is rare.

Now we are going to describe how the scheduling works and the data structures 
involved. For simplicity we assume that there is only block in the super block. 

Step 1:

    For all the instructions (AINS) in the block a create a corresponding
    schedulee object (SCHEDULEE). 

Step 2:

    The schedulees constitute the nodes of a dependency graph.
    In this step the constraint edges (CONSTRAINT) for this graph are created.
    An instruction can only be scheduled if all the instructions 
    it depends on have been scheduled.
     There are different kinds of constraint edges:
    o register
    o resource
    o control 
    o memory
    
    Edges carry additional information such as latencies.
    
    The memory constraits exploit aliasing information. 
    A trivial aliasing mechanism is also available as part
    of the resource constraints but currently disabled.

    After all the constraints have been created compute for each node the length of longest
    path to the sinks of the graph. (Latencies are interpreted as lengths.)

Step 3: 


    This step is encapsuled in ScheduleeCompute() and
    represents the core of the list scheduler. 

    while the set of schedulees is non empty
    
        o find the subset of instructions
          that can be scheduled now, for each of them a
          CANDIDATES object is created.
        o rank the candiadtes
        o schedule the one with the highest rank.
          (For each scheduled instruction a 
          SCHLOT object is created.)
          

Step 4:

    Remove the instructions from the block
    and put them back in according to the schedule
    which is manifest in the SCHLOT objects.