Project-stage 2

 This is the stage 2 for the project. Continue on stage 1, which download the codebase and build it in my own computer. (Before professor change the requirement, I have finished the stage 1 so that I choose to build gcc in my own laptop). By the recommendation steps to finish the stage 2. First I will create a dummy pass with diagnostic dump. 

By finishing the first step, I have create a file call tree-mypass.cc file which is a pass file. The code in the pass file is that

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tree.h"

#include "tree-pass.h"

#include "context.h"

#include "function.h"

#include "dumpfile.h"

namespace {

    const pass_data my_pass_data = {

        GIMPLE_PASS,         

        "my_pass",        

        OPTGROUP_NONE,       

        TV_NONE,           

        PROP_gimple_any,   

        0,                   

        0,                   

        0,                   

    };

    class pass_my_pass : public gimple_opt_pass {

    public:

        pass_my_pass(gcc::context* ctxt)

            : gimple_opt_pass(my_pass_data, ctxt) {}

        bool gate(function* fun) override {

            return true;

        }

        unsigned int execute(function* fun) override {

            if (dump_file) {

                fprintf(dump_file, "My pass is running on function: %s\n", function_name(fun));

            }

            return 0;

        }

    };

} 

gimple_opt_pass* make_pass_my_pass(gcc::context* ctxt) {

    return new pass_my_pass(ctxt);

}

This is a simple pass file that will write a message to the dump file for each function it processes.

Then in order to use this pass file in build process. I need to update Makefile.in. I have add the tree-mypass.o in OBJS list in the Makefile.in file. Then I also need to update the tree-pass.h file by adding extern struct gimple_opt_pass* make_pass_my_pass(gcc::context*); After doing that, I will need to update passes.def by adding line NEXT_PASS(make_pass_my_pass);. After doing all these steps, I have implement the basic dummy test.

The next step that the professor recommend us to do is to add logic to iterate through the code in the program being complied. By doing this step, I will need to open the created file tree-mypass.cc and update the execute functon. to 

unsigned int execute(function* fun) override {

            if (dump_file) {

                fprintf(dump_file, "My pass is running on function: %s\n", function_name(fun));

            }

            basic_block bb;

            FOR_EACH_BB_FN(bb, fun) {

                gimple_stmt_iterator gsi;

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

                    gimple* stmt = gsi_stmt(gsi);

                    if (dump_file) {

                        print_gimple_stmt(dump_file, stmt, 0, TDF_SLIM);

                    }

                }

            }

            return 0;

        }. 

This will iterate basic blocks and the FOR_EACH_BB_FN is a macro that iterate over each basic block.  And for 

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

                    gimple* stmt = gsi_stmt(gsi);

                    if (dump_file) {

                        print_gimple_stmt(dump_file, stmt, 0, TDF_SLIM);

                    }

                } will iterate over the GIMPSE statements.

Continue to the next step, which is adding logic to find the cloned functions. In this project, we have assumed that there is only one base function that has been cloned and there are any two versions of that function. So we can collect all function names during the pass and determine the base and cloned function. I will need to modify the execute function again. In the execute function, I will need to collect funtion info which will be using to collect the function name

const char *fname = function_name(fun); if (fname) { std::string function_name_str(fname); functions.emplace_back(function_name_str, fun); }

and we need to override a complier optimization class called next_pass, to opt_pass *next_pass() override { analyze_cloned_functions(); return gimple_opt_pass::next_pass(); }

And the analyze_cloned_functions() funtion is :

void pass_my_pass::analyze_cloned_functions() {

    if (functions.empty())

        return;

    std::string base_function_name;

    function* base_function = nullptr;

    function* cloned_function = nullptr;

    for (const auto& func_pair : functions) {

        const std::string& fname = func_pair.first;

        if (is_possible_base_function(fname)) {

            base_function_name = fname;

            base_function = func_pair.second;

            break;

        }

    }

    if (!base_function) {

        if (dump_file) {

            fprintf(dump_file, "No base function found.\n");

        }

        return;

    }

    for (const auto& func_pair : functions) {

        const std::string& fname = func_pair.first;

        if (is_clone(fname, base_function_name)) {

            cloned_function = func_pair.second;

            break;

        }

    }

    if (!cloned_function) {

        if (dump_file) {

            fprintf(dump_file, "No cloned function found for base function: %s\n", base_function_name.c_str());

        }

        return;

    }

    if (dump_file) {

        fprintf(dump_file, "Base function: %s\n", base_function_name.c_str());

        fprintf(dump_file, "Cloned function: %s\n", function_name(cloned_function));

    }

    // Proceed to compare the functions in the next step

}

For the next step which is adding the logic to compare the gimple representation of the funtions.

In order to accomplish this step, we will need to first collect the GIMPLE statements by adding a funtion in our class to collect the GIMPLE statements and return them in vector. This will be accomplished by the funtion 

std::vector<gimple*> get_gimple_statements(function* fun) {

    std::vector<gimple*> stmts;

    basic_block bb;

    FOR_EACH_BB_FN(bb, fun) {

        gimple_stmt_iterator gsi;

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

            gimple* stmt = gsi_stmt(gsi);

            stmts.push_back(stmt);

        }

    }

    return stmts;

}

After using this funtion to collect the GIMPLE statements, I have implemented a funtion to compare the statements from the statements we got. 

bool functions_are_equivalent(function* fun1, function* fun2) {

    auto stmts1 = get_gimple_statements(fun1);

    auto stmts2 = get_gimple_statements(fun2);

    if (stmts1.size() != stmts2.size()) {

        if (dump_file) {

            fprintf(dump_file, "Functions have different number of statements.\n");

        }

        return false;

    }

    for (size_t i = 0; i < stmts1.size(); ++i) {

        gimple* stmt1 = stmts1[i];

        gimple* stmt2 = stmts2[i];

        if (!gimple_structural_equiv_p(stmt1, stmt2)) {

            if (dump_file) {

                fprintf(dump_file, "Statements at position %zu are not equivalent.\n", i);

                print_gimple_stmt(dump_file, stmt1, 0, TDF_SLIM);

                print_gimple_stmt(dump_file, stmt2, 0, TDF_SLIM);

            }

            return false;

        }

    }

    return true;

}

This funtion will compare the statements from two funtion and check if they are euqivalent. 

For the last step, we will add the code to check if a funtion should be removed or not. 

For this step I just need to update the funtion analyze_cloned_functions() to perform the comparison by using the funtions we have implement from last step, 

bool equivalent = functions_are_equivalent(base_function, cloned_function);

And based on the comparison result, we will remove the funtion that have the same statement.

Conclusion, for the stage 2 of this project, we have use some knowledge that we learned from step 1 like implementing dummy test and use it during the process of compilation. But it still took so much time to implement all the steps since it is quite complicated to think about how to get the funtion name, the cloned funtion and GLIMPSE statements.