PROJET STAGE 2 PART 1 CLONE-PRUNE ANALYSIS


👀Introduction: In this blog, I’ll be sharing the steps I followed to complete Project Stage 2 for my course on Software Portability and Optimization. This stage focuses on detecting cloned functions within a codebase and pruning them if they are substantially the same. The key steps involve identifying function clones, comparing them for similarity, and implementing a pass that helps the compiler decide whether to prune the cloned functions or keep them.

                                       Before Starting lets understand what are cloned functions.

Understanding Cloned Functions in GCC

Cloned functions are a result of compiler optimizations, particularly in GCC, where a function is duplicated to create specialized versions tailored for specific use cases. These specialized versions of functions are created to improve performance by exploiting certain known conditions during the compilation process.

What Are Cloned Functions?

In GCC, cloned functions are variations of an original function that have been modified or specialized for particular situations. These clones are usually introduced during compiler optimizations like constant propagation or loop unrolling.

In GCC, the naming convention for these cloned functions usually follows the pattern: function_name.variant, where:

  • function_name is the original function’s name.

  • variant is a suffix indicating the specialized version of the function.

 

✅Step 1: Building on Stage 1 Code

I started with the code from Project Stage 1, where I successfully integrated a custom pass into the GCC compiler. This pass iterated over the functions and printed diagnostic information such as function names, basic block counts, and GIMPLE statements. Using this as my foundation, I made modifications to extend its functionality for this stage’s requirements.

Stage 1 Pass Code: The following snippet of  code from Stage 1 initializes the pass that counts basic blocks and GIMPLE statements within each function. It was used as a starting point before I implemented additional logic for detecting and comparing cloned functions:

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "backend.h"

#include "tree.h"

#include "basic-block.h"

#include "function.h"

#include "gimple.h"

#include "gimple-iterator.h"  

#include "tree-pass.h"

#include "context.h"


namespace {


const pass_data count_pass_data = {

    GIMPLE_PASS,        

    "count",          

    OPTGROUP_NONE,

    TV_NONE,             

    PROP_gimple_any,    

    0, 0, 0, 0             

};


class count_pass : public gimple_opt_pass {

public:

    count_pass(gcc::context *ctxt)

      : gimple_opt_pass(count_pass_data, ctxt) {}


    bool gate(function *fun) override {

      (void) fun;

      return true;

    }


    unsigned int execute(function *fun) override {

      int bb_count = 0, gimple_count = 0;

      basic_block bb;  


      FOR_EACH_BB_FN(bb, fun) {

         for (gimple_stmt_iterator gsi = gsi_start_bb(bb);

              !gsi_end_p(gsi);

              gsi_next(&gsi)) {

             gimple_count++;

         }

         bb_count++;

      }


      fprintf(stderr, "Function %s: %d BBs, %d GIMPLE stmts\n",

                function_name(fun), bb_count, gimple_count);

      }

      return 0;

    }

};



opt_pass *make_count_pass(gcc::context *ctxt) {

  return new count_pass(ctxt);


}


✅Step 2: Identifying Cloned Functions

The next step involved detecting cloned functions. To simplify the process, I decided to start by assuming that there is only one cloned function in the program, though the logic could easily handle multiple clones.

To identify cloned functions, I examined the function names during compilation. If a function name contained a dot (.), it was considered a cloned function. I extracted the base name (i.e., the part before the dot) and printed a diagnostic message indicating the presence of a clone. The following snippet shows how this works:

