NI LabVIEW 컴파일러: 내부 기술

개요

평범한 프로그래밍 언어를 위한 컴파일러의 디자인도 복합적인 특성을 띄는 경우가 많습니다. 컴파일러 이론은 전문 소프트웨어 엔지니어들 조차도 특수 지식으로 분류하는 고난이도 지식입니다. NI LabVIEW는 다중 패러다임 언어로써 데이터흐름, 객체 지향, 이벤트 구동 프로그래밍과 같은 광범위한 개념을 통합하였습니다. 또한 LabVIEW는 다중 OS (Windows, Linux, Mac), 다중 칩셋 (PowerPC, Intel) 심지어 임베디드 디바이스 및 FPGA와 같은 타겟에서 사용되는 것이 기존의 PC 아키텍처와 큰 차이입니다. 이미 예상할 수 있듯이 LabVIEW 컴파일러는 문서로 설명된 범위를 훨씬 능가하는 고급 시스템입니다.

내용

본 문서에서는 LabVIEW 컴파일러를 소개하며, 1986년 LabVIEW 1.0을 시작으로 LabVIEW가 어떤 발전을 거쳤는지 알아보고, 현재의 사용에 대해 간략하게 살펴봅니다. 또한 최신 컴파일러 혁신에 대해 살펴보고 이같은 새로운 기능이 LabVIEW 아키텍처와 사용자 모두에 어떤 영향을 미치는지 살펴봅니다.

컴파일 (Compilation) vs 인터프리테이션 (Interpretation)

LabVIEW는 컴파일 언어이므로 일반적인 G 개발 동안 컴파일 과정이 없습니다. 따라서 VI에 변경을 적용한 후에 실행 버튼을 클릭하여 실행하기만 하면 됩니다. 컴파일은 사용자가 작성하는 G 코드가 원시 기계 코드로 전환된 후 호스트 컴퓨터가 직접 실행한다는 의미입니다. 또 다른 방법인 인터프리테이션 (interpretation) 방식 하에서는 프로그램이 컴퓨터에서 직접 수행되지 않고 다른 소프트웨어 프로그램 (인터프리터)에 의해 간접 실행됩니다.

LabVIEW 언어는 컴파일 또는 인터프리테이션이 필요하지 않습니다. 그러나 LabVIEW의 첫 번째 버전은 인터프리터를 사용하였습니다. 그 후 버전에서는 VI 런타임 성능 향상을 위해 컴파일러가 인터프리터를 대신하게 되었습니다. VI 런타임 성능 향상은 컴파일러와 인터프리터를 구별짓는 요소입니다. 인터프리터는 런타임 성능이 느린 대신 작성이나 유지가 편리한 반면, 컴파일러는 실행이 복합적이지만 실행 시간이 보다 빠릅니다. LabVIEW 컴파일러 사용의 주요 장점은 컴파일러에 적용된 개선사항을 모든 VI에서 변경없이 확인 가능하다는 점입니다. 사실상, LabVIEW 2010 버전에서는 VI 실행 시간을 가속화하기 위해 컴파일러 내의 최적화에 주안점을 두었습니다.

진화 과정을 통해 살펴보는 LabVIEW 컴파일러

현재 사용되는 컴파일러를 심도있게 살펴보기 전에 20여년 전 초기 형태의 컴파일러 개발을 짚어보는 것은 의미가 있습니다. type propagation, clumping, inplaceness와 같은 일부 알고리즘은 LabVIEW 컴파일러에서 자세히 설명됩니다.

LabVIEW 1.0은 1986년 제작되었습니다. 앞서 설명했듯이 LabVIEW 최초 버전에서는 인터프리터를 사용하였고 Motorola 68000만을 타겟팅하였습니다. LabVIEW 언어는 그 당시에는 훨씬 간단하였으므로 컴파일러 (당시의 인터프리터를 뜻함)에 대한 요구사항도 적었습니다. 예를 들어, 다형성이 없었고 숫자 유형만이 확장형 부동소수였습니다. LabVIEW 1.1에서는 inplaceness 알고리즘 즉 “inplacer”가 도입되었습니다. 본 알고리즘은 실행 중 사용자가 재사용할 수 있는 데이터 할당을 파악하므로, 불필요한 데이터 복사를 방지하여 실행 성능이 대폭 증대됩니다.

