LLVM-9.0-Learner-Tutorial

A blog for LLVM(v9.0.0) beginner, step by step, with detailed documents and comments. (Since there are many differences between LLVM 9 and LLVM 11, I also implemented a similar tutorial for LLVM-11). This blog records the way I learn LLVM and finnaly accomplish a complete project with it. Therefore, I will keep updating this blog according to the progress of my project. Currently, my target is to implement a source code optimizer. I am happy to discuss and any suggestion will be welcome ^_^ (tliang@ust.hk). If this blog is useful for you, a STAR will be encouragement to me. LOL

The learner note leads to our project for FPGA HLS, Light-HLS, presented in ICCAD 2019. If you are interested in analyzing LLVM from the perspective of project, you can have a look at Light-HLS. Please note that Light-HLS targets at FPGAs.If Light-HLS helps for your works, please cite our paper in ICCAD 2019 ^_^:

T. Liang, J. Zhao, L. Feng, S. Sinha and W. Zhang, "Hi-ClockFlow: Multi-Clock Dataflow Automation and Throughput Optimization in High-Level Synthesis," 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Westminster, CO, USA, 2019, pp. 1-6. doi: 10.1109/ICCAD45719.2019.8942136

LLVM is very interesting tool but it is also upsetting for beginners (e.g. me). In this blog, I begin with the simplest pass construction and invocation, trying to explain the usage of some functions, types and variables. A complete project will be built gradually. I just hope this github can help some people like me to understand and handle LLVM better. PS: Clang provides user with Python-APIs, hence some people may use python to handle/analyze/transform the source code. An example project can be found here.

Please note that all the experiments are built with LLVM-9.0.0. In this blog, I tend to make the passes standalone, which means that they can be called in a main source code, but do not implement in the way which requires users compile the pass into dynamic library, re-make the LLVM source code and invoke the pass by "opt" command in the terminal. I think it might not be flexible, convenient and portable for development and testing. Visual Studio Code is the suggested editor since you can trace the functions and variables in LLVM very easily with VScode.

Category:

How to use this blog

List of Experiments I conducted

Further development

---

How to use this blog

1. download the blog (entire project) and install LLVM-9.0.0. If you get problems during install LLVM, I suggest you to use the LLVM package with my install shell script.
2. basic functiones and passes are implemented in the directory "Implementations". Nearly all the directories have their own README file to explain the directory.
3. experiments are tested in the directory "Test".
4. by making a "build" directory and using CMake in each experiment directory (e.g. this one), executable can be generated and tried. (hint: cmake .. & make)
5. for user's convenience, I prepare some scripts for example, BuildAllFiles.sh, which will build all the projects, CleanBuiltFiles.sh, which will clean all the built files to shrink the size of the directories, and Build.sh in test directory, which will just build one test project. All these scripts can be run directly.
6. looking into the source code with detailed comments, reader can trace the headers and functions to understand how the experiment work.

---

usage example

  When built, most test executables can be used like below but please check the source code for confirmation.
  (1) ./LLVM_expXXXXX  <C/C++ FILE> <top_function_name>   
  or
  (2) ./LLVM_expXXXXX  <C/C++ FILE>

  for comprehensive evaluation test:
  (1) ./LLVM_expXXXXX  <C/C++ FILE> <top_function_name> <configuration_file> [DEBUG]

---

List of Experiments I conducted:

Experiment 0: Find all the functions' names in the program. (Analysis Pass) PASS CODE TEST CODE

  -- keywords: installation of LLVM, basic pass template

Experiment 1: Get the dependence graph in a function and plot it. (Analysis Pass) PASS CODE TEST CODE

  -- keywords: dependence types, graph, iterator, passmanager, iterator, types in LLVM 

Experiment 2: Utilize existing LLVM passes in your project (Analysis Pass) TEST CODE

  -- keywords: invoke different passes in your application, createXXXXPass (or new xxxxPass), 

Experiment 3: Basic Loop information analysis (Analysis Pass) PASS CODE TEST CODE

  -- keywords: co-operation/dependence between Pass, Basic function for loop analysis

Experiment 4: Invoke polyhedral Information Pass (Analysis Pass) PASS CODE TEST CODE

  -- keywords: compilation with polly libraries, pass dependence

Experiment 5: Build a ASAP scheduler to schedule the instructions for parallel machine (e.g. FPGA) and evaluate latency (Analysis Pass) PASS CODE TEST CODE

  -- keywords: information processing, DFS traverse, comprehensively used the Function/Loop/Block information, basic scheduler implementation
  -- PS: Experiment 5a is just used to collect involved instructions in a IR file.

Experiment 6: Analyze the GEP lowering transformation pass (Passed implemented in previous experimented are analysis passes.) TEST CODE TEST CODE

  -- SeparateConstOffsetFromGEP, GEP Lowering, Transformation Pass, DataLayout

Experiment 7: Implementation a transformation pass to safely remove duplicated instrcutions (Transformation Pass) PASS CODE TEST CODE

  -- keywords: erase an instruction, remove duplicatied instruction, eraseFromParent, replaceAllUsesWith

