npm package: @specs-feup/extended-task-graph
Description: An Extended Task Graph (ETG) implementation for the Clava C/C++ to C/C++ source-to-source compiler
Author: Tiago Lascasas Santos
Latest version: 1.0.0

# Extended Task Graph

This is an implementation of the [Extended Task Graph (ETG)](https://dl.acm.org/doi/abs/10.1145/3652032.3657580) intermediate representation for C/C++, built as an extension for the [Clava](https://github.com/specs-feup/clava) C/C++ to C/C++ Source-to-source compiler. Just like the compiler itself, it is packaged and distributed as an NPM package, which can be either used as a standalone app or as a library for other Clava-based NPM projects.

 These task graphs are automatically analyzed and characterized by several metrics, and through a highly flexible granularity mechanism we can perform extensive graph operations, such as task merging, splitting and clustering, while always outputting valid and readable C/C++ source code.

<div align="center">
<img src="edgedetect.png" width="300"  >
<p>Extended Task Graph of the edge detection application in
<a href="https://github.com/specs-feup/extended-task-graph/blob/main/inputs/edgedetect/edge_detect.cpp">edge_detect.cpp</a>
</p>
</div>

## How to install

This package is [available on NPM](https://www.npmjs.com/package/@specs-feup/extended-task-graph). Assuming you already have a [Clava-based NPM project](https://github.com/specs-feup/clava-project-template) setup, you can install the latest stable release with:

```bash
npm install @specs-feup/extended-task-graph@latest
```

If you want to use unstable and experimental features, use the `staging` or `nightly` tags instead, as they are both built using the most recent commit in the repository. Nightly builds are built automatically every day, while staging builds are built on-demand:

```bash
npm install @specs-feup/extended-task-graph@nightly
```

## Basic usage

To build an ETG for a given application, you can run something like this:

```TypeScript
import { ExtendedTaskGraphAPI } from "@specs-feup/extended-task-graph/ExtendedTaskGraphAPI";
import { GenFlowConfig } from "@specs-feup/extended-task-graph/GenFlowConfig";
import { TransFlowConfig } from "@specs-feup/extended-task-graph/TransFlowConfig";

const topFunctionName = "edge_detect";
const outputDir = "outputs";
const appName = "edge_detect";
const api = new ExtendedTaskGraphAPI(topFunctionName, outputDir, appName);

// Run code transformation flow
const config1 = new TransFlowConfig();  // You can omit the configs if you don't change anything
api.runCodeTransformationFlow(config1);

// Run ETG generation flow
const config2 = new GenFlowConfig();
const etg = api.runTaskGraphGenerationFlow(config2);
```

This package offers more than this simple example. Check [this folder](https://github.com/specs-feup/extended-task-graph/tree/main/test/simple-use-cases) to see more use cases.

### Output folders

Under normal usage (i.e., running the entire flow from code preprocessing, task graph generation and subsequent extraction of metrics) this package outputs the following folders:

```
<app name>
├── ast
│   ├── original - some metrics about the original application's source code, as well as its call graph and AST
│   ├── trans - same as the above, but after applying all code preprocessing transformations
│   ├── <label> - a dump explicitly triggered by the user, using a subfolder name provided by them
│   └── <...>
├── etg 
│   ├── default - a dotfile dump of the task graph generated by the graph generation flow, prior to any user transformations
│   ├── <label> - a task graph dump explicitly triggered by the user, possibly after applying transformations, using a subfolder name provided by them
│   └── <...>
└── src
    ├── golden - source code of the original program. It differs from the input only in that all macros have been resolved
    ├── inter
    │   ├── t0-normalization - source code after applying the normalization transformation (which is always the first)
    │   ├── t1-array-flattening - source code after applying the 1st transformation of the provided recipe (e.g., array flattening by default)
    |   ├── t2-constant-folding-propagation
    |   ├── t3-struct-decomposition
    │   └── tn-<label>
    ├── subset - source code after the preprocessing transformations are applied, except for function outlining
    ├── trans - source code after applying function outlining, i.e., a valid representation for generating task graphs
    ├── trans_instr - the same as the above, but with time measuring instrumentation for each function. Useful for profiling
    ├── <label> - source code output explicitly triggered by the user, possibly after applying transformations, using a subfolder name provided by them
    └── <...>
```

### Citing this work

If you found our work useful, please consider citing it as follows:

```bibtex
@inproceedings{10.1145/3652032.3657580,
     author = {Santos, Tiago and Bispo, Jo\~{a}o and Cardoso, Jo\~{a}o M. P.},
     title = {A Flexible-Granularity Task Graph Representation and Its Generation from C Applications (WIP)},
     year = {2024},
     isbn = {9798400706165},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {https://doi.org/10.1145/3652032.3657580},
     doi = {10.1145/3652032.3657580},
     booktitle = {Proceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems},
     pages = {178–182},
     numpages = {5},
     keywords = {FPGA, Hardware Accelerators, Hardware/Software Partitioning, Source-to-Source Compiler, Task Graph},
     location = {Copenhagen, Denmark},
     series = {LCTES 2024}
}
```