llvm 사용법

왜 llvm::makeunique?

make_unique C++14     ，C++11   make_shared

순환 최적화

순환 불변식 계산을 순환 외부로 이동

추가 귀납 변수 제거

불변량 코드를 외부로 이동하는 반복 프로세스:

	FOR index := 1 TO 10000 DO	          t := y * z
	BEGIN				                  FOR index := 1 TO 10000 DO
		x := y * z ;		              BEGIN
		j := index * 3 ;          -->		  x := t
	END					                      j := index * 3
	.				                      END
--------------------- 
  ：https://blog.csdn.net/qq_29674357/article/details/78564033 

마지막 호출 최적화

개념: 어떤 함수의 마지막 단계는 다른 함수를 호출하는 것이다.

function f(x){
  return g(x);
}

다음 두 가지 상황은 모두 미호출에 속하지 않는다.

//    ：    g  ，      ，        ，        
function f(x){
  let y = g(x);
  return y;   
}

//    ：          ，       。
function f(x){
  return g(x) + 1;		
}

꼬리 호출은 함수의 마지막 작업이기 때문에 외부 함수의 호출 기록을 보존할 필요가 없다. 호출 위치, 내부 변수 등 정보가 다시 사용되지 않기 때문에 내부 함수의 호출 기록을 직접 사용하여 외부 함수의 호출 기록을 대체하면 된다.

꼬리 귀속의 경우 귀속은 메모리를 많이 소모한다. 수천 수백 개의 호출 기록을 동시에 저장해야 하기 때문에'창고 넘침'오류가 발생하기 쉽다(stack overflow).그러나 꼬리 귀속에 있어 호출 기록이 하나만 존재하기 때문에 '창고 넘침' 오류가 영원히 발생하지 않습니다.피보나치 수열을 구하는 두 단락의 함수를 비교한다:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

SSA

https://blog.csdn.net/qq_29674357/article/details/78731713

SSA를 사용해야 하는 이유첫째, 많은 번역 최적화 방법의 과정을 간소화할 수 있다.둘째, 많은 컴파일 최적화 방법에 있어 더욱 좋은 최적화 결과를 얻을 수 있다.https://wiki.aalto.fi/display/t1065450/LLVM+ SSA 소개 llvm IR 예

LLVM Type

@ and % in LLVM Global identifiers (functions, global variables) begin with the ‘@’ character. Local identifiers (register names, types) begin with the ‘%’ character.

Function Type The function type can be thought of as a function signature. It consists of a return type and a list of formal parameter types. The return type of a function type is a void type or first class type — except for label and metadata types. Syntax: () Examples:

i32 (i32)	function taking an i32, returning an i32
float (i16, i32 *) *	Pointer to a function that takes an i16 and a pointer to i32, returning float.
i32 (i8*, ...)	A vararg function that takes at least one pointer to i8 (char in C), which returns an integer. This is the signature for printf in LLVM.
{i32, i32} (i32)	A function taking an i32, returning a structure containing two i32 values

Integer Type The integer type is a very simple type that simply specifies an arbitrary bit width for the integer type desired. Any bit width from 1 bit to 223-1 (about 8 million) can be specified. Syntax: iN

i1	a single-bit integer.
i32	a 32-bit integer.
i1942652	a really big integer of over 1 million bits.

Floating-Point Types

Type	Description
half	16-bit floating-point value
float	32-bit floating-point value
double	64-bit floating-point value
fp128	128-bit floating-point value (112-bit mantissa)
x86_fp80	80-bit floating-point value (X87)
ppc_fp128	128-bit floating-point value (two 64-bits)

The binary format of half, float, double, and fp128 correspond to the IEEE-754-2008 specifications for binary16, binary32, binary64, and binary128 respectively.

Array Type Syntax: [ x ] The number of elements is a constant integer value; elementtype may be any type with a size.

Examples:

[40 x i32]	Array of 40 32-bit integer values.
[41 x i32]	Array of 41 32-bit integer values.
[4 x i8]	Array of 4 8-bit integer values.
Here are some examples of multidimensional arrays:

[3 x [4 x i32]]	3x4 array of 32-bit integer values.
[12 x [10 x float]]	12x10 array of single precision floating-point values.
[2 x [3 x [4 x i16]]]	2x3x4 array of 16-bit integer values.

Vector Type

Syntax: < x >

<4 x i32>	Vector of 4 32-bit integer values.
<8 x float>	Vector of 8 32-bit floating-point values.
<2 x i64>	Vector of 2 64-bit integer values.
<4 x i64*>	Vector of 4 pointers to 64-bit integer values.

Poison Value는 넘침이 불확실한 행동을 가져올 수 있음을 감안하면%add = add nsw i32 %x, 1https://stackoverflow.com/questions/34190997/the-poison-value-and-undefined-value-in-llvm

LLVM IR