Experiment 8: By using SCEV, Successfully obtain the range of the targe value and then implement bitwidth optimization (IR insertion/operand replacement/IR removal/reduncdant instruction check T_T....) (Transformation Pass) PASS CODE TEST CODE

  -- keywords: SCEV, value range, bitwidth optimization, Usage of IR Builder, change type/width of value

Experiment 9: Build a GEP operation transformation pass for HLS (Transformation Pass) PASS CODE TEST CODE

  --- HLS, ByteAlignment->ElementAlignment, SeparateConstOffsetFromGEP, GEP Lowering, Transformation Pass, DataLayout
  --- WARNING: Currently, array of struct is not supported. In the future, we need to transform array of struct to seperate array.

Experiment 10: Hack on Clang to detect arbitary precision integer ap_int in source code for VivadoHLS and mark them in the source code (Front-end Operation: AST Consumer) ACTION CODE

  --- Front-End Operation, AST Consumer, Visit Nodes in AST, Clang, Template Detection

Experiment 11: (Patch-Applied) Hack on Clang to properly map arbitary precision integer ap_int in source code for VivadoHLS into iX in IR generation (Front-end Operation: CodeGen) TEST CODE. Since a patch for LLVM-9 necessary for this tutorial is still under the review of LLVM, complete source code of LLVM for this tutorial can be downloaded via github in case that you cannot make the patch work properly. Example of declaring arbitrary precision integer variables is shown here.

  --- CodeGen Operation, AST Consumer, Visit Nodes in AST, Clang
  --- The original way I implement is too ugly and I applied the patch which Erich Keane shared via maillist clang-cfe.
  --- The patch, under review: https://reviews.llvm.org/D59105 , is developed by Erich Keane, Compiler Engineer, Intel Corporation. (Thanks Erich!^_^)

Experiment 12: Based on the library collected from VivadoHLS synthesis result, a Pass for more accurate evaluation of timing and resource is implemented. (Analysis Pass) PASS CODE TEST CODE

  --- HLS Timing/Resource Library for most instructions, Timing/Resource Evaluation, Operation Chaining for DSP Utilization

Experiment 12(a): Based on DominatorTree push instructions back to dominant ancestor to improve parallelism and reduce redundant instructions. (Transformation Pass) PASS CODE TEST CODE

  --- DominatorTree algorithm, parallelism, redudant instruction removal

Experiment 12(c): Since LLVM-provided loop strength reduction (LSR) pass limits itself according to the Target ISA addressing mode, an aggressive LSR pass is implemented for HLS to reduce the cost of DSPs on FPGA. (Transformation Pass) PASS CODE TEST CODE

  --- Loop Strength Reduction, Analysis based on Scalar Evolution, AddRecExpr, (Aggressive: may not stable for all the situations 0-0, but it works fine temporarily)
  --- Thank Momchil Velikov for his detailed reply about my inquiry about LSR pass

Experiment 13: Before involving HLS directives (array partitioning, loop pipelining/unroll), we need to check the memory access pattern of arrays in the source code (Analysis Pass) PASS CODE

  --- SCEV, Scalar Evolution Interpretation (AddRec, Add, Unknown, Constant), Array Access Pattern

Experiment 13c: map IR code back to source code based on DWARF debug information in IR metadata (Instruction=>line in source code; basic block/loop/function=>range in source code) PASS CODE TEST CODE

  --- DWARF Debug Information for the mapping from IR code to Source Code

Experiment 13d: unroll the specifc loops according to the label set in the source code and the setting in the configuration file (Transformation Pass) PASS CODE TEST CODE

  --- Loop Unrolling, Debug Information from Source Code

Experiment 14: (WIP) Based on the IR file, evaluate the resource and timing of the Window/Buffer/Filter in HLS

  --- IR transformation, Timing/Resource Evaluation for special structures on FPGA

Experiment 15: A flow of high-level synthesis including source code processing, implementation of HLS directives, IR optimization for FPGA implementation, timing scheduling and resource binding. It consists of a series of front-end IR processing and back-end (HI_WithDirectiveTimingResourceEvaluation pass is used to evaluate the timing and resource of the application, considering the effect of HLS directives.) TEST CODE (for more information for this flow, please refer to Light-HLS)

  --- Clang Source Code Transformation, IR optimization for FPGA HLS, implementation of HLS directives, timing scheduling and resource binding.

---

Further development

If you want to do your own works based on this project, following hints might be useful.

1. user can add their passes according to the examples in the directory "Implementations".
2. Note for development: (a) remember to define unique marco for header files (like #ifndef _HI_HI_POLLY_INFO); (b) Modify the CMakelists.txt file in the 4 directories: the pass directory(example), Implementation directory(example), LLVM_Learner_Libs directory(example) and the test directory(example). The modification should add subdirectory and consider the including path/library name.

Good Good Study Day Day Up (^o^)/~