[LLVMdev] Recursion in TableGen

David Greene dag at cray.com
Mon Aug 30 14:07:37 PDT 2010


I've been playing around with some ways to tighted up our AVX
specification and have hit upon a nice way to reduce a bunch of code.
Unfortunately, right now TableGen can't handle it.  Here's a simple
example of what I want to do:

class Data<string n, int v> {
  string Name = n;
  int Value = v;
}

// Define some objects usable as arguments.
def X : Data<"X", 1>;
def Y : Data<"Y", 1>;
def Z : Data<"X", 2>;

// Implement a recursive algorith to search a list and return a value
// if it is found.

class FindHelper<Data head, list<Data> tail,
                 string name, int default> {
  int Result = !if(!eq(head.Name, name),
                   head.Value,
                   !if(!null(tail),
                       default,
                       FindHelper<!car(tail),
                                  !cdr(tail),
                                  name,
                                  default>.Result));
}

class Find<list<Data> data, string name, int default> {
  int Result = !if(!null(data),
	           default,
	           FindHelper<!car(data),
                              !cdr(data),
                              name,
                              default>.Result);
}

class Foo<string name, list<Data> data = []> {
  string Name = name;

  // Set some data.
  int XData = Find<data, "X", 0>.Result;
  int YData = Find<data, "Y", 0>.Result;
  int ZData = Find<data, "X", 0>.Result;
}

def FOOX : Foo<"X", [X]>;
def FOOY : Foo<"Y", [X, Y]>;
def FOOZ : Foo<"Z", [Y, Z]>;

Unfortunately, the part of TableGen that generates anonymous classes
from assignments in class bodies doesn't know how to deal with
recursion.  It can't resolve the recursive "calls" to FindHelper and so
we end up with undefined data members if the list is more than one item
long.

In the short term I guess I'll add a !find() operator that just knows
how to do a search.  But it would be really nice to be able to code this
in a functional way in the .td file rather than add special operators.
There are lots of other "functions" one could implement if this kind of
recursion was supported.

I tried hacking around in TableGen guts for a while but couldn't puzzle
out a way to get this to work.

Anyone have ideas of how to make this work?  Or want to take on the
challenge to make it work?  :)

                        -Dave



More information about the llvm-dev mailing list