LabVIEW 2.0에서 인터프리터는 실제의 컴파일러로 대체되었습니다. 여전히 Motorola 68000만을 타겟팅하였지만, LabVIEW는 원시 기계 코드를 생성할 수 있었습니다. 또한 type propagation 알고리즘이 Version 2.0에 추가되었으며, 여러 기능 중 LabVIEW 언어에서 구문 확인 및 type resolution 처리 기능이 있습니다. LabVIEW 2.0의 또 다른 눈에 띄는 혁신은 clumper입니다. clumping 알고리즘은 LabVIEW 다이어그램의 병렬성을 파악하고, 노드를 병렬로 실행되는 “clumps”로 그룹짓습니다. type propagation, inplaceness, clumping 알고리즘은 LabVIEW 컴파일러의 중요한 부분을 차지하며, 시간이 지남에 따라 여러가지 개선이 있어왔습니다. LabVIEW 2.5의 새로운 컴파일러 인프라스트럭처에는 여러 개의 백엔드, 특히 Intel x86 및 Sparc에 대한 지원이 추가되었습니다. LabVIEW 2.5에는 또한 linker가 도입되었습니다. linker는 VI가 재컴파일되어야 할 시기를 추적하기 위해 의존성을 관리합니다.

새로운 두 가지 백엔드인 PowerPC와 HP PA-RISC는 상수 계산과 함께 LabVIEW 3.1에 추가되었습니다. LabVIEW 5.0 및 6.0에서는 코드 생성기가 개선되었고 여러 개의 백엔드에 대한 일반 인터페이스인 GenAPI가 추가되었습니다. GenAPI는 리얼타임 개발에서 중요한 크로스 컴파일을 수행합니다. 리얼타임 개발자들은 일반적으로 호스트 PC에서 VI를 작성하지만, VI를 리얼타임 타겟에 배포 (VI를 컴파일)합니다. 또한, 루프 불변값 (loop-invariant) 코드 모션의 일부 형태가 포함되었습니다. 마지막으로, 여러 개의 스레드를 지원하기 위해 LabVIEW 멀티태스킹 실행 시스템이 확장되었습니다.

LabVIEW 8.0은 레지스터 할당 알고리즘을 추가하기 위해 버전 5.0에서 도입된 GenAPI 인프라스트럭처에 기반하여 구축되었습니다. GenAPI가 도입되기 이전에는 각 노드에 대해 생성된 코드에 레지스터가 하드코딩되었습니다. 또한, 제한된 형태의 완료되지 않은 코드 (unreachable code) 및 데드 코드 (dead code) 제거 기능이 소개되었습니다. LabVIEW 2009는 64-비트 LabVIEW와 DFIR (Dataflow Intermediate Representation)를 제공합니다. DFIR는 루프 불변값 (loop-invariant) 코드 모션, 상수 계산, 데드 코드 (dead code) 제거, 완료되지 않은 (unreachable code) 코드 제거의 더욱 고급 형태를 구축하기 위해 즉시 사용되었습니다. 병렬 For 루프와 같은 2009에 도입된 새로운 언어 기능은 DFIR에서 구축되었습니다.

마지막으로, LabVIEW 2010의 DFIR은 algebraic reassociation, CSE (common subexpression elimination), 루프 풀기 (loop unrolling), subVI 인라인과 같은 새로운 컴파일러 최적화를 제공합니다. 또한 본 버전은 LLVM (Low-Level Virtual Machine)을 LabVIEW 컴파일러 체인에 통합하였습니다. LLVM은 업계에서 널리 사용되고 있는 개방 소스 컴파일러 인프라스트럭처입니다. LLVM으로 지시 스케쥴링 (instruction scheduling), 루프 스위치 전환 (loop unswitching), 지시 병합 (instruction combining), 조건 전파 (conditional propagation) 및 한 단계 고급의 레지스터 할당기 등의 새로운 최적화가 추가되었습니다.

현재 사용되는 컴파일 과정

LabVIEW 컴파일러의 발전 과정을 간략히 이해하였으므로 이제는 현대식 LabVIEW에서 컴파일하는 과정을 살펴보겠습니다. 첫째, 다양한 컴파일 단계 상위 레벨의 개요를 살펴본 후 각 부분을 더욱 자세하게 살펴봅니다.

VI 컴파일의 첫 번째 단계는 type propagation 알고리즘입니다. 이 단계는 터미널 변경에 따라 함축된 타입이 변경되며, 구문 오류를 감지합니다. G 프로그래밍 언어에서의 모든 구문 오류는 type propagation 알고리즘 동안 감지됩니다. 알고리즘이 VI가 유효하다고 판단할 경우, 컴파일은 계속됩니다.

