Stage 1.1: Creating a Custom GCC Pass

Introduction

This is Stage 1 of the project, where I will be working on creating compiler optimizations for gcc. The purpose of this stage, is to practice with creating GCC Passes.

1. Iterates through the code being compiled;
2. Prints the name of every function being compiled;
3. Prints a count of the number of basic blocks in each function; and
4. Prints a count of the number of gimple statements in each function.

GCC Pass

GCC is a multi-stage compiler which translates high-level source code, into machine code. The process of compilation has many stages, which can be called passes, where the code goes through a specific optimization or transformation.

All the passes are contained within the inner gcc directory: ~/gcc/gcc/passes.cc. There are 4 types of passes, each refering to a different stage within the optimization process. Here is a list of these types, in order of processing:

ipa – relationships between different parts of the program, like inlining, values returned by subroutines,

1. tree passes run first, working on the high-level representation that’s closest to your source code
2. ipa (inter-procedural analysis) passes analyze relationships between different functions
3. lto (link-time optimization) passes operate when multiple translation units are linked together
4. rtl (register transfer language) passes run last, handling the low-level machine code transformations

Creating a Dummy Pass

The first step I will be taking, is to create a completely dummy pass file, that I will include and configure correctly, to build my project. I will do this first, and then I will proceed to implement a

Creating the Pass – Copying Existing Pass

Since this code base is large, constantly changing, and not well documented, the easiest method to start creating a pass is copying an existing pass. For this purpose, I chose tree-nrv.cc, which was also used by the professor, as the building block for my first mock pass.

cd ~/gcc/gcc
cp tree-nrv.cc tree-efagin.cc

tree-nrv.cc is actually a really long file, whose purpose is quite simple:
the NRV (Named Return Value) pass optimizes functions returning aggregate types by eliminating unnecessary copying between local variables and the return destination, essentially constructing the return value directly where it needs to be.

Basic Pass Structure

To understand the pass, and how to modify it, here is the generic, simple pass structure. It is important to note that in order for this example pass to work, we need to include the right libraries and headers.

Pass Registration Data

This part will always come first, it is responsible for defining the metadata about the pass, including the name, type, required/provided properties, and more. This helps define how a pass will function.

const pass_data pass_data_efagin = {
  GIMPLE_PASS,   /* type */
  "efagin",      /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_NONE,       /* tv_id */
  PROP_cfg,      /* properties_required */
  0,             /* properties_provided */
  0,             /* properties_destroyed */
  0,             /* todo_flags_start */
  0              /* todo_flags_finish */
};

Pass Class Definition

This part defines the actual class, and specifies the inheritance from the base class (in this case, the gimple_opt_class).

The gate function is actually important – it defines whether or not this pass should run on a particular function. It can enable or disable the pass, based on a specific condition. In this case, it always returns true – meaning it will always be applied, to any function, no matter what flags were used to compile. But in other scenarios, we can check the optimization level that was specified by the flags, and determine if the pass should be run.

class pass_efagin : public gimple_opt_pass {
public:
  pass_efagin(gcc::context *ctxt)
    : gimple_opt_pass(pass_data_efagin, ctxt) {}

  bool gate(function *) final override { return true; }
  unsigned int execute(function *) final override;
};

Execute Method

This is the “meat” of the file, the actual logic of the pass. It can analyze, or perform optimizations, iterate through different elements in the code, and more. There are different predefined macros that can be used here, like FOR_EACH_BB_FN and FOR_EACH_FUNCTION, which iterate through basic blocks and functions.

unsigned int execute (function *fun) final override {
  struct cgraph_node *node;
  int func_cnt = 0;

  // macro for iterating thru all functions
  FOR_EACH_FUNCTION (node) {
    if (dump_file) { // if a dumpfile exists
      fprintf(dump_file, "=== Function %d Name '%s' ===\n", ++func_cnt, node->name());
    }
  }

  // output end of dump
  if (dump_file) {
    fprintf(dump_file, "\n\n*** End efagin diagnostic dump ***\n\n");
  }

  return 0;
}

Factory Function

