buildit-lang / buildit

Online demo without installing at - https://buildit.so/tryit

BuildIt   

"Every problem in Computer Science can be solved with a level of indirection and every problem in Software Engineering can be solved with a step of code-generation"

BuildIt is a a framework for rapidly developing high-performance Domain Specific Languages (DSLs) with little to no compiler knowledge. A lightweight type-based multi-stage programming framework in C++ that supports generating expresisons and rich data-dependent control flow like if-then-else conditions and for and while loops using its novel re-execution strategy for a variety of targets.

Some completed and WIP projects with BuildIt

1. NetBlocks: A Performant, customizable and modular network stack to specialize protocols and implementations
2. Easy-GraphIt: A 2021 LoC GraphIt compiler that generates high-performance GPU code!
3. Mini-Einsum DSL: Compiler for Einsum-expressions on N-dimensional dense tensors in 300 LoC (CPU and GPU parallel)

BuildIt is available opensource on GitHub under the MIT license. Many more samples are available in the samples/ directory and the website

Key Features

1. A portable light-weight multi-stage library that can be used with any standard C++ compiler.

#include <builder/dyn_var.h>
#include <builder/static_var.h>
...
> g++ foo.cpp -lbuildit -I buildit/include/

2. Write expressions and statements with dyn_var variables to generate the same code. Easily port a high-performance library into a compiler by changing types of variables.

// Code written with dyn_var<T>
for (dyn_var<int> i = 0; i < 512; i = i + 1) {
  A[i] = 0;
}

// Generates the same code

for (int var1 = 0; var1 < 512; var1 = var1 + 1) {
  var0[var1] = 0;
}

3. Use conditions and expressions on static_var to specialize generated code for high-performance.

static_var<int> bound, block_size;
...
// Splitting of loop with known bounds
for (dyn_var<int> i0 = 0; i0 < bound / block_size; i0 = i0 + 1) {
  for (dyn_var<int> i1 = i0 * block_size; i1 < (i0 + 1) * block_size; i1 = i1 + 1) {
    ...
  }
}
// conditionally generate padding loops
if (bound % block_size != 0) {
  for (dyn_var<int> i1 = (bound / block_size) * block_size; i1 < bound; i1 = i1 + 1) {
    ...
  }
}

4. Supports generation of parallel code for CPUs and GPUs with simple annotations

builder::annotate("pragma: omp parallel for");
for (dyn_var<int> i = 0; i < 512; i = i + 1) {
  A[i] = 0;
}

Debugging support

Checkout D2X a debugging library that works in tandem with BuildIt and provides debugging support for DSLs.

Build and Run

BuildIt is a pure library framework and does not require any special compiler support. To build the library, clone the repository, navigate to the top-level directory and run (please make sure you are using GNU-make and not just make) -

make

For building the library with Debugging support, run

make DEBUG=1 

To run the samples provided with the library (that also serve as simple test cases), run -

make run

The make system will report the first failing test case if any.

BuildIt is currently under active development. More features are being added to the framework to make building DSLs easy. If you notice BuildIt not functioning correctly on certain inputs, please create an issue with the code snippet and expected behavior.

buildit's Issues

Documentation?

Please add: mkdir build
to the documentation, or else make silently does nothing.

Also, it is unclear how to actually compile and run the emitted code. The examples seem to output something that can't be input into a C compiler. This is strange for a library which claims to be easy to use.

Encountered failed assertion: static_var.h:117

Hi, I got a failed assertion recently with the following error message:
buildit/include/builder/static_var.h:117: builder::static_var<T>::~static_var() [with T = double]: Assertion builder_context::current_builder_context->static_var_tuples.back().ptr == (unsigned char *)&val' failed.

I probably made a mistake somewhere in my code; is there a particular situation in which this assertion is triggered? Would be super helpful to know what to look for when I go bug hunting.

Thank you!

Bug in control flow extraction when blocks with jump labels are duplicated

There is a bug in the control flow extraction when a block of code that contains a jump target is duplicated because of "failure to merge". This causes the inserted goto to jump to a jump target that is in a different branch. This completely messes up the assumption in loop_finder that gotos and labels are structured.

A sample code that reproduces the bug is as follows -

static void bar(void) {                                                                                                                                                                                                  dyn_var<int> k = 0;
        dyn_var<int> t = 0;
        while (1) {
                while (k != 0) {
                        if (k == 0)
                                break;
                }
                while (k != 0) {
                }
        }
}

Complete example in online tool: https://buildit.so/tryit/?sample=shared&pid=0f5cd93baaaa44ac2992bc4656d178ce

A potential fix would require the label inserter to disentangle the copies and try to maintain the structured loop invariant. This bug was discovered by @VedantParanjape when working on the loop analysis pass.

Integer power base^exponent sample 27 incorrect for exponent==0

buildit/samples/sample27.cpp
buildit.pdf paper, Fig. 7, top of page 4;

constexpr
int power(int base, int exponent) {
 int res = 1, x = base;       
 while (exponent > 1) {            //  while (exponent > 0) {            
   if (exponent % 2 == 1)       
     res = res * x;      
   x = x * x;           
   exponent = exponent / 2;
 }                 
 return res * x;                   //  return res;                   
}                

static_assert( power(2,0) == 1 );  // FAIL
static_assert( power(2,1) == 2 );
static_assert( power(2,2) == 4 );

As they say in Yorkshire; "Owt to the nowt is one".
Apologies for the OCD pedantry; I know it's just a sample...
Enjoying the read; interesting stuff. Thanks for putting this out here.