Project Stage 2 (Part 3): Implementing the Clone-Pruning Logic

Building the Heart of the Pass

Once I had GCC built and the demo pass working, it was time to dive into the real challenge: implementing the clone-pruning logic in tree-ctyler.cc.

How I Tackled It

1. Understanding Gimple IR

GCC represents programs using intermediate representations, and my pass needed to analyze the Gimple IR. At first, Gimple seemed overwhelming, but once I found examples of basic block and statement iteration, it started making sense.

2. Comparing Functions

The goal was to check if two cloned functions were equivalent. I wrote a function to compare Gimple statements:
That I added the following logic to tree-ctyler.cc:

bool compare_gimple_statements(gimple *stmt1, gimple *stmt2) {
    if (gimple_code(stmt1) != gimple_code(stmt2))
        return false; // Different types of statements
    return true;
}

Then, I added a loop to iterate through the basic blocks and statements of two functions:

bool are_functions_equivalent(tree f1, tree f2) {
    basic_block bb1, bb2;

    FOR_EACH_BB_FN(bb1, cfun_for_decl(f1)) {
        FOR_EACH_BB_FN(bb2, cfun_for_decl(f2)) {
            gimple_stmt_iterator gsi1 = gsi_start(bb1);
            gimple_stmt_iterator gsi2 = gsi_start(bb2);

            while (!gsi_end_p(gsi1) && !gsi_end_p(gsi2)) {
                if (!compare_gimple_statements(gsi_stmt(gsi1), gsi_stmt(gsi2)))
                    return false; // Functions differ
                gsi_next(&gsi1);
                gsi_next(&gsi2);
            }

            if (!gsi_end_p(gsi1) || !gsi_end_p(gsi2))
                return false;
        }
    }

    return true; // Functions are equivalent
}

And also the pass was registered in passes.def;

NEXT_PASS(pass_ctyler);

3. Diagnostic Messages

Finally, the pass emitted messages based on whether the functions were equivalent:

if (are_functions_equivalent(fndecl, clone_decl)) {
    fprintf(stderr, "PRUNE: %s\n", get_name(fndecl));
} else {
    fprintf(stderr, "NOPRUNE: %s\n", get_name(fndecl));
}

Challenges

• Statement Matching: Even small differences (e.g., variable names) can cause false negatives, so I kept the comparison logic simple for now.
• Debugging: Adding print statements to the Gimple IR helped me understand what was happening under the hood.

Reflections

This stage was the most fun for me. Gimple IR is like looking into the soul of a program, and writing logic to analyze it felt empowering. The PRUNE and NOPRUNE messages were satisfying proof that the pass was working.