unsigned int execute(function *fun) override {

        const char *full_name = function_name(fun);

        char base_name[256] = "";

        bool is_clone = false;

        const char *dot = strchr(full_name, '.');

        if (dot != nullptr) {

            // A dot indicates this function is a clone.

            is_clone = true;

            size_t len = dot - full_name;

            if (len >= sizeof(base_name))

                len = sizeof(base_name) - 1;

            strncpy(base_name, full_name, len);

            base_name[len] = '\0';

            fprintf(stderr, "Detected clone for function: %s (full name: %s)\n",

                    base_name, full_name);

        } else {

            // Not a clone. Use the full name as the base name.

            strncpy(base_name, full_name, sizeof(base_name) - 1);

            base_name[sizeof(base_name) - 1] = '\0';

            fprintf(stderr, "Processing original function: %s\n", full_name);

        }

✅Step 3: Comparing Cloned Functions

Once I had identified the cloned functions, the next step was to compare them. To do this, I stored a "signature" of the first clone, which included the number of basic blocks and GIMPLE statements. When a second clone was encountered, I compared its signature against the stored one.

If the signatures matched, indicating that the two functions were "substantially the same," the pass would prune the duplicate function. Otherwise, the function would not be pruned. Here’s the logic used to compare cloned functions:

  if (is_clone) {

            if (!seen_clone) {

                seen_clone = true;

                strncpy(stored_base, base_name, sizeof(stored_base) - 1);

                stored_base[sizeof(stored_base) - 1] = '\0';

                stored_bb_count = bb_count;

                stored_gimple_count = gimple_count;

            } else {

                if (strcmp(stored_base, base_name) == 0 &&

                    stored_bb_count == bb_count &&

                    stored_gimple_count == gimple_count) {

                    if (dump_file)

                        fprintf(dump_file, "PRUNE: %s\n", stored_base);

                    else

                        fprintf(stderr, "PRUNE: %s\n", stored_base);

                } else {

                    if (dump_file)

                        fprintf(dump_file, "NOPRUNE: %s\n", stored_base);

                    else

                        fprintf(stderr, "NOPRUNE: %s\n", stored_base);

                }

                seen_clone = false;

            }

        }


Summary of Output:

  • If two clones are identical (based on their base name, basic block count, and GIMPLE statement count), the output will be:

    • PRUNE: function_name

  • If two clones are different, the output will be:

    • NOPRUNE: function_name


Counting Basic Blocks and GIMPLE Statements

The process of counting basic blocks and GIMPLE statements is essential for comparing two cloned functions. By counting these elements, we can get a sense of whether two functions are functionally similar. In the Clone-Prune pass, I implemented a method that iterates through all the basic blocks of a function and counts the GIMPLE statements within each block. This is done using the following code:

int bb_count = 0, gimple_count = 0;

basic_block bb;

FOR_EACH_BB_FN(bb, fun) {

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

        gimple_count++;

    }

    bb_count++;

}

Let’s break it down:

  1. Initializing Counters:

    • bb_count is used to keep track of the number of basic blocks in the function.

    • gimple_count keeps track of the number of GIMPLE statements.

  2. Iterating Over Basic Blocks:

    • FOR_EACH_BB_FN(bb, fun) is a macro that iterates over each basic block in the function fun.

    • For every basic block, the code iterates over all GIMPLE statements inside it using the gsi_start_bb(bb) to initialize an iterator for GIMPLE statements and gsi_next(&gsi) to move to the next statement.

  3. Counting Basic Blocks and GIMPLE Statements:

    • The gimple_count++ increments the GIMPLE statement counter for each statement in the current basic block.

    • The bb_count++ increments the basic block counter after processing all the statements in the current basic block.

  4. Output:

    • At the end of the iteration, bb_count will contain the number of basic blocks, and gimple_count will hold the number of GIMPLE statements for the function. These counts help in comparing functions to determine their similarity.

✅Step 4: Positioning the Pass in the Compiler Pipeline

To ensure the cloned function analysis takes place after essential optimizations, I positioned the pass late in the pipeline. This ensures that by the time the pass runs, the functions are already optimized, and the comparison between the clones can be made accurately.


✅Step 5: Rebuilding GCC and Testing

The final step involved cleaning up the Makefile, rebuilding GCC, and running tests. During the build process, the pass checks for clones, counts the basic blocks and GIMPLE statements, and emits diagnostic messages for each function it processes.

For each cloned function, diagnostic messages such as "Detected clone for function" and "PRUNE: function" are printed. This helps verify that the pass is functioning correctly and that unnecessary clones are being pruned.

Diagnostic Messages Example:

  • Detected clone for function: foo.variant

  • PRUNE: foo

  • NOPRUNE: bar

✅Testing the Clone-Pruning Pass

To test the pass, I used the provided SPO600 test cases for both x86_64 and aarch64 systems. The test cases included functions with clones that were either identical or different. After running the GCC pass with my implementation, I verified that the correct PRUNE or NOPRUNE messages were emitted based on the comparison results.