type propagation 이후, VI는 우선 블록 다이어그램 편집기에서 사용된 모델에서 컴파일러에서 사용된 DFIR로 전환됩니다. 일단 DFIR로 변환되면, 컴파일러는 DFIR 그래프에서 여러 변환을 실행하여 분석, 최적화 및 코드 생성을 준비합니다. 여러 컴파일러 최적화 (예, inplacer, clumper)는 변환으로 실행되며 이 단계에서 실행됩니다.

DFIR 그래프가 최적화되고 단순화된 후, LLVM IR (intermediate representation)로 전환됩니다. 일련의 LLVM 패스는 IR에서 실행되어 최적화된 후 기계 코드로 변환됩니다.

Type Propagation

이전에 언급된 바와 같이 type propagation 알고리즘은 타입을 변형하고 프로그래밍 오류를 감지합니다. 본 알고리즘은 다음과 같은 기능을 수행합니다.

  • 터미널 타입에 따라 함축된 타입 변경
  • subVI 호출을 변경하고 유효성 파악
  • 와이어 방향 계산
  • VI에서 주기 확인
  • 구문 오류 감지 및 보고

본 알고리즘은 사용자가 VI에 변경을 적용한 후에 실행되어 VI가 여전히 유효한지를 확인합니다. 따라서 본 단계가 "컴파일"의 일부인지 여부에는 논란의 여지가 있습니다. 그러나 본 단계는 기존 컴파일러의 어휘 분석, 분석 또는 의미 분석에 해당하는 LabVIEW 컴파일 체인의 단계입니다.

타입에 따라 변경된 터미널의 간단한 예로는 LabVIEW의 더하기 프리미티브가 있습니다. 두 개의 정수를 더하면 결과는 정수이지만, 두 개의 부동소수 숫자를 더하면 결과는 부동소수 숫자입니다. 유사한 패턴은 배열과 클러스터 같은 복합 타입에서도 볼 수 있습니다. 시프트 레지스터와 같이 더욱 복합적인 타입 규칙을 가진 언어도 있습니다. 더하기 프리미티브의 경우, 출력 타입은 입력 타입에서 결정되며, 타입은 다이어그램을 통해 "전파"되므로, 알고리즘의 이름이 Type Propagation라고 붙여졌습니다.

더하기 프리미티브 예제는 또한 type propagation 알고리즘의 구문 확인 기능을 설명합니다. 정수와 문자열을 더하기 프리미티브에 와이어로 연결한다고 가정한다면, 어떻게 될까요? 이 경우, 두 값을 추가하는 것이 의미가 없으므로 type propagation 알고리즘은 이것을 오류라고 보고하며, VI를 “불량”이라고 표시할 것입니다. 따라서, 실행 화살표가 깨진 상태로 표시됩니다.

IR (Intermediate Representations)의 정의 및 필요한 이유

type propagation을 통해 VI가 유효한지 여부가 결정되면, 컴파일은 계속 진행되며 VI는 DFIR로 전환됩니다. DFIR를 자세히 살펴보기 전에 일반적인 IR (intermediate representations)을 살펴보겠습니다.

IR은 컴파일이 다양한 단계를 거치는 동안 조작된 사용자 프로그램을 표현한 것입니다. IR의 개념은 현대식 컴파일러에서 일반적이며 모든 프로그래밍 언어에 적용됩니다.

다음의 예제를 살펴보십시오. 현재, 보편적으로 사용되는 다양한 종류의 IR이 있습니다. 두 개의 일반적인 예제로는 추상 구문 트리 (AST)와 3-주소 코드가 있습니다.

ast.JPG

t0 <- y

t1 <- 3

t2 <- t0 * t1

t3 <- x

t4 <- t3 + t2

그림 1. AST IR 예제 표 1. 3-주소 코드 IR 예제

그림 1은 “x + y * 3”의 AST식 표현이며 표 1은 3-주소 코드식 표현입니다.

이 두 가지의 명백한 차이라면 AST가 더욱 레벨이 높다는 점입니다. 이는 타겟 표현 (기계 코드) 보다 프로그램 (C)의 소스 표현에 더욱 가깝습니다. 반대로 3-주소 코드는 로우 레벨이며 어셈블리와 유사합니다.

하이 레벨과 로우 레벨의 표현은 모두 각각의 장점이 있습니다. 예를 들어, 의존성 분석과 같은 분석은 3-주소 코드와 같은 로우 레벨보다 AST와 같은 하이 레벨에서 수행하는 것이 더욱 수월할 것입니다. 레지스터 할당 또는 명령어 스케쥴링과 같은 최적화는 3-주소 코드와 같은 로우 레벨에서 수행됩니다.

