PROJECT STAGE2

Introduction:

In this task, I am required to create a pass for the GCC compiler that analyzes cloned functions in a program and determines whether or not they should be pruned. The goal is to identify cloned functions and compare them to see if they are "substantially the same" or different. I will find which functions are cloned and then analyze the differences between the two versions of the function. If the functions are identical except for things like variable names or labels, I will indicate that the function can be pruned. If they are different, I will indicate that the function should not be pruned. The functions are cloned using the FMV (Function Multi-Versioning) mechanism, which automatically handles function versioning. My pass must be positioned late in the compilation process, after optimizations are complete. To compare the cloned functions, I can either examine each statement or use a hash/signature to check if they are the same.


Comparing Cloned Function Versions:

When using the command objdump -d clone-test-aarch64-prune | grep '>:', we can observe and compare the two versions of a function, such as scale_samples.default and scale_samples._Mrng(in aarch64 server), but we should not compare the resolver, which would have a name like scale_samples.resolver. To properly compare functions, we need to focus on those whose names end with a dot followed by something else (e.g., scale_samples.default, scale_samples._Mrng). It's important to exclude the resolver from the comparison, and only compare the variations of the original function itself.

Step 1:Modifying GCC Pass to Print GIMPLE Statement Numbers, Function Names, and Operands for Comparison

We need to modify the GCC pass we implemented in stage 1 to print GIMPLE statement numbers, function names, and operands for each function, in order to facilitate function comparison. 

Updated code at this point:Click here

Then, we can use the command gcc -g -O0 -fno-builtin -fdump-tree-zwang331 -o hello hello.c to see the output of the hello.c file.

The output we get is:

                                   


The reason we are doing this is to test if two functions with different GIMPLE statements (i.e., having a different number of statements) are not considered equivalent. For example, as shown in the screenshot above, the sequence of GIMPLE statement numbers is 8, 6, 4, and 10. If our cloned functions have a different sequence of statement numbers, they are considered not equivalent. However, if the sequence of GIMPLE statement numbers is the same but their operands differ, the functions are still considered not equivalent.


Step 2:Find the cloned function(s)

To find cloned functions, first, get the base function name from fun->decl. Then, go through all functions in the program using FOR_EACH_FUNCTION(node), making sure each function has a valid name. For each function, check if its name starts with the base function name and has a dot (.) after it. Also, ignore functions that contain .resolver in their name. If a function meets these conditions, print it as a cloned function. This way, we will find as many cloned functions as possible, as long as they meet these conditions.(we have to set DUMP_ALL = 1 to enable all GCC dumps)

Updated code at this point:Click here

Example:Result for clone-test-aarch64-prune-clone-test-core.c.265t.zwang331:


    （Result for scale_samples.default: Found cloned function: scale_samples.rng）



 （Result for scale_simples.defualt: no cloned function are found）

Example:Result for clone-test-aarch64-noprune-clone-test-core.c.265t.zwang331:


（Result for scale_samples.default: Found cloned function: scale_samples.sve2）

（Result for scale_samples.resolver: No cloned function found）


Step 3:Compare the function's GIMPLE Code

In order to compare two functions.I added a function to compare the GIMPLE codes of the base and cloned functions. If their codes are the same, I mark the cloned function as "PRUNE", meaning it's a clone. If the codes differ, I mark it as "NOPRUNE", meaning the function is not a clone. This approach helps me detect cloned functions and decide whether they can be pruned or need further analysis.

Updated code at this point:Click here
Example:Result for clone-test-aarch64-prune-clone-test-core.c.265t.zwang331:

(Result for scale_samples.default and its cloned function: [PRUNE])

Example:Result for clone-test-aarch64-unprune-clone-test-core.c.265t.zwang331:
(Result for scale_samples.default and its cloned function: [NOPRUNE] )



Step 4:Compare the operands

