Week 11 - Project Stage 2: Phase 3&4 - Comparing Cloned Functions & Outputs

Hamza TeliHamza Teli
12 min read

Table of contents

Welcome again! In this article, I will be documenting how I completed the compare cloned functions and also output whether a function is pruned or not.

However, before I get into the code. I want to teach you all a shortcut I created that you may also implement to make your life easier.

Basically, each time I log back into the SPO600 servers, the GCC is reset to the default GCC within the bin directory. You can determine this by executing the following command:

  • which gcc

So now you have two options, either type in the path of your custom gcc each time you want to execute a .c file, or set it manually using the following command: PATH=”$HOME/gcc-test-001/bin:$PATH”

But what if I told you, theres an easier way? We can create an alias inside the .bashrc file that when executed, it runs that command. Please follow the steps below

  • Execute → nano ~/.bashrc

  • Add the following line to the end → alias addgcc="export PATH=\"$HOME/gcc-test-001/bin:\$PATH\"" . NOTE: The ‘addgcc’ can be anything you want

  • Execute → source ~/.bashrc

  • Now run the newly created alias → addgcc

  • And finally double check by executing → which gcc

If you see your gcc is set to the custom one you created, you are good to go!

Comparing the cloned functions

In this section, I will go over the way I implemented the functionality that compares the cloned functions. I will cover this section in phases and the changes I made.

Phase 1 - Obtaining the functions cloned

If you read the previous article, I completed the logic that finds the variant cloned functions. I utilized a map data structure to hold the base and its corresponding values are a vector of string names for the clones. So for example, it can look like this

  • “foo” :

    • → foo.default

    • → foo.sve2

Now what I did initially is I utilized the map and created another method that takes in a pointer of the map I set. It loops the map and uses the names of the cloned functions. I then initialize two null pointers of type function. I do this because we assume that a function if it has a resolver will have only 2 clones variants. Now I use the FOR_EACH_FUNCTION macro to then set each function by ensuring it meets the if condition. After looping, I validate the functions and if both were found, I simply print a statement that the function was found.

Please see the code for the method below

// This function will compare the two variants for each base function.
            // If the two functions are identical then it will print PRUNE, if not then NOPRUNE
            void compare_the_cloned_functions(const std::map<std::string, std::vector<std::string>> &variantMap) {
                // Lets loop and see if we have two variants
                for (const auto &base : variantMap) {

                    // Get the key and values
                    const std::string &baseName = base.first;
                    const std::vector<std::string> &variantValues = base.second;

                    // We assume that each base function has two clones
                    if (variantValues.size()!=2) {
                        fprintf(dump_file, "The number of variants for %s are not %d", baseName.c_str(), 2);
                        continue;
                    }

                    // Instantiate function pointers
                    function *functionOne = nullptr;
                    function *functionTwo = nullptr;

                    // Same logic as before
                    cgraph_node *node;
                    // Loop through each function and return the function we need
                    FOR_EACH_FUNCTION(node) {
                        function *fun = node->get_fun();

                        // Validate it
                        if (!fun) {
                            continue;
                        }
                        std::string functionName(function_name(fun));
                        // 
                        if (functionName == variantValues[0] || (functionName + ".default") == variantValues[0]) {
                            functionOne = fun;
                        }
                        else if (functionName == variantValues[1] || (functionName + ".default") == variantValues[1]) {
                            functionTwo = fun;
                        }
                    }

                    // Validate if both are valid
                    if (!functionOne || !functionTwo) {
                        fprintf(dump_file, "ERROR! Function 1 and function 2 could not be retrieved. Check the logic!\n");
                    }
                    else 
                    {
                        fprintf(dump_file, "Successfully retrieved both function 1 and two, the addresses are as follows: %p,  %p \n", (void*)functionOne, (void*)functionTwo);
                    }
                }
            }

After re-building my custom gcc build, I obtained the following output. Please see the output and image below.

[hteli1@aarch64-002 test-clone]$ cat *-noprune*.hteli1

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=5500, cgraph_uid=24, symbol_order=23)

