안녕하세요, 에너자이에서 HPC에 특화된 프로그래밍 언어 Nadya를 개발하고 있는 김재우라고 합니다.

이 글에서는 Nadya가 자체 데이터를 처리하는 데 사용하는 일반적인 언어 기능과 그 기본적인 의미론에 대해 이야기하려 합니다. 이후, 이를 MLIR에서 어떻게 모델링할 수 있는지 여러 예제와 함께 설명하겠습니다.

이 글이 Nadya의 아키텍처를 이해하고, MLIR 인프라를 활용하여 일반적인 프로그래밍을 모델링하는 방법을 알고 싶은 분들에게 도움이 되길 바랍니다.

범용 언어의 semantics 구현하기

현대 프로그래밍 언어는 데이터를 다루기 위한 여러 규칙을 가지고 있습니다. 물론, 각 언어마다 이러한 규칙이 다르지만, 일반적으로 대부분의 규칙은 유사합니다. (특히 C++, Rust와 같은 컴파일 언어의 경우 더욱 그렇습니다)

연산(Operation)

• copy (복사) : 값을 깊은 복사(또는 클론)하여 원본 값과 독립적인 새로운 값을 생성합니다. 복사된 값은 원본 값과 완전히 별개로 취급됩니다.

• move (이동) : 값의 모든 내용을 다른 값으로 이동시키며, 원본 값을 무효화합니다.*

• borrow (대여) : 다른 l-value(스택에 할당된 값)의 대여를 생성합니다. 즉, 대여된 값은 원본 값이 “소유”하게 됩니다. 일반적으로 대여된 값은 l-value의 스택 주소로 모델링됩니다.

• access (접근) : 대여된 값을 다시 접근하여 원래의 l-value를 반환합니다. 하지만 access 연산을 통해 생성된 l-value는 여전히 원본 값에서 대여된 것으로 간주됩니다. 즉, 이 값은 직접 삭제될 수 없으며, 원래 대여된 값이 삭제될 때 함께 사라집니다.

• assign (할당) : 변경 가능한 let 바인딩의 값을 새로운 값으로 교체합니다. assign 연산은 l-value에서만 수행될 수 있으며, 이는 스택 메모리에 저장된 값을 변경하는 의미를 가지기 때문입니다. 만약 let 바인딩이 변경 불가능(immutable)하면, 할당을 시도할 경우 컴파일 오류가 발생합니다.

복사 (Copy)

값을 복사하면 원본과 완전히 독립적인 새로운 instance를 생성합니다. 복사된 값은 “소유된(Owned)” 값으로 간주되므로, 자유롭게 삭제하거나 이동할 수 있으며, 아무런 제한이 없습니다.

간단한 바이트 복사로 수행할 수 있는 값은 “trivially copyable”로 간주됩니다. 그렇지 않은 경우, 해당 타입은 Copy trait을 구현해야 하며, 사용자 또는 컴파일러(내장 타입의 경우)가 전체 데이터를 복사하는 핸들러를 직접 구현해야 합니다.

let mut a = tensor((2i, 3i), 0.0f32)
let b = a // 여기서 복사 연산이 수행됨 (기본적으로 let 바인딩이 l-value를 복사)
a[(0i, 1i)] <- 10.0f // a를 수정
print(toStr(b)) // b는 수정되지 않음

이동 (Move)

deep copy를 가능한 최소화하는 것이 성능 측면에서 유리하며, 값을 참조할 수 있다면 더욱 효율적입니다. Nadya에서는 이러한 처리를 move 및 borrow semantic을 통해 수행합니다.

예를 들어, 아래 코드에서 tensor 값을 이동하면, 값 a의 내부 데이터가 b로 이동합니다. 이 과정에서 deep copy는 필요하지 않으며, shallow copy만으로 충분합니다. 따라서 nadyaCore.move 연산은 내부적으로 llvm.load 연산과 동일하지만, 이를 더 높은 추상화 수준에서 제공하기 위해 존재합니다.

let a = tensor((2i, 3i), 0.0f32)
let b = move(a)
print(toStr(a)) // 오류! (a는 무효화됨)

대여 (Borrow)