alloca https://stackoverflow.com/questions/45507294/llvm-ir-alloca-instruction The alloca instruction reserves space on the stack frame of the current function. The amount of space is determined by element type size, and it respects a specified alignment. The first instruction, %a.addr = alloca i32, align 4, allocates a 4-byte stack element, which respects a 4-byte alignment. A pointer to the stack element is stored in the local identifier, %a.addr. The alloca instruction is commonly used to represent local (automatic) variables.

load & store The ‘load’ instruction is used to read from memory.

%ptr = alloca i32                               ; yields i32*:ptr
store i32 3, i32* %ptr                          ; yields void
%val = load i32, i32* %ptr                      ; yields i32:val = i32 3

getelementptr http://llvm.org/docs/GetElementPtr.html

LLVM Command

생성ll 파일 #How to make clang compile to llvm IRhttps://stackoverflow.com/questions/9148890/how-to-make-clang-compile-to-llvm-ir

clang -S -emit-llvm add.c

운행하다.ll 파일

llvm-as < printf.ll | lli

LLVM Blogs

llvm Makefile

LLVM_DIR = /usr/lib/llvm-3.9
CXXFLAGS = -g -std=c++11 -Wall -Wno-deprecated -Wno-unused -fpermissive -Wno-write-strings
CXXFLAGS += `${LLVM_DIR}/bin/llvm-config --cxxflags`
LDFLAGS += `${LLVM_DIR}/bin/llvm-config --ldflags`
LLVMLIBS = `${LLVM_DIR}/bin/llvm-config --libs`
LLVMLIBS += `${LLVM_DIR}/bin/llvm-config --system-libs`
CXX = clang++

all:
	${CXX} llvm_test.cpp ${CXXFLAGS} ${LDFLAGS} ${LLVMLIBS} -o llvm_test

llvm 링크 방식

할 수 있다.bc 파일 및.o 파일 링크 사용,.ll 파일에서 사용할 함수를 설명해야 합니다. example:

1. execute.c  main  ，     print_hello()，print_hello() runtime.c   
2.clang -c -emit-llvm execute.c	//   .ll
3.llvm-as execute.ll -o execute.bc  //.ll -> .bc
4.llc -filetype=asm execute.bc -o execute.s  // .bc->.s
3.clang -c runtime.c -o runtime.o	//           
4.clang -g execute.s runtime.o -o main.out  // .s  .o  -> .out

llvm demo

해당 CMake 파일

cmake_minimum_required(VERSION 3.15)
project(llvm_test)

set(CMAKE_CXX_STANDARD 11)
find_package(LLVM REQUIRED CONFIG)
set(LLVM_LINK_COMPONENTS
        Core
        Support)
add_executable(llvm_test main.cpp)
llvm_map_components_to_libnames(llvm_libs ${LLVM_LINK_COMPONENTS})
target_link_libraries(llvm_test ${llvm_libs})

창설 함수, 호출 함수, 연산

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include 
#include 
#include 

생성된 llvm IR:

define double @add(double %a, double %b, i32 %c) {
entry:
  ret double 0.000000e+00

label1:                                           ; No predecessors!
  ret double 1.000000e+00
  %0 = fadd double %a, %b
  %1 = fsub double %a, %0
  %2 = fmul double %a, %b
  %3 = fdiv double %a, %b
  %4 = fcmp ult double %a, %b
  %5 = uitofp i1 %4 to double
}

if-then-else

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include 
#include 
#include 

생성된 llvm ir

define double @func(double %a, double %b, double %c) {
entry:
  %ifcond = fcmp one double 0.000000e+00, %c
  br i1 %ifcond, label %then, label %else

then:                                             ; preds = %entry
  %0 = fadd double %a, %b
  br label %merge

else:                                             ; preds = %entry
  %1 = fmul double %a, %b
  br label %merge

merge:                                            ; preds = %else, %then
  %iftmp = phi double [ %0, %then ], [ %1, %else ]
}

alloca,load,store

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include 
#include 
#include 

출력 llvm ir

define void @main() {
entry:
  %a = alloca double
  %b = alloca double
  store double 1.000000e+00, double* %a
  store double 2.000000e+00, double* %b
  %0 = load double, double* %a
  %1 = load double, double* %b
  store double %0, double* %b
  store double %1, double* %a
  %c = alloca i32
  %d = alloca i32
  store i32 1, i32* %c
  store i32 1, i32* %d
  %2 = load i32, i32* %c
  %3 = load i32, i32* %d
  %4 = add i32 %2, %3
  store i32 %4, i32* %c
}

생성된 llvm ir를 파일로 출력

 std::ofstream fs("output.txt");
std::ostream& os = fs;
 llvm::raw_os_ostream llvm_os(os);  //　  #include "llvm/Support/raw_os_ostream"
TheModule->print(llvm_os, nullptr);

에 "hello wrold!"

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/Support/raw_os_ostream.h"
#include 
#include 
#include 

생성된 llvm ir, lli 명령 후 직접 실행

; ModuleID = 'llvm_test'
source_filename = "llvm_test"

