Compare and Remove the same (redundant) functions in LLVM

Background

In my last blog, I introduced how to clone functions in LLVM. After a range of specific optimization passes, some cloned functions may not change as a redundant function. This blog shows how to delete these redundant functions.

I didn’t find related discussion on Google. Maybe no one has the need to clone the functions and delete them like I do. But class MergeFunctions in llvm/lib/Transforms/IPO/MergeFunctions.cpp gives a good example. In this class, it didn’t provide an external API, but we can still learn some techniques from it. LLVM’s doc also introduces this clearly.

Solution

The key point is to use std::set, an STL container with unique key value, to filter the unique functions. This means we need to program our own compare functions for the set data structure. diralik provides 5 ways to design a custom std::set comparator. In this blog, I chose the traditional old way with () operator.

I used a FunctionNode class to store the Function in LLVM and its FunctionComparator::FunctionHash. Then I had a FunctionNodeCmp class with a custom () operator, and use the FunctionComparator::FunctionHash and FunctionComparator::compare() to compare if two functions are the same.

The last step is to insert each function into the std::set. And remember,

Code

Anyone is free to use it, and please indicate the reference when using or publishing. Thank you!

References