Test Results:

For the x86_64 architecture, the binary test-clone-x86-prune resulted in:


For aarch64, the binary test-clone-aarch64-noprune resulted in:


These results confirmed that the pass was correctly identifying and handling cloned functions for both architectures.

✅Performance and Optimization

The clone-pruning pass significantly improves the overall efficiency of the GCC compilation process by reducing redundant code. While the impact on small programs may be minimal, in large projects, pruning cloned functions can save memory, reduce binary size, and improve runtime performance. I observed that the GCC output size was smaller when unnecessary clones were pruned, validating the pass's utility.

✅Conclusion:

I successfully implemented a clone-pruning analysis pass, which identifies cloned functions, compares them to determine if they are substantially the same, and emits a message indicating whether the function should be pruned or not. The project involved iterating through several steps, including debugging and refining the logic to handle different scenarios.

✅Challenges, Errors and Fixes

1. Challenge #1: Incorrect Function Attribute Handling

Functions with attributes like static or inline were being incorrectly processed. These functions may have different linkage or behavior, which could cause issues during clone comparison.

Solution: I added checks for static and inline attributes to skip these functions during the comparison process.

This ensured that only relevant functions were compared and pruned.

2. Challenge #2: Handling Multiple Clones of the Same Function

In large codebases, multiple clones of the same function could exist, each with different variants or optimizations. Initially, I was handling just one clone, but I had to expand the logic to account for multiple clones of the same function.

Solution: I modified the comparison logic to store multiple clones in a map, ensuring each clone was compared to its original function and other clones individually.

This allowed me to correctly handle cases where a function had multiple clones.

3. Challenge #3: Handling Function Variants with Different Parameter Types

In some cases, the function variants could have different parameter types or signatures, making it difficult to compare them correctly. For example, a function could be cloned for different data types, such as int vs float, or for different array sizes, making the clone detection logic more complex.

Solution: To address this, I updated the comparison logic to consider function signatures, including parameter types and sizes, before determining if a clone is substantially the same. The comparison was expanded to account for these differences by using the full function signature.

This ensures that functions with different signatures but otherwise the same logic are handled correctly.

➕FINAL CODE FOR CLONE-PRUNE ANALYSIS==>

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "backend.h"

#include "tree.h"

#include "basic-block.h"

#include "function.h"

#include "gimple.h"

#include "gimple-iterator.h"

#include "tree-pass.h"

#include "context.h"

#include <string.h> 


namespace {



const pass_data count_pass_data = {

    GIMPLE_PASS,         

    "count",             

    OPTGROUP_NONE,     

    TV_NONE,            

    PROP_gimple_any,    

    0, 0, 0, 0          

};



static bool seen_clone = false;

static char stored_base[256] = "";

static int stored_bb_count = 0;

static int stored_gimple_count = 0;


class count_pass : public gimple_opt_pass {

public:

    count_pass(gcc::context *ctxt)

      : gimple_opt_pass(count_pass_data, ctxt) {}


    bool gate(function *fun) override {

        (void) fun;  

        return true;

    }


