Clang-LLVM Compiler-Architecture Diagram | Collected & Edited by Author ©

Enhanced IR Code for Compilation Efficiency with LLVM Clang

Abstract:

This blog post details a project undertaken as part of the CSE425 (Concepts of Programming Language) course at North South University. The project’s primary focus was on developing energy-efficient, high-performance implementations of machine learning algorithms in C/C++. The key algorithms, including K-Nearest Neighbors (KNN), Naive Bayes, and Decision Trees, play a crucial role in data analysis and data-driven decision-making. The objective was to significantly reduce energy usage while maintaining optimal algorithmic performance, contributing to sustainable machine learning practices and environmentally conscious computing.

Introduction:

The primary aim of this project was to build energy-efficient, high-performance implementations of machine learning algorithms, specifically K-Nearest Neighbors (KNN), Support Vector Machine (SVM), and Decision Trees, using C/C++. The emphasis was on leveraging compiler optimization techniques, with a focus on LLVM, to enhance software efficiency and promote environmentally friendly computing methods.

Motivation:

The motivation behind this project stemmed from the increasing demand for computing systems that combine high performance with energy efficiency. The project honed in on KNN, K-means, SVM, and Decision Trees, striving to establish sustainable software development practices while harnessing the powerful capabilities of C/C++.

Algorithms Used:

The project delved into the implementation of several machine learning algorithms:

1. K-Nearest Neighbors Algorithm (KNN)
2. Support Vector Machine (SVM)
3. K-means
4. Decision Tree

Tools/Language:

Several tools were instrumental in the successful execution of the project:

1. VS Code: A simplified code editor for development tasks.
2. WSL (Windows Subsystem for Linux): Enabling the running of Linux tools on Windows.
3. LLVM: A compiler infrastructure designed for reusable libraries.
4. Python
5. C/C++
6. Assembly Language

About LLVM:

LLVM, implemented in C++, served as a compiler infrastructure with several front-ends and back-ends, providing efficient compilation since its first release in 2003. Comparisons between Clang and Clang++ with other compilers revealed LLVM’s efficiency, with Clang and Clang++ being significantly faster in certain benchmarks.

Methodology:

The methodology employed in this project involved creating both unoptimized and optimized LLVM Intermediate Representation (IR) for algorithms, measuring execution times in Python, and storing data in a CSV file. The process included documenting IR file discrepancies, discussing performance impacts, and identifying optimization areas based on observed changes in optimized IR.

Algorithm Development and LLVM IR Generation:

1. Algorithm Implementation: Implement algorithms in C++ and save as a source file (e.g., source.cpp).

2. Generate Unoptimized LLVM IR Commands:

clang++ -S -emit-llvm -o source.ll source.cpp
llc -o source_asm.s source.ll
as -o source_obj.o source_asm.s
g++ -no-pie -o source_bin source_obj.o

3. Generate Optimized LLVM IR:

clang++ -O3 -S -emit-llvm source.cpp -o optimized.ll
opt -mem2reg -simplifycfg ... -simplifycfg optimized.ll -o more_optimized.ll

Further optimization using various LLVM optimizations.

4. Generate Optimized Binary:

llc -o optimized_asm.s more_optimized.ll
as -o optimized_obj.o optimized_asm.s
g++ -no-pie -o optimized_bin optimized_obj.o

Execution Time Measurement in Python:

Utilize Python’s subprocess module to execute both unoptimized and optimized binaries. Use a Python script to measure and record execution times for each binary.

Data Collection:

Capture and store execution times for each algorithm, both unoptimized and optimized.

Data Storage as CSV:

Use Python’s csv module to save collected execution times in a CSV file for further analysis.

Visualization and Comparative Analysis:

Notebook preview: IR Code Optimization Log Comparison.

1. Data Loading: Read the saved CSV file in a Jupyter Notebook using Pandas or relevant data analysis libraries.

2. Data Visualization: Utilize Python libraries like Matplotlib, Seaborn, or Plotly to create visualizations for comparing execution times.

3. Performance Analysis: Analyze algorithm performance using visualized data. Correlate differences in LLVM IR files with observed execution time disparities.

Study Results:

The analysis conducted showed that LLVM-optimized code performed better than the original source code, with a notable reduction in execution time. This highlights the effectiveness of LLVM’s optimization techniques in improving algorithm speed and efficiency.

Discussion:

The reduction in execution times emphasizes the importance of using LLVM optimization techniques during algorithm development. The documentation of differences in LLVM IR files deepens the understanding of how LLVM optimizations impact algorithm performance, showcasing the revolutionary potential of LLVM optimization in various software applications.

Future Work:

1. Build a Cost Function: Develop a cost function to further evaluate the efficiency and performance gains achieved by LLVM optimizations.

2. Extend Algorithm Set: Explore the application of LLVM optimization techniques to a broader set of machine learning algorithms.

3. Explore Parallel Processing: Investigate the potential benefits of parallel processing in conjunction with LLVM optimizations.

4. Compare with Other Optimization Tools: Conduct a comparative analysis with other optimization tools to assess LLVM’s standing in the broader landscape of software optimization.

Git Repository:

Check here for full code: Enhanced IR Code for Compilation Efficiency with LLVM Clang.