@0 = private unnamed_addr constant [14 x i8] c"hello world!\0A\00"

define void @main() {
entry:
  %0 = call i32 @puts(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @0, i32 0, i32 0))
  ret void
}

declare i32 @puts(i8*)

StructType, getelementptr,bitcast(유형 A를 유형 B로 변환하고 변환하는 과정에서 원래의 데이터를 바꾸지 않으며 읽는 방식만 바꾸는 것과 같다)

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/Support/raw_os_ostream.h"
#include 
#include 
#include 

생성된 llvm ir

; ModuleID = 'llvm_test'
source_filename = "llvm_test"

%A = type { double, i32 }

define void @main() {
entry:
  %0 = alloca %A
  %1 = getelementptr %A, %A* %0, i32 1
  %2 = bitcast %A* %0 to i32*
  ret void
}

vable 만들기(정의되지 않은 형식의 포인터 만들기)

void define_vtable() {
    StructType *foo = StructType::create(TheContext, "Foo");   //       create   get，        setBody()
    StructType *vtable = StructType::create(TheContext, "vtable");
    auto *foo_ptr = foo->getPointerTo();

    std::vector fields({vtable->getPointerTo(), Type::getInt32Ty(TheContext), Type::getInt32Ty(TheContext)});
    FunctionType *foo_create_default_type = FunctionType::get(Type::getVoidTy(TheContext), {foo_ptr},
                                                              false);
    Function *foo_create_default = Function::Create(foo_create_default_type, Function::ExternalLinkage,
                                                    "Foo_Create_Default", TheModule.get());
    func_map["Foo_Create_Default"] = foo_create_default;
    for (auto &arg : foo_create_default->args())
        arg.setName("this");
    Function *func_ptr = TheModule->getFunction("Foo_Create_Default");
    BasicBlock *entry_block = BasicBlock::Create(TheContext, "entry", func_ptr);
    Builder.SetInsertPoint(entry_block);


    Builder.CreateAlloca(foo->getPointerTo());
    //foo->setBody({Type::getInt32Ty(TheContext), Type::getInt32Ty(TheContext)});
    foo->setBody(fields);
    vtable->setBody({foo_create_default_type});
    outs() << *TheModule;
}

생성된 llvm ir:

%Foo = type { %vtable*, i32, i32 }
%vtable = type { void (%Foo*) }

define void @Foo_Create_Default(%Foo* %this) {
entry:
  %0 = alloca %Foo*
}

내장된 printf 함수 사용

void print_test() {
    Function *print_func = get_printf(TheModule.get());
    FunctionType *func_type = FunctionType::get(Type::getVoidTy(TheContext), std::vector(), false);
    Function *main = Function::Create(func_type, Function::ExternalLinkage, "main", TheModule.get());
    BasicBlock *entry_block = BasicBlock::Create(TheContext, "entry", main);
    Builder.SetInsertPoint(entry_block);
    Value *print_arg = ConstantInt::get(Type::getInt32Ty(TheContext), APInt(32, 1));
    Builder.CreateCall(print_func, {Builder.CreateGlobalStringPtr("in llvm fun, value = %d
"), print_arg});
    Builder.CreateCall(print_func, {Builder.CreateGlobalStringPtr("%s
"), Builder.CreateGlobalStringPtr("hello world!")});
    outs() << *TheModule;
}

인쇄 형식의 이름입니다. primitive 형식에서 getStructName을 호출하면 오류가 발생합니다

void llvm_test1() {
    StructType *A = StructType::create(TheContext, {}, "A");
    std::vector Doubles(2, Type::getDoubleTy(TheContext));  //       
    Doubles.push_back(Type::getInt32Ty(TheContext));
    Doubles.push_back(A);
    FunctionType *FT = FunctionType::get(Type::getVoidTy(TheContext),
                                         Doubles, false);    //       ，param2   NULL
    Function *F = Function::Create(FT, Function::ExternalLinkage,
                                   "add", TheModule.get());    //     ，    add

    //     ,        
    std::vector<:string> name_vec = {"a", "b", "c", "A"};
    unsigned idx = 0;
    for (auto &arg : F->args())
        arg.setName(name_vec[idx++]);

    for (auto &arg : F->args())
        if (arg.getType() == Type::getDoubleTy(TheContext))
            std::cout << "Double" << std::endl;
        else if (arg.getType() == Type::getInt32Ty(TheContext))
            std::cout << "Int" << std::endl;
        else if (arg.getType() == Type::getInt1Ty(TheContext))
            std::cout << "Bool" << std::endl;
        else
            std::cout << std::string(arg.getType()->getStructName()) << std::endl;

    //        ，   entry，    F

    Builder.CreateRetVoid();
    outs() << *TheModule;
}

생성된 llvm ir를 파일로 출력

#include 
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/Support/raw_os_ostream.h"
#include "llvm/Support/raw_ostream.h"
#include 
#include 
#include