각 IR에는 각기 다른 장단점이 있으므로 여러 컴파일러는 (LabVIEW 포함) 여러 개의 IR을 사용합니다. LabVIEW의 경우, DFIR는 하이 레벨 IR로 사용되는 반면 LLVM IR은 로우 레벨 IR로 사용됩니다.

DFIR

LabVIEW에서 하이 레벨의 표현인 DFIR은 계층적이며 그래프 기반이며 G 코드와 유사합니다. G와 마찬가지로 DFIR은 다양한 노드로 구성되며 각각에는 터미널이 있습니다. 터미널은 다른 터미널에 연결됩니다. 루프와 같은 일부 노드에는 다이어그램이 있고 여기에는 또한 다른 노드가 포함됩니다.

g.PNG

before.PNG

그림 2. LabVIEW G 코드 및 해당 DFIR 그래프

그림 2는 DFIR 표현과 간단한 VI를 그래프로 나타냅니다. VI를 위한 DFIR 그래프가 처음 생성되면, G 코드가 직접 전환되며, DFIR 그래프의 노드는 일반적으로 G 코드의 노드에 대해 일대일 대응됩니다. 컴파일이 진행되면 DFIR 노드는 이동 또는 나뉘어지거나 새로운 DFIR 노드가 삽입될 수도 있습니다. DFIR의 주요 장점은 G 코드에서의 병렬성과 같은 특징을 보유한다는 점입니다. 반대로 3-주소 코드에 표현된 병렬성은 식별하기 훨씬 어렵습니다.

DFIR은 LabVIEW 컴파일러에 두 가지 중요한 이점을 제공합니다. 첫째, DFIR은 VI의 컴파일러 표현에서 편집기를 분리합니다. 두 번째로, DFIR은 컴파일러에 대한 일반 허브로 동작하며, 여기에는 여러 개의 프런트엔드와 백엔드가 있습니다. 각각의 장점에 대해 더욱 자세하게 살펴보십시오.

DFIR 그래프는 컴파일러 표현에서 편집기를 분리합니다.

DFIR가 도입되기 전 LabVIEW에는 편집기와 컴파일러에 의해 공유되는 VI에 대한 단일 표현 방식이 있었습니다. 이 때문에 컴파일러는 컴파일 과정 동안 표현을 변경할 수 없었으므로, 컴파일러 최적화 수행이 어려웠습니다.

after.PNG

그림 3. DFIR은 컴파일을 통해 코드를 최적화할 수 있는 프레임워크를 제공합니다.

그림 3은 이전에 도입되었던 VI에 대한 DFIR 그래프입니다. 이 그래프는 여러가지 변환이 분리와 최적화를 수행한 후 컴파일러 과정에의 훨씬 후의 시기를 설명합니다. 보이는 것과 같이 그래프는 이전의 그래프와 매우 다른 모습입니다. 예를 들어:

  • 분해 변환으로 컨트롤, 인디케이터, SubVI 노드를 없애고 이를 새로운 노드 (UIAccessor, UIUpdater, FunctionResolver, FunctionCall)로 대체
  • 루프 불변값 (loop-invariant) 코드 모션은 증분 및 곱셈 노드를 루프 본체의 외부로 이동함
  • clumper는 YieldIfNeeded 노드를 For 루프 내에 삽입함으로써 실행 스레드가 다른 경쟁하는 작업 아이템과 실행을 공유하도록 함

변환은 이후 섹션에서 더욱 자세히 설명됩니다.

DFIR IR은 여러 개의 컴파일러 프런트엔드 및 백엔드에 대한 공통 허브 역할을 합니다.

LabVIEW는 여러 다른 타겟과 작업하며, 이 중 일부는 x86 데스크탑 PC와 Xilinx FPGA와 같이 각각 매우 다른 형태입니다. 유사하게 LabVIEW는 여러가지 연산 모델을 사용자에게 제공합니다. G의 그래픽 프로그래밍 이외에도, 한 예로 LabVIEW는 MathScript의 텍스트 기반 수학을 제공합니다. 그 결과로, 프런트엔드와 백엔드의 모음이 생성되며 이 모두가 LabVIEW 컴파일러와 작동해야 합니다. DFIR을 일반 IR (모든 프런트엔드는 생성하고 모든 백엔드는 소비하는)로 사용하면 다양한 조합간 재사용이 편리해집니다. 예를 들어, DFIR 그래프에서 실행되는 상수 계산 최적화를 실행하면, 한 번 작성된 후 데스크탑, 리얼타임, FPGA, 임베디드 타겟에 적용됩니다.

