Identifying the Essence of a Function Clone

The first step in developing Automatic Function Multi-versioning (AFMV) is to identify whether the clones of a function are essentially the same or not. The easiest way we could go about doing this is to try to go through each function clone's GIMPLE statements line by line and compare them against other clones. If no differences are found, then we can assume that these clones are essentially the same.

The Issue

One issue we have with this though is that functions that are supposed to be "essentially" the same semantically look different after being converted to GIMPLE.

As you can see here, these lines look semantically different because they are using different variables names, etc.; however, when you look a bit closer you may notice that these lines are pretty much logically the same. This "logical essence" is what we want to try compare between clones, but how do we identify this?

The Solution

After thinking and doing some experimentation, I have come to realize that maybe instead of comparing the actual gimple statements, we could instead compare the "type" of gimple statement used. Because at the end of the day, despite using different names for variable or object properties, a GIMPLE assignment is still a GIMPLE assignment. A GIMPLE switch is still a GIMPLE switch. With this in mind, we could essentially tell that two clones are the same if they have the same order of GIMPLE statement types used.

I managed to create a pass that does just that and identifies this "essence" for any function clone and print it to a dump file. The code for the pass is available in the following GitHub gist:

https://gist.github.com/JonPeeAir/cc020a67e321ad9a0bdfe881e82243f1

Note: These files should be added / is part of the gcc subdirectory withing the gcc codebase, i.e., gcc/gcc/

In here, the "essence" of a function is basically a string of numbers that represent the order of gimple types used. When we visually compare this with other functions clones, those that have matching string are what we consider essentially the same and those that do not are considered vastly different.

Here are function clones that should be the same, so they should be pruned.

Here are function clones that should NOT be the same, so they should NOT be pruned.

What's next?

So far, the pass I made only calculates this "essence" of a function but is not yet able to compare it with other functions clones. I have been struggling to get this done, and I suspect that it might be because I am using a GIMPLE pass when I should instead be using an IPA pass. I am not quite sure though and will keep experimenting. I will continue my work on comparing function "essences" and will post updates on my next post.

For now, thanks for reading!

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