최적화 컴파일러가 IR 명령의 효과(부작용)를 추적하는 방식들을 비트셋과 힙 범위 등으로 정리하고, Cinder와 JavaScriptCore, Simple을 비롯한 여러 구현을 비교한다.
최적화 컴파일러는 각 IR 명령의 _효과_를 추적하는 것을 좋아합니다. 어떤 명령의 효과는 전혀 없을 수도 있고, 특정 변수를 쓰는 정도일 수도 있으며, 완전히 알 수 없음(모든 상태를 씀)일 수도 있습니다.
이 글은 IR에 대해 IR을 이야기할 때 내가 이야기하는 것의 연장선으로 볼 수 있는데, 특히 올바른 질문을 던지는 부분을 잇습니다. 효과를 이야기할 때는 _이게 어떤 오퍼코드인가?_가 아니라 _이 오퍼코드는 어떤 효과를 가지는가?_를 물어야 합니다.
컴파일러마다 이런 효과를 표현하고 추적하는 방식이 다릅니다. 저는 일 년 내내 이 효과들을 어떻게 표현할지 고민해 왔고, 그래서 이것저것 읽어 봤습니다. 이 글에서는 접근법의 지형에 대한 요약을 몇 가지 제시하겠습니다. 더 좋은 자료가 있으면 제안해 주세요.
내부 IR 효과 추적은 타입 시스템에서의 대수적 효과(algebraic effects)라는 프로그래밍 언어 개념과 비슷하지만, 컴파일러 내부에서는 더 미세한 효과를 추적합니다. “로컬 변수에 쓴다”, “리스트에 쓴다”, “스택에서 읽는다” 같은 효과는 어떤 명령들이 재정렬될 수 있는지, 복제될 수 있는지, 혹은 완전히 제거될 수 있는지를 나타냅니다.
예를 들어, 컴파일러 IR 조각을 대신하는 어떤 가상의 언어에 대한 다음 의사코드를 생각해 봅시다:
# ...
v = some_var[0]
another_var[0] = 5
# ...
효과의 목표는 예컨대 이 두 IR 명령을 재정렬할 수 있는지 같은 정보를 컴파일러에 전달하는 것입니다. 두 번째 명령은 첫 번째가 읽는 위치에 쓸 수도 있습니다. 하지만 아닐 수도 있습니다! 핵심은 some_var와 another_var가 _별칭(alias)_인지—즉 같은 객체를 가리키는 서로 다른 이름인지—를 아는 것입니다.
우리는 때때로 그 질문에 직접 답할 수 있지만, 대개는 근사 답을 계산하는 편이 더 저렴합니다: 애초에 둘이 별칭일 _가능성_이 있는가? some_var와 another_var가 서로 다른 타입일 수도 있는데, (엄격한 별칭 규칙이 있다면) 이 읽기/쓰기를 구현하는 Load와 Store 연산은 정의상 서로 다른 위치를 건드리게 됩니다. 그리고 서로 분리된 위치를 본다면, 명시적인 순서를 강제할 필요가 없습니다.
컴파일러마다 이 정보를 추적하는 방식이 다릅니다. 널 효과 분석(null effect analysis)은 포기하고 “모든 명령은 최대한으로 효과가 있다”고 말하며, 따라서 “어떤 명령도 재정렬하거나 삭제할 수 없다”고 결론냅니다. 처음 컴파일러를 만들 때는 그게 아마도 괜찮습니다. 강도 감소(strength reduction)만으로도 큰 속도 향상을 얻을 수 있기 때문입니다. 효과의 과대근사(over-approximation)는 항상 유효해야 합니다.
하지만 어느 시점부터는 죽은 코드 제거(DCE), 공통 부분식 제거(CSE), 로드/스토어 제거, 혹은 명령 이동을 하고 싶어집니다. 그러면 효과를 어떻게 표현할지 고민하게 됩니다. 저는 지금 딱 그 지점에 있습니다. 그래서 최근에 살펴본 여러 컴파일러를 카탈로그로 정리해 보겠습니다.
제가 본 효과 표현 방식은 크게 두 가지입니다: 비트셋과 힙 범위 리스트. 각각에 대해 예시 컴파일러를 하나씩 보고, 트레이드오프를 조금 이야기한 뒤, 다른 주요 컴파일러들에 대한 참고 링크를 잔뜩 제공하겠습니다.
Cinder부터 시작하겠습니다. 제가 예전에 일하던 Python JIT입니다.
Cinder는 고수준 IR(HIR)에 대한 힙 효과를 instr_effects.h에서 추적합니다. 거의 모든 일은 memoryEffects(const Instr& instr) 함수에서 일어나며, 이 함수는 주어진 명령이 가질 수 있는 효과를 전부 알고 있어야 한다고 기대됩니다.
데이터 표현은 AliasClass라는 격자(lattice)의 비트셋 표현이며, alias_class.h에 정의되어 있습니다. 비트셋의 각 비트는 힙의 서로 다른 위치를 나타냅니다. 이 각각의 위치에 대한 읽기/쓰기는 다른 어떤 위치에도 영향을 주지 않는다고 보장됩니다.
이를 정의하는 X-macro는 다음과 같습니다:
#define HIR_BASIC_ACLS(X) \
X(ArrayItem) \
X(CellItem) \
X(DictItem) \
X(FuncArgs) \
X(FuncAttr) \
X(Global) \
X(InObjectAttr) \
X(ListItem) \
X(Other) \
X(TupleItem) \
X(TypeAttrCache) \
X(TypeMethodCache)
enum BitIndexes {
#define ACLS(name) k##name##Bit,
HIR_BASIC_ACLS(ACLS)
#undef ACLS
};
각 비트가 암묵적으로 집합을 나타낸다는 점에 주목하세요. ListItem은 특정 리스트 인덱스를 가리키는 것이 아니라 가능한 모든 리스트 인덱스의 무한 집합을 가리킵니다. 즉 어떤 리스트 인덱스든 됩니다. 그래도 어떤 리스트 인덱스도, 예컨대 전역 변수 테이블의 어떤 엔트리와도 완전히 분리되어 있습니다.
(명확히 하자면, 리스트 안의 객체가 전역 변수 테이블 안의 객체와 같을 수는 있습니다. 객체 자체는 별칭일 수 있습니다. 하지만 쓰거나 읽는 대상, 즉 부작용이 발생하는 대상은 컨테이너입니다.)
다른 비트셋 격자들처럼, 비트 OR로 집합을 합칠 수 있습니다. 비트 AND로 겹침을 질의할 수도 있습니다.
class AliasClass {
// The union of two AliasClass
AliasClass operator|(AliasClass other) const {
return AliasClass{bits_ | other.bits_};
}
// The intersection (overlap) of two AliasClass
AliasClass operator&(AliasClass other) const {
return AliasClass{bits_ & other.bits_};
}
};
이게 익숙하게 들린다면, 저장소 설명에 적혀 있듯 Cinder의 타입 격자 표현과 비슷한 아이디어이기 때문입니다.
다른 격자들과 마찬가지로, 바닥 원소(효과 없음)와 꼭대기 원소(가능한 모든 효과)가 있습니다:
#define HIR_OR_BITS(name) | k##name
#define HIR_UNION_ACLS(X) \
/* Bottom union */ \
X(Empty, 0) \
/* Top union */ \
X(Any, 0 HIR_BASIC_ACLS(HIR_OR_BITS)) \
/* Memory locations accessible by managed code */ \
X(ManagedHeapAny, kAny & ~kFuncArgs)
합집합 연산은 자연스럽게 Any에서 고정점(fixpoint)에 도달하고, 교집합 연산은 자연스럽게 Empty에서 고정점에 도달합니다.
이 모든 것을 합치면 최적화기는 다음과 같은 질문을 묻고 답할 수 있습니다:
등등.
이제 서론의 코드 조각을 (가상의) IR 버전으로 보고, 최적화기에서 분석이 어떻게 생겼을지 살펴봅시다. 다음은 가짜 IR입니다:
v0: Tuple = ...
v1: List = ...
v2: Int[5] = ...
# v = some_var[0]
v3: Object = LoadTupleItem v0, 0
# another_var[0] = 5
StoreListItem v1, 0, v2
LoadTupleItem은 TupleItem 힙에서 읽는다고 선언하고 StoreListItem은 ListItem 힙에 쓴다고 선언한다고 상상할 수 있습니다. 튜플 포인터와 리스트 포인터는 서로 캐스팅될 수 없고 따라서 별칭이 될 수 없으므로, 비트셋에서 이 둘은 분리된 힙입니다. 따라서 ListItem & TupleItem == 0이며, 이 메모리 연산들은 절대로 서로 간섭할 수 없습니다! (예를 들어) 임의로 재정렬할 수 있습니다.
Cinder에서 이런 메모리 효과는 장차 명령 재정렬에 사용될 수도 있지만, 현재는 주로 두 곳에서 사용됩니다: refcount 삽입 패스와 DCE.
DCE는 먼저 유용/중요/효과가 있어서 남겨야 하는 명령들의 집합을 찾는 과정이 포함됩니다. Cinder의 DCE isUseful는 다음과 같습니다:
bool isUseful(Instr& instr) {
return instr.IsTerminator() || instr.IsSnapshot() ||
(instr.asDeoptBase() != nullptr && !instr.IsPrimitiveBox()) ||
(!instr.IsPhi() && memoryEffects(instr).may_store != AEmpty);
}
다른 검사들도 있지만, 핵심에 memoryEffects가 딱 자리하고 있습니다!
이제 비트셋 표현과 Cinder 구현을 봤으니, 다른 표현과 JavaScriptCore의 구현을 살펴봅시다.
저는 JavaScriptCore(JSC)의 주요 기여자 중 한 명인 Fil Pizlo가 쓴 How I implement SSA form으로 계속 돌아오게 됩니다. 특히 Uniform Effect Representation 섹션으로요. “추상 힙(abstract heaps)”이라는 개념은 참… 음, 추상적으로 느껴졌습니다. 비트셋 표현보다도 더 추상적이랄까요. 중첩된 힙 효과를 표현하기 위한 전위(pre-order)/후위(post-order) 정수 쌍은 도무지 감이 오지 않았습니다.
실제로 JavaScriptCore 안을 파고 들어가 여러 구현 중 하나를 찾아보기 전까지는 전혀 이해가 되지 않았습니다. 왜냐하면 JSC는 트렌치코트 하나에 컴파일러 여섯 개쯤이 들어 있는 물건이니까요[citation needed].
DFG, B3, DOMJIT, 그리고 아마 다른 것들도 각자의 추상 힙 구현을 가지고 있습니다. 여기서는 주로 DOMJIT을 보겠습니다. 더 작은 예시이기도 하고, 또 흥미로운 다른 것 하나를 보여 주기 때문입니다: builtin입니다. builtin 이야기는 잠시 뒤에 다시 하겠습니다.
DOMJIT이 abstract heaps를 구조화하는 방식부터 봅시다: YAML 파일입니다.
DOM:
Tree:
Node:
- Node_firstChild
- Node_lastChild
- Node_parentNode
- Node_nextSibling
- Node_previousSibling
- Node_ownerDocument
Document:
- Document_documentElement
- Document_body
계층 구조입니다. Node_firstChild는 Node의 부분 힙(subheap)이고, Node는 …의 부분 힙이고, 이런 식입니다. 어떤 Node_nextSibling에 대한 쓰기는 Node에 대한 쓰기이고, 또 …에 대한 쓰기입니다. 형제(sibling) 힙들은 서로 관련이 없습니다. 예를 들어 Node_firstChild와 Node_lastChild는 분리되어 있습니다.
감각을 잡기 위해, 저는 ZJIT의 비트셋 생성기( 타입! 용)를 단순화한 버전으로 YAML 문서를 읽고 비트셋을 생성하도록 연결해 봤습니다. 그 결과 다음 Rust 코드가 생성되었습니다:
mod bits {
pub const Empty: u64 = 0u64;
pub const Document_body: u64 = 1u64 << 0;
pub const Document_documentElement: u64 = 1u64 << 1;
pub const Document: u64 = Document_body | Document_documentElement;
pub const Node_firstChild: u64 = 1u64 << 2;
pub const Node_lastChild: u64 = 1u64 << 3;
pub const Node_nextSibling: u64 = 1u64 << 4;
pub const Node_ownerDocument: u64 = 1u64 << 5;
pub const Node_parentNode: u64 = 1u64 << 6;
pub const Node_previousSibling: u64 = 1u64 << 7;
pub const Node: u64 = Node_firstChild | Node_lastChild | Node_nextSibling | Node_ownerDocument | Node_parentNode | Node_previousSibling;
pub const Tree: u64 = Document | Node;
pub const DOM: u64 = Tree;
pub const NumTypeBits: u64 = 8;
}
화려한 X-macro는 아니지만, 짧고 유연한 Ruby 스크립트입니다.
그 다음에는 DOMJIT abstract heap generator—재미있게도 이것도 짧은 Ruby 스크립트인데—출력 포맷을 살짝 바꾸고, 정수 쌍을 생성하도록 했습니다:
mod bits {
/* DOMJIT Abstract Heap Tree.
DOM<0,8>:
Tree<0,8>:
Node<0,6>:
Node_firstChild<0,1>
Node_lastChild<1,2>
Node_parentNode<2,3>
Node_nextSibling<3,4>
Node_previousSibling<4,5>
Node_ownerDocument<5,6>
Document<6,8>:
Document_documentElement<6,7>
Document_body<7,8>
*/
pub const DOM: HeapRange = HeapRange { start: 0, end: 8 };
pub const Tree: HeapRange = HeapRange { start: 0, end: 8 };
pub const Node: HeapRange = HeapRange { start: 0, end: 6 };
pub const Node_firstChild: HeapRange = HeapRange { start: 0, end: 1 };
pub const Node_lastChild: HeapRange = HeapRange { start: 1, end: 2 };
pub const Node_parentNode: HeapRange = HeapRange { start: 2, end: 3 };
pub const Node_nextSibling: HeapRange = HeapRange { start: 3, end: 4 };
pub const Node_previousSibling: HeapRange = HeapRange { start: 4, end: 5 };
pub const Node_ownerDocument: HeapRange = HeapRange { start: 5, end: 6 };
pub const Document: HeapRange = HeapRange { start: 6, end: 8 };
pub const Document_documentElement: HeapRange = HeapRange { start: 6, end: 7 };
pub const Document_body: HeapRange = HeapRange { start: 7, end: 8 };
}
이미 작은 다이어그램이 함께 나오는데, 가독성 면에서 엄청 도움이 됩니다.
빈 범위(empty range)는 빈 힙 효과를 의미합니다. start와 end가 같은 숫자면 효과가 없습니다. 하나의 Empty 값이 있는 것은 아니지만, 어떤 빈 범위든 HeapRange { start: 0, end: 0 }로 정규화할 수 있습니다.
어쩌면 독자 여러분에게는 자명했겠지만, 이 전위/후위 방식은 중첩된 범위(nested ranges)에 관한 것입니다! 생성기의 출력이 이렇게 명확히 펼쳐진 것을 보니 저는 훨씬 이해가 되었습니다.
겹침(overlap) 검사는 어떨까요? 다음은 JSC의 구현입니다:
namespace WTF {
// Check if two ranges overlap assuming that neither range is empty.
template<typename T>
constexpr bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
{
ASSERT_UNDER_CONSTEXPR_CONTEXT(leftMin < leftMax);
ASSERT_UNDER_CONSTEXPR_CONTEXT(rightMin < rightMax);
return leftMax > rightMin && rightMax > leftMin;
}
// Pass ranges with the min being inclusive and the max being exclusive.
template<typename T>
constexpr bool rangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax) {
ASSERT_UNDER_CONSTEXPR_CONTEXT(leftMin <= leftMax);
ASSERT_UNDER_CONSTEXPR_CONTEXT(rightMin <= rightMax);
// Empty ranges interfere with nothing.
if (leftMin == leftMax)
return false;
if (rightMin == rightMax)
return false;
return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
}
}
class HeapRange {
bool overlaps(const HeapRange& other) const {
return WTF::rangesOverlap(m_begin, m_end, other.m_begin, other.m_end);
}
}
(더 재미를 원하면 How to check for overlapping intervals와 Range overlap in two compares도 보세요.)
비트셋은 밀집(dense) 표현(모든 비트를 들고 있어야 함)이지만, 매우 압축적이고 매우 정밀합니다. 64비트나 128비트의 조합을 단일 레지스터에 담을 수 있습니다. 합집합/교집합 연산도 아주 저렴합니다.
정수 범위를 쓰면 조금 더 복잡합니다. a와 b의 부정밀한 합집합은 둘을 모두 덮는 최대 범위를 취할 수 있습니다. 더 정밀한 합집합을 원하면 둘 다를 추적해야 합니다. 최악의 경우, 효율적인 임의 질의를 원한다면 정수 범위를 interval tree에 저장해야 합니다. 그럼에도 왜 이렇게 할까요?
저는 Fil에게 “비트셋과 정수 범위가 같은 질문에 답한다면 왜 정수 범위를 쓰나요?”라고 물었습니다. 그는 장기적으로 더 유연하기 때문이라고 했습니다. 비트셋은 128비트를 넘기기 시작하면 비용이 급증(힙 할당이 필요할 수도!)하는 반면, 범위에는 그런 상한이 없습니다. 하지만 범위 시퀀스를 들고 있으면 힙 할당이 필요하지 않나요? Fil이 SSA 글에서 이렇게 썼음에도 말이죠:
The purpose of the effect representation baked into the IR is to provide a precise always-available baseline for alias information that is super easy to work with. […] you can have instructions report that they read/write multiple heaps […] you can have a utility function that produces such lists on demand.
중요한 점은, 이것이 실제로 어떤 리스트의 할당을 포함하지 않는다는 것입니다. JSC는 아주 영리하게도, 명령의 효과에서 원하는 것을 압축/요약하는 “펑터(functor)”를 인자로 넘기는 방식을 씁니다.
예를 들어 DFG가 이 힙 범위들을 분석에서 어떻게 사용하는지 봅시다. DFG는 DOMJIT 힙 범위를 직접 활용할 수 있게 구조화되어 있는데, 멋집니다.
아래 예시의 AbstractHeap은 DFG 컴파일러 자체의 DOMJIT::HeapRange 동등물 위에 얇게 씌운 래퍼입니다:
class AbstractHeapOverlaps {
public:
AbstractHeapOverlaps(AbstractHeap heap)
: m_heap(heap)
, m_result(false)
{
}
void operator()(AbstractHeap otherHeap) const
{
if (m_result)
return;
m_result = m_heap.overlaps(otherHeap);
}
bool result() const { return m_result; }
private:
AbstractHeap m_heap;
mutable bool m_result;
};
bool writesOverlap(Graph& graph, Node* node, AbstractHeap heap)
{
NoOpClobberize noOp;
AbstractHeapOverlaps addWrite(heap);
clobberize(graph, node, noOp, addWrite, noOp);
return addWrite.result();
}
clobberize는 주어진 IR 명령 node가 선언하는 각 효과에 대해 이런 펑터들(여기서는 noOp나 addWrite)을 호출하는 함수입니다.
clobberize는 꽤 긴데, 그 중 흥미롭다고 생각한 일부를 뽑았습니다.
먼저 어떤 명령(여기서는 상수)은 효과가 없습니다. def(PureValue(...)) 호출에 약간의 유틸리티가 있는데, 저는 완전히 이해하지는 못했습니다.
그 다음에는 피연산자의 use 타입에 따라 조건적으로 효과가 생기는 명령들이 있습니다.1 Int32나 Double의 절댓값은 효과가 없지만, 그 외에는 임의의 코드를 실행할 수 있는 것처럼 보입니다.
부수 탈출(side exit)을 일으킬 수 있는 어떤 런타임 IR 가드들은 그렇게 주석 처리되어 있으며, SideState 힙에 쓴다고 표시됩니다.
로컬 변수 명령은 로컬 인덱스처럼 보이는 것으로 인덱싱된 특정 힙을 읽습니다(확실하진 않지만). 이는 서로 다른 두 로컬에 접근하는 것은 별칭이 되지 않는다는 뜻입니다!
할당하는 명령은 재정렬될 수 없어 보이는데, HeapObjectCount를 읽고 쓰기 때문입니다. 이는 할당 sinking의 양을 제한할지도 모릅니다.
그리고 제가 말하던 builtin 관련 CallDOM이 있습니다. 코드 블록 뒤에서 다시 이야기하겠습니다.
template<typename ReadFunctor, typename WriteFunctor, typename DefFunctor, typename ClobberTopFunctor>
void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFunctor& write, const DefFunctor& def)
{
// ...
switch (node->op()) {
case JSConstant:
case DoubleConstant:
case Int52Constant:
def(PureValue(node, node->constant()));
return;
case ArithAbs:
if (node->child1().useKind() == Int32Use || node->child1().useKind() == DoubleRepUse)
def(PureValue(node, node->arithMode()));
else
clobberTop();
return;
case AssertInBounds:
case AssertNotEmpty:
write(SideState);
return;
case GetLocal:
read(AbstractHeap(Stack, node->operand()));
def(HeapLocation(StackLoc, AbstractHeap(Stack, node->operand())), LazyNode(node));
return;
case NewArrayWithSize:
case NewArrayWithSizeAndStructure:
read(HeapObjectCount);
write(HeapObjectCount);
return;
case CallDOM: {
const DOMJIT::Signature* signature = node->signature();
DOMJIT::Effect effect = signature->effect;
if (effect.reads) {
if (effect.reads == DOMJIT::HeapRange::top())
read(World);
else
read(AbstractHeap(DOMState, effect.reads.rawRepresentation()));
}
if (effect.writes) {
if (effect.writes == DOMJIT::HeapRange::top()) {
if (Options::validateDFGClobberize())
clobberTopFunctor();
write(Heap);
} else
write(AbstractHeap(DOMState, effect.writes.rawRepresentation()));
}
ASSERT_WITH_MESSAGE(effect.def == DOMJIT::HeapRange::top(), "Currently, we do not accept any def for CallDOM.");
return;
}
}
}
(이 AbstractHeap 연산은 DOMJIT의 HeapRange와 아주 비슷하며, 몇 가지 세부사항이 더해진 것입니다. 그리고 어떤 경우에는 DOMJIT HeapRange를 포함하기도 합니다!)
이 CallDOM 노드는 브라우저의 DOM API—builtin의 상당 부분으로, C++로 작성됨—가 최적화 컴파일러에 자신이 무엇을 하는지 전달하는 방식입니다. 아무 주석이 없다면, JIT는 C++로 들어가는 호출이 JIT 상태에 대해 무엇이든 할 수 있다고 가정해야 합니다. 안타깝죠!
하지만 예를 들어 Node.firstChild가 읽는 메모리를 주석으로 달고 어떤 곳에는 _쓰지 않는지_까지 표시해 두면, JIT는 그 주변을 더 잘 최적화할 수 있고—심지어 접근 자체를 완전히 제거할 수도 있습니다. 이는 JIT가 알려진 builtin 호출을 일반 JIT 오퍼코드와 같은 방식으로 추론할 수 있게 해 줍니다.
(덧붙이자면, C 호출을 하는 것조차 아닌 것 같고, JIT 빌더 API로 작은 메모리 읽기 스니펫으로 인라인되는 것처럼 보입니다. 멋지네요.)
마지막으로 Simple을 보겠습니다. 이것은 이 모든 것에 대해 약간 다른 관점을 가지고 있습니다.
Simple은 Cliff Click의 개인 Sea of Nodes(SoN) 프로젝트로, HotSpot C2 맥락 밖에서 그 아이디어를 세상에 보여 주려는 시도입니다.
이건 저에게 조금 이해하기 어렵지만, 각 번역 단위(translation unit)마다 StartNode가 있고, 이것이 각 alias class에 대해 서로 다른 클래스의 메모리 노드들을 배분하는 것처럼 보입니다. 그런 다음 각 IR 노드는 자신이 사용할 수도 있는 효과 노드들에 대해 데이터 의존성을 가집니다.
Alias class는 논문 Type-Based Alias Analysis (PDF)를 기반으로 나뉩니다: “우리 접근법은 논문에 опис된 ‘FieldTypeDecl’ 알고리즘과 유사한 TBAA의 한 형태다.”
Simple 프로젝트는 순차적인 구현 단계로 구성되어 있고, alias class는 Chapter 10에서 등장합니다.
다른 프로젝트들은 어떻게 하는지 보기 위해 한참을 파고 들었기 때문에, 제가 살펴본 프로젝트 목록을 여기에 적어 둡니다. 대부분은 비트셋을 사용합니다.
HHVM은 Hack 언어용 JIT이며, 메모리 효과에 비트셋을 사용합니다. 예를 들어 alias-class.h와 memory-effects.h를 보세요.
HHVM은 이 정보를 사용하는 곳이 몇 군데 있습니다. 예를 들면 definition-sinking 패스, alias 분석, DCE, store 제거, refcount 최적화 등이 있습니다.
HHVM 표현이 Cinder 표현과 비슷해 보이는 이유가 궁금하다면, Brett Simmers 같은 일부 전 HHVM 엔지니어들이 Cinder에서도 일했기 때문입니다!
(참고로 저는 GitHub에 있는 ART 포크를 링크하지만, 업스트림 코드는 googlesource에 호스팅되어 있습니다.)
Android의 ART Java runtime도 효과 표현에 비트셋을 사용합니다. nodes.h의 SideEffects라는 매우 компакт한 클래스입니다.
이 부작용들은 루프 불변 코드 이동, global value numbering, write barrier 제거, 스케줄링 등에서 사용됩니다.
CoreCLR은 SideEffectSet 클래스에 대해 대체로 비트셋을 사용합니다. 다만 흥미로운 점은, 로컬 변수 집합(LclVarSet)을 포함하도록 효과를 따로 분리한다는 것입니다.
V8도 트렌치코트 하나에 완전히 다른 컴파일러 여섯 개쯤이 들어 있습니다.
Turboshaft는 operations.h의 OpEffects라는 구조체를 쓰는데, 효과의 읽기/쓰기를 위한 두 개의 비트셋입니다. 이것은 value numbering과 그 외 여러 작은 최적화 패스(그들이 “reducers”라고 부르는 것들)에서 사용됩니다.
Maglev도 IR 노드에 있는 NodeT::kProperties라는 것을 가지고 있는데, 이것도 비트셋처럼 보이며 다양한 reducer에서 사용됩니다. can_eager_deopt, can_write 같은 효과 질의 메서드도 있습니다.
최근까지 V8은 Sea of Nodes를 IR 표현으로 사용했는데, 그 또한 IR의 구조 자체에서 부작용을 더 명시적으로 추적합니다.
Guile Scheme은 커스텀 태깅 스킴 같은 방식을 쓰는 것으로 보입니다.
비트셋과 정수 범위는 모두 IR의 힙 효과를 표현하는 데 완전히 그럴듯(cromulent)한 방법입니다. Sea of Nodes 접근도 HotSpot C2를 구동하고 (한동안) V8도 구동했으니 아마 괜찮을 겁니다.
분석을 할 때 IR에 대해 _올바른 질문_을 던지는 것을 잊지 마세요.
Fil Pizlo가 최초의 GitHub Gist를 써서 저를 이 여정으로 이끌어 준 것에 감사드리고, 설명을 더 도움이 되게 다듬는 데 피드백을 준 Chris Gregory, Brett Simmers, Ufuk Kayserilioglu에게도 감사드립니다.