Higher-Order Programming - HLS of C# Closure/Delegate to RTL

Introduction

Dynamic method dispatch is where which function body that gets called from a callsite is potentially data-dependent. Computed function calls occur with action and function delegates and dynamic object polymorphism.

In C++ there are restrictions that higher-order programming is only possible within a class hierarchy. This arises from the C compatibility issues where the higher-order function passing does not have to manage an object pointer. These issues are neatly wrapped up in C# using delegates. An action delegate has void return type whereas a function delegate returns a value.

Kiwi supports the function and action delegates of C#.

KiwiC partitions dynamically-callable method bodies into equivalence classes and gives each body within a class an integer. These classes typically contain only a very few members each. It then uses constant folding on the entire system control-flow graph as a general optimisation. This may often turn a dynamic dispatch into a static dispatch, hence these integers will not appear in the output hardware unless truly dynamic dispatch is being used, such as in the third example below.

Action Delegates

Here is an example of an action delegate and dynamic dispatch that works fine for Kiwi synthesis:

  static void t55_0()
  {
    Console.WriteLine("Kiwi Demo - Test55_0 starting - function delegate.");    
    Func<int, int, string> baz_topper = delegate(int var1, int var2)
      {	Console.WriteLine("  {1} {0} baz_topper", var1, var2);
	return "kandy";
      };

    Kiwi.Pause();
    for(int pp=0; pp<3; pp++)
      {
	Kiwi.Pause();
	string p = baz_topper(pp+1000, 50-pp);
	Console.WriteLine("  yielding {0}", p);
      }
    Console.WriteLine("t55_0 done.");
  }

Example output: Run dotnet PE file using mono

$ MONO_PATH=/home/djg11/d320/hprls/kiwipro/kiwic/distro/support mono test55.exe
Kiwi Demo - Test55 starting.
Kiwi Demo - Test55_0 starting - function delegate.
  50 1000 baz_topper
  yielding kandy
  49 1001 baz_topper
  yielding kandy
  48 1002 baz_topper
  yielding kandy
t55_0 done.

We should get the same output from the RTL.

After KiwiC compilation we have this file test55.v.

Example output RTLSIM using Icarus Verilog

$ iverilog vsys.v test55_0.v 
% ./a.out
VCD info: dumpfile vcd.vcd opened for output.
Kiwi Demo - Test55 starting.
Kiwi Demo - Test55_0 starting - function delegate.
  50 1000 baz_topper
Warning (vpi_const.cc): %d on constant strings only looks at first 4 bytes!
  yielding 1801547364
  49 1001 baz_topper
Warning (vpi_const.cc): %d on constant strings only looks at first 4 bytes!
  yielding 1801547364
  48 1002 baz_topper
Warning (vpi_const.cc): %d on constant strings only looks at first 4 bytes!
  yielding 1801547364
t55_0 done.

Did we get the same output? Yes, although iverilog is warning about something or other of little importance.

Function Delegate with Free Variables

C# 3.0 onwards supports proper closures. These are implemented inside the C# compiler and compile fine under Kiwi provided the static allocation restrictions are obeyed (which, for Kiwi 1, are that the heap is the same shape on each iteration of a loop not unwound at compile time).

Here is a full example, from the Kiwi tiny regression tests, where a free variable is captured and used as part of a higher-order function. This C# source fragment came from Stack Overflow.

// Kiwi Scientific Acceleration Example - C# closures
// (C) 2016 DJ Greaves, University of Cambridge, Computer Laboratory.
using System;
using System.Text;
using KiwiSystem;

public class test55
{
  public static Func<int,int> GetAFunc()
  {
    var myVar = 1; // This is a dynamic free variable, or would be if this were not static ... enlarge test please.
    Func<int, int> inc = delegate(int var1)
      {
	Console.WriteLine("   ... GetAFun anonymous delegate body arg={0} fv={1}", var1, myVar);
	myVar = myVar + 1;
	return var1 + myVar;
      };
    return inc;
  }

  static void t55_1()
  {
    Console.WriteLine("Kiwi Demo - Test55_1 starting.");    
    var inc = GetAFunc();
    Console.WriteLine(inc(5));
    Console.WriteLine(inc(6));
    Console.WriteLine("Test55_1 done.");
  }


  [Kiwi.HardwareEntryPoint()]
  static void Main()
  {
    Console.WriteLine("Kiwi Demo - Test55 starting.");    
    t55_1();
  }
}

HLS Synthesis of Higher-Order C# to Verilog RTL

$ mcs  /r:/home/djg11/d320/hprls/kiwipro/kiwic/distro/support/Kiwi.dll  test55.cs 
$ kiwic -vnl-roundtrip=disable  -kiwic-finish=enable  -vnl-resets=synchronous -vnl test55.v  test55.exe
$ iverilog vsys.v test55.v
$ ./a.out
VCD info: dumpfile vcd.vcd opened for output.
Kiwi Demo - Test55 starting.
Kiwi Demo - Test55_1 starting.
   ... GetAFun anonymous delegate body arg=5 fv=1
7
   ... GetAFun anonymous delegate body arg=6 fv=2
9
Test55_1 done.

Final Example

Here we demo dynamic swap of delegate pointers:

Action<int, string> boz_green = delegate(int var1, string var2)
   {	Console.WriteLine("  {1} {0} boz green", var1, var2);
   };
 Action<int, string> boz_red = delegate(int var1, string var2)
   {	Console.WriteLine("  {1} {0} boz red", var1, var2);
   };
 for(int pp=0; pp<3; pp++)
   { Kiwi.Pause(); // Pause makes this loop unwind at run time.
     boz_red(pp+100, "site1");
     boz_green(pp+200, "site2"); 
     var x = boz_red; boz_red = boz_green; boz_green = x; //swap
   }

Which can be seen to work when you run test55 in the regression suite.

Conclusions

This compiles and works fine.

But, there is a Kiwi 1 restriction that the GetAFunc call must be before the end of static elaboration since this creates the closure that is allocated on the heap. If no closure is needed, Action and Function delegates suffer from no static allocation restriction. Future Kiwi developments will relax these issues in two ways: by hoisting certain allocations to reside inside the static elaboration lasso stem and to properly support run-time dynamic allocation.

Updated Summer 2016               UP.