# swc를 위한 구글 클로져 컴파일러 분석 ## 글을 쓰는 이유 삼대구년만에 공부한 김에 공부한 걸 기록으로 남기려고 한다. 물론 이것도 공부라고 하기엔 좀 애매할 수 있지만... 내 기준에선 이 정도면 공부다. 난 원래 남의 코드를 보지 않는다. 내가 원하는 건 이것저것 시도해보면서 얻어지는 사고방식이지 결과물로 남아있는 코드가 아니라서 그렇다. 사실 내가 머리가 좀 좋다. 그래서 난 어지간하면 내가 혼자 생각해내려고 노력한다. 그래서 [swc][]에는 독창적인 시스템이 굉장히 많다. 그런데 이번에 코드를 본 건 이번에 구현하려는 게 이론 지식이 아예 없는 내가 혼자 생각해내기엔 지나치게 이론적인 배경 지식이 많이 필요할 것 같아서이다. 그리고 코드를 보니까 그 생각은 맞았다. 직관으로 때려맞추기엔 많이 복잡해보여서 제대로 읽고 글로 남기게 되었다. ## 프로젝트 구조 파악 내가 구현하려는 건 변수 이름을 재사용하는 패스였다. 구글 클로져 컴파일러 소스코드를 다 읽어볼 순 없으니까 일단 깃허브 기능으로 `reuse`를 검색했다. 소스코드에 주석으로 reuse가 들어가 있을 수도 있지만, 테스트 이름에 있을 확률이 더 높을 거라고 생각하고 보다보니까 [CoalesceVariableNamesTest.java](https://github.com/google/closure-compiler/blob/7ff6e25843097791416d1544c88dc8711f6be64a/test/com/google/javascript/jscomp/CoalesceVariableNamesTest.java)에 테스트가 존재하더라. 그래서 보니까 [CoalesceVariableNames.java](https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java) 가 있었다. 참고로 난 모든 걸 이해할 생각이 아니었고, 흐름만 완전히 파악하는 게 목표였다. ## `CoalesceVariableNames.java` 분석 1 일단 클래스 주석부터 읽어봤다. ```java /** * Reuse variable names if possible. * *

For example, from var x = 1; print(x); var y = 2; print(y); * to var x = 1; print(x); x = 2; print(x). The benefits are * slightly shorter code because of the removed var declaration, * less unique variables in hope for better renaming, and finally better gzip * compression. * *

