Coconut Road Map

Make a better Adapter interface

Remove Output dependency in Adapter

Add CGOutput to reduce Adapter instances

Why was this necessary? Say i try and create adapter instances

instance (Unwrappable h a,Unwrappable h b) => Adapter h a b where
  type AdaptedIn h a b = a
  type AdaptedOut h a b = b

  adapt = id

instance (Unwrappable h a,Unwrappable h b,Unwrappable h c)
         => Adapter h a (b -> c) where
  type AdaptedIn h a (b -> c) = (a,b)
  type AdaptedOut h a (b -> c) = c

  adapt f (x,y) = f x y

 ...

This doesn’t work because the first instance has overlapping type families with the second (ok with type classes, big no-no for open type families).

Remember function application associates to the right. So it does work if we make the last operand a concrete type like

instance (Unwrappable h a) => Adapter h a (Graph h n0) where
  type AdaptedIn h a (Graph h n0) = a
  type AdaptedOut h a (Graph h n0) = (Graph h n0)

  adapt = id

instance (Unwrappable h a,Unwrappable h b)
         => Adapter h a (b -> (Graph h n0)) where
  type AdaptedIn h a (b -> (Graph h n0)) = (a,b)
  type AdaptedOut h a (b -> (Graph h n0)) = (Graph h n0)

  adapt f (x,y) = f x y

 ...

But now I’m stuck enumerating all the different tuple outputs for Graph and Interp!

Remove type parameter h from Adapter

This might an unfortunate necessity

Add all appropriate Adapter instances

Implement Conditional Register Instructions

Add cmpGPR and cmpVR to CoreISA

Add Interp instance for cmpGPR and cmpVR

Implement Graph instance for cmpGPR and cmpVR

Implement real compare instructions for Z

Implement Control Flow Interface

Implement doWhileCFA

Implement ifCFA

Replace underlying Hypergraph (with tree or fgl?)

Possibly use Control-Flow Graph based on Huet’s Zipper?

where to insert jump instructions? they have no input/output don’t belong in data flow graph?

add modulo scheduling control flow

Implement Code Generation (i.e. Printer)

ask Robert about using alignment hint?

Implement Register Allocator

add global chiatin-briggs allocation

add support for loops in ScheduledGraph generation

add extra coalesce pass

add real briggs heuristic to avoid spilling

add support for verims

add spilling

add the correct amount of registers in regColors

MR’s need to be mapped to GPR’s (and map inputs/outputs like verims)

collect constants (undwrds) to put in .data section

we can use one pointer for constant region, including displacement in table
we can interleave tables (our offset vector will multiply by two for two tables, then shift by a displacement to control which table we access)

Port Scheduler to use ControlFlow

Port old MASS functions

implement modulo scheduling

map incMR to proper instruction

Implement the rest of Core MetaData

Implement CodeGraph Interp

Adjust assembly header for modulo code

replace llgf with llgfr?

vlbb allows use to load data without adjusting for size

Better debugging

add strings to inputs/outputs dataflow graph

add tag function

add new vector load instruction?

handle MR in register allocator

generate tables for initMR

assign initMR to larl in codegen (need to add to CoreMetaData?)

add agfi (sgfi exist?)

need to handle register overwriting

change modulo block counter to decrement?

fix input/output registers in register allocation?

Tune HashedSchedule for Register Allocation

when re materializing, reconstruct overwrites list

are constant loads and verims getting the same dispatch times?

Maybe write constraint to push instructions the are consumed by an instruction that also consumes a constant load away from that constant load

Add Multiple Stages

Unstaged 2

for i in range(0,n):
    S0[i]
    S1[i]
    S2[i]

2 Stages

-- Prologue
S0[0]

for i in range(0,n-1):
-- Kernel
    S0[i+1] ; S1[i]

-- Epilogue
S1[n]

Unstaged 3

for i in range(0,n):
    S0[i]
    S1[i]
    S2[i]

3 Stages

-- Prologue
S0[0]
S1[0]
if n <= 1
  goto epilogue(n)
S0[1]
if n <= 2
  goto epilogue(n-1)
for i in range(0,n-2):
-- Kernel
    S0[i+2] ; S1[i+1] ; S2[i]
-- epilogue(n-1)
S2[n-1]
-- epilogue (n)
S1[n]
S2[n]

Need to label inputs/outputs by stage?

Prologue -> Kernel Ties S1[0] -> S2[i] S0[1] -> S1[i+1]

Kernel -> Kernel Ties S0[i+2] -> S1[i+1] S1[i+1] -> S2[i]

Kernel -> Epilogue Ties S0[i+2] -> S1[n] S1[i+1] -> S2[n-1]

Notes

Trouble getting a unified DataFlow and ControlFlow interface

Old data flow interface

used to have to separate builders, CGMState (to build data flow graph) and CGFState (to build control flow graph)

The old type

data Graph h a = Graph { genGraph :: CGMState (ResType h) (EL h) UniqueNodeIndex }

was used to build a composable data flow DSL (NOTE CGMState returns a single UniqueNodeIndex corresponding to the most recently created output node in the data flow graph)

class CoreISA repr where
  vs :: repr VR -> repr VR -> repr VR
  incMR :: repr MR -> repr GPR -> (repr GPR,repr MR)


instance CoreISA (Graph h) where
  vs :: Graph h VR -> Graph h VR -> Graph h VR
  ...
  incMR :: Graph h MR -> Graph h GPR -> (Graph h GPR,Graph h MR)
  ...

NOTE that multiple outputs are given as tuples with Graph inside the tuple

What we want out of a control flow interface

CGFState would need to build a data flow graph (previously just called CodeGraph) by running cgFrom which would return a CodeGraph
We want a type safe ControlFlow interface, this would mean we want types like
```
class ControlISA repr where
  compose :: repr (a,b) -> repr (b,c) -> repr (a,c)
  branch :: repr (a,CR) -> repr (a,c) -> repr (a,c)
  ...
    
```
NOTE the type variables a,b,c should represent a pair of (input,output) types of a data flow graph. These types should be something like (GPR,MR) NOT (Graph h GPR,Graph h MR)

And ideally the type parameter repr should be the same as the instance for CoreISA

Problem with combining ControlFlow and DataFlow Interface

We create a single State monad for building both data flow and control flow graphs, and reassign Graph to

newtype Graph h a = Graph { genGraph :: CGBState h Node }

CGBState here has all the data required for building both data and control flow
In order to have a unified interface, we need some way to take functions of types

dataFlow :: Graph h VR -> Graph h MR -> (Graph h GPR,Graph h MR)
...

and convert them to

basicBlock :: Graph h ((VR,MR),(GPR,MR))
basicBlock  = toBasicBlock dataFlow

OR we supply the inputs for the graph, in which case we only need to have a function that takes tuples, i.e.

dataFlow :: Graph h VR -> Graph h MR -> (Graph h GPR,Graph h MR)
...

basicBlock :: Graph h ((VR,MR),(GPR,MR)
basicBlock = let
     mr = ldMR 0
     vr = createVR 
  in toBasicBlock (vr,mr) (dataFlow vr mr)

Need some way to pull the phantom types out

FilesExpand file tree

TODOs.org

Latest commit

History