Project Stage 3

-

 

Project Stage 3: Tidy & Wrap – Clone-Prune Analysis at Scale

Welcome to the final part of my SPO600 project! In the previous stage, I built a GCC pass that could compare a cloned function to its original version by checking the number of basic blocks and the GIMPLE statements inside them. The pass would then decide whether the cloned function was identical and could be safely pruned.

That version worked well when there was only one cloned function to analyze. But in this stage I wanted to scale things up.

What’s New in Stage 3?

The goal for Stage 3 was to make the Clone-Prune Analysis Pass more complete and scalable. Here's what I aimed to do:

  • Handle multiple cloned functions, not just one.

  • Automatically skip resolver functions, which are internal compiler helpers we don’t want to compare.

  • Make the output more clear and architecture-independent (i.e., it works the same on both x86_64 and aarch64).

  • Improve diagnostic logging to make testing and verification easier.

This meant refactoring some parts of the code, updating the logic for comparing functions, and testing the pass thoroughly across both architectures to ensure consistent results.

Why This Matters

Modern compilers often create cloned versions of functions for optimization purposes (e.g., based on CPU-specific features). But sometimes, those clones end up being identical to the original function. In those cases, we can "prune" them i.e., remove or avoid keeping them, to save space and reduce redundancy.

Here is the final version of my compiler pass for Stage 3:

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tree.h"

#include "tree-pass.h"

#include "cgraph.h"

#include "function.h"

#include "basic-block.h"

#include "gimple.h"

#include "gimple-iterator.h"

#include "gimple-pretty-print.h"

#include "cfg.h"


#include <string>

#include <vector>

#include <map>


namespace {


const pass_data pass_data_project = {

    GIMPLE_PASS,    // type

    "pass_project", // 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

class pass_project : public gimple_opt_pass {

    std::vector<std::string> functions;

    std::map<std::string, std::vector<int>> gimpleCodes;

    std::map<std::string, int> bbCnts;


public:

    // Constructor

    pass_project(gcc::context* ctxt) : gimple_opt_pass(pass_data_project, ctxt) {}


    unsigned int execute(function* fun) override {

        cgraph_node* node = cgraph_node::get(fun->decl);

        std::string currFunName = node->name();

        basic_block bb;

        int bb_cnt = 0;

        int funIndex = findClonedFunction(currFunName);


        if (dump_file) {

            if (funIndex != EOF) {

                fprintf(dump_file, "===== This %s is a cloned function =====\n", currFunName.c_str());

            } else {

                fprintf(dump_file, "===== This is not a cloned function =====\n");

            }

        }


        // Store function names

        functions.push_back(currFunName);


        // Store GIMPLE code

        FOR_EACH_BB_FN(bb, fun) {

            bb_cnt++;

            for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {

                gimple* stmt = gsi_stmt(gsi);

                gimpleCodes[node->name()].push_back(gimple_code(stmt));

            }

        }


        bbCnts[currFunName] = bb_cnt;


        if (dump_file) {

            if (funIndex == EOF) {

                fprintf(dump_file, "NOPRUNE: %s\n\n", removeSuffix(currFunName).c_str());

            } else {

                fprintf(

                    dump_file, "%s: %s\n\n",

                    isIdenticalFunction(currFunName, funIndex) ? "PRUNE" : "NOPRUNE",

                    removeSuffix(currFunName).c_str()

                );

            }

        }


        return 0;

    }


    // Finds index of cloned function if one exists, else returns -1

    int findClonedFunction(std::string checkingFunName) {

        if (functions.empty()) {

            return -1;

        }


        size_t dotPos = checkingFunName.find('.');

        std::string funName = checkingFunName.substr(0, dotPos);

        std::string suffix = "";

        if (dotPos != std::string::npos) {

            suffix = checkingFunName.substr(dotPos + 1);

        }


        for (size_t i = 0; i < functions.size(); ++i) {

            if (funName == functions[i] && suffix != "resolver") {

                return i;

            }

        }


        return -1;

    }


    // Checks if two functions are identical based on basic block and GIMPLE comparison

    bool isIdenticalFunction(std::string currFunName, int orgFunIndex) {

        fprintf(dump_file, "========== Comparing Original Function and the Cloned Function ==========\n");

        fprintf(dump_file, "*** Compare Basic Block ***\n");


        fprintf(dump_file,

                "Current Function Basic Block: %d\n"

                "Original Function Basic Block: %d\n",

                bbCnts[currFunName], bbCnts[functions[orgFunIndex]]);


        if (bbCnts[currFunName] != bbCnts[functions[orgFunIndex]]) {

            fprintf(dump_file, "*** Different amount of Basic Blocks ***\n");

            return false;

        }


        fprintf(dump_file, "*** They have same amount of Basic Blocks ***\n");

        fprintf(dump_file, "Cloned Function GIMPLE code (Current) | Original Function GIMPLE code\n");


        for (size_t i = 0; i < gimpleCodes[currFunName].size(); ++i) {

            if (gimpleCodes[currFunName][i] == gimpleCodes[functions[orgFunIndex]][i]) {

                fprintf(

                    dump_file, "%d | %d\n",

                    gimpleCodes[currFunName][i], gimpleCodes[functions[orgFunIndex]][i]

                );

            } else {

                return false;

            }

        }


        return true;

    }


    // Removes ".clone" or ".resolver" suffix from function name

    std::string removeSuffix(std::string fullName) {

        size_t dotPos = fullName.find('.');

        return dotPos != std::string::npos ? fullName.substr(0, dotPos) : fullName;

    }

};


} // end namespace


// Custom pass creation function

gimple_opt_pass* make_pass_project(gcc::context* ctxt) {

    return new pass_project(ctxt);

}


Summary

This custom GCC pass identifies and analyzes cloned functions during the compilation process. Here's what it does:

  • Stores function names as they are encountered.

  • Collects GIMPLE codes for each basic block in a function.

  • Tracks basic block counts to compare function structures.

  • Detects cloned functions by comparing names and suffixes like .clone or .resolver.

  • Performs structural comparisons between original and cloned functions based on:

    • Number of basic blocks

    • Sequence of GIMPLE statements

  • Prints out pruning decisions using PRUNE or NOPRUNE based on similarity.

This pass helps determine whether a cloned function can be safely pruned, which is useful for optimizing code size and performance, especially when comparing across architectures like x86_64 and aarch64.

Testing with Multiple Cloned Functions

To test whether my pass can handle multiple cloned functions, I created a custom test case with three different functions, all marked to be cloned using the target_clones attribute. Each function does some simple computation using different data types (int16_t, float, and int32_t), so they produce meaningful GIMPLE code for analysis.

Here’s the test file I used:

#include <stdio.h>

#include <stdint.h>

#include <stddef.h>


CLONE_ATTRIBUTE

int process_int16(int16_t *data, size_t len) {

    int sum = 0;

    for (size_t i = 0; i < len; ++i) {

        sum += data[i] * 3 - data[i] / 2 + data[i] % 7;

    }

    return sum;

}


CLONE_ATTRIBUTE

float process_floats(float *data, size_t len) {

    float sum = 0.0f;

    for (size_t i = 0; i < len; ++i) {

        sum += data[i] * 1.5f - data[i] / 3.0f + data[i] * data[i];

    }

    return sum;

}


CLONE_ATTRIBUTE

int process_int32(int32_t *data, size_t len) {

    int result = 0;

    for (size_t i = 0; i < len; ++i) {

        result += (data[i] & 0xFF) + (data[i] >> 3) - (data[i] << 1);

    }

    return result;

}


int main() {

    int16_t a[128];

    float b[128];

    int32_t c[128];


    for (int i = 0; i < 128; ++i) {

        a[i] = i;

        b[i] = (float)i;

        c[i] = i;

    }


    printf("process_int16: %d\n", process_int16(a, 128));

    printf("process_floats: %.2f\n", process_floats(b, 128));

    printf("process_int32: %d\n", process_int32(c, 128));


    return 0;

}

Compiling and Testing the Pass

To actually generate the clones and see how my pass behaves with different target_clones, I compiled the test file with two different target settings:

  • One setup where the functions are similar enough to prune.

