SPO600 Closing Remarks (Update to Function Clone Pruning Analysis)

With the fall semester coming to an end and my SPO600 class coming to a close, here are some updates as to what I've been able to accomplish since my previous blog post.

Updates to Function Clone Pruning Analysis

Until now, I haven't been able to find a good way to properly compare function clones with my method of identifying functions through accumulating their GIMPLE statement types. This is because for each call to execute() on a function, the GIMPLE body of all functions in the call graph changes, so I am unable to compare their bodies accurately. What I've noticed is that when looping through all function bodies, only the function in question that was passed to execute() has the full body GIMPLE body ready while all other functions look incomplete.

The images I show below are snippets from my pass dump on an example of a test program whose clones should be pretty much identical, and so should be marked for "pruning."

Here is the pass dump for the default function clone

As you can see, the function code summary for the popcnt clone is a lot shorter compared to the default clone when really it shouldn't be because there should be almost no difference between a default and popcnt clone.

Now here is the pass dump for the popcnt clone.

Notice how the function code summary for the default clone now is pretty much non-existent! The popcnt clone, on the other hand, finally has a fully analyzed GIMPLE body with codes similar to the default function in the previous call to execute.

This got me thinking that maybe my method for comparing functions by looping through all functions in the call graph is probably not ideal and that I should try to find another strategy to do so.

I tried to do some further digging as to why I am unable to loop through complete GIMPLE bodies every call to execute, and from what I've gathered, it could potentially be due to the way passes are being executed.

I initially assumed that passes are executed on the whole program one at a time, but based on my digging it looks like we have these pass groups that get executed all at once for one function, then all at once again for the next function. This might explain why when looping through all the functions in every call to execute() their GIMPLE bodies look completely different from the last call to execute(). Though I could be wrong in this and have to dig deeper and experiment, but with the current state of the GCC documentation this feels like a near impossible task.

Conclusion and Recommendations

Having started with 6502 Assembly to working with 64-bit Assembly to then finally working on contributing to the GCC compiler, my SPO600 journey ends here with this solution for analyzing function clones.

Though it may be a pretty naive solution to compare functions based on their gimple statement codes (because some statements might have the same code but are logically different), it is the best solution I've come up with so far for identifying functions that essentially the same or different.

The next steps here would be to find a way to actually compare these function "essences" to determine which clones should be marked for pruning. Here are a couple ideas I have in mind to do this:

  • Maybe we could create two passes, one for analyzing and marking each function with their "essences" then another pass for actually comparing these "essences". The issue with this, however, is that other passes might make changes to the body later, and so it may deem the previously marked "essence" as outdated.

  • Another is maybe we could create a whole new pass group instead of just one new pass. Maybe by putting the pass in a clean pass group we will be able to access the full GIMPLE bodies of all functions and be able to compare them properly then. This will require a lot more understanding about pass groups however and whether or not adding a whole new pass group doesn't disrupt the current standards of the GCC compiler.

But with all that said, my biggest recommendation for the future of Automatic Function Multi-Versioning (AFMV) is to start by creating a more up to date and comprehensive documentation for GCC passes because without good documentation, trying to understand how passes work feels like a lost cause and achieving AFMV feels like such a far off dream.

Continuing off my work

For anyone wishing to continue off the work I have done, here is a link to my personal fork of GCC:

https://github.com/JonPeeAir/gcc/tree/function-clone-pruning

You can find my changes in the function-clone-pruning branch.

The main file for my pass can be found in the gcc subdirectory: gcc/gcc/tree-prunecheck.cc

And that concludes this blog. Thank you for reading and until next time!

Comments

Post a Comment

Popular posts from this blog

Lab 03 - Breakout Game

Image
This lab is quite special compared to previous ones, as it is more subjective and taps into our creativity. We were tasked with creating any program we want, as long as it meets these criteria: The program must work in the 6502 Emulator It must output to the character screen as well as the graphics (bitmapped) screen. It must accept user input from the keyboard in some form. It must use some arithmetic/math instructions (to add, subtract, do bitwise operations, or rotate/shift) Some suggestions given by our professor were to make either a simple game or a simple calculator/converter. With that in mind, I decided to remake the 1976 arcade game Breakout. What is Breakout? Based on its Wikipedia description , Breakout is a 1967 arcade game developed and published by Atari, Inc. It involves some bricks, a paddle, and a bouncing ball. The goal is to destroy all bricks with a bouncing ball, using the paddle as a sort of tool to keep the ball in play. You lose when the ...
Read more

Building GCC

In my last blog, I talked about contributing to the GCC compiler by helping out with the Automatic Function Multi-versioning (AFMV) for aarch64. In order to do that I must first learn how to build GCC myself. Unfortunately, since I do not have an aarch64 machine, I have to rely on the aarch64 systems my professor has setup in order to build/work with GCC. The system I decided to start my GGC build is an ARMv8 machine with 4 cores and 16 GiB ram. Now to start, the first step we must do is to clone the GCC git repository. Following the steps from my class wiki page I cloned the repo to my spo600 directory using the following command. $ git clone git://gcc.gnu.org/git/gcc.git ~/spo600/ After cloning, the next step is to create a build directory and configure our build to use that directory. Here are the commands I used to do so. $ mkdir ~/spo600/gcc-build-001 $ cd ~/spo600/gcc-build-001 $ ~/spo600/gcc/configure --prefix=$HOME/spo600/gcc-build-001 Now we can start the build ...
Read more

Lab 04 - Diving into 64-bit Assembly

Image
After having worked with 6502 Assembly, we now move on to the more complex 64-bit Assembly that is being used by the majority of computers today. In this lab we explore the 64-bit assembly language used in both aarch64 (ARM) and x86_64 (Intel/AMD) architectures. We will explore their differences, similarities, as well as the tradeoffs for using either. The task for this lab was to develop a simple program that prints the following output: Loop: 0 Loop: 1 Loop: 2 Loop: 3 Loop: 4 Loop: 5 Loop: 6 Loop: 7 Loop: 8 Loop: 9 Loop: 10 Loop: 11 Loop: 12 Loop: 13 Loop: 14 Loop: 15 Loop: 16 Loop: 17 Loop: 18 Loop: 19 Loop: 20 Loop: 21 Loop: 22 Loop: 23 Loop: 24 Loop: 25 Loop: 26 Loop: 27 Loop: 28 Loop: 29 Here is program I developed to do this in Aarch64 assembly. .text .globl _start min = 0 max = 30 _start: mov x19, min // Store to x19 the value of min (0) loop: /* ... body of the loop ... do something useful here ... */ // write() syscall takes 3 args; file descr...
Read more