Table of Contents

Introduction

Welcome back to my SPO600 blog! If you didn't read my previous post, in which I described creating a basic GCC pass that counts basic blocks and GIMPLE statements, you should definitely check it out first to understand the foundation of what we're building on.

In Stage 2, we tackle a more complex challenge: building a Clone-Pruning Analysis Pass for GCC. This pass analyzes functions cloned during compilation and determines if they are substantially similar enough to be pruned. It's a deep dive into GCC optimization processes and how we can extend compiler capabilities!

Learning about GCC was really interesting, especially through Professor Chris Tyler's lectures. His clear explanations helped me a lot to navigate the complexity of compiler development. Without his videos, I probably still trying to understand how GCC works!

Project Requirements

For Stage 2, we need to create a pass that:

  • Identifies functions that have been cloned (these will have names like function.variant)
  • Examines clones to determine if they are substantially the same or different
  • Outputs diagnostic message indicating whether functions should be pruned or not

To simplify the project, we allowed to make these assumptions:

  • There is only one cloned function in the program
  • There are only two versions (clones) of that function (ignoring resolver)

What is Function Multi-Versioning (FMV)?

Before diving into implementation, it's worth understanding what function cloning or multi-versioning is in GCC.

Function Multi-Versioning is technique where a compiler creates multiple versions of the same function, each optimized for different processor capabilities. For example, one version might use AVX instructions for newer processors, while another uses more basic instructions for compatibility.

NOTE! When program runs, resolver function chooses appropriate version based on actual CPU capabilities of machine. This allows single binary to efficiently run on different processor generations without needing separate builds.

Understanding the Challenge

The challenge here is to determine when two function variants are substantially the same. According to project specs, functions are substantially the same if they are identical except for identifiers like:

  • Temporary variable names
  • Single static assignment (SSA) variable names
  • Labels
  • Basic block numbers

If two cloned functions are substantially same, there's no reason to keep both versions in final binary—we can prune the redundant one.

My Implementation Approach

After studying GCC codebase and our previous work from Stage 1, I decided implement relatively simple but effective approach:

  1. Function Recognition: Identify base function name by stripping away variant suffixes
  2. Basic Comparison Metrics: Compare structure of functions using:
    • Number of basic blocks
    • Number of GIMPLE statements

While this isn't full structural comparison, it provides solid first-pass heuristic. Functions with different block counts or statement counts definitely different, while those with matching counts likely similar (though not guaranteed).

Here's core logic from my implementation:

// Clone comparison logic using previous_function_name as flag.
if (previous_function_name.empty()) {
    // No clone stored; store current information.
    previous_function_name = base_name;
    previous_block_total = bb_count;
    previous_statement_total = gimple_count;
    // For standalone function, print footer.
    print_frame_footer(out, "ANALYSIS FINISHED!");
} else {
    // A clone already been stored; compare stored info with current function.
    if (previous_function_name == base_name &&
        previous_block_total == bb_count &&
        previous_statement_total == gimple_count)
    {
        fprintf(out, "PRUNE: %s\n", previous_function_name.c_str());
        fprintf(out, "CLONE FOUND: %s\n", previous_function_name.c_str());
        fprintf(out, "CURRENT: %s\n", full_fname.c_str());
    } else {
        fprintf(out, "NOPRUNE: %s\n", previous_function_name.c_str());
        fprintf(out, "CLONE FOUND: %s\n", previous_function_name.c_str());
        fprintf(out, "CURRENT: %s\n", full_fname.c_str());
    }
    print_frame_footer(out, "End of Diagnostic");
    // Clear previous_function_name to allow storing next clone.
    previous_function_name = "";
    previous_block_total = 0;
    previous_statement_total = 0;
}

My overall approach was:

  1. Store information about first clone encountered
  2. When encountering second clone with same base name, compare it to stored information
  3. Output PRUNE or NOPRUNE decision based on comparison
  4. Reset stored state for potential future clone pairs

Key Functions and Data Structures

Main components of my implementation include:

  • Static Storage Variables: To maintain state between function calls 
static std::string previous_function_name = "";
  static size_t previous_block_total = 0;
  static size_t previous_statement_total = 0;
  • Base Name Extraction: Strips variant suffixes to find base function name 
std::string get_base_function_name(function *fun) {
      struct cgraph_node *node = cgraph_node::get(fun->decl);
      std::string fname = (node != nullptr) ? std::string(node->name())
                                            : std::string(function_name(fun));
      size_t pos = fname.find(".resolver");
      if (pos != std::string::npos)
          return fname.substr(0, pos);
      pos = fname.find('.');
      if (pos != std::string::npos)
          return fname.substr(0, pos);
      return fname;
  }
  • Resolver Detection: Special handling for resolver functions 
bool is_resolver = (full_fname.find(".resolver") != std::string::npos);
  if (is_resolver) {
      print_frame_footer(out, "ANALYSIS FINISHED (resolver function)");
      return 0;
  }
  • Block and Statement Counting: Basic metrics for function comparison 
size_t bb_count = 0;
  size_t gimple_count = 0;
  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))
      {
          gimple_count++;
      }
  }

(In Part 2, I'll cover testing process, results, limitations, and future improvements for project.)