연산 시퀀스에 대해 매우 단순한 옵티마이저가 어떻게 동작할 수 있는지 Python3로 전체 코드를 통해 보여준다. SSA 형태의 IR, 유니온-파인드로 동치성을 추적하고, 상수 폴딩·공통 부분식 제거·강도 감소를 단일 패스로 결합하는 방법을 다룬다.
URL: https://pypy.org/posts/2022/07/toy-optimizer.html
이 블로그 글에서는 연산 시퀀스에 대해 매우 단순한 옵티마이저가 어떻게 동작할 수 있는지에 대한 전체 코드(Python3)를 보여주고자 한다. 이런 알고리즘은 (정말 단순한) 컴파일러나 JIT의 일부가 될 수 있다. 이 글의 코드 아키텍처는 PyPy JIT의 트레이스 옵티마이저와 매우 비슷하다. 트레이스가 만들어진 뒤, PyPy가 실행 중인 CPU 아키텍처용 바이너리 명령어를 만들어 내는 머신 코드 백엔드로 보내기 전에 트레이스를 최적화한다.
시작하려면 먼저 연산을 어떻게 저장할지 정의해야 한다. 컴파일러가 최적화 중인 프로그램을 저장하는 형식은 보통 중간 표현(Intermediate Representation)(IR)이라고 부른다. 많은 실전 컴파일러는 정적 단일 대입 형태(Static Single-Assignment Form)(SSA)의 IR을 사용하며, 여기서도 그렇게 하겠다. SSA 형태는 모든 변수가 정확히 한 번만 대입되고, 모든 변수가 사용되기 전에 정의된다는 성질이 있다. 이는 많은 것을 단순하게 해 준다.
좀 더 구체적으로 보자. 입력 프로그램이 a * (b + 17) + (b + 17) 같은 복잡한 표현식이라면, 그에 대한 중간 표현(혹은 최소한 텍스트 표현)은 대략 다음과 같을 수 있다:
var1 = add(b, 17)
var2 = mul(a, var1)
var3 = add(b, 17)
var4 = add(var2, var3)
이 명령 시퀀스는 비효율적이다. add(b, 17) 연산이 두 번 계산되며, 두 번째 것을 제거하고 한 번만 계산하면 시간을 절약할 수 있다. 이 글에서는 그런 최적화(및 관련 최적화들)를 수행할 수 있는 옵티마이저를 보여주고자 한다.
IR을 보면 입력 표현식이 연산의 시퀀스로 선형화(linearize)되었고, 모든 중간 결과에 유일한 변수 이름이 부여되었다. 각 변수가 대입받는 값은 오른쪽 항에서 계산되는데, 이는 피연산자(이 글에서는 name)와 임의 개수의 인자들로 이뤄진 어떤 연산이다. 연산의 인자들은 변수이거나 상수다.
입력 프로그램을 IR로 번역하는 과정은 전혀 다루지 않겠다. 대신 이미 그런 번역을 하는 컴포넌트가 있다고 가정한다. 이 글의 테스트들은 작은 IR 조각을 손으로 직접 구성할 것이다. 최적화 이후에 무슨 일이 일어나는지도 다루지 않는다(보통 최적화된 IR은 머신 코드로 번역된다).
파이썬 클래스로 중간 표현을 모델링하는 것부터 시작하자. 먼저 연산의 인자로 사용될 수 있는 모든 값의 베이스 클래스를 정의하고, 상수를 나타내는 클래스도 추가하자.
pythonimport pytest from typing import Optional, Any class Value: pass class Constant(Value): def __init__ (self, value: Any): self.value = value def __repr__ (self): return f"Constant({self.value})"
모든 변수가 한 번만 대입된다는 사실의 한 가지 결과는, 변수와 그 유일한 대입문의 오른쪽 항이 1:1로 대응된다는 점이다. 즉 변수를 나타내는 클래스를 아예 만들 필요가 없다. 대신 연산(오른쪽 항)을 나타내는 클래스만 있으면 충분하며, 정의상 그 연산이 바로 그 왼쪽 항(변수)과 동일하다.
pythonclass Operation(Value): def __init__ (self, name: str, args: list[Value]): self.name = name self.args = args def __repr__ (self): return f"Operation({self.name}, {self.args})" def arg(self, index: int): return self.args[index]
이제 위의 예시 연산 시퀀스를 나타내기 위해 이 두 클래스를 인스턴스화할 수 있다.
pythondef test_construct_example(): # 먼저 "a"와 "b"를 표현할 무언가가 필요하다. # 제한된 관점에서 우리는 이것들이 어디서 오는지 # 모르므로, "getarg"라는 가짜 연산으로 정의하겠다. # 이 연산은 숫자 n을 인자로 받아 n번째 입력 인자를 # 반환한다. 올바른 SSA 방식이라면 phi 노드를 써야 한다. a = Operation("getarg", [Constant(0)]) b = Operation("getarg", [Constant(1)]) # var1 = add(b, 17) var1 = Operation("add", [b, Constant(17)]) # var2 = mul(a, var1) var2 = Operation("mul", [a, var1]) # var3 = add(b, 17) var3 = Operation("add", [b, Constant(17)]) # var4 = add(var2, var3) var4 = Operation("add", [var2, var3]) sequence = [a, b, var1, var2, var3, var4] # 사실 테스트할 건 없다. 크래시만 안 나면 됨.
보통 복잡한 프로그램은 컴파일러에서 제어 흐름 그래프(control flow graph)로 표현되는데, 이는 프로그램 실행 중 제어가 갈 수 있는 모든 경로를 나타낸다. 제어 흐름 그래프의 각 노드는 기본 블록(basic block)이다. 기본 블록은 내부에 제어 흐름이 없는 선형 연산 시퀀스다.
프로그램을 최적화할 때 컴파일러는 보통 함수의 전체 제어 흐름 그래프를 본다. 하지만 그건 여전히 너무 복잡하다. 그래서 더 단순화해서, 하나의 기본 블록과 그 안의 명령 시퀀스만 볼 때 할 수 있는 최적화(지역 최적화, local optimizations)만 살펴보자.
기본 블록을 나타내는 클래스를 정의하고, 연산 시퀀스를 구성하기 위한 편의 함수도 추가하자. test_construct_example의 코드는 좀 불편하기 때문이다.
pythonclass Block(list): def opbuilder(opname): def wraparg(arg): if not isinstance(arg, Value): arg = Constant(arg) return arg def build(self, *args): # Operation을 만들고 필요하면 인자를 Constant로 감싼다 op = Operation(opname, [wraparg(arg) for arg in args]) # 기본 블록 self에 추가 self.append(op) return op return build # 지원하는 여러 연산들 add = opbuilder("add") mul = opbuilder("mul") getarg = opbuilder("getarg") dummy = opbuilder("dummy") lshift = opbuilder("lshift") def test_convencience_block_construction(): bb = Block() # getarg로 a를 다시 구성. # 아래 한 줄은 Operation 인스턴스를 정의하고 # 즉시 기본 블록 bb에 추가한다. a = bb.getarg(0) assert len(bb) == 1 assert bb[0].name == "getarg" # Constant이다 assert bb[0].args[0].value == 0 # getarg로 b b = bb.getarg(1) # var1 = add(b, 17) var1 = bb.add(b, 17) # var2 = mul(a, var1) var2 = bb.mul(a, var1) # var3 = add(b, 17) var3 = bb.add(b, 17) # var4 = add(var2, var3) var4 = bb.add(var2, var3) assert len(bb) == 6
테스트를 쉽게 작성하기 위한 인프라가 꽤 마련되었다. 하지만 한 가지 빠진 것이 있는데, 기본 블록을 보기 좋게 읽을 수 있는 텍스트 표현으로 출력하는 방법이다. 현재 형태에서 Block의 repr은 굉장히 성가시다. 위 테스트에서 bb를 예쁘게 출력하면 다음처럼 나온다.
python[Operation('getarg', [Constant(0)]), Operation('getarg', [Constant(1)]), Operation('add', [Operation('getarg', [Constant(1)]), Constant(17)]), Operation('mul', [Operation('getarg', [Constant(0)]), Operation('add', [Operation('getarg', [Constant(1)]), Constant(17)])]), Operation('add', [Operation('getarg', [Constant(1)]), Constant(17)]), Operation('add', [Operation('mul', [Operation('getarg', [Constant(0)]), Operation('add', [Operation('getarg', [Constant(1)]), Constant(17)])]), Operation('add', [Operation('getarg', [Constant(1)]), Constant(17)])])]
여기서는 무슨 일이 벌어지는지 보기 어렵다. 기본 블록 안의 Operation들이 리스트의 원소로 한 번 나오고, 리스트 아래쪽에서는 또 다른 연산의 인자로 반복해서 나타나기 때문이다. 그래서 디버깅을 할 수 있도록, 다시 읽기 쉬운 텍스트 표현으로 바꿔 주는 코드가 필요하다.
pythondef bb_to_str(bb: Block, varprefix: str = "var"): # 구현은 그다지 중요하지 않다. # 아래 테스트를 보면 결과가 어떻게 생겼는지 알 수 있다. def arg_to_str(arg: Value): if isinstance(arg, Constant): return str(arg.value) else: # 키는 반드시 존재해야 한다. 그렇지 않다면 # 유효한 SSA 기본 블록이 아니다: # 변수는 첫 사용 전에 정의되어야 한다. return varnames[arg] varnames = {} res = [] for index, op in enumerate(bb): # 출력 시 사용할 연산 이름 부여 var = f"{varprefix}{index}" varnames[op] = var arguments = ", ".join( arg_to_str(op.arg(i)) for i in range(len(op.args)) ) strop = f"{var} = {op.name}({arguments})" res.append(strop) return "\n".join(res) def test_basicblock_to_str(): bb = Block() var0 = bb.getarg(0) var1 = bb.add(5, 4) var2 = bb.add(var1, var0) assert bb_to_str(bb) == """\ var0 = getarg(0) var1 = add(5, 4) var2 = add(var1, var0)""" # 발명된 변수 이름에 다른 prefix 사용 assert bb_to_str(bb, "x") == """\ x0 = getarg(0) x1 = add(5, 4) x2 = add(x1, x0)""" # 그리고 우리의 예시: bb = Block() a = bb.getarg(0) b = bb.getarg(1) var1 = bb.add(b, 17) var2 = bb.mul(a, var1) var3 = bb.add(b, 17) var4 = bb.add(var2, var3) assert bb_to_str(bb, "v") == """\ v0 = getarg(0) v1 = getarg(1) v2 = add(v1, 17) v3 = mul(v0, v2) v4 = add(v1, 17) v5 = add(v3, v4)""" # 변수 재번호화에 주의! Operation에 이름을 붙이지 않으므로 # 출력은 시퀀스 순서대로 번호를 붙인다. # 때때로 혼동의 원인이 될 수 있다.
훨씬 낫다. 이제 기본 인프라는 끝났다. 연산 시퀀스를 정의하고 읽기 쉽게 출력할 수 있다. 다음으로는 기본 블록을 실제로 최적화할 때 쓰는 핵심 자료구조가 필요하다.
연산 시퀀스를 최적화할 때는 실행 비용을 줄이고 싶다. 보통 이를 위해 연산을 제거하거나(그리고 때로는 더 값싼 연산으로 바꾸기도) 한다. 예를 들어 소개 부분의 add(v1, 17) 중복처럼, 중복 계산을 하는 연산은 제거할 수 있다. 즉 우리가 하고 싶은 것은 다음 입력 시퀀스를:
v0 = getarg(0)
v1 = getarg(1)
v2 = add(v1, 17)
v3 = mul(v0, v2)
v4 = add(v1, 17)
v5 = add(v3, v4)
다음과 같은 최적화된 출력 시퀀스로 바꾸는 것이다:
optvar0 = getarg(0)
optvar1 = getarg(1)
optvar2 = add(optvar1, 17)
optvar3 = mul(optvar0, optvar2)
optvar4 = add(optvar3, optvar2)
두 번째 add(즉 v4를 정의하던 것)를 빼고, 마지막 연산에서 v4의 사용을 v2로 대체했다.
우리가 실제로 한 일은 v2와 v4가 동치라는 사실을 발견하고 v4를 v2로 바꾼 것이다. 일반적으로 더 많은 동치성을 발견할 수 있으며, 이를 저장할 자료구조가 필요하다. 이런 동치성을 저장하기에 좋은 자료구조는 유니온-파인드(Union Find)(또는 서로소 집합, Disjoint-set)로, 서로 겹치지 않는(disjoint) 집합들의 컬렉션을 저장한다. 서로소란 어떤 연산도 둘 이상의 집합에 동시에 속할 수 없다는 뜻이다. 우리의 경우 각 집합은 같은 결과를 계산하는 연산들의 집합이다.
처음에는 모든 연산이 다른 멤버가 없는 단일 원소 집합에 있다. 더 많은 동치성을 발견할수록, 집합을 합쳐서(unify) 같은 결과를 계산하는 연산들의 더 큰 집합으로 만든다. 그래서 자료구조가 지원하는 한 연산은 두 집합을 합치는 union인데, 아래 코드에서는 이를 make_equal_to라고 부르겠다.
자료구조의 다른 연산은 find로, 연산을 받아 그 연산이 속한 동치 집합의 “대표(representative)”를 돌려준다. 두 연산에 대해 find가 돌려주는 대표가 같다면, 두 연산은 같은 집합에 속한다.
자료구조의 정확한 동작 방식은 약간만 중요하다(하지만 정말 멋지다고 약속한다!). 구현은 넘어가도 된다. 이 자료구조를 Value, Constant, Operation 클래스 안에 바로 넣어 보자.
pythonclass Value: def find(self): raise NotImplementedError("abstract") def _set_forwarded(self, value): raise NotImplementedError("abstract") class Operation(Value): def __init__ (self, name: str, args: list[Value]): self.name = name self.args = args self.forwarded = None def __repr__ (self): return ( f"Operation({self.name}," f"{self.args}, {self.forwarded})" ) def find(self) -> Value: # 유니온-파인드 의미에서 self의 "대표" 값을 반환 op = self while isinstance(op, Operation): # 여기서도 경로 압축(path compression)을 할 수 있지만 # 필수는 아니다. next = op.forwarded if next is None: return op op = next return op def arg(self, index): # 위와의 변화: 인자 'index'의 대표를 반환 return self.args[index].find() def make_equal_to(self, value: Value): # 유니온-파인드 의미에서 "union"이지만 # 방향이 중요하다! Operation들의 합집합 대표는 # Constant이거나, 우리가 확실히 최적화로 제거되지 # 않는다고 아는 연산이어야 한다. self.find()._set_forwarded(value) def _set_forwarded(self, value: Value): self.forwarded = value class Constant(Value): def __init__ (self, value: Any): self.value = value def __repr__ (self): return f"Constant({self.value})" def find(self): return self def _set_forwarded(self, value: Value): # 어떤 Operation이 상수와 같다는 것을 알아냈다면, # 또 다른 상수와 같다고 알아내는 것은 컴파일러 버그다. assert isinstance(value, Constant) and \ value.value == self.value def test_union_find(): # 세 개의 연산을 만들고 단계적으로 합친다 bb = Block() a1 = bb.dummy(1) a2 = bb.dummy(2) a3 = bb.dummy(3) # 처음에는 모든 op가 자신의 대표다: {a1} {a2} {a3} assert a1.find() is a1 assert a2.find() is a2 assert a3.find() is a3 # a2와 a1을 합치면 {a1, a2} {a3} a2.make_equal_to(a1) assert a1.find() is a1 assert a2.find() is a1 assert a3.find() is a3 # 이제 모두 같은 집합 {a1, a2, a3} a3.make_equal_to(a2) assert a1.find() is a1 assert a2.find() is a1 assert a3.find() is a1 # 이제 이들이 상수 6과도 같다는 것을 배움: # {6, a1, a2, a3} c = Constant(6) a2.make_equal_to(c) assert a1.find() is c assert a2.find() is c assert a3.find() is c # 같은 상수로 다시 union 하는 것도 괜찮다 a2.make_equal_to(c)
이제 첫 번째 실제 최적화인 간단한 상수 폴딩(constant folding) 패스를 구현하자. 이 패스는 모든 인자가 상수인 연산을 제거하고, 그 결과 상수로 대체한다.
각 패스는 같은 구조를 가진다. 기본 블록의 모든 연산을 순서대로 훑으면서 각 연산이 제거 가능한지 결정한다. 상수 폴딩에서는 인자들이 상수인 연산을 제거할 수 있다(하지만 여기서는 add 케이스만 구현한다).
먼저 버그가 있는 상수 폴딩 패스를 보여주겠다. 이 버그는 왜 유니온-파인드가 필요한지와 관련이 있다. 조금 뒤에서 고칠 것이다.
pythondef constfold_buggy(bb: Block) -> Block: opt_bb = Block() for op in bb: # 기본 아이디어: 리스트를 순회하며 가능한 경우 add를 상수 폴딩 if op.name == "add": arg0 = op.args[0] arg1 = op.args[1] if isinstance(arg0, Constant) and \ isinstance(arg1, Constant): # 상수 폴딩 가능: op가 특정 상수와 같다는 새로운 동치성을 학습 value = arg0.value + arg1.value op.make_equal_to(Constant(value)) # 최적화된 기본 블록에는 이 연산이 필요 없다 continue # 그 외에는 출력 리스트에 넣는다 opt_bb.append(op) return opt_bb def test_constfold_simple(): bb = Block() var0 = bb.getarg(0) var1 = bb.add(5, 4) var2 = bb.add(var1, var0) opt_bb = constfold_buggy(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = add(9, optvar0)""" @pytest.mark.xfail def test_constfold_buggy_limitation(): # 이 테스트는 실패한다! constfold_buggy의 문제를 보여준다. bb = Block() var0 = bb.getarg(0) # 이건 폴딩된다 var1 = bb.add(5, 4) # 이것도 폴딩되길 원하지만 동작하지 않는다 var2 = bb.add(var1, 10) var3 = bb.add(var2, var0) opt_bb = constfold_buggy(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = add(19, optvar0)"""
왜 이 테스트는 실패할까? opt_bb 출력은 다음과 같다:
optvar0 = getarg(0)
optvar1 = add(9, 10)
optvar2 = add(optvar1, optvar0)
문제는 constfold_buggy가 두 번째 덧셈을 최적화할 때 그 연산의 인자가 Constant가 아니라 _Operation_이라는 점이다. 그래서 두 번째 add에는 상수 폴딩이 적용되지 않는다. 하지만 우리는 이미 var2 연산의 인자인 var1이 Constant(9)와 같다는 것을 배웠다. 이 정보는 유니온-파인드 자료구조에 저장되어 있다. 즉 상수 폴딩 패스에서, 이전에 배운 동치성을 활용하도록 적절한 find 호출이 빠져 있다.
수정된 버전은 다음과 같다:
pythondef constfold(bb: Block) -> Block: opt_bb = Block() for op in bb: # 기본 아이디어: 리스트를 순회하며 가능한 경우 add를 상수 폴딩 if op.name == "add": # >>> 변경 arg0 = op.arg(0) # .find() 사용 arg1 = op.arg(1) # .find() 사용 # <<< 변경 끝 if isinstance(arg0, Constant) and \ isinstance(arg1, Constant): # 상수 폴딩 가능 value = arg0.value + arg1.value op.make_equal_to(Constant(value)) continue opt_bb.append(op) return opt_bb def test_constfold_two_ops(): # 이제 동작한다! bb = Block() var0 = bb.getarg(0) var1 = bb.add(5, 4) var2 = bb.add(var1, 10) var3 = bb.add(var2, var0) opt_bb = constfold(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = add(19, optvar0)"""
constfold 패스는 Operation과 Constant 사이의 동치성만 발견한다. 두 번째 패스로 Operation과 다른 Operation 사이의 동치성도 발견해 보자.
이를 수행하는 단순한 최적화가 공통 부분식 제거(common subexpression elimination)(CSE)다. 이 패스는 드디어 서론의 예시 코드에서 문제였던 중복을 최적화해 없앤다.
pythondef cse(bb: Block) -> Block: # 구조는 동일: 입력을 순회하며 일부 연산만 출력에 추가 opt_bb = Block() for op in bb: # 여기서는 add에 대해서만 CSE를 수행하지만 일반화 가능 if op.name == "add": arg0 = op.arg(0) arg1 = op.arg(1) # 이미 같은 연산을 출력했는지 확인 prev_op = find_prev_add_op( arg0, arg1, opt_bb) if prev_op is not None: # 그렇다면 op를 제거하고 이전 결과로 치환 op.make_equal_to(prev_op) continue opt_bb.append(op) return opt_bb def eq_value(val0, val1): if isinstance(val0, Constant) and \ isinstance(val1, Constant): # 상수는 값으로 비교 return val0.value == val1.value # 그 외는 identity로 비교 return val0 is val1 def find_prev_add_op(arg0: Value, arg1: Value, opt_bb: Block) -> Optional[Operation]: # 매우 순진한 O(n^2) 구현. # 이미 출력한 연산을 순회하며 같은 add가 있었는지 확인. # 실전에서는 해시맵을 쓰거나 제한된 윈도만 보는 등 개선 가능. for opt_op in opt_bb: if opt_op.name != "add": continue # 여기서 arg를 호출하는 것이 중요하다. # constfold에서 필요했던 것과 같은 이유로 .find()가 # 호출되도록 보장해야 한다. if eq_value(arg0, opt_op.arg(0)) and \ eq_value(arg1, opt_op.arg(1)): return opt_op return None def test_cse(): bb = Block() a = bb.getarg(0) b = bb.getarg(1) var1 = bb.add(b, 17) var2 = bb.mul(a, var1) var3 = bb.add(b, 17) var4 = bb.add(var2, var3) opt_bb = cse(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = getarg(1) optvar2 = add(optvar1, 17) optvar3 = mul(optvar0, optvar2) optvar4 = add(optvar3, optvar2)"""
이제 Operation을 Constant로 바꾸는 패스 하나와, Operation을 이미 존재하는 다른 Operation으로 바꾸는 패스 하나를 만들었다. 마지막으로 Operation을 새로 “발명한” Operation으로 바꾸는 패스를 하나 더 만들어 보자. 간단한 강도 감소(strength reduction)로 하겠다.
pythondef strength_reduce(bb: Block) -> Block: opt_bb = Block() for op in bb: if op.name == "add": arg0 = op.arg(0) arg1 = op.arg(1) if arg0 is arg1: # x + x 를 x << 1로 바꾼다 newop = opt_bb.lshift(arg0, 1) op.make_equal_to(newop) continue opt_bb.append(op) return opt_bb def test_strength_reduce(): bb = Block() var0 = bb.getarg(0) var1 = bb.add(var0, var0) opt_bb = strength_reduce(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = lshift(optvar0, 1)"""
각 패스마다 모든 연산을 한 번씩 보는 대신, 하나의 단일 패스로 합쳐서 모든 연산을 정확히 한 번만 순회하도록 해 보자.
pythondef optimize(bb: Block) -> Block: opt_bb = Block() for op in bb: if op.name == "add": arg0 = op.arg(0) arg1 = op.arg(1) # 상수 폴딩 if isinstance(arg0, Constant) and \ isinstance(arg1, Constant): value = arg0.value + arg1.value op.make_equal_to(Constant(value)) continue # CSE prev_op = find_prev_add_op( arg0, arg1, opt_bb) if prev_op is not None: op.make_equal_to(prev_op) continue # 강도 감소: # x + x -> x << 1 if arg0 is arg1: newop = opt_bb.lshift(arg0, 1) op.make_equal_to(newop) continue # 산술 단순화도 추가: # a + 0 => a if eq_value(arg0, Constant(0)): op.make_equal_to(arg1) continue if eq_value(arg1, Constant(0)): op.make_equal_to(arg0) continue opt_bb.append(op) return opt_bb def test_single_pass(): bb = Block() # 상수 폴딩 var0 = bb.getarg(0) var1 = bb.add(5, 4) var2 = bb.add(var1, 10) var3 = bb.add(var2, var0) opt_bb = optimize(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = add(19, optvar0)""" # CSE + 강도 감소 bb = Block() var0 = bb.getarg(0) var1 = bb.getarg(1) var2 = bb.add(var0, var1) var3 = bb.add(var0, var1) # var2와 동일 var4 = bb.add(var2, 2) var5 = bb.add(var3, 2) # var4와 동일 var6 = bb.add(var4, var5) opt_bb = optimize(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = getarg(1) optvar2 = add(optvar0, optvar1) optvar3 = add(optvar2, 2) optvar4 = lshift(optvar3, 1)""" # + 0 제거 bb = Block() var0 = bb.getarg(0) var1 = bb.add(16, -16) var2 = bb.add(var0, var1) var3 = bb.add(0, var2) var4 = bb.add(var2, var3) opt_bb = optimize(bb) assert bb_to_str(opt_bb, "optvar") == """\ optvar0 = getarg(0) optvar1 = lshift(optvar0, 1)"""
이번 글은 여기까지다. 왜 이 아키텍처가 멋질까? 소프트웨어 엔지니어링 관점에서 optimize처럼 모든 것을 단일 함수에 집어넣는 것은 분명 좋은 방식이 아니다. 실제로 하려면 케이스들을 개별적으로 이해하기 쉬운 여러 함수로 나누거나, 패턴 매칭을 더 읽기 좋게 해 주는 DSL을 쓰고 싶을 것이다. 하지만 이 아키텍처의 장점은 꽤 효율적이라는 점이다. 기본 블록을 한 번만 순회하면서도 많은 좋은 최적화를 집어넣을 수 있다.
물론 이는 트레이싱(tracing) 문맥에서 더 잘 작동한다. 모든 것이 트레이스에 들어가는데, 트레이스는 사실상 엄청나게 긴 하나의 기본 블록이기 때문이다. JIT 문맥에서는 옵티마이저 자체가 빠르게 실행되는 것도 매우 중요하다.
이 모델에서는 다양한 다른 최적화도 가능하다. 뒤이은 후속 글에서는 PyPy의 가장 중요한 최적화라고 할 수 있는 것을 구현하는 방법을 보여 준다.
이 글은 짧은 소개이며 몇 가지 지름길을 택했다. 다룬 주제들에 대한 더 일반적인 문헌을(비포괄적으로) 몇 가지 가리켜 보겠다.
여기서 설명한 CSE 접근법은 보통 값 번호 매기기(value numbering)로 볼 수 있다. 다만 일반적으로는 해시맵으로 구현된다. 단일 기본 블록을 넘어서 다양한 구현 스타일을 설명하는 논문도 있다. 이 논문은 같은 결과를 계산하는 연산들의 동치류(equivalence class)를 발견하는 관점도 부분적으로 취한다.
연산 간 동치성을 찾는 데 더 강하게 기대는 기법으로 e-graph를 사용하고 등식 포화(equality saturation)를 적용하는 방법도 있다(이는 여기서 설명한 것보다 상당히 더 고급이다). 이 기법을 적용하는 멋진 현대 프로젝트로 egg가 있다.
조금 다르게 보면, 상수 폴딩 패스는 부분 평가(Partial Evaluation)의 아주 단순한 형태로 일반적으로 볼 수도 있다. 상수 인자를 가진 모든 연산은 상수 폴딩으로 사라지고, 나머지는 “잔여화(residualized)”되어 출력 프로그램에 들어간다. 이 관점은 현재 글에서는 그리 중요하지 않지만, 다음 글에서는 중요해진다.
감사의 말: Thorsten Ball에게, 이 글을 쓰도록 부추겨 주고 열정적인 피드백을 준 것에 감사한다. 또한 Max Bernstein, Matti Picus, Per Vognsen에게도 훌륭한 피드백을 받았다. 아주 오래 전 Peng Wu와의 대화가 계속 기억에 남아, 컴파일러 최적화를 바라보는 다양한 방식에 대해 계속 생각하게 되었다.