let mut a = tensor((1i, 1i), 0.0f32) // (1i, 1i) 형태의 2차원 텐서 생성
let mut b = &mut a // "let mut"은 "b가 다시 할당될 수 있음"을 의미하며, "&mut"은 b를 통해 a를 수정할 수 있음을 의미
b[(0i, 0i)] <- 10.0f32 // b를 통해 값 수정
print(toStr(a)) // tensor((1i, 1i), 10.000000f32) 출력

b와 같은 대여된 변수의 수명은 a의 수명에 종속됩니다. 즉, b는 a보다 오래 살아남을 수 없으며, b가 존재하는 동안 a는 삭제될 수 없습니다. 이러한 제한은 Nadya 컴파일러의 내부 verification 메커니즘을 통해 보장됩니다.

borrow가 LLVM IR로 컴파일될 때는 실제로 아무 연산도 수행되지 않습니다. 단순히 a의 스택 주소를 가리키는 포인터로 표현될 뿐입니다. 따라서 대여될 값(즉, owner)은 반드시 l-value여야 합니다.

예를 들어, 다음 코드는 Nadya에서 유효하지 않습니다. (Rust에서는 가능하지만, 내부적으로 l-value를 생성합니다. 반면 Nadya에서는 명시적으로 오류로 처리됩니다.)

let mut a = &10 // 잘못된 코드!

접근 (Access)

let mut a = tensor((1i, 1i), 0.0f32) // (1i, 1i) 형태의 2차원 텐서 생성
let mut b = &mut a // a를 대여함
let accessed = @b // '@' 연산자를 사용하여 대여된 값에 접근

access 연산은 대여된 값을 다시 접근하여 원본 타입을 반환합니다. 이를 포인터를 통해 값을 접근하는 것과 유사하게 생각할 수 있습니다. 그러나 Nadya의 수명 분석 알고리즘은 접근된 값을 여전히 원본 값의 종속값으로 간주합니다.

위 예제에서 accessed의 수명은 여전히 a에 종속됩니다. 즉, a가 삭제되기 전에 accessed가 먼저 삭제되어야 합니다.

할당 (Assign)

let mut a = 10
a <- 20 // a의 스택 메모리에 저장된 값을 20으로 교체

let mut tensorA = tensor((2i, 3i), 0) // i32 타입의 텐서 생성
tensorA[(0i, 1i)] <- 1 // 부분 할당 수행 (스택 할당된 값의 일부를 교체하는 것과 유사)

assign 연산은 스택 메모리에 저장된 값을 새로운 값으로 교체합니다. let mut 키워드는 해당 변수의 스택 메모리가 완전히 또는 부분적으로 교체될 수 있음을 의미합니다. (&mut과는 다른 점에 유의할 것.)

이와 같은 의미론적 개념을 활용하여 Nadya에서는 효율적인 데이터 관리와 메모리 안전성을 보장할 수 있습니다.

MLIR을 이용해 범용 언어 구현하기

Nadya는 백엔드 기술로서 MLIR을 사용하고 있는데요. MLIR은 서로 다른 추상화 수준에서 정의된 IR(Intermediate Representation)을 통해 복잡한 연산을 추상화할 수 있는 강력한 컴파일러 인프라로, 프로그래밍 언어를 개발할 때 매우 유용한 기반을 제공합니다. 또한 다양한 기본 IR(“Dialect”)을 구현하여 여러 추상화 수준에서 최적화를 수행할 수 있다는 것 또한 큰 장점입니다.

MLIR 인프라를 활용하면 범용(general-purpose) 프로그래밍 언어를 구현하는 것도 가능하지만, MLIR에는 범용 프로그래밍 언어를 직접 모델링하기 위한 Default IR들에 대한 지원이 다소 미흡하다는 단점이 있습니다. 실제로 범용 프로그래밍 언어를 구현하기 위해서는 아래와 같은 개념을 명확히 정의해야 하는데요.

• 어떤 값이 스택에 저장되고, 어떤 값은 그렇지 않은가?

• 메모리에서 값들은 어떻게 서로 연관되어 있는가?

• 데이터 타입을 올바르게 복사하고 삭제하는 방법은 무엇인가?

• (Nadya의 경우) 이러한 고수준(Higher-level) concept을 어떻게 최적화에 활용할 수 있는가?

