SPO600 - Project Stage 1: Gimple and Passes

Introduction In the previous post, a development instance gcc was set up - where we can experiment and contribute our changes. x86 variants are rapidly growing, where each variant is optimized for different architectures, use cases, etc. gcc unfortunately struggles to keep up with increasing number of platform-specific optimizations, leading to an increasing amount of time when selecting the platform to build . This project aims to automate the platform selection process, widening the range of supported platforms. The first stage of the project involves the introduction of GIMPLE and “passes”. Specifically focussing on counting the number of basic blocks and statements during compilation, providing insight into code structure. GIMPLE GIMPLE is a intermediate representation used by gcc when compiling. It breaks down the source code into a lower-level where it can be easier to analyze and manipulate - this becomes important in the optimization stages of compilation where transformations occur to improve performance and efficiency. Passes Passes are steps in the compiling process where the code is transformed or analyzed to improve performance, or for efficiency. Setup and Execution Overview Implementing a pass requires 4 major steps: Define the pass in a source file (.cc) Register the pass in the sequence of transformations found in passes.def Modify tree-pass.h to associate the header files for helper functions Update the Makefile to compile and link the pass Creating the Pass The pass must be created in the gcc subfolder (i.e. gcc-source/gcc). A quick ls is this directory will reveal the existing passes and transformations in gcc. japablo@x86-001:~/gccsrc/gcc$ ls ABOUT-GCC-NLS gimple.def range-op-float.cc acinclude.m4 gimple-expr.cc range-op.h aclocal.m4 gimple-expr.h range-op-mixed.h ada gimple-fold.cc range-op-ptr.cc addresses.h gimple-fold.h read-md.cc adjust-alignment.cc gimple.h read-md.h alias.cc gimple-harden-conditionals.cc README.Portability Note: these are some of the transformations. Moving back to the main topic of creating the source code in the pass, here is implementation of the pass. // gcc/tree-japablo.cc #include "config.h" #include "system.h" #include "coretypes.h" #include "backend.h" #include "tree.h" #include "gimple.h" #include "tree-pass.h" #include "ssa.h" #include "tree-pretty-print.h" #include "gimple-iterator.h" #include "gimple-walk.h" #include "internal-fn.h" #include "gimple-pretty-print.h" #include "cgraph.h" #include "gimple-ssa.h" #include "attribs.h" #include "pretty-print.h" #include "tree-inline.h" #include "intl.h" #include "function.h" #include "basic-block.h" namespace { // Pass metadata definition const pass_data my_pass_data = { GIMPLE_PASS, // Pass type (GIMPLE-level pass) "japablo", // Name of the pass OPTGROUP_NONE, // No specific option group TV_NONE, // No timevar (profiling category) PROP_cfg, // Requires CFG (Control Flow Graph) 0, // Properties required (None) 0, // Properties destroyed (None) 0, // Todo flags start 0 // Todo flags finish }; // Custom GIMPLE pass class class pass_japablo : public gimple_opt_pass { public: // Constructor: initialize the parent class with the pass context pass_japablo(gcc::context ctx) : gimple_opt_pass(my_pass_data, ctx) {} // Execute method: called when the pass runs on a function unsigned int execute(function fun) override { printf("\nFunction: %s\n", function_name(fun)); // Count basic blocks and GIMPLE statements int bb_count = 0; int stmt_count = 0; // Iterate through all basic blocks basic_block bb; FOR_EACH_BB_FN(bb, fun) { ++bb_count; for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) { ++stmt_count; // Count GIMPLE statements } } printf("Basic blocks: %d\n", bb_count); printf("GIMPLE statements: %d\n", stmt_count); return 0; // Pass execution successful } bool gate(function * /* fun /) override { return true; // Always run this pass } }; } // Factory function to instantiate the pass gimple_opt_pass make_pass_japablo(gcc::context *ctxt) { return new pass_japablo(ctxt); } Namespace and Pass Metadata namespace { const pass_data m

Mar 10, 2025 - 06:08

SPO600 - Project Stage 1: Gimple and Passes

Introduction

In the previous post, a development instance gcc was set up - where we can experiment and contribute our changes. x86 variants are rapidly growing, where each variant is optimized for different architectures, use cases, etc. gcc unfortunately struggles to keep up with increasing number of platform-specific optimizations, leading to an increasing amount of time when selecting the platform to build .

This project aims to automate the platform selection process, widening the range of supported platforms. The first stage of the project involves the introduction of GIMPLE and “passes”. Specifically focussing on counting the number of basic blocks and statements during compilation, providing insight into code structure.

`GIMPLE`

GIMPLE is a intermediate representation used by gcc when compiling. It breaks down the source code into a lower-level where it can be easier to analyze and manipulate - this becomes important in the optimization stages of compilation where transformations occur to improve performance and efficiency.