The pass operates similar to a typical register allocator found in an * optimizing compiler by first computing live ranges with * {@link LiveVariablesAnalysis} and a variable interference graph. Then it uses * graph coloring in {@link GraphColoring} to determine which two variables can * be merge together safely. */ ``` > ... > 네? 정리해보면 - 일반적인 컴파일러의 register allocator 와 비슷하다 - live variable analysis를 사용한다 - variable inference graph 라는 이름만 들어도 구현이 두려운 무언가를 사용한다 - graph coloring은 또 뭐람 모르는 게 너무 많아서 그냥 코드나 보기로 했다. ### 스코프 처리 코드 내리다가 흥미로운 함수를 발견했는데, `enterScope`이다. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java#L132-L177 ```java @Override public void enterScope(NodeTraversal t) { AllVarsDeclaredInFunction allVarsDeclaredInFunction = shouldOptimizeScope(t); if (allVarsDeclaredInFunction == null) { shouldOptimizeScopeStack.push(false); return; } shouldOptimizeScopeStack.push(true); Scope scope = t.getScope(); checkState(scope.isFunctionScope(), scope); // live variables analysis is based off of the control flow graph ControlFlowGraph cfg = t.getControlFlowGraph(); liveness = new LiveVariablesAnalysis( cfg, scope, null, compiler, this.scopeCreator, allVarsDeclaredInFunction); if (FeatureSet.ES3.contains(compiler.getOptions().getOutputFeatureSet())) { // If the function has exactly 2 params, mark them as escaped. This is a work-around for a // bug in IE 8 and below, where it throws an exception if you write to the parameters of the // callback in a sort(). See http://blickly.github.io/closure-compiler-issues/#58 and // https://www.zachleat.com/web/array-sort/ Node enclosingFunction = scope.getRootNode(); if (NodeUtil.getFunctionParameters(enclosingFunction).hasTwoChildren()) { liveness.markAllParametersEscaped(); } } liveness.analyze(); liveAnalyses.push(liveness); // The interference graph has the function's variables as its nodes and any interference // between the variables as the edges. Interference between two variables means that they are // alive at overlapping times, which means that their variable names cannot be coalesced. UndiGraph interferenceGraph = computeVariableNamesInterferenceGraph(cfg, liveness.getEscapedLocals()); // Color any interfering variables with different colors and any variables that can be safely // coalesced wih the same color. GraphColoring coloring = new GreedyGraphColoring<>(interferenceGraph, coloringTieBreaker); coloring.color(); colorings.push(coloring); } ``` 함수 스코프를 처리하는 패스고, liveness 라는 것 보니까 대충 변수가 언제까지 살아있는지에 대한 것이라고 생각하고 넘어갔다. 오래된 브라우저 버그 처리하고 variable inference graph를 만든 뒤 그 그래프를 사용해 `GreedyGraphColoring`으로 처리를 하는 것 같다. ### 이름 변경 코드 저걸 본 뒤 실제 이름 변경을 수정하는 코드를 찾아봤는데 https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java#L189-L257 인 것 같았다. ```java @Override public void visit(NodeTraversal t, Node n, Node parent) { if (colorings.isEmpty() || !n.isName() || parent.isFunction()) { // Don't rename named functions. return; } Var var = liveness.getAllVariables().get(n.getString()); GraphNode vNode = colorings.peek().getGraph().getNode(var); if (vNode == null) { // This is not a local. return; } Var coalescedVar = colorings.peek().getPartitionSuperNode(var); if (!usePseudoNames) { if (vNode.getValue().equals(coalescedVar)) { // The coalesced name is itself, nothing to do. return; } // Rename. n.setString(coalescedVar.getName()); compiler.reportChangeToEnclosingScope(n); if (NodeUtil.isNameDeclaration(parent) || (NodeUtil.getEnclosingType(n, Token.DESTRUCTURING_LHS) != null && NodeUtil.isLhsByDestructuring(n))) { makeDeclarationVar(coalescedVar); removeVarDeclaration(n); } } else { // This code block is slow but since usePseudoName is for debugging, // we should not sacrifice performance for non-debugging compilation to // make this fast. Set allMergedNames = new TreeSet<>(); for (Var iVar : liveness.getAllVariablesInOrder()) { // Look for all the variables that can be merged (in the graph by now) // and it is merged with the current coalescedVar. if (colorings.peek().getGraph().getNode(iVar) != null && coalescedVar.equals(colorings.peek().getPartitionSuperNode(iVar))) { allMergedNames.add(iVar.getName()); } } // Keep its original name. if (allMergedNames.size() == 1) { return; } String pseudoName = Joiner.on("_").join(allMergedNames); while (t.getScope().hasSlot(pseudoName)) { pseudoName += "$"; } // Rename. n.setString(pseudoName); compiler.reportChangeToEnclosingScope(n); if (!vNode.getValue().equals(coalescedVar) && (NodeUtil.isNameDeclaration(parent) || (NodeUtil.getEnclosingType(n, Token.DESTRUCTURING_LHS) != null && NodeUtil.isLhsByDestructuring(n)))) { makeDeclarationVar(coalescedVar); removeVarDeclaration(n); } } } ``` 이 부분은 상당히 직관적이었다. 디버깅용 코드가 끼어있어서 복잡한거지 실제 코드는 상당히 간단하다. ### 변수 그래프 생성 코드 위에 스코프 분석 코드를 보면 알겠지만 결국 마지막에 남는 건 `GraphColoring`이고, 그건 `interferenceGraph`이라는 변수에 저장된 데이터를 사용한다. 그러므로 다음으로 분석할 코드는 `computeVariableNamesInterferenceGraph`이다. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java#L259-L386 ```java private UndiGraph computeVariableNamesInterferenceGraph( ControlFlowGraph cfg, Set escaped) { UndiGraph interferenceGraph = LinkedUndirectedGraph.create(); // First create a node for each non-escaped variable. We add these nodes in the order in which // they appear in the code because we want the names that appear earlier in the code to be used // when coalescing to variables that appear later in the code. Var[] orderedVariables = liveness.getAllVariablesInOrder().toArray(new Var[0]); // index i in interferenceGraphNodes is set to true when interferenceGraph // has node orderedVariables[i] BitSet interferenceGraphNodes = new BitSet(); // interferenceBitSet[i] = indices of all variables that should have an edge with // orderedVariables[i] BitSet[] interferenceBitSet = new BitSet[orderedVariables.length]; Arrays.setAll(interferenceBitSet, i -> new BitSet()); int vIndex = -1; for (Var v : orderedVariables) { vIndex++; if (escaped.contains(v)) { continue; } // NOTE(user): In theory, we CAN coalesce function names just like any variables. Our // Liveness analysis captures this just like it as described in the specification. However, we // saw some zipped and unzipped size increase after this. We are not totally sure why // that is but, for now, we will respect the dead functions and not play around with it if (v.getParentNode().isFunction()) { continue; } // NOTE: we skip class declarations for a combination of two reasons: // 1. they are block-scoped, so we would need to rewrite them as class expressions // e.g. `class C {}` -> `var C = class {}` to avoid incorrect semantics // (see testDontCoalesceClassDeclarationsWithDestructuringDeclaration). // This is possible but increases pre-gzip code size and complexity. // 2. since function declaration coalescing seems to cause a size regression (as discussed // above) we assume that coalescing class names may cause a similar size regression. if (v.getParentNode().isClass()) { continue; } // Skip lets and consts that have multiple variables declared in them, otherwise this produces // incorrect semantics. See test case "testCapture". // Skipping vars technically isn't needed for correct semantics, but works around a Safari // bug for var redeclarations (https://github.com/google/closure-compiler/issues/3164) if (isInMultipleLvalueDecl(v)) { continue; } interferenceGraph.createNode(v); interferenceGraphNodes.set(vIndex); } // Go through every CFG node in the program and look at variables that are live. // Set the pair of live variables in interferenceBitSet so we can add an edge between them. for (DiGraphNode cfgNode : cfg.getNodes()) { if (cfg.isImplicitReturn(cfgNode)) { continue; } LinearFlowState state = cfgNode.getAnnotation(); // Check the live states and add edge when possible. An edge between two variables // means that they are alive at overlapping times, which means that their // variable names cannot be coalesced. LiveVariableLattice livein = state.getIn(); for (int i = livein.nextSetBit(0); i >= 0; i = livein.nextSetBit(i + 1)) { for (int j = livein.nextSetBit(i); j >= 0; j = livein.nextSetBit(j + 1)) { interferenceBitSet[i].set(j); } } LiveVariableLattice liveout = state.getOut(); for (int i = liveout.nextSetBit(0); i >= 0; i = liveout.nextSetBit(i + 1)) { for (int j = liveout.nextSetBit(i); j >= 0; j = liveout.nextSetBit(j + 1)) { interferenceBitSet[i].set(j); } } LiveRangeChecker liveRangeChecker = new LiveRangeChecker(cfgNode.getValue(), orderedVariables, state); liveRangeChecker.check(cfgNode.getValue()); liveRangeChecker.setCrossingVariables(interferenceBitSet); } // Go through each variable and try to connect them. int v1Index = -1; for (Var v1 : orderedVariables) { v1Index++; int v2Index = -1; for (Var v2 : orderedVariables) { v2Index++; // Skip duplicate pairs. Also avoid merging a variable with itself. if (v1Index > v2Index) { continue; } if (!interferenceGraphNodes.get(v1Index) || !interferenceGraphNodes.get(v2Index)) { // Skip nodes that were not added. They are globals and escaped locals. continue; } if ((v1.isParam() && v2.isParam()) || interferenceBitSet[v1Index].get(v2Index)) { // Add an edge between variable pairs that are both parameters // because we don't want parameters to share a name. interferenceGraph.connectIfNotFound(v1, null, v2); } } } return interferenceGraph; } ``` 일단 변수를 선언된 순서대로 정렬한다. 내가 하려는 작업을 생각하면 당연한 동작이다. 그리고 비트셋을 사용한다. 성능 목적일테니 그리 중요한 건 아니다. 우선 첫번쨰 루프문에서 'escape' 여부 확인하고, 클래스 / 함수 / 변수 같은 종류 중 변수만 골라서 그래프에 넣는다. 두번쨰 루프에서는 liveness 데이터를 이용해 `BitSet`을 수정한다. 뭔가 타입이 굉장히 많고, `getAnnotation` 이란 이름하고 타입 이름이 안 맞는 것 같아서 보니까 control flow graph의 각 노드와 엣지에 메타데이터를 붙일 수 있게 되어있었다. `LiveRangeChecker`라는 타입을 사용하는데, 얘는 먼저 `liveness` 관련 패스들의 흐름도를 안 뒤에 보는 게 좋을 것 같아서 미뤘다. 마지막 루프는 간단하다. 이름을 바꿀 수 있으면 바꾼다. 물론 파라미터 이름을 다른 파라미터의 이름으로 바꾸진 않는다. ```js function a(b, c) {} ``` 를 ```js function a(b, b) {} ``` 처럼 바꾸지 않는다는 소리다. ## `DataFlowAnalysis.java` 분석 일단 메인 파일 로직은 이해했고, 이걸 구현하려면 이제 control flow graph와 liveness 데이터를 분석하는 코드를 보면 된다. [LiveVariablesAnalysis.java](https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/LiveVariablesAnalysis.java)를 열었다. 그런데 로직이 많지 않았다. 그래서 부모 클래스인 [DataFlowAnalysis.java](https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/DataFlowAnalysis.java)를 먼저 분석했다. ### `analyze` 분석 우선 메인 파일에서 호출했던 `analyze()`를 먼저 살펴봤다. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/DataFlowAnalysis.java#L215-L241 ```java final void analyze() { initialize(); while (!this.workQueue.isEmpty()) { DiGraphNode curNode = this.workQueue.removeFirst(); LinearFlowState curState = curNode.getAnnotation(); if (curState.stepCount++ > MAX_STEPS_PER_NODE) { throw new IllegalStateException("Dataflow analysis appears to diverge around: " + curNode); } joinInputs(curNode); if (flow(curNode)) { // If there is a change in the current node, we want to grab the list // of nodes that this node affects. List> nextNodes = isForward() ? cfg.getDirectedSuccNodes(curNode) : cfg.getDirectedPredNodes(curNode); for (DiGraphNode nextNode : nextNodes) { if (nextNode != cfg.getImplicitReturn()) { this.workQueue.add(nextNode); } } } } if (isForward()) { joinInputs(getCfg().getImplicitReturn()); } } ``` 생각보다 간단했다. 직관적으로 보이는 것들은 일단 - 작업 큐를 사용한다 - `joinInputs`라는 함수를 사용한다. 리턴값이 없는 것으로 봐서 얘가 실제 데이터를 수정하는 함수일 것이다. - `flow`라는 함수는 다음 노드를 방문할지말지 결정하는데 사용된다. ### `joinInputs` 분석 실제 데이터를 수정하는 로직일테니 먼저 살펴봤다. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/DataFlowAnalysis.java#L314-L348 ```java private void joinInputs(DiGraphNode node) { LinearFlowState state = node.getAnnotation(); if (this.isForward() && cfg.getEntry() == node) { state.setIn(createEntryLattice()); return; } List> inEdges = this.isForward() ? node.getInEdges() : node.getOutEdges(); final L result; switch (inEdges.size()) { case 0: return; case 1: result = this.getInputFromEdge(inEdges.get(0)); break; default: { FlowJoiner joiner = this.createFlowJoiner(); for (DiGraphEdge inEdge : inEdges) { joiner.joinFlow(this.getInputFromEdge(inEdge)); } result = joiner.finish(); } } if (this.isForward()) { state.setIn(result); } else { state.setOut(result); } } ``` 대충 그래프에서 Edge를 가지고 와서 연결하는 코드인 것 같은데, `private` 함수이므로 `joiner.joinFlow`가 이 함수를 재귀적으로 호출할리는 없다. 그리고 반복문도 없다. 따라서 이 함수는 `node` 한 개만 처리하는 함수일 것이다. 현재 BB (basic block)으로 들어오는 경우의 수에 따라 분기하는 것 같고, 개수가 1일 때의 로직과 2 이상일 때의 로직은 결국 비슷할 것이다. 대충 흐름도가 보여서 이 함수는 여기까지만 분석하고 넘어가기로 했다. ### `flow` 분석 https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/DataFlowAnalysis.java#L277-L306 ```java /** * Performs a single flow through a node. * * @return {@code true} if the flow state differs from the previous state. */ private boolean flow(DiGraphNode node) { LinearFlowState state = node.getAnnotation(); if (isForward()) { L outBefore = state.getOut(); state.setOut(flowThrough(node.getValue(), state.getIn())); boolean changed = !outBefore.equals(state.getOut()); if (this.isBranched()) { FlowBrancher brancher = this.createFlowBrancher(node.getValue(), state.getOut()); for (DiGraphEdge outEdge : node.getOutEdges()) { L outBranchBefore = outEdge.getAnnotation(); outEdge.setAnnotation(brancher.branchFlow(outEdge.getValue())); if (!changed) { changed = !outBranchBefore.equals(outEdge.getAnnotation()); } } } return changed; } else { L inBefore = state.getIn(); state.setIn(flowThrough(node.getValue(), state.getOut())); return !inBefore.equals(state.getIn()); } } ``` `analyze()`에서 `flow`가 다음 노드 방문 여부를 결정하는 역할을 했고, 코드를 보니 변경 여부를 확인하는 것 같았다. 이 정도까지만 알아도 흐름도를 그리는 데엔 문제 없을 것 같아서 넘어갔다. ## `LiveVariablesAnalysis.java` 분석 ### `flowThrough` 분석 위 클래스를 볼 때는 대충 봐서 몰랐는데 `flowThrough`가 있길래 이것부터 살펴봤다. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/LiveVariablesAnalysis.java#L219-L238 ```java @Override LiveVariableLattice flowThrough(Node node, LiveVariableLattice input) { final BitSet gen = new BitSet(input.liveSet.size()); final BitSet kill = new BitSet(input.liveSet.size()); // Make kills conditional if the node can end abruptly by an exception. boolean conditional = false; List> edgeList = getCfg().getOutEdges(node); for (DiGraphEdge edge : edgeList) { if (Branch.ON_EX.equals(edge.getValue())) { conditional = true; } } computeGenKill(node, gen, kill, conditional); LiveVariableLattice result = new LiveVariableLattice(input); // L_in = L_out - Kill + Gen result.liveSet.andNot(kill); result.liveSet.or(gen); return result; } ``` 딱봐도 `computeGenKill`이 메인이고, 아마 얘는 새로 생성되는 변수와 스코프에서 사라지는 변수를 계산하는 함수일 것이다. 그러면 굳이 구현을 볼 필요가 없다. 물론 나중에 러스트로 포팅하면서 볼 것이지만, 내 목적은 완전한 흐름도다. ## 코드 흐름 그래프 (control flow graph) 이건 분석하지 않았다. Deno lint 룰 중에서 control flow graph가 필요한 린트 룰들은 내가 구현했는데, 그래서 어느 정도까지는 알고 있고, 러스트로 포팅하다가 필요하면 그때 볼 생각이다. ## `CoalesceVariableNames.java` 분석 2 ### `LiveRangeChecker` 분석 아까 미뤄뒀던 것인데 같은 파일에 있더라. https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java#L522-L619 ```java void check(Node n) { // For most AST nodes, traverse the subtree in postorder because that's how the expressions // are evaluated. if (n == root || !ControlFlowGraph.isEnteringNewCfgNode(n)) { if ((n.isDestructuringLhs() && n.hasTwoChildren()) || (n.isAssign() && n.getFirstChild().isDestructuringPattern()) || n.isDefaultValue()) { // Evaluate the rhs of a destructuring assignment/declaration before the lhs. check(n.getSecondChild()); check(n.getFirstChild()); } else { for (Node c = n.getFirstChild(); c != null; c = c.getNext()) { check(c); } } if (shouldVisit(n)) { visit(n, n.getParent()); } } } ``` 중요한 메소드는 이것인 것 같았다. 보니까 해석 순서에 맞춰서 `check`이나 `visit`을 호출하는 함수였다. `visit`은 https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/CoalesceVariableNames.java#L564-L578 ```java void visit(Node n, Node parent) { for (int iVar = 0; iVar < orderedVariables.length; iVar++) { if (isAssignTo(orderedVariables[iVar], n, parent)) { isAssignToList.add(iVar); } } if (!isAssignToList.isEmpty()) { for (int iVar = 0; iVar < orderedVariables.length; iVar++) { boolean varOutLive = state.getOut().isLive(iVar); if (varOutLive || isReadFrom(orderedVariables[iVar], n)) { isReadFromList.add(iVar); } } } } ``` 변수에 할당하는 것과 변수의 값을 사용하는 걸 읽어와서 기록하는 함수였다. ## 마무리 Graph coloring은 러스트로 구현할 때 분석해도 될 것 같아서 말았다. 어쩌면 글을 하나 더 쓸 수도 있다. 원래 최대한 작업을 줄일 생각이었는데 보니까 코드들이 전반적으로 유용해보여서 최대한 유사하게 구현할 생각이다. 그리고 글을 제대로 쓰려다가 귀찮아져서 그냥 분석한 걸 적었다. 그러다보니 글이라기보단 분석 노트처럼 됐는데... 알 게 뭐람. --- [swc]: https://swc.rs