이미 한 차례 말씀드렸듯이, MLIR에는 이러한 개념을 직접 모델링할 수 있는 기능이 부족했기 때문에 저희는 Nadya를 완성도 높은 범용 프로그래밍 언어로 만들기 위해 해당 개념들을 직접 정의해야 했는데요. 이번 게시물에서는 전 세계의 다른 잠재적 언어 개발자들을 위해 저희가 그 과정에서 마주한 문제들과 해결 경험을 공유하려고 합니다.

Separating l-values and r-values

처음으로 떠올린 아이디어는 l-value와 r-value를 분리하는 것이었는데요. 아래 Nadya 코드를 통해 간단히 설명드리도록 하겠습니다.

// function receiving single 32bit integer, and returning 32bit integer
fun add(arg : i32) -> i32 {
 let a = 10
 let b = 20
 a + b + arg
}

개념적으로 a와 b는 스택 메모리에 올라가게 되고, 10과 20은 임시 상수로 취급되는데요. 여기서 10과 20 같은 값들은 r-value, a와 b를 l-value로 볼 수 있습니다.

r-value와 l-value의 가장 큰 차이는 **수명(lifetime)**입니다.

• r-value는 즉시 사용한 뒤 파괴되는 값

• l-value는 scope가 끝날 때까지(위 예시에서는 add 함수가 종료될 때까지) 생존하여, 동일 scope 내에서 추후에도 사용 가능

즉, 10과 20은 스택에 올라간 뒤 곧바로 삭제되어야 하며(지금 단계에서는 최적화에 대해서는 고려하지 않도록 하겠습니다), 위 예시의 함수를 실행하면 프로그램 스택은 대략적으로 아래와 같은 형태를 띱니다.

// stack-bottom
| arg : i32 // argument. It's pushed on the stack since it's conceptually an l-value since it's name is assigned
| 10 : i32 // "a" points to this value
| 20 : i32 // "b" points to this value
// stack-top (stack grows downwards)

그리고 추후에 a + b + arg 연산을 수행할 때는 컴파일러가 arg, a, b를 모두 r-value로 로드하여 덧셈을 수행하게 됩니다.

사실 LLVM IR에도 llvm.alloca (스택 메모리를 할당), llvm.store (스택에 값을 저장), llvm.load (스택에서 값을 읽어옴) 등의 명령어가 있기 때문에 위와 같은 간단한 예제는 LLVM IR을 직접 사용해도 쉽게 모델링할 수 있습니다.

이러한 종류의 타입을 **“trivially copyable”**이라고 하는데요. Trivially copyable 타입인 경우 **단순한 바이트 단위 복사(메모리 복사)**만으로도 값을 완전히 복사할 수 있으며, shallow copy와 deep copy에 아무런 차이가 없습니다.

(Nadya에서는 shallow copy를 move, deep copy를 copy라고 부릅니다)

Why do we need special modeling over low-level llvm IR?

그러나 대부분의 범용 프로그래밍 언어는 문자열(Strings), 사용자 정의 구조체, list, array 등 훨씬 복잡한 타입들을 사용하는데요.

(예를 들어, Nadya에서는 타입이 직접 copy 및 drop 연산을 구현할 수도 있습니다)

아래 예시는 Nadya로 작성된 간단한 DataWrapper 코드입니다.

// filename : example.ndy
type DataWrapper with Copy | Drop
 public
  data : tensor<f32, 2>
  name : string

impl DataWrapper 
 trait Copy
  // Automtically called when value is copied
  fun copy(&self : Self) -> Self {
   print("Copy called on " + self.name)
   let new_tensor = self.data // deep-copy the tensor (In nadya, deep-copy is default behavior)
   DataWrapper(new_tensor, self.name)
  }
  
 trait Drop 
  // Automatically called when value is deleted
  fun drop(mut& self : Self) -> () {
   print("Drop called on " + self.name)
   // data is automatically deallocated by the wrapper after "drop"
  }

만약 DataWrapper 를 C++로 구현한다면, 아래와 같은 형태가 될 것입니다.

typedef struct Tensor{
 void* data;
 std::size_t rank;
 std::size_t* shape;
};

typedef struct String{
 char* data;
 std::size_t length;
}

struct DataWrapper{
 Tensor data;
 String name;
};