Passes

Passes are steps in the compiling process where the code is transformed or analyzed to improve performance, or for efficiency.

Setup and Execution

Overview

Implementing a pass requires 4 major steps:

Define the pass in a source file (.cc)
Register the pass in the sequence of transformations found in passes.def
Modify tree-pass.h to associate the header files for helper functions
Update the Makefile to compile and link the pass

Creating the Pass

The pass must be created in the gcc subfolder (i.e. gcc-source/gcc). A quick ls is this directory will reveal the existing passes and transformations in gcc.

japablo@x86-001:~/gccsrc/gcc$ ls
ABOUT-GCC-NLS                   gimple.def                        range-op-float.cc
acinclude.m4                    gimple-expr.cc                    range-op.h
aclocal.m4                      gimple-expr.h                     range-op-mixed.h
ada                             gimple-fold.cc                    range-op-ptr.cc
addresses.h                     gimple-fold.h                     read-md.cc
adjust-alignment.cc             gimple.h                          read-md.h
alias.cc                        gimple-harden-conditionals.cc     README.Portability

Note: these are some of the transformations. Moving back to the main topic of creating the source code in the pass, here is implementation of the pass.

// gcc/tree-japablo.cc
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "internal-fn.h"
#include "gimple-pretty-print.h"
#include "cgraph.h"
#include "gimple-ssa.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"
#include "function.h"
#include "basic-block.h"

namespace {
    // Pass metadata definition
    const pass_data my_pass_data = {
        GIMPLE_PASS,       // Pass type (GIMPLE-level pass)
        "japablo",         // Name of the pass
        OPTGROUP_NONE,     // No specific option group
        TV_NONE,           // No timevar (profiling category)
        PROP_cfg,          // Requires CFG (Control Flow Graph)
        0,                 // Properties required (None)
        0,                 // Properties destroyed (None)
        0,                 // Todo flags start
        0                  // Todo flags finish
    };

    // Custom GIMPLE pass class
    class pass_japablo : public gimple_opt_pass {
    public:
        // Constructor: initialize the parent class with the pass context
        pass_japablo(gcc::context *ctx) : gimple_opt_pass(my_pass_data, ctx) {}

        // Execute method: called when the pass runs on a function
        unsigned int execute(function *fun) override {

            printf("\nFunction: %s\n", function_name(fun));

            // Count basic blocks and GIMPLE statements
            int bb_count = 0;
            int stmt_count = 0;

            // Iterate through all basic blocks
            basic_block bb;
            FOR_EACH_BB_FN(bb, fun) {
               ++bb_count;
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
                    ++stmt_count;  // Count GIMPLE statements
                }
            }

            printf("Basic blocks: %d\n", bb_count);
            printf("GIMPLE statements: %d\n", stmt_count);

            return 0; // Pass execution successful
        }

        bool gate(function * /* fun */) override {
            return true; // Always run this pass
        }
    };
}

// Factory function to instantiate the pass
gimple_opt_pass *make_pass_japablo(gcc::context *ctxt) {
    return new pass_japablo(ctxt);
}

Namespace and Pass Metadata

namespace {
    const pass_data my_pass_data = {
        GIMPLE_PASS,       // Pass type (GIMPLE-level pass)
        "japablo",         // Name of the pass
        OPTGROUP_NONE,     // No specific option group
        TV_NONE,           // No timevar (profiling category)
        PROP_cfg,          // Requires CFG (Control Flow Graph)
        0,                 // Properties required (None)
        0,                 // Properties destroyed (None)
        0,                 // Todo flags start
        0                  // Todo flags finish
    };
}

This groups the pass definition and metadata - configuring the pass, how it should be behave, and how it fits into gcc.

Custom Pass Class `pass_japablo`

    class pass_japablo : public gimple_opt_pass {
    public:
        // Constructor: initialize the parent class with the pass context
        pass_japablo(gcc::context *ctx) : gimple_opt_pass(my_pass_data, ctx) {}

        // Execute method: called when the pass runs on a function
        unsigned int execute(function *fun) override {

            printf("\nFunction: %s\n", function_name(fun));

            // Count basic blocks and GIMPLE statements
            int bb_count = 0;
            int stmt_count = 0;

            // Iterate through all basic blocks
            basic_block bb;
            FOR_EACH_BB_FN(bb, fun) {
               ++bb_count;
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
                    ++stmt_count;  // Count GIMPLE statements
                }
            }

            printf("Basic blocks: %d\n", bb_count);
            printf("GIMPLE statements: %d\n", stmt_count);

            return 0; // Pass execution successful
        }

        bool gate(function * /* fun */) override {
            return true; // Always run this pass
        }
    };
}

The pass inherits from the gimple_opt_pass, a base class defining a GIMPLE pass. The pass is initialized with the metadata defined previously.