Finally, I added more to improve the comparison between the base function and cloned functions by considering operand types, not just GIMPLE codes. Previously, we determined whether to prune a function based solely on GIMPLE codes, which wasn’t always accurate because two functions could have identical operations but different operand types, leading to incorrect pruning. By including operand type checks, I ensure that pruning only happens when both the operations and data types match exactly, preventing unintended optimizations that could change program behavior. This makes function cloning analysis more precise.

Updated code at this point:Click here:

(Result for scale_samples.default and its cloned function: [PRUNE])


(Result for scale_samples.default and its cloned function: [NOPRUNE])

Capabilities:

My code is designed to compare a base function with multiple related cloned functions and can successfully run on both x86 and AArch64 server.It searches for cloned functions by looking for functions whose names start with the base function's name and do not contain ".resolver." For each related cloned function, it compares the GIMPLE code and operand types with the base function. If the codes and operand types are the same, it marks the cloned function as "PRUNE," indicating it is identical to the base function. If they differ, it marks the cloned function as "NOPRUNE."

Reflection:

I have learned several things within Stage 2. For example, I gained a deeper understanding of what GIMPLE code is and how it serves as an intermediate representation used by the GCC compiler. GIMPLE statements are operations that the compiler performs, each consisting of a specific operation and operands, which can be variables, constants, or more complex expressions. It is also important to compare these statements to determine whether a base function and a cloned function should be pruned or not, based on whether their GIMPLE codes and operands match. It is interesting to browse through gimple files and other related source files in the GCC codebase.However, it is also the challenging part, especially when it comes to comparing GIMPLE statements in a fast and efficient way. The method I am currently using feels inefficient because it involves iterating through all the functions and comparing them after processing, which isn't optimal.I also found that if I want to compare operand types, I need to use TREE_TYPE, which I didn't fully understand before. TREE_TYPE is a macro in the GCC compiler that gets the type of a tree node. A tree in GCC is a structure that represents things like variables, constants, and expressions. Since operands in GIMPLE statements are stored as tree nodes, using TREE_TYPE helps me get the type of each operand. This is important for comparing operand types between functions, so I did some research online to understand it better.

Issues / Improvements I Want to Make for Stage 3:

When I first tried to retrieve the GIMPLE code of a cloned function, I decided to loop through the other functions, comparing each one to the current function to find the cloned one. I was able to identify the cloned function successfully. However, when trying to extract and save its GIMPLE code using the FOR_EACH_BB_FN function, I ran into an error. I realized I might have been passing the wrong arguments. Despite trying different syntaxes, the issue persisted. As a result, I chose to save the names of all functions along with their GIMPLE code and compare them later after processing all the functions. However, this method is not efficient, and it's something I aim to improve in stage 3 so I don't need to loop through the functions twice,and save all the  functions' GIMPLE code and statements.

Error Part:
// Find and print only matching functions
        cgraph_node *node;
        FOR_EACH_FUNCTION(node) {
            if (!node->decl || !DECL_NAME(node->decl))
                continue;

            const char *func_name = IDENTIFIER_POINTER(DECL_NAME(node->decl));
            if (strncmp(func_name, base_func_name, strlen(base_func_name)) == 0 &&
                func_name[strlen(base_func_name)] == '.' &&
                strstr(func_name, ".resolver") == NULL) {
                fprintf(dump_file, "Cloned function: %s\n", func_name);

                // Save the gimple code sequence for cloned functions
                FOR_EACH_BB_FN(bb, node->decl) {
                    for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
                        gimple *stmt = gsi_stmt(gsi);
                        cloned_function_gimple_code.push_back(gimple_code(stmt));
                    }
                }
            }
        }