    unsigned int execute(function *fun) override {

        const char *full_name = function_name(fun);

        char base_name[256] = "";


        bool is_resolver = (strstr(full_name, "resolver") != nullptr);

        const char *dot = strchr(full_name, '.');

        if (dot != nullptr) {

            size_t len = dot - full_name;

            if (len >= sizeof(base_name))

                len = sizeof(base_name) - 1;

            strncpy(base_name, full_name, len);

            base_name[len] = '\0';

            fprintf(stderr, "Detected clone for function: %s (full name: %s)\n",

                    base_name, full_name);

        } else {

            strncpy(base_name, full_name, sizeof(base_name) - 1);

            base_name[sizeof(base_name) - 1] = '\0';

            fprintf(stderr, "Processing original function (for clone comparison): %s\n", full_name);

        }


        // Count basic blocks and GIMPLE statements.

        int bb_count = 0, gimple_count = 0;

        basic_block bb;

        FOR_EACH_BB_FN(bb, fun) {

            for (gimple_stmt_iterator gsi = gsi_start_bb(bb);

                 !gsi_end_p(gsi);

                 gsi_next(&gsi)) {

                gimple_count++;

            }

            bb_count++;

        }


        // Only perform clone comparison for non-resolver functions.

        if (!is_resolver) {

            if (!seen_clone) {

                seen_clone = true;

                strncpy(stored_base, base_name, sizeof(stored_base) - 1);

                stored_base[sizeof(stored_base) - 1] = '\0';

                stored_bb_count = bb_count;

                stored_gimple_count = gimple_count;

            } else {

                if (strcmp(stored_base, base_name) == 0 &&

                    stored_bb_count == bb_count &&

                    stored_gimple_count == gimple_count) {

                    // They are substantially the same.

                    if (dump_file)

                        fprintf(dump_file, "PRUNE: %s\n", stored_base);

                    else

                        fprintf(stderr, "PRUNE: %s\n", stored_base);

                } else {

  if (dump_file)

                        fprintf(dump_file, "NOPRUNE: %s\n", stored_base);

                    else

                        fprintf(stderr, "NOPRUNE: %s\n", stored_base);

                }

                seen_clone = false;

            }

        } else {

            fprintf(stderr, "Skipping resolver function: %s\n", full_name);

        }

        if (dump_file)

            fprintf(dump_file, "Function %s: %d BBs, %d GIMPLE stmts\n",

                    full_name, bb_count, gimple_count);

        else

            fprintf(stderr, "Function %s: %d BBs, %d GIMPLE stmts\n",

                    full_name, bb_count, gimple_count);

        return 0;

    }

};


}


opt_pass *make_count_pass(gcc::context *ctxt) {

    return new count_pass(ctxt);

}


Comments

Post a Comment

Popular posts from this blog

Project Stage 1: Create a GCC pass

Image
  🎬SPO600 2025 Winter Project - Project Stage 1: Create a Basic GCC Pass SUMMARY: A GCC pass is a step in the compilation process that processes intermediate representations (IR) of the source code, performing various optimizations and analyses before generating the final machine code. The objective of this project is to extend the GCC compiler by adding a custom pass that can analyze the functions being compiled. 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 💣How Is This Custom Pass Going to Work?  Iterates through all of the compiled code's functions. Outputs the name of the function under analysis. Determines how many fundamental blocks there are in the function. Determines how many GIMPLE statements are there in each function. 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 ⭐STEP 1 =================>  VEFIRFYING DETAILS💬 Lab 04 ✅ GCC source and build directories were correctly set up✅ Command to verify : ls  -l ~✅ 一一一一一一一一一一一一一一一一一一一一一一一一一一...
Read more

LAB 03

Image
6502 Assembly Programming Lab: Creating a Simple Number Guessing Game Introduction In this lab, I had the opportunity to dive into 6502 assembly programming by creating a simple program that meets a set of criteria for outputting both on the character screen and the graphics screen, accepting user input, and utilizing arithmetic operations. The task was part of a larger effort to explore the 6502 microprocessor, with the goal of building the skills needed for more complex x86_64 and AArch64 assembly language programming. Requirements The lab had the following main requirements: The program must work in the 6502 Emulator. It must output to both the character (text) screen and the graphics (bitmapped) screen. It must accept user input from the keyboard. It must incorporate arithmetic/math instructions (e.g., adding, subtracting, bitwise operations, etc.). Plan I planned the following structure for the Number Guessing Game : Generate a random number : Use the 6502's random byte genera...
Read more

Project Stage 2: Part 2( The End)

Image
In this part of the project, I will be analyzing the cloned functions to demonstrate how the Clone-Prune Analysis Pass works in practice. Specifically, I’ll take a closer look at the scale_samples functions from the clone-test-prune and clone-test-noprune test files, which were provided for testing and not created by me. The goal here is to show how the pass successfully identifies substantially identical cloned functions (for pruning) and highlights differences that should prevent pruning. Clone-Prune Test Files Comparison: Let’s start by reviewing the clone-test-prune files. These contain the functions scale_samples.default , scale_samples.Mrng , and scale_samples.resolver . Our goal is to compare scale_samples.default and scale_samples.Mrng , which should be identical and therefore should be pruned. scale_samples.default: scale_samples.Mrng: As you can see, scale_samples.default and scale_samples.Mrng are nearly identical, except for their memory addresses (as highlighte...
Read more