  • One where the clones are different and shouldn’t be pruned.

Here’s how I did it:

PRUNE Case

gcc -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default", "popcnt")))' -march=x86-64 -O3 -fdump-tree-pass_project testcase.c -o testcase_prune


In this case, the functions are compiled with clone targets "default" and "popcnt", which are close enough that the cloned versions often have the same GIMPLE structure. This lets my pass mark them as PRUNE.

NOPRUNE Case

gcc -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default", "arch=x86-64-v3")))' -march=x86-64 -O3 -fdump-tree-pass_project testcase.c -o testcase_noprune


This time, the cloned versions can be quite different, especially when the architecture target is more specific like x86-64-v3. As a result, my pass usually reports NOPRUNE for these functions because the GIMPLE structure changes enough to not be identical.

Results for testcase_prune

After running my pass on the testcase_prune binary, the results looked promising. The pass correctly identified cloned functions and was able to detect identical GIMPLE

structures between them, making the right pruning decisions.

Here’s a summary of what was printed in the .pass_project dump file:

===== This is not a cloned function =====

NOPRUNE: process_int16


__attribute__((target ("default"), target_clones ("default", "popcnt")))

int process_int16 (int16_t * data, size_t len)


The function process_int16 was not considered a clone (it was treated as the base/original), so no comparison or pruning applied here.

;; Function process_floats (process_floats.default, ...)

===== This is not a cloned function =====

NOPRUNE: process_floats


__attribute__((target ("default"), target_clones ("default", "popcnt")))

float process_floats (float * data, size_t len)


Same with process_floats — this function was the base version and didn't trigger a clone comparison either.

;; Function process_int32 (process_int32.default, ...)

===== This is not a cloned function =====

NOPRUNE: process_int32


__attribute__((target ("default"), target_clones ("default", "popcnt")))

int process_int32 (int32_t * data, size_t len)


Again, the default process_int32 was treated as the original.

But now it gets interesting...

Clone Detected: process_int32.popcnt

;; Function process_int32.popcnt (process_int32.popcnt, ...)


===== This process_int32.popcnt is a cloned function =====

===== Comparing Original Function and the Cloned Function =====

*** Compare Basic Block ***

Current Function Basic Block: 11

Original Function Basic Block: 11

*** They have same amount of Basic Block ***

Cloned Function Gimple code(Current) | Original Function Gimple code

1 | 1

6 | 6

1 | 1

6 | 6

6 | 6

6 | 6

6 | 6

6 | 6

6 | 6

6 | 6

6 | 6

10 | 10

PRUNE: process_int32


The pass successfully detected that process_int32.popcnt is a cloned version of process_int32.

It checked the number of basic blocks and found that they matched (11 in both), then compared the GIMPLE

statement codes one by one. Since all matched perfectly, the function was marked as PRUNE.

The Result for testcase_noprune

Let's now look at the output when running the GCC pass without enabling pruning.

As expected, this version still performs target cloning, but it does not attempt to prune any of the functions even if they are identical or very similar. Here's what the output looked like:

Not a Cloned Function

Function: process_int16

NOPRUNE: process_int16


__attribute__((target("default"), target_clones("default", "arch=x86-64-v3")))

int process_int16(int16_t * data, size_t len)

Not a Cloned Function

Function: process_floats

NOPRUNE: process_floats


__attribute__((target("default"), target_clones("default", "arch=x86-64-v3")))

float process_floats(float * data, size_t len)

Not a Cloned Function

Function: process_int32

NOPRUNE: process_int32


__attribute__((target("default"), target_clones("default", "arch=x86-64-v3")))

int process_int32(int32_t * data, size_t len)

Cloned Function Detected

Function: process_int32.arch_x86_64_v3

===== This process_int32.arch_x86_64_v3 is a cloned function =====

===== Comparing Original Function and the Cloned Function =====

*** Compare Basic Block ***

Current Function Basic Block: 15  

Original Function Basic Block: 15  

*** Same amount of Basic Blocks ***

NOPRUNE: process_int32


__attribute__((target("arch=x86-64-v3"), target_clones("default", "arch=x86-64-v3")))

int process_int32.arch_x86_64_v3(int32_t * data, size_t len)

Cloned Function Detected

Function: process_floats.arch_x86_64_v3

===== This process_floats.arch_x86_64_v3 is a cloned function =====

===== Comparing Original Function and the Cloned Function =====

*** Compare Basic Block ***

Current Function Basic Block: 15  

Original Function Basic Block: 13  

*** Different amount of Basic Blocks ***

NOPRUNE: process_floats


__attribute__((target("arch=x86-64-v3"), target_clones("default", "arch=x86-64-v3")))

float process_floats.arch_x86_64_v3(float * data, size_t len)

Cloned Function Detected

Function: process_int16.arch_x86_64_v3

===== This process_int16.arch_x86_64_v3 is a cloned function =====

===== Comparing Original Function and the Cloned Function =====

*** Compare Basic Block ***

Current Function Basic Block: 19  

Original Function Basic Block: 15  

*** Different amount of Basic Blocks ***

NOPRUNE: process_int16

__attribute__((target("arch=x86-64-v3"), target_clones("default", "arch=x86-64-v3")))

int process_int16.arch_x86_64_v3(int16_t * data, size_t len)

Summary

As you can see, none of the cloned functions were removed, even if some had the same number of basic blocks (like process_int32). This makes sense since in the nopruned version, we explicitly chose not to prune anything. It confirms that our analysis and pruning logic is gated correctly.

What I Learned

This project was a deep dive into compiler internals, and it was honestly the most technical thing I’ve done so far. A few key takeaways:

