LLVM Optimization (5)

실습 4

[실습 4]에서는 [실습 3]을 바탕으로 전체 명령어 중 특정 종류의 명령어에 접근하여 새로운 명령어를 생성하고, 기존의 명령어를 삭제하고, 새로운 명령어로 기존의 명령어를 대체하는 작업을 수행한다.

명령어 생성

LLVM에서는 명령어를 생성하기 위해 llvm::IRBuilder 클래스를 제공한다. 이 IRBuilder 인스턴스를 사용할 수 있고, 각 명령어 클래스들에서 제공하는 static 메소드인 Create()를 사용하여 명령어를 생성할 수 있다.

예제

Add 명령어가 있다면 해당 명령어 바로 앞에 1+1 연산을 추가해보자. 이는 위에서 나왔듯이 Create() 함수를 이용하여 생성할 수 있다.

InsertInst.cpp 코드

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stdlib.h>

#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/DiagnosticPrinter.h"
#include "llvm/IR/DiagnosticHandler.h"
#include "llvm/Bitcode/BitcodeReader.h"
#include "llvm/Bitcode/BitcodeWriter.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/IRReader/IRReader.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/raw_os_ostream.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/FileSystem.h"

std::string input_path;
std::string output_path;
llvm::LLVMContext* TheContext;
std::unique_ptr<llvm::Module> TheModule;

void ParseIRSource(void);
void TraverseModule(void);
void PrintModule(void);

int main(int argc , char** argv)
{
	if(argc < 3)
	{
		std::cout << "Usage: ./InsertInst <input_ir_file> <output_ir_file>" << std::endl;
		return -1;
	}
	input_path = std::string(argv[1]);
	output_path = std::string(argv[2]);

	// Read & Parse IR Source
	ParseIRSource();
	// Traverse TheModule
	TraverseModule();
	// Print TheModule to output_path
	PrintModule();

	return 0;
}

// Read & Parse IR Sources
//  Human-readable assembly(*.ll) or Bitcode(*.bc) format is required
void ParseIRSource(void)
{
	llvm::SMDiagnostic err;

	// Context
	TheContext = new llvm::LLVMContext();
	if( ! TheContext )
	{
		std::cerr << "Failed to allocated llvm::LLVMContext" << std::endl;
		exit( -1 );
	}

	// Module from IR Source
	TheModule = llvm::parseIRFile(input_path, err, *TheContext);
	if( ! TheModule )
	{
		std::cerr << "Failed to parse IR File : " << input_path << std::endl;
		exit( -1 );
	}
}

// Traverse Instructions in TheModule
void TraverseModule(void)
{
	for( llvm::Module::iterator ModIter = TheModule->begin(); ModIter != TheModule->end(); ++ModIter )
	{
		llvm::Function* Func = llvm::cast<llvm::Function>(ModIter);

		for( llvm::Function::iterator FuncIter = Func->begin(); FuncIter != Func->end(); ++FuncIter )
		{
			llvm::BasicBlock* BB = llvm::cast<llvm::BasicBlock>(FuncIter);
			
			for( llvm::BasicBlock::iterator BBIter = BB->begin(); BBIter != BB->end(); ++BBIter )
			{
				llvm::Instruction* Inst = llvm::cast<llvm::Instruction>(BBIter);
				if( Inst->getOpcode() == llvm::Instruction::Add )
				{
					llvm::BinaryOperator::Create( 
							llvm::Instruction::Add,	/* Opcode */
							llvm::ConstantInt::get( llvm::IntegerType::get( *TheContext, 32 ), 1, true ),	/* S1 : i32 1 */
							llvm::ConstantInt::get( llvm::IntegerType::get( *TheContext, 32 ), 1, true ),	/* S2 : i32 1 */
							"addtmp",	/* Name */
							Inst /* BeforeInst */ );
				}
			}
		}
	}
}

// Print TheModule to output path in human-readable format
void PrintModule(void)
{
	std::error_code err;
	llvm::raw_fd_ostream raw_output( output_path, err, llvm::sys::fs::OpenFlags::F_None );

	if( raw_output.has_error() )
	{
		std::cerr << "Failed to open output file : " << output_path << std::endl;
		exit(-1);
	}

	TheModule->print(raw_output, NULL);
	raw_output.close();
}

Test.c 코드

#include <stdlib.h>
#include <stdio.h>
int Add(int*arr,int*brr,int*crr,size_t n)
{
     crr[n]= arr[n]+brr[n]+n;
     return crr[n];
}

int main()
{

     int N=0;
     printf("Input N (0~5)\n");
     scanf("%d",&N);
     int crr[5]={0,0,0,0,0};
     int arr[5]={1,2,3,4,5};
     int brr[5]={2,3,4,5,6};
     int result = Add(arr,brr,crr,N);
     printf("... %d PLUS %d PLUS %d = %d\n" ,arr[N],brr[N],N,result);
}

해당 코드는 아래와 같이 실행할 수 있다.

clang++ InsertInst.cpp -o InsertInst $(llvm-config --cxxflags --ldflags --system-libs --libs mcjit irreader)  
clang -emit-llvm -S Test.c -o Test.ll  
./InsertInst Test.ll Test.Processed.ll  
vimdiff Test.ll Test.Processed.ll  # 원본과 차이 비교
clang ./Test.Processed.ll -o Test
./Test

명령어 삭제