DFIR 분해

일단 DFIR에서 VI는 우선 일련의 분해 변환을 통해 실행됩니다. 분해 변환은 DFIR 그래프를 축소하거나 정상화하는 데 사용됩니다. 예를 들어, 와이어 연결되지 않은 출력 터널 분해는 와이어 “연결되지 않으면 기본값 사용”으로 구성된 케이스 구조와 이벤트 구조에서 출력 터널을 검색합니다. 이같은 터미널의 경우, 변환은 기본값이 있는 상수를 터미널에 와이어 연결함으로써 “연결되지 않으면 기본값 사용” 동작이 DFIR 그래프에 명시적이도록 합니다. 차후의 컴파일러 통과는 모든 터미널을 동일하게 취급하며 모든 터미널에 와이어로 연결된 입력이 있다고 가정합니다. 본 경우, “연결되지 않으면 기본값 사용” 기능은 표현을 더욱 기본적인 형태로 줄임으로써 "컴파일"되었습니다.

본 개념은 더욱 복합적인 언어 기능에도 적용가능합니다. 예를 들어, 분해 변환은 피드백 노드를 While 루프의 시프트 레지스터로 줄이는 데 사용됩니다. 또 다른 분해는 병렬 For 루프를 몇몇 추가 로직이 있는 여러 순차적인 For 루프로 실행함으로써 순차적인 루프를 위해 입력을 병렬화가능한 부분으로 나누고 각 부분을 차후에 결합합니다.

LabVIEW 2010의 새로운 기능인 subVI 인라인 기능 또한 DFIR 분해로 실행됩니다. 컴파일의 본 단계 동안 “인라인”으로 표시된 subVI의 DFIR 그래프는 호출자의 DFIR 그래프에 직접 주입됩니다. subVI 호출의 오버헤드를 피하는 것 이외에도, 인라인은 호출자와 피호출자를 DFIR 그래프로 통합함으로써 추가 최적화를 위한 기회를 제공합니다. 예를 들어 vi.lib에서 TrimWhitespace.vi를 호출하는 간단한 VI를 생각해 보십시오.

01_caller.PNG

그림 4. DFIR 최적화 설명을 위한 간단한 VI 예제

TrimWhitespace.vi는 다음과 같이 vi.lib로 정의됩니다.

그림 5. TrimWhitespace.vi 블록 다이어그램

subVI는 호출자로 인라인되므로, 그 결과로 다음의 G 코드에 상응하는 DFIR 그래프가 나옵니다.

03_inlined.PNG

그림 6. 인라인된 TrimWhitespace.vi DFIR 그래프에 해당되는 G 코드

subVI의 다이어그램이 호출자 다이어그램으로 인라인되므로, 완료되지 않은 (unreachable) 코드 제거 및 데드 코드 (dead) 제거를 통해 코드를 간소화할 수 있습니다. 첫 번째 케이스 구조는 항상 실행되며, 두 번째 케이스 구조는 실행되지 않습니다.

04_unreach.PNG

그림 7. 케이스 구조는 입력 로직이 일정하므로 제거될 수 있습니다.

유사하게 루프 불변값 코드 모션은 정규식 일치 프리미티브를 루프 밖으로 이동시킵니다. 최종 DFIR 그래프는 다음 G 코드에 해당됩니다.

05_LICM.PNG

그림 8. 최종 DFIR 그래프에 해당되는 G 코드

TrimWhitespace.vi는 LabVIEW 2010에서 기본값으로 인라인 표시되므로 본 VI의 모든 클라이언트는 자동적으로 이같은 이점을 얻습니다

DFIR 최적화

DFIR 그래프가 완벽하게 분해되면 DFIR 최적화 통과가 시작됩니다. LLVM 컴파일 동안 심지어 더 많은 최적화가 수행됩니다. 본 섹션에서는 여러가지 최적화 중 일부만을 다룹니다. 각 변환은 일반적인 컴파일러 최적화이므로 특정 최적화에 대한 더욱 많은 정보를 검색하기가 편리할 것입니다.

완료되지 않은 (unreachable) 코드 제거

실행되지 않는 코드는 도달할 수 없음을 의미합니다. 이같은 코드를 제거하면 직접적으로 실행 시간이 빨라지지는 않지만 제거된 코드가 차후의 컴파일 통과에서 방해하지 않으므로 코드가 더욱 작아지며 컴파일 시간이 향상됩니다.

완료되지 않은 코드 제거 전

 

완료되지 않은 코드 제거 후

 