위 예시에서, shallow copy(move)와 deep copy(copy)는 전혀 다르게 동작하게 됩니다. deep copy가 데이터 전체를 복제하는 반면, shallow copy는 ptr 값만 복제하게 되는데요. 만약 이러한 구조체의 복사(copy) 및 소멸(drop) semantic을 직접 LLVM 코드로 작성해야 한다면, 굉장히 복잡해질 가능성이 높습니다.

따라서, 저희는 nadyaCore dialect를 통해 LLVM으로 모델링하기 어려운 복잡한 타입들도 지원할 수 있는 모델을 자체적으로 개발했는데요.

nadyaCore dialect는 다음과 같은 기능들을 지원합니다.

• push 연산: r-value를 스택에 올려 l-value를 생성

• copy 연산: 임의의 타입에 대한 deep copy 수행

• drop 연산: 임의의 타입을 소멸

• move 연산: shallow copy 수행 (원본 값은 이동 후 무효화됨)

• borrow 연산: 다른 l-value를 참조하는 r-value를 생성

예를 들어, 아래 Nadya 코드를 컴파일한다고 가정해봅시다.

// filename : example.ndy
attr[Extern]
fun nadya_main() -> i32 {
 // Define tensors
 let left = DataWrapper (tensor((2i, 3i), 1.0f32), "left")
 let right = DataWrapper (tensor((2i, 3i), 2.0f32), "right")
 
 // add two tensors. left and right have to be copied here since left, right is used later
 let added = left.data + right.data
 
 // print left, right and computation result
 print("left : " + toStr(left.data))
 print("right : " + toStr(right.data))
 print("result : " + toStr(added))
 
 0 // return code
 // Before exiting, left, right and added must be destructed (inserted automatically by compiler).
}

해당 코드를 ndc example.ndy -o example 명령어로 실행하면(최적화 없이 컴파일) 다음과 같은 결과물이 생성됩니다.

Copy called on left
Drop called on left
Copy called on right
Drop called on right
Copy called on left
Drop called on left
Drop called on left
left : tensor<f32, 2>((2i, 3i, ), 1.000000f32, 1.000000f32, 1.000000f32, 1.000000f32, 1.000000f32, 1.000000f32)
Copy called on right
Drop called on right
Drop called on right
right : tensor<f32, 2>((2i, 3i, ), 2.000000f32, 2.000000f32, 2.000000f32, 2.000000f32, 2.000000f32, 2.000000f32)
result : tensor<f32, 2>((2i, 3i, ), 3.000000f32, 3.000000f32, 3.000000f32, 3.000000f32, 3.000000f32, 3.000000f32)

아래 결과물은 AST를 추상화한 MLIR output입니다.

...
%left_pushed = nadyaCore.push %left // push value to the stack
%right_pushed = nadyaCore.push %right // push value to the stack

%left_copied = nadyaCore.copy %left_pushed // copy the value
%right_copied = nadyaCore.copy %right_copied // copy the value
%added = nadyaCore.add %left_copied, %right_copied // add two values together
...
// Drop operations are inserted automatically by lifetime analysis (Data is destructed before scope ends)
nadyaCore.drop %left_copied
nadyaCore.drop %right_copied
nadyaCore.drop %left // Calls drop handler we defined above, and completely frees internal memory
nadyaCore.drop %right
nadyaCore.drop %added

결국 Nadya에서 l-value 와 r-value 를 구분하는 목적은 데이터의 수명 및 의존성을 효과적으로 관리하는 것에 있는데요. 이러한 아이디어가 적용된 Nadya 코드 또한 MLIR로 손쉽게 추상화할 수 있습니다.

범용 프로그래밍 언어를 모델링하는 것은 쉽지 않지만, MLIR은 강력한 인프라를 제공합니다

앞서 설명했듯이, MLIR은 일반적인 프로그래밍 기능을 추상화하는 데 사용할 수 있으며, Nadya 프로그래밍 언어의 의미론을 간단하게 표현할 수 있습니다. MLIR의 내장 분석 도구와 커스터마이징 가능한 패스 파이프라인을 활용하면, 프로그래밍 언어를 구축하는 데 강력한 인프라를 제공합니다.

개인적으로, 사람들이 MLIR을 AI 워크로드 최적화뿐만 아니라 보다 일반적인 목적으로 확장하는 것에 더 많은 관심을 가진다면, 이 프레임워크의 잠재력이 훨씬 더 커질 수 있다고 생각합니다.