Error Message:
g++ -std=c++14 -fno-PIE -c -g -DIN_GCC -fno-exceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall -Wno-error=narrowing -Wwrite-strings -Wcast-qual -Wno-format -Wmissing-format-attribute -Wconditionally-supported -Woverloaded-virtual -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -DHAVE_CONFIG_H -fno-PIE -I. -I. -I/home/zwang331/git/gcc/gcc -I/home/zwang331/git/gcc/gcc/. -I/home/zwang331/git/gcc/gcc/../include -I/home/zwang331/git/gcc/gcc/../libcpp/include -I/home/zwang331/git/gcc/gcc/../libcody -I/home/zwang331/git/gcc/gcc/../libdecnumber -I/home/zwang331/git/gcc/gcc/../libdecnumber/bid -I../libdecnumber -I/home/zwang331/git/gcc/gcc/../libbacktrace -o tree-zwang331.o -MT tree-zwang331.o -MMD -MP -MF ./.deps/tree-zwang331.TPo /home/zwang331/git/gcc/gcc/tree-zwang331.cc In file included from /home/zwang331/git/gcc/gcc/backend.h:32, from /home/zwang331/git/gcc/gcc/tree-zwang331.cc:4: /home/zwang331/git/gcc/gcc/tree-zwang331.cc: In member function ‘virtual unsigned int {anonymous}::pass_zwang331::execute(function*)’: /home/zwang331/git/gcc/gcc/basic-block.h:213:29: error: ‘union tree_node’ has no member named ‘cfg’ 213 | FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb) | ^~~ /home/zwang331/git/gcc/gcc/basic-block.h:210:13: note: in definition of macro ‘FOR_BB_BETWEEN’ 210 | for (BB = FROM; BB != TO; BB = BB->DIR) | ^~~~ /home/zwang331/git/gcc/gcc/tree-zwang331.cc:88:17: note: in expansion of macro ‘FOR_EACH_BB_FN’ 88 | FOR_EACH_BB_FN(bb, node->decl) { | ^~~~~~~~~~~~~~ /home/zwang331/git/gcc/gcc/basic-block.h:213:68: error: ‘union tree_node’ has no member named ‘cfg’ 213 | FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb) | ^~~ /home/zwang331/git/gcc/gcc/basic-block.h:210:25: note: in definition of macro ‘FOR_BB_BETWEEN’ 210 | for (BB = FROM; BB != TO; BB = BB->DIR) | ^~ /home/zwang331/git/gcc/gcc/tree-zwang331.cc:88:17: note: in expansion of macro ‘FOR_EACH_BB_FN’ 88 | FOR_EACH_BB_FN(bb, node->decl) { | ^~~~~~~~~~~~~~ make[3]: *** [Makefile:1209: tree-zwang331.o] Error 1

Comments

Post a Comment

Popular posts from this blog

PROJECT STAGE1

Image
Project Stage 1 Overview In this project, we will update the compiler to add automatic features, allowing us to create one binary that works on more platforms. In the first stage, we will improve the compiler by adding extra optimization or transformation steps. This includes making a basic GCC pass that goes through the compiled code, prints each function's name, counts how many basic blocks are in each function, and shows the total number of GIMPLE statements in each function.  Step 1:Environment  Setup We will use three separate directories to manage our GCC setup and the modifications made in lab4 : Directories contain: git/gcc Directory – This is the source code directory where the GCC source files are stored. gcc-build-001 Directory – This is the build directory where the compilation process takes place. gcc-test-001 Directory – This is the installation directory where the final GCC binaries and related files are placed after a successful build. Step 2:  Understandi...
Read more

LAB 4

Image
Building GCC process: Step 1: Create a Directory for the GCC Source Code: Step 2: Clone the GCC Repository into the Source Directory:  Step 3: Create a Separate Build Directory Note: Building GCC directly in its source code directory is not recommended. Doing so can mix original source files with new files created during the build process, making it hard to manage the code. This can also cause problems with version control systems, which track changes in the code. To avoid these issues, it's better to create a separate directory for building GCC. This keeps the original source code clean and makes it easier to manage different build versions. For example, you can create a directory named gcc-build next to your GCC source code directory and perform the build process there. Step 4: Configure the Build Note: --prefix option specifies the installation directory for GCC after the build process. In this case, GCC will be installed in ~/gcc-test-001. gcc-build-001 Directory: Purpose: This...
Read more