그림 9. DFIR 완료되지 않은 코드 제거 분해에 해당하는 G 코드 

이 경우, 케이스 구조의 “Do not increment” 다이어그램은 결코 실행되지 않으므로 변환은 본 케이스를 제거합니다. 케이스 구조에는 단 하나의 남은 케이스가 있으므로 시퀀스 구조로 대체됩니다. 데드 코드 제거는 그 후 프레임과 열거형 상수를 제거합니다.

루프 불변값 코드 모션

루프 불변값 코드 모션은 사용자가 루프 본체 외부로 안전하게 이동할 수 있는 루프 내 코드를 파악합니다. 이동된 코드가 더 적은 횟수로 실행되므로, 전체 실행 속도가 향상됩니다.

루프 불변값 코드 모션 변환 전

루프 불변값 코드 모션 변환 후

그림 10. DFIR 루프 불변성 코드 모션 분해에 해당하는 G 코드

본 경우, 증분 작업은 루프 외부로 이동됩니다. 루프 본체는 배열이 구축될 수 있도록 그대로 유지되지만 계산은 각 반복에서 되풀이될 필요가 없습니다.

CSE (Common Subexpression Elimination)

공통 부호 제거 반복된 계산을 파악하고 계산을 단 한번 수행하며 결과를 재사용합니다.

                         

전                                                                                    후              

그림 11. DFIR CSE (Common Subexpression Elimination) 분해에 해당하는 G 코드

상수 계산 (Constant Folding)

상수 계산은 실행 시간에서 다이어그램의 일정한 부분을 파악하므로 초반에 파악됩니다.

constant folding.PNG

그림 12. 상수 계산은 LabVIEW 블록 다이어그램에서 시각화 처리됩니다.

