Project Stage 2: Clone-Pruning Analysis Pass
Revamping the GCC Pass for Function Clones
In my first project, I created a tool (called a "GCC pass") that worked on two types of computer systems (x86-64 and AARCH64). This tool could print the names of functions (pieces of code that do specific tasks) and count how many "blocks" (sections of code) each function had. However, I wanted to improve it in my second project to do something more advanced — specifically, to detect when a function is a copy of another one (a "cloned" function).
Here's how I went about improving this tool.
Making Changes to the Tool
The first thing I did was teach the tool how to detect a cloned function. When the tool detects one, it stops checking further because I only need to work with one cloned function at a time for now. I also decided to temporarily skip counting the statements and blocks of code, since I will come back to that later when comparing cloned functions.
Writing the Updated Code
I started by writing the updated code that would help the tool detect cloned functions. The new code checks if a function is a "base function" (the original version before any clones) by looking for certain names in the code. Once the base function is found, the tool compares the function's stats (like how many blocks of code and statements it has) to those of cloned functions. If the stats match, the tool will decide whether to keep or ignore the function.
Here's the updated code that does this:
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "tree-pass.h"
#include "cgraph.h"
#include "function.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "cfg.h"
#include <vector>
namespace{
const pass_data pass_data_ayoung = {
GIMPLE_PASS, /* type */
"ayoung", /* name */
OPTGROUP_NONE, /* optinfo_flags */
TV_NONE, /* tv_id */
PROP_cfg, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
0, /* todo_flags_finish */
};
// Pass class
class pass_ayoung : public gimple_opt_pass {
std::vector<const char*> functions;
public:
// Constructor
pass_ayoung(gcc::context* ctxt) : gimple_opt_pass(pass_data_ayoung, ctxt){};
unsigned int execute(function* fun) override{
cgraph_node* node = cgraph_node::get(fun->decl);
if(dump_file){
int funIndex = findClonedFunctionByName(node->name());
if(funIndex == EOF){
fprintf(dump_file, "===== This is not a cloned function =====\n\n");
}else{
fprintf(dump_file, "===== This %s maight be a clonded function =====\n"
"===== Another function with the same name: %s =====\n\n", node->name(), functions[funIndex]);
}
}
functions.push_back(node->name());
return 0;
}
// Function recevie the name of current checking function
// Return the function name index in the vector if the vector has the same function name but it is not a resolver.
// Reutrn -1 if no function name match.
int findClonedFunctionByName(const char* checkingFunName){
if(functions.empty()){
return -1;
}
for(size_t i = 0; i < functions.size(); ++i){
size_t j = 0;
for(; checkingFunName[j] != '.' || checkingFunName[j] != '\0' ; ++j){
if(functions[i][j] != checkingFunName[j]){
break;
}
}
if(checkingFunName[j] == '.'){
const char* resolver = "resolver";
const char* suffix = &checkingFunName[j + 1];
for(size_t k = 0; suffix[k] != '\0'; ++k){
if(suffix[k] != resolver[k]){
return i;
}
}
}
}
return -1;
}
};
}
//Custom pass creation function
gimple_opt_pass* make_pass_ayoung(gcc::context* ctxt){
return new pass_ayoung(ctxt);
}
Rebuilding the Tool with the New Features
Once I finished updating the code, I needed to rebuild the tool with these new features. To do this, I ran a series of commands (which are like instructions for the computer to follow) to rebuild the tool from scratch and install it.
time make -j 24 |& tee build.logmake install
After running the installation commands, everything went smoothly, and there were no errors. This was a positive sign that the tool was set up correctly.
Testing the Tool
Next, I needed to make sure my tool was working as expected. To do this, I retrieved some test files from my professor. These files contained example code that I could use to test my tool.
I then updated the instructions (called a "Makefile") to make sure the tool could be compiled with any version of the compiler, making it easier to switch between different tools in the future.
After doing that, I compiled the test files and ran the tool to check if it could detect cloned functions.
The Disappointing Results
Unfortunately, when I checked the results of the test, the tool didn't show any indication that it had detected any cloned functions. This was a bit disappointing, as I had expected it to work.
Making Another Change
I realized that the tool wasn't placed at the right step in the compilation process. So, I moved it to a later step and started the whole process again — rebuilding the tool and re-running the tests from scratch.
Testing Again
After making the changes, I re-ran the tests.
The "cloning" of basic blocks and certain operations in the provided code are represented by labels such as Removing basic block X, which refers to optimizations or transformations made on the code, likely through a compiler transformation process (e.g., dead code elimination or inlining).
Here’s a breakdown of which function is "cloned" and which is "not cloned":
Function sum_sample (Not Cloned)
-
This function contains references like
Removing basic block 5, which indicates the removal of certain parts of the function (likely due to optimization). These blocks are not executed in the optimized code. -
The rest of the code is not marked as being "cloned," and the transformations suggest it’s part of a normal compiler optimization process, such as instruction reordering, vectorization, etc.
Function scale_samples (Cloned)
- This function shows multiple instances of
Removing basic block Xthroughout the function, suggesting that a lot of optimization has been done, possibly by the compiler to eliminate certain branches or instructions deemed unnecessary. -
A crucial part of the optimization seems to be eliminating or reducing some conditional branches (
ifchecks), and inlining specific operations. -
The function is marked as
__attribute__((noinline)), meaning it explicitly instructs the compiler not to inline this function, yet this could still refer to an "optimized" or "cloned" version of the function where certain operations are optimized, but not fully cloned.
Key Indicators of Cloning / Removal
-
Removing basic block X: This generally means that parts of the function are being optimized away (not cloned but optimized to improve performance). -
PHI,VEC_PACK_TRUNC_EXPR,MEM,vec_unpack_lo_expr: These are compiler optimizations used to handle vectorization and memory manipulation, indicating that parts of the function are being transformed to use more efficient operations.
Conclusion:
-
Function
sum_sample: It does not seem to be cloned. The removal of basic blocks is part of optimization, but no direct cloning is indicated. -
Function
scale_samples: This function involves extensive block removals, optimizations, and vectorization, which might give the impression of being "cloned" in the sense of transformed or optimized code rather than literal function cloning.
Reflection on Stage II of the Project
Stage II of the project was challenging and time-consuming, but it significantly deepened my understanding of how the GCC compiler works. I learned how to use the execute() function in a GIMPLE pass to analyze and compare cloned functions. By inspecting basic blocks and GIMPLE statements, I could identify function clones, although I recognize that more in-depth comparisons could be made in the future.
Pass Limitations and Capabilities
My pass works only with GIMPLE intermediate representation and C programs, focusing on detecting function clones that can be pruned. It compares the first cloned function with others but doesn’t handle more than two clones effectively. Additionally, it processes only GIMPLE_ASSIGN, GIMPLE_COND, and GIMPLE_DEBUG statements, limiting its functionality if other GIMPLE statement types appear.
Despite these limitations, the pass successfully compares clones based on basic blocks and GIMPLE statement types, checking for equality of operands and variable patterns.
What I Learned
I learned how the execute() function operates within passes, the structure of call graph nodes, and how to analyze GIMPLE types. The biggest challenge was understanding the relationship between the execute() function and cgraph_node. Initially, I attempted an ineffective approach, but after revising it, I gained a much clearer understanding of the process.
To fill knowledge gaps, I revisited lectures, ran test programs, and consulted documentation. The most rewarding part was successfully writing and running the C/C++ code for the pass.
Future Improvements
For Stage III, I plan to extend the variable checking to more GIMPLE statement types and refine how clones are compared directly. I also want to improve the pass’s ability to handle multiple clones more effectively and prune unnecessary ones.
Comments
Post a Comment