  • GCC passes are hard but incredibly rewarding once they work.

  • I got comfortable working with GIMPLE, basic blocks, and function declarations at the compiler level.

  • Architecture differences can be subtle but important, testing on both is crucial.

  • Writing blog posts alongside development helped me organize my thoughts and reflect as I went.

Final Thoughts

I came into SPO600 not knowing much about compilers, and now I’ve written a working GCC pass that can help identify

cloned functions and give smart pruning suggestions. That’s wild to me!

Huge thanks to my instructor and classmates and if you’re just starting out with compilers, trust me, it does get easier. Stick with it.

Thanks for following along! 🙌

~ Haroon Ahmed Bajwa

Comments

Post a Comment

Popular posts from this blog

Project Stage 2.A

-
Project Stage 2 – Part A: Finding Cloned Functions For Stage 2 of my SPO600 project, I’m taking the basic GCC analysis pass I built in Stage 1 and evolving it into something a bit more interesting—analyzing cloned functions. The end goal? Build a Clone-Pruning Analysis Pass that checks if functions in a compiled program are just duplicates and, if they are, recommends pruning them to save space and avoid redundancy. But before we can make any pruning decisions, we first need to find these clones. That’s what this blog is all about: detecting cloned functions in the compiled code. What Is a Cloned Function? When GCC optimizes code, it often makes slightly modified copies of functions—these are called clones . You’ll see them with names like: scale_samples.constprop.0 scale_samples.Mrng scale_samples.resolver These cloned functions usually come from optimizations like constant propagation , inlining , or architecture-specific tuning . For example, if the compiler notices that a functio...
Read more

Project Stage 2.C

-
  Project Stage 2 – Part C: Clone-Pruning in Action This is it the final part of my Clone-Pruning Analysis Pass series! So far, I’ve: Found cloned functions using name patterns and suffixes (Part A) Extracted and compared their GIMPLE to check for similarity (Part B) Now, in this post, I’ll show the analysis in action—specifically how my pass performs on two test cases provided in the course: clone-test-prune and clone-test-noprune . This is where all the logic from earlier pays off! Clone-Prune Test Files These test files contain three functions: scale_samples.default scale_samples.Mrng scale_samples.resolver My goal here: identify whether scale_samples.Mrng is identical to scale_samples.default —and if so, recommend pruning . Let’s look at them. scale_samples.default // Simplified view of instructions... vscale = 2; for (...) {     result[i] = input[i] * vscale; } scale_samples.Mrng // Basically the same logic, just cloned for target Mrng vscale = 2; for ...
Read more

Welcome to My SPO600 Journey

-
Welcome to My SPO600 Journey Hello and welcome to my first blog post! This space will document my journey through SPO600: Software Portability and Optimization ,  a course  taught by Chris Tyler   focused on understanding how software can be optimized for different hardware architectures. Throughout the course, I will be exploring low-level programming concepts, performance analysis techniques, and optimization strategies, starting with the 6502 microprocessor and advancing towards modern architectures like x86_64 and AArch64. About Me Hi everyone! My name is Haroon bajwa and I am currently studying Computer Programming and Analysis at Seneca College Newnham Campus, with a keen interest in system-level programming and performance optimization. This course presents an exciting opportunity to dive deep into assembly language and understand how code interacts with hardware. Through this blog, I aim to track my learning, share insights, and explore different optimization tech...
Read more

Lab1 6502 Assembly Language

-
  Optimizing Assembly: Insights from Lab 1 Introduction Lab 1 introduced me to the fundamentals of 6502 Assembly programming. It was my first real experience diving into low-level code, and honestly, it was a mix of confusion and excitement. The goal of the lab was to analyze an existing assembly program, understand how it works, and then try making changes to improve or modify what it does. This blog post walks through my personal journey with the lab—from running the original code to experimenting with new instructions—and what I learned along the way. Running the Bitmap Code We kicked things off with a basic assembly program designed to fill the emulator’s display with a single solid color. The code sets a pointer in memory to start writing pixel data and loops through, placing the same color on each pixel. Here’s a quick breakdown of what happens: The program sets up a pointer to location $0200 (the start of the bitmap). It sets the color to yellow with LDA #$07 . Then it uses...
Read more

Stage 1 Completed

-
Project Stage 1 Completed! For the first stage of my SPO600 project, I created a custom GCC pass that prints out the name of each function being compiled, along with the number of basic blocks and GIMPLE statements in that function. This gave me a deeper look into how the compiler breaks down high-level code during the compilation process. Setting Up My Environment I used the recommended three-directory setup: ~/git/gcc/         # GCC source directory ~/gcc-build-001/   # Build directory ~/gcc-test-001/    # Install/test directory I followed the official GCC documentation to configure the build: ../git/gcc/configure --prefix=$HOME/gcc-test-001 --enable-languages=c --disable-bootstrap --disable-multilib time make -j$(nproc) |& tee build.log The build process took a while at first, but using make for incremental rebuilds really saved time later. I made sure to always build inside a screen session so I wouldn't lose progress if my SSH connection dro...
Read more

Project Stage 2.B

-
Project Stage 2 – Part B: Comparing GIMPLE of Cloned Functions In the previous post , I wrote about how I detected cloned functions in the compiled program. I used naming conventions (like .constprop , .variant , and .resolver ) to group clones by their original function name. Now that I’ve found these cloned functions, it’s time to look inside them —into their GIMPLE representation —and figure out if they’re actually doing the same thing. This blog is all about how I accessed, compared, and analyzed the internal structure of these functions. Wait, What Is GIMPLE Again? GIMPLE is a simplified version of C/C++ code that GCC uses for optimization. It’s kind of like a low-level, easy-to-analyze form of your code, broken down into really basic steps (like x = y + 1 ). Each function is made up of: Basic Blocks : These are sequences of instructions with no jumps except at the end. GIMPLE Statements : Individual operations or assignments. In this part, I extracted GIMPLE from each clone and i...
Read more

Lab 4 Building GCC on My Linux VM

-
  Lab 4 Building GCC on My Linux VM (ft. My M2 MacBook Air) For this lab, I took a dive into the world of large software builds, specifically building the GCC compiler from source. The goal was to get hands-on experience using tools like make and autotools , since we’ll be working with GCC during our course project. Instead of using the SPO600 servers (x86-001 and aarch64-002), I decided to try something a little different and ran everything inside a Linux VM on my M2 MacBook Air (which is arm64 under the hood). Spoiler alert: it actually worked out great! Step 1: Cloning the Source Code First things first, I needed the latest development version of GCC. I SSH’d into my Linux VM and cloned the official GCC Git repo: git clone git://gcc.gnu.org/git/gcc.git gcc-source This gave me a folder full of source code, ready to be built. Step 2: Configuring the Build I’ve learned it's a bad idea to build inside the source directory, so I created a separate directory for building: mkdir gcc-b...
Read more

Lab 2 Adventures in 6502 Assembly

-
  Bouncing Pixels and Going Solo: Lab 2 Adventures in 6502 Assembly Introduction Lab 2 was originally meant to be a mob programming session, think pair programming, but with a full group, all sharing one screen and collaborating on every line of code. Unfortunately, I couldn’t make it to the in-class session, so I ended up taking on the lab solo. While I missed out on the live collaboration part, I still got a chance to dive deep into the code, experiment with the animation logic, and get creative with bouncing a graphic around the screen using 6502 Assembly. This post walks through my solo journey with Lab 2: animating a graphic diagonally, making it bounce off the edges of the screen, and exploring some fun optional challenges along the way. Setting Up the Animation We were given a base program that moves a 5×5 pixel graphic diagonally across the emulator screen. The starting point was a neat little subroutine called DRAW , which takes an image, its position, and then places it o...
Read more

Project Stage 1 Diving In!

-
  Project Stage 1 – Understanding GCC Passes and Setting things UP Alright, time to dive into the SPO600 course project! In Stage 1, our goal is to create a basic GCC pass that can analyze a program during compilation and print out some useful info. This is my first time working this closely with the GCC compiler, and let me just say, it’s a deep rabbit hole. But it’s also been really interesting figuring things out. In this post, I’ll talk about: What the project is about How I approached it Some of the issues I ran into and how I fixed them What’s This Project About? GCC processes code in multiple steps called passes . These passes can analyze and transform code at various intermediate stages before turning it into machine code. For this project, I had to: Iterate through each function being compiled Print the name of each function Count how many basic blocks are in each function Count how many GIMPLE statements are in each function These details come from GCC's internal repre...
Read more