명령어 삭제를 위해서는 당연히 해당 명령어의 겨로가 값을 사용하는 명령어들의 종속 관계를 해결해야 한다. 예를 들어 A = 2 + 3을 게산한다고 하면 2 + 3을 수행한 후 이를 A에 store해줘야 한다.

명령어 삭제 예제에서는 타겟 어플리케이션 내의 ADD 명령어를 SUB 명령어로 바꾸는 과정을 수행할 것이며 이를 위해서는 ADD 명령어의 피연산자로 SUB 계산을 수행한 후 ADD 명령어의 결과 값이 사용되는 부분을 SUB 명령어의 결과 값을 사용하도록 수정 후 ADD 명령어를 지우는 과정을 거친다.

예제 1

기존의 예제 코드에서 TraverseModule 함수를 아래와 같이 수정하여 ADD 명령어 대신에 SUB 명령을 수행하도록 한다.
ReplaceInst.cpp 코드

// Traverse Instructions in TheModule
void TraverseModule(void)
{
	for( llvm::Module::iterator ModIter = TheModule->begin(); ModIter != TheModule->end(); ++ModIter )
	{
		llvm::Function* Func = llvm::cast<llvm::Function>(ModIter);

		for( llvm::Function::iterator FuncIter = Func->begin(); FuncIter != Func->end(); ++FuncIter )
		{
			llvm::BasicBlock* BB = llvm::cast<llvm::BasicBlock>(FuncIter);
			std::vector< llvm::Instruction* > AddInsts;
			
			for( llvm::BasicBlock::iterator BBIter = BB->begin(); BBIter != BB->end(); ++BBIter )
			{
				llvm::Instruction* AddInst = llvm::cast<llvm::Instruction>(BBIter);

				if( AddInst->getOpcode() == llvm::Instruction::Add )
				{
					llvm::Instruction* SubInst = llvm::BinaryOperator::Create( 
							llvm::Instruction::Sub,	/* Opcode */
							AddInst->getOperand(0),	/* S1 */
							AddInst->getOperand(1),	/* S2 */
							"subtmp",	/* Name */
							AddInst /* BeforeInst */ );
					AddInst->replaceAllUsesWith( SubInst );

					AddInsts.push_back( AddInst );
				}
			}

			for( int i=0, Size=AddInsts.size(); i<Size; ++i ) AddInsts[i]->eraseFromParent();
		}
	}
}  

실행 결과

Test.Processed.ll 코드에서 ADD 명령어 대신에 SUB 명령어가 자리잡은 것을 확인할 수 있다.

또한 위와 같이 PLUS 연산에서 ADD 명령어가 아닌 SUB 명령어를 부르게 되어 A+B+C가 아닌 A-B-C 연산을 수행한다.

여기서 주의할 점은 ADD 명령어를 삭제 시 BBIter가 삭제할 명령어를 가리키고 있기 때문에 loop 밖에서 삭제를 진행해야 한다.

예제 2

A+B+C 연산 대신에 A*B-C연산을 수행하고자 한다.
ReplaceInst2.cpp 코드

// Traverse Instructions in TheModule
void TraverseModule(void)
{
	for( llvm::Module::iterator ModIter = TheModule->begin(); ModIter != TheModule->end(); ++ModIter )
	{
		llvm::Function* Func = llvm::cast<llvm::Function>(ModIter);

		for( llvm::Function::iterator FuncIter = Func->begin(); FuncIter != Func->end(); ++FuncIter )
		{
			llvm::BasicBlock* BB = llvm::cast<llvm::BasicBlock>(FuncIter);
			std::vector< llvm::Instruction* > AddInsts;
			
			for( llvm::BasicBlock::iterator BBIter = BB->begin(); BBIter != BB->end(); ++BBIter )
			{
				llvm::Instruction* AddInst1 = llvm::cast<llvm::Instruction>(BBIter);
				BBIter++;
				BBIter++;
				BBIter++;
				llvm::Instruction* AddInst2 = llvm::cast<llvm::Instruction>(BBIter);

				if( AddInst1->getOpcode() == llvm::Instruction::Add 
					&& AddInst2->getOpcode() == llvm::Instruction::Add)
				{
					llvm::Instruction* MulInst = llvm::BinaryOperator::Create(
							llvm::Instruction::Mul, /* Opcode */
							AddInst1->getOperand(0), /* S1 */
							AddInst1->getOperand(1),	/* S2 */
							"multmp",	/* Name */
							AddInst1 /* BeforeInst */ );
					AddInst1->replaceAllUsesWith( MulInst );
					
					AddInsts.push_back( AddInst1 );

					llvm::Instruction* SubInst = llvm::BinaryOperator::Create( 
							llvm::Instruction::Sub,	/* Opcode */
							AddInst2->getOperand(0),	/* S1 */
							AddInst2->getOperand(1),	/* S2 */
							"subtmp",	/* Name */
							AddInst2 /* BeforeInst */ );
					AddInst2->replaceAllUsesWith( SubInst );

					AddInsts.push_back( AddInst2 );
				}

				BBIter--;
				BBIter--;
				BBIter--;
			}

			for( int i=0, Size=AddInsts.size(); i<Size; ++i ) AddInsts[i]->eraseFromParent();
		}
	}
}  

위와 같이 코드를 수정한 것은 Test.ll을 확인하니 A+B+C 패턴이 나오기 위해 add 연산 실행 후 3 사이클 이후에 add 연산을 실행하기 때문이다.
Test.ll

변경 후 TestProcessed.ll

실행 결과

위와 같이 의도한대로 동작하는 것을 확인할 수 있다.