execute takes in a function and prints the name of the function with the number of basic blocks using FOR_EACH_BB_FN, a loop macro in gcc that simplifies iterating over each basic block of a function. The inner loop counts the number of GIMPLE statements using GIMBLE specific functions to iterate over GIMPLE statements in its intermediate form.

Factory Function for the Pass

gimple_opt_pass *make_pass_japablo(gcc::context *ctxt) {
    return new pass_japablo(ctxt);
}

A factory function is used to create an instance of the pass class (i.e. pass_japablo) and create objects (e.g. .o).

Registering the Pass

  NEXT_PASS (pass_assumptions);
  NEXT_PASS (pass_tm_init);
  PUSH_INSERT_PASSES_WITHIN (pass_tm_init)
      NEXT_PASS (pass_tm_mark);
      NEXT_PASS (pass_tm_memopt);
      NEXT_PASS (pass_tm_edges);
  POP_INSERT_PASSES ()
  NEXT_PASS (pass_simduid_cleanup);
  NEXT_PASS (pass_vtable_verify);
  NEXT_PASS (pass_lower_vaarg);
  NEXT_PASS (pass_lower_vector);
  NEXT_PASS (pass_lower_complex_O0);
  NEXT_PASS (pass_lower_bitint_O0);
  NEXT_PASS (pass_sancov_O0);
  NEXT_PASS (pass_lower_switch_O0);
  NEXT_PASS (pass_asan_O0);
  NEXT_PASS (pass_tsan_O0);
  NEXT_PASS (pass_sanopt);
  NEXT_PASS (pass_cleanup_eh);
  NEXT_PASS (pass_musttail);
  NEXT_PASS (pass_lower_resx);
  **NEXT_PASS (pass_japablo);**
  NEXT_PASS (pass_nrv);
  NEXT_PASS (pass_gimple_isel);
  NEXT_PASS (pass_harden_conditional_branches);

Where the pass is placed matters. In this case, pass_japablo will count the basic blocks and statements of the functions that were transformed in previous passes.

Semantics is key in this part. I found out the hard way by putting NEXT_PASS (make_pass_japablo); instead of NEXT_PASS (pass_japablo); resulting in this error:

./pass-instances.def: In constructor ‘gcc::pass_manager::pass_manager(gcc::context*)’:
../../gccsrc/gcc/passes.cc:1624:20: error: ‘make_make_jp_pass’ was not declared in this scope; did you mean ‘make_jp_pass’?
 1624 |       PASS ## _1 = make_##PASS (m_ctxt);          \
      |                    ^~~~~
./pass-instances.def:68:3: note: in expansion of macro ‘NEXT_PASS’
   68 |   NEXT_PASS (make_jp_pass, 1);
      |   ^~~~~~~~~

Luckily, the hints PASS ## _1 = make_##PASS (m_ctxt); and ‘make_make_jp_pass’ was not declared in this scope; did you mean ‘make_jp_pass’? led to the fix

led to the fix.

Modifying `tree-pass.h`

extern gimple_opt_pass *make_pass_tracer (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_warn_restrict (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_warn_unused_result (gcc::context *ctxt);
**extern gimple_opt_pass *make_pass_japablo (gcc::context *ctxt);**

Updating the `Makefile`

OBJS = \
...
 tree-inline.o \
        tree-into-ssa.o \
        tree-iterator.o \
        **tree-japablo.o \**
        tree-logical-location.o \

Rebuilding `gcc`

Rebuilding gcc with the new pass will require to cd into the build directory japablo@x86-001:~/gcc-build-001$ and run make clean. According to the Makefile documentation:

# 3. Use "make clean" to remove the previous build.

Running make clean will give us a clean slate, reducing the chance for build conflicts from a previous build.

Results

Here is a sample of what if printed to the console as japablo-pass is executed.

Function: gimple_simplify_373
Basic blocks: 465
GIMPLE statements: 4630

Let’s recompile the code in lab 4, a simple "hello world" program. The pass should print the number of basic blocks and GIMPLE statements in the simple hello world program.

japablo@x86-001:~/l4$ $HOME/gcc-test-001/bin/gcc test.c -o test

Function: main
Basic blocks: 2
GIMPLE statements: 4

japablo@x86-001:~/l4$ ./test
Hello, World!

Conclusion

This stage of the project will serve as the basis on how to analyze the intermediate representation of source code. Being exposed to the underlying transformations of gcc made me realize how complex a “hello world” program is. There are hundreds of optimizations happening “under the hood”, none that I am familiar with but made me curious to look into the source code of one of the “simpler” transformations and possibly experiment with it.

So far I have been mostly studying and working with high-level programming and concepts and never had the opportunity to work with lower level code. Low-level programming is verbose and requires a deeper understanding of memory management, CPU architecture, etc. Excited to continue onto the next stage - let the experimenting begin!