그림 12의 VI의 (#) 마크는 상수 계산된 부분을 나타냅니다. 이 경우, “오프셋” 컨트롤은 상수 계산될 수 없지만 For 루프와 같은 더하기 프리미티브의 피연산자는 상수값을 지닙니다.

루프 풀기 (Loop Unrolling)

루프 풀기 (Loop unrolling)는 생성된 코드에서 루프의 본체를 여러 차례 되풀이하며 전체 반복 횟수를 동일한 인수로 줄여서 루프 오버헤드를 줄입니다. 이를 통해 루프 오버헤드가 줄어들며, 코드 크기가 증가하는 대신 추가적인 최적화를 수행할 수 있는 기회를 제공합니다.

데드코드 제거

데드코드는 불필요한 요소입니다. 데드 코드를 제거하면 제거된 코드가 더이상 실행되지 않으므로 실행 시간이 가속화됩니다.

데드 코드는 사용자가 직접 작성하지 않은 변환에 의한 DFIR 그래프를 조작하여 생성됩니다. 다음 예제를 참조하십시오. 완료되지 않은 (unreachable) 코드 제거는 케이스 구조가 제거될 수 있는지 여부를 결정합니다. 이를 통해 데드코드 제거 변환으로 제거될 수 있는 데드코드가 “생성”됩니다.

도달불가 코드 제거 후

 

데드코드 제거 후

 

그림 13. 데드 코드를 제거하면 컴파일러가 거쳐야 하는 코드 양을 줄입니다.

본 섹션에서 다루는 대부분의 변환에는 다음과 같은 상관 관계가 있습니다. 즉, 하나의 변환을 실행하면 다른 변환을 실행할 기회가 생길 수도 있습니다.

DFIR 백엔드 변환

DFIR 그래프가 분해되고 최적화된 후에 여러 백엔드 변환이 실행됩니다. 백엔드 변환은 궁극적으로 DFIR 그래프를 LLVM IR로 낮추기 위한 준비로 DFIR 그래프를 평가하고 주석을 답니다.

Clumper

clumping 알고리즘은 DFIR 그래프의 병렬성을 분석하며 노드를 사용자가 병렬로 실행할 수 있도록 “클럼프”로 그룹짓습니다. 본 알고리즘은 멀티스레드 협동 멀티태스킹을 사용하는 LabVIEW의 런타임 실행 시스템과 긴밀히 연결되어 있습니다. clumper에 의해 생성된 각 클럼프는 실행 시스템의 개별 태스크로 스케쥴링됩니다. 클럼프 내의 노드는 고정된 직렬화 순서로 실행됩니다. 각 클럼프의 미리 결정된 실행 순서를 통해 inplacer는 데이터 할당을 공유하며 성능을 대폭 향상할 수 있게 됩니다. 또한 clumper는 루프 또는 I/O와 같은 긴 작업에 yield를 삽입하는 역할을 하므로, 클럼프가 다른 클럼프와 함께 협동하여 멀티태스킹을 수행합니다.

Inplacer

inplacer는 DFIR 그래프를 분석하며 사용자가 데이터 할당을 재사용할 수 있는 시기와 반드시 복사를 해야하는 시기를 파악합니다. LabVIEW의 와이어는 단순한 32-비트 스칼라이거나 32 MB 배열일 수 있습니다. 데이터가 가능한한 많이 재사용되도록 하는 것은 LabVIEW와 같은 데이터흐름 언어에서 매우 중요합니다.

다음 예제를 고려하십시오. (참고로, 최상의 성능과 메모리 공간을 얻기 위해 VI 디버깅은 비활성화됩니다.)

inplace.JPG

그림 14. Inplaceness 알고리즘을 설명하는 간단한 예제

본 VI는 배열을 시작하며 일부 스칼라 값을 각 요소에 추가하며 이를 2진 파일로 작성합니다. 몇 개의 배열 복사본이 있어야 할까요? LabVIEW는 초기에 배열을 생성해야 하지만 추가 작업은 해당 배열에서만 수행됩니다. 따라서 와이어당 하나의 할당 대신 배열의 단 하나의 복사본만이 필요합니다. 이는 배열이 클 경우, 메모리 사용과 실행 시간 두 가지 모두에 큰 차이를 가져옵니다. 본 VI에서 inplacer는 “in place” 작업 기회를 인식한 후 이를 활용하기 위해 더하기 노드를 구성합니다.

도구»프로파일 아래의 “버퍼 할당 보이기” 도구를 사용하여 사용자가 작성하는 VI의 동작을 검사할 수 있습니다. 도구는 더하기 프리미티브에서의 할당을 보여주지 않으므로 데이터 복사본이 만들어지지 않았고 더하기 연산이 발생했음을 나타냅니다.

이것이 가능한 이유는 다른 여러 노드가 원시 배열을 필요로 하지 않기 때문입니다. 사용자가 그림 15와 같이 VI를 변경할 경우, inplacer는 더하기 프리미티브에 대한 복사본을 만들어야 합니다. 이는 두 번째 2진 파일에 쓰기 원시파일이 원래의 배열을 필요로 하고, 첫 번째 2진 원시파일에 쓰기 이후에 반드시 실행되어야 하기 때문입니다. 이같은 변경을 통해 버퍼 할당 보이기 도구는 더하기 프리미티브에서 할당을 보여줍니다.

not-inplace.PNG

그림 15. 원래 배열 와이어를 분기하면 메모리에 복사본이 만들어집니다.

할당기

inplacer가 어떤 노드가 메모리 위치를 다른 노드와 공유할 것인지를 파악하고 나면 VI가 실행해야 하는 할당을 생성하기 위해 할당기가 실행됩니다. 이는 각 노드와 터미널을 방문하여 실행됩니다. 다른 터미널에 대해 in-place인 터미널은 새로운 할당을 생성하는 대신 할당을 재사용합니다.

코드 생성기

코드 생성기는 DFIR 그래프를 타겟 프로세서를 위한 실행가능한 기계 지시로 변환하는 컴파일러 요소입니다. LabVIEW는 DFIR 그래프의 각 노드를 데이터 흐름 순서대로 거치며, 각 노드는 GenAPI 인터페이스를 호출합니다. GenAPI 인터페이스는 DFIR 그래프를 해당 노드의 기능을 설명하는 순차적으로 IL (intermediate language)로 변환합니다. IL은 노드의 로우 레벨 동작을 설명하기 위한 플랫폼 독립적인 방법을 제공합니다. IL의 다양한 지시는 산술을 실행하고, 메모리에 읽거나 쓰고, 비교 및 조건적 분기 뿐 아니라 기타 작업을 수행합니다. IL 지시는 메모리에서 작동하거나 중간값 저장에 사용되는 버추얼 레지스터의 값에서 작동합니다. IL 지시 예로는 GenAdd, GenMul, GenIf, GenLabel, GenMove 등이 있습니다.

LabVIEW 2009와 이전 버전에서 본 IL 형태는 타겟 플랫폼을 위한 기계 지시 (80X86 및 PowerPC 등)로 직접 변환되었습니다. LabVIEW는 버추얼 레지스터를 물리적인 머신 레지스터로 맵핑하기 위해 간단한 one-pass 레지스터 할당기를 사용하였으며, 각 IL 지시는 각 지원되는 타겟 플랫폼에서 실행하기 위해 특정 기계의 지시에 대한 하드 코딩된 세트를 내보냈습니다. 속도가 눈에 띄게 빠르지만 임시적인 것이며 불량한 코드를 생성하였을 뿐 아니라 최적화에 적합하지 않았습니다. DFIR은 하이 레벨이며, 플랫폼 독립적인 표현방식으로써 지원할 수 있는 코드 변환에 한계가 있습니다. 현대식 최적화 컴파일러에서 코드 최적화 완벽한 세트를 위한 지원을 추가하기 위해 LabVIEW는 최근 LLVM이라고 하는 타사의 개방 소스 기술을 채택하였습니다.

LLVM

LLVM (Low-Level Virtual Machine)은 일리노이 주립대에서 연구 프로젝트 목적으로 개발된 다목적의 고성능 개방 소스 컴파일러 프레임워크입니다. LLVM은 유연성, 깔끔한 API 및 비제한적인 라이센스로 인해 학계와 업계에서 광범위하게 사용되고 있습니다.

LabVIEW 2010에서 LabVIEW 코드 생성기는 타겟 기계 코드를 생성하기 위해 LLVM을 사용하도록 리팩토링되었습니다. 기존의 LabVIEW IL 표현은 편리한 시작점을 제공함으로써 LabVIEW에 의해 지원되는 더욱 큰 DFIR 노드와 원시파일 세트가 아닌 약 80개의 IL 지시만이 재작성되도록 요구하였습니다.

VI의 DFIR 그래프로부터 IL 코드 스트림을 생성한 후, LabVIEW는 각 IL 지시를 방문하고 해당 LLVM 어셈블리 표현을 생성합니다. LabVIEW는 다양한 최적화 통과를 유도하며 그 후 메모리에서 실행가능한 기계 명령을 생성하기 위해 LLVM Just-in-Time (JIT) 프레임워크를 사용합니다. LLVM의 기계 이동 정보는 LabVIEW 표현으로 변환되므로 사용자가 VI를 디스크에 저장하고 이를 다른 메모리 베이스 주소로 다시 로딩하면 새로운 위치에서 실행하기 위해 정확하게 패치할 수 있습니다.

LabVIEW가 LLVM을 통해 표준 컴파일러 최적화를 진행하여 다음을 수행할 수 있습니다.

  • Instruction combining
  • Jump threading
  • Scalar replacement of aggregates
  • Conditional propagation
  • Tail call elimination
  • Expression reassociation
  • Loop invariant code motion
  • Loop unswitching and index splitting
  • Induction variable simplification
  • Loop unrolling
  • Global value numbering
  • Dead store elimination
  • Aggressive dead code elimination
  • Sparse conditional constant propagation

이같은 최적화 각각에 대한 설명은 본 문서 내용 범위에 속하지 않지만, 인터넷 뿐 아니라 대부분의 컴파일러 교재를 통해 풍부한 정보를 확인할 수 있습니다.

내부 벤치마크를 통해 살펴본 결과, LLVM을 사용함으로써 VI 실행 시간이 평균 20 퍼센트 증가하였습니다. 각 개별 결과는 VI에 의해 수행되는 연산의 특성에 따라 달라집니다. 다시 말해, 일부 VI는 결과가 더욱 우수했고 또 다른 VI에서는 성능의 변화가 없었습니다. 예를 들어, 고급 분석 라이브러리를 사용하는 VI 또는 최적화된 C에 이미 실행된 코드에 매우 의존적인 VI의 경우, 성능에 별다른 차이가 없었습니다. LabVIEW 2010은 LLVM을 사용하는 최초 버전이며 미래의 개선을 위한 잠재성이 아직도 충분합니다.

DFIR와 LLVM이 협력하여 실행됨

앞서 설명된 여러 최적화 즉, 루프 불변성 코드 모션 및 데드코드 제거 등의 여러 최적화는 DFIR이 수행하는 것으로 이미 설명되었습니다. 사실상, 일부 최적화 통과는 여러 번 그리고 컴파일러의 여러 레벨에서 실행하는 것이 효율적입니다. 그 이유는 다른 최적화 통과가 새로운 최적화 기회가 사용가능하도록 하는 방식으로 코드를 변환할 수 있기 때문입니다. 여기서 중요한 사실은 DFIR이 하이 레벨 IR이고 LLVM이 로우 레벨 IR인 반면, 이 두 가지는 코드 실행에 사용되는 프로세서 아키텍처를 위해 작성하는 LabVIEW 코드를 최적화하기 위해 함께 실행된다는 점입니다.