LLVM Optimization (6)

실습 5

[실습 5]에서는 IR 레벨에서 명령어의 위치를 변경하고 메모리 명령어의 종속성 관계에 대해 파악한다. 일반적으로 산술 연산 명령어와는 다르게 메모리 명령어(load/store)의 종속 관계는 컴파일러 입장에서 알기 어렵다. 예를 들어 X주소에서 값을 읽는 명령어 load와 Y주소에서 값을 쓰는 명령어 store가 있다고 할 떄, X와 Y의 값이 같거나 다르다는 것을 보장하지 않는 이상 두 명령어간 순서는 종속관계가 아니라도 쉽게 바뀔 수 없다.

[실습 5]에서는 store 명령어를 BasicBlock의 가장 마지막 부분으로 옮겨주고 차이를 확인하고자 한다.

예제

순회를 하면서 프로그램 내의 store 명령어를 식별하도록 한다. 이후 BasicBlock 내의 마지막 명령어를 탐색하고 해당 위치로 store 명령어를 옮겨준다.

MoveInst.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: ./MoveInst <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);

			std::vector< llvm::StoreInst* > StoreInsts;
			llvm::Instruction* LastInst;
			
			for( llvm::BasicBlock::iterator BBIter = BB->begin(); BBIter != BB->end(); ++BBIter )
			{
				llvm::Instruction* Inst = llvm::cast<llvm::Instruction>(BBIter);

				//if( Inst->getOpcode() == llvm::Instruction::Store )
				if( llvm::isa< llvm::StoreInst >( Inst ) )
				{
					StoreInsts.push_back( llvm::cast< llvm::StoreInst >( Inst ) );
				}

				LastInst = Inst;
			}

			for( int i=0, Size=StoreInsts.size(); i<Size; ++i )
			{
				StoreInsts[i]->moveBefore(LastInst);
			}
		}
	}
}

// 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 <stdio.h>

int main(void)
{
	int a = 3;
	int b = 4;

	a = a + 5;
	b = a + b;

	printf( "a(3+5) = %d, b(a+4) = %d\n", a, b );

	return 0;
}

실행 결과

clang++ MoveInst.cpp -o MoveInst $(llvm-config --cxxflags --ldflags --system-libs --libs mcjit irreader)  
clang -emit-llvm -S Test.c -o Test.ll  
./MoveInst ./Test.ll ./Test.Processed.ll  
vimdiff ./Test.ll ./Test.Processed.ll  
  
clang Test.ll -o Test
clang Test.Processed.ll -o Test.Processed  
./Test
./Test.Processed  

Test.ll과 TestProcessed.ll을 비교했을 떄 store 명령어의 위치가 달라진 것을 확인할 수 있었다.

이에 따라 실제 프로그램 동작 시 연산결과의 차이가 발생한 것을 확인할 수 있다.