--------------------------------------------------------------------------------
**** ---> Resolver was found for base function: scale_samples
**** ---> Clone variant successfully found: scale_samples.sve2 (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
**** ---> Clone variant successfully found: scale_samples.default (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
------------------------- Summary --------------------------
Resolver Function: scale_samples.resolver
 -------->  Variant: scale_samples.sve2
 -------->  Variant: scale_samples.default
-----------------------------------------------------------
Successfully retrieved both function 1 and two, the addresses are as follows: 0xffff8dbb5a90,  0xffff8d829ea0 

^^^^^^^^LOOK AT THIS LAST LINE!!!!^^^^^^^^^^^

Phase 2 - Comparing the two functions

If you understand my logic, you would know that my next step would be too then use the function pointers to compare the two and identify if they are similar. Now it might sound simple, but honestly, this part took me quite some time. [Took me like almost 3 days :( ]

The way I approached this logic was I had 3 checks whereby thanks to Professor Chris Tyler I knew which checks to complete

  1. Compare the basic block counts

  2. Compare the GIMPLE statement counts

  3. Compare the GIMPLE instructions

Step 1 - Compare basic block counts

If the basic block in each function differs, we can assume they are not the same. I created a simple method that takes a function pointer as a parameter and returns its number of basic blocks. Please see the logic below

// Get the number of basic blocks
size_t get_number_of_basic_blocks(function* func) {
  // Instantiate counter
  size_t count = 0;

  basic_block bb;
  FOR_EACH_BB_FN(bb, func) {
    count++;
  }

  return count;
}

Step 2 - Compare the GIMPLE statement counts

Same concept as the logic above, I simply compare the number of GIMPLE statements by again passing the function as the parameter.

// Get the number of statements inside the function
size_t get_number_of_gimple_statements(function* func) {
  // Initialize basic block
  basic_block bb;

  // Hold number of GIMPLE values
  std::vector < gimple * > allStatements;

  FOR_EACH_BB_FN(bb, func) {
    for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next( & gsi)) {
      gimple * stmt = gsi_stmt(gsi);
      allStatements.push_back(stmt);
    }
  }

  if (allStatements.size() > 0) {
    fprintf(dump_file, "Number of gimple statements is %zu\n", allStatements.size());
  }

  return allStatements.size();
}

Step 3 - Compare each GIMPLE instruction

If it passes each of the passes above, then the last one is to check each GIMPLE operations. The logic checks if it has the same number of operands (values used in the operation) and opcode (the type of operation). In this function I pass in each function as a pointer.

// This function performs the gimple code check by checking the operands and number of statements
bool are_functions_identical_by_gimple_code_and_ops(function* f1, function* f2) {
  basic_block bb1;
  basic_block bb2;

  // Create vector of gimple to store statements
  std::vector < gimple * > stmts1, stmts2;

  // Collect all statements from function 1
  FOR_EACH_BB_FN(bb1, f1) {
    for (gimple_stmt_iterator gsi = gsi_start_bb(bb1); !gsi_end_p(gsi); gsi_next( & gsi)) {
      stmts1.push_back(gsi_stmt(gsi));
    }
  }

  // Collect all statements from function 2
  FOR_EACH_BB_FN(bb2, f2) {
    for (gimple_stmt_iterator gsi = gsi_start_bb(bb2); !gsi_end_p(gsi); gsi_next( & gsi)) {
      stmts2.push_back(gsi_stmt(gsi));
    }
  }

  // Compare rhe statement counts
  if (stmts1.size() != stmts2.size()) {
    fprintf(dump_file, "Statement count mismatch: %zu vs %zu\n", stmts1.size(), stmts2.size());
    return false;
  }

  // Compare GIMPLE codes and operand counts
  for (size_t i = 0; i < stmts1.size(); ++i) {
    gimple * s1 = stmts1[i];
    gimple * s2 = stmts2[i];

    enum gimple_code code1 = gimple_code(s1);
    enum gimple_code code2 = gimple_code(s2);
    unsigned ops1 = gimple_num_ops(s1);
    unsigned ops2 = gimple_num_ops(s2);

    if (code1 != code2) {
      fprintf(dump_file, "GIMPLE code mismatch at statement %zu:\n", i);
      fprintf(dump_file, "Function 1: ");
      print_gimple_stmt(dump_file, s1, 0, TDF_NONE);
      fprintf(dump_file, "\nFunction 2: ");
      print_gimple_stmt(dump_file, s2, 0, TDF_NONE);
      fprintf(dump_file, "\n");
      return false;
    }

    if (ops1 != ops2) {
      fprintf(dump_file, "Operand count mismatch at statement %zu:\n", i);
      fprintf(dump_file, "Function 1: %u operands, Function 2: %u operands\n", ops1, ops2);
      return false;
    }
  }
  return true;
}

This concludes Phase 2 of this logic, and the only phase remaining is to output a statement indicating whether to PRUNE or NOPRUNE.

Phase 3 - Output PRUNE or NOPRUNE

The code for this was hands down the easiest part of the project (Thankfully). It’s a simple if statement that checks my identical flag.

// Set a flag
bool identical = true;

// Final flag set
if (basicBlockCountForFunctionTwo != basicBlockCountForFunctionOne || gimpleCountForFunctionTwo != gimpleCountForFunctionOne || !gimpleCodeAndOpsCheck) {
  identical = false;
}

// Now just print the PRUNE / NOPRUNE MESSAGE
if (identical) {
  fprintf(dump_file, "PRUNE: %s\n", baseName.c_str());
} else {
  fprintf(dump_file, "NOPRUNE: %s\n", baseName.c_str());
}

Full Solution Code

To access the full code, please visit the following link: https://github.com/Hamza-Teli/spo600-project-stage-2

Final Output - Testing on AArch64

I developed this pass and first added it into an AArch64 system. Therefore I am going to test it there first.

Testing Instructions

Please navigate to the gcc-build-001 directory and execute the following commands:

  • time make -j$(nproc) |& tee third_build_log_analyzing_cloned_variants_final.log

  • make install

Please ensure you have the following directory unzipped (/public/spo600-test-clone.tgz)

Once its unzipped, please perform the following actions.

  • Navigate to test-clone → cd ~/spo600/examples/test-clone

  • Execute → make clean

  • Execute → make

Many files will be created, to make things easier to read, please execute the following command:

  • ls *hteli1

This will output the files ending with my pass name which are just two:

[hteli1@aarch64-002 test-clone]$ ls *hteli1
clone-test-aarch64-noprune-clone-test-core.c.265t.hteli1  clone-test-aarch64-prune-clone-test-core.c.265t.hteli1

Output for NOPRUNE - AArch64

I simply executed the command: cat clone-test-aarch64-noprune-clone-test-core.c.265t.hteli1 and I received the following output:

[hteli1@aarch64-002 test-clone]$ cat clone-test-aarch64-noprune-clone-test-core.c.265t.hteli1

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=5500, cgraph_uid=24, symbol_order=23)

--------------------------------------------------------------------------------
**** ---> Resolver was found for base function: scale_samples
**** ---> Clone variant successfully found: scale_samples.sve2 (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
**** ---> Clone variant successfully found: scale_samples.default (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------

------------------------- Summary --------------------------
Resolver Function: scale_samples.resolver
 -------->  Variant: scale_samples.sve2
 -------->  Variant: scale_samples.default
-----------------------------------------------------------
Successfully retrieved both function 1 and two, the addresses are as follows: 0xffff8a863a90,  0xffff8a4d7ea0 

---------------------------------------------------------
----------------- Basic Block Counts ---------------------
Function 1: (scale_samples.sve2) Block Count 5
Function 2: (scale_samples) Block Count 32
---------------------------------------------------------
Number of gimple statements is 24
Number of gimple statements is 130

---------------------------------------------------------
----------------- GIMPLE Counts ---------------------
Function 1: (scale_samples.sve2) Gimple Count 24
Function 2: (scale_samples) Gimple Count 130
---------------------------------------------------------
Statement count mismatch: 24 vs 130
0 for gimpleCodeAndOpsCheck. (1 means pass, 0 means fail)
NOPRUNE: scale_samples

Looking at the last line it correctly identifies that there is NOPRUNE. However, unfortunately this is not the case. You will see in the PRUNE example what I mean by that.

Output for PRUNE - AArch64

[hteli1@aarch64-002 test-clone]$ cat clone-test-aarch64-prune-clone-test-core.c.265t.hteli1

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=5500, cgraph_uid=24, symbol_order=23)

--------------------------------------------------------------------------------
**** ---> Resolver was found for base function: scale_samples
**** ---> Clone variant successfully found: scale_samples.rng (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
**** ---> Clone variant successfully found: scale_samples.default (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------

------------------------- Summary --------------------------
Resolver Function: scale_samples.resolver
 -------->  Variant: scale_samples.rng
 -------->  Variant: scale_samples.default
-----------------------------------------------------------
Successfully retrieved both function 1 and two, the addresses are as follows: 0xffff9254ba90,  0xffff921bfea0 

---------------------------------------------------------
----------------- Basic Block Counts ---------------------
Function 1: (scale_samples.rng) Block Count 5
Function 2: (scale_samples) Block Count 32
---------------------------------------------------------
Number of gimple statements is 24
Number of gimple statements is 130

---------------------------------------------------------
----------------- GIMPLE Counts ---------------------
Function 1: (scale_samples.rng) Gimple Count 24
Function 2: (scale_samples) Gimple Count 130
---------------------------------------------------------
Statement count mismatch: 24 vs 130
0 for gimpleCodeAndOpsCheck. (1 means pass, 0 means fail)
NOPRUNE: scale_samples

As you can see, there is something clearly wrong with my comparison functions. I know that my identifying cloned functions logic works as you can see in the output. But there must be something wrong with my comparison. I will discuss this with Professor Chris Tyler as I tried for a few hours but unfortunately could not find out why. Logically to me it makes sense but this is something new to me.

Nonetheless, I do want to conclude this article by saying that although this stage was quite difficult, I do feel like I learned a lot. I have a better understanding of AFMV, how to find basic blocks, gimple statement counts, etc. These are fundamental concepts to build something big. Based on the unfortunate output above, I do have quite a bit to learn and I hope to fix the issue above.

Final Output - Testing on x86

I completed the same steps above for x86 and listed the output on the terminal below:

Output for NOPRUNE - x86

hteli1@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-noprune-clone-test-core.c.265t.hteli1 

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=3954, cgraph_uid=24, symbol_order=23)

--------------------------------------------------------------------------------
**** ---> Resolver was found for base function: scale_samples
**** ---> Clone variant successfully found: scale_samples.arch_x86_64_v3 (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
**** ---> Clone variant successfully found: scale_samples.default (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------

------------------------- Summary --------------------------
Resolver Function: scale_samples.resolver
 -------->  Variant: scale_samples.arch_x86_64_v3
 -------->  Variant: scale_samples.default
-----------------------------------------------------------
Successfully retrieved both function 1 and two, the addresses are as follows: 0x7effa3c1b750,  0x7effa3cde750 

---------------------------------------------------------
----------------- Basic Block Counts ---------------------
Function 1: (scale_samples.arch_x86_64_v3) Block Count 5
Function 2: (scale_samples) Block Count 31
---------------------------------------------------------
Number of gimple statements is 24
Number of gimple statements is 165

---------------------------------------------------------
----------------- GIMPLE Counts ---------------------
Function 1: (scale_samples.arch_x86_64_v3) Gimple Count 24
Function 2: (scale_samples) Gimple Count 165
---------------------------------------------------------
Statement count mismatch: 24 vs 165
0 for gimpleCodeAndOpsCheck. (1 means pass, 0 means fail)
NOPRUNE: scale_samples

PRUNE Output for AArch64

hteli1@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-prune-clone-test-core.c.265t.hteli1 

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=3954, cgraph_uid=24, symbol_order=23)

--------------------------------------------------------------------------------
**** ---> Resolver was found for base function: scale_samples
**** ---> Clone variant successfully found: scale_samples.popcnt (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------
**** ---> Clone variant successfully found: scale_samples.default (base function: scale_samples) with resolver: scale_samples.resolver
--------------------------------------------------------------------------------

------------------------- Summary --------------------------
Resolver Function: scale_samples.resolver
 -------->  Variant: scale_samples.popcnt
 -------->  Variant: scale_samples.default
-----------------------------------------------------------
Successfully retrieved both function 1 and two, the addresses are as follows: 0x7fc46541b750,  0x7fc4654de750 

---------------------------------------------------------
----------------- Basic Block Counts ---------------------
Function 1: (scale_samples.popcnt) Block Count 5
Function 2: (scale_samples) Block Count 31
---------------------------------------------------------
Number of gimple statements is 24
Number of gimple statements is 165

---------------------------------------------------------
----------------- GIMPLE Counts ---------------------
Function 1: (scale_samples.popcnt) Gimple Count 24
Function 2: (scale_samples) Gimple Count 165
---------------------------------------------------------
Statement count mismatch: 24 vs 165
0 for gimpleCodeAndOpsCheck. (1 means pass, 0 means fail)
NOPRUNE: scale_samples

Once again, there is something wrong with my logic… [ :( ]. I did try really hard to debug this but couldn’t fix it unfortunately.

Next Steps

My next steps include discussing my solution with Professor Chris Tyler and fixing my solution with some assistance before I engage the last phase.

Credit & References

I do want to provide credit to Professor Chris Tyler with his great explanations during the lecture sessions over the past few weeks for this project stage. I highly recommend you all to visit the following link and learn more about this project and GCC passes in general. It’s challenging but I can guarantee you will leave learning something useful. (Hands down one of the most unique courses here at Seneca College). Link: http://spo600.cdot.systems/doku.php?id=spo600:start

0
Subscribe to my newsletter

Read articles from Hamza Teli directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Programming BlogsProgramming TipscompilerAFMVsoftware developmentComputer Sciencecomputer programminggcc compilerGcc

Written by

Hamza Teli
Hamza Teli