This last section has a simple goal – to create an instance of the pass, to be registered with the pass manager. Registering the pass is a crucial step – our pass wouldn’t be able to process any code.

gimple_opt_pass *
make_pass_efagin(gcc::context *ctxt) {
  return new pass_efagin(ctxt);
}

Registering the New Pass

After creating the pass for the first time, we must register it in the appropriate files, and complete these specific steps, to ensure it gets included in the chain.

Include Pass in passes.def

The first step is to include the pass in the passes.def file. The order here actually matters a lot – this is the order in which the passes will be applied to the code. Earlier placement means the code is closer to its source code, meaning not many optimizations were done. Later in the list, means the code has undergone significant transformations, often making it more optimized but potentially harder to relate back to the original source.

...
NEXT_PASS (pass_nrv);
NEXT_PASS (pass_efagin); // My pass 
NEXT_PASS (pass_gimple_isel);
...

Add Pass to tree-pass.h

The order here doesn’t matter, but it is still important to add the pass decleration to this header file. This ensures that the tree-pass.h can be used to access the pass that we just created.

...
extern gimple_opt_pass *make_pass_warn_unused_result (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_efagin (gcc::context *ctxt); // My pass
extern gimple_opt_pass *make_pass_diagnose_tm_blocks (gcc::context *ctxt);
...

Modify Makefile.in

Adding the object file to the makefile is important because otherwise your new pass won’t be compiled and linked into the GCC executable. The order doesn’t matter.

Note: you must use tabs, instead of spaces, to match the style of the original Makefile.in file. Otherwise, there will be errors.

...
tree-complex.o \
tree-efagin.o \
tree-data-ref.o \
...

Reconfigure the Makefile (in build directory)

Unfortunately, these changes will not be automatically detected in the build directory – we must re-create the Makefile, so that it reflects the new pass we added. For that, we need to go to our build directory, delete the file, reconfigure the build, and re-run the Make job. The job shouldn’t take as long as the first build, but it might still take a few minutes.

# 1. change to build directory
> cd ~/gcc-build-001 

# 2. remove the makefile
> rm Makefile

# 3. reconfigure the build
> ~/gcc/configure --prefix=$HOME/gcc-test-001 --enable-languages=c,c++

# 4. run Make Job
> (time make -j 24) |& tee build.log

# 5. run Install  
> make install

Note: These steps are only required when adding a new pass. Any subsequent change to the existing pass will only require a rebuild, and an install.

Testing the Pass

To test this dummy pass, first I want to ensure that my “custom” gcc build, is the default gcc build on my system, when executing gcc ... commands:

> which gcc
~/gcc-test-001/bin/gcc

This output tells me that the gcc command, points to my build directory. Now all I need, is to create a sample file, and execute it using a gcc command, and inspect the dump files. The sample file can be as simple as this:

// hello.c

#include <stdio.h>
int main (void) {

  printf("\nHello, World!\n\n");
  return 0;
}

To run the file, we will use a few flags to clean up the output

• -fno-builtin prevents GCC from replacing standard library functions with its built-in versions.
• -fdump-tree-efagin specifies which dump file to produce, excluding others (for simplicity).
• -g adds debugging information t o the program.
• -O0 disables all optimizations, ensuring code is compiled in a straight-forward way.

# Compile 'hello.c' into the executable 'hello'
gcc -g -O0 -fno-builtin -fdump-tree-efagin hello.c -o hello

To ensure that all these changes didn’t break the compiler, we must run the executable. If the output is as expected, the compiler works, its not broken!

# Execute to view output
> ./hello

Hello, World!

Then, we must ensure that our pass works as expected, so we can print the dump file that was created:

# View dump file
> cat a-hello.c.265t.efagin

;; Function main (main, funcdef_no=0, decl_uid=2336, cgraph_uid=1, symbol_order=0)

=== Function 1 Name 'printf' ===
=== Function 2 Name 'main' ===

*** End efagin diagnostic dump ***

Conclusion

The dummy pass that we created is fully integrated and working, on both servers: aarch64 & x86! There were many steps to create, and properly register the brand new pass, but from now on the work will be focused on implementing the optimization/diagnostic logic, and building on it each time.