글을 쓰는 이유

삼대구년만에 공부한 김에 공부한 걸 기록으로 남기려고 한다. 물론 이것도 공부라고 하기엔 좀 애매할 수 있지만... 내 기준에선 이 정도면 공부다.

난 원래 남의 코드를 보지 않는다. 내가 원하는 건 이것저것 시도해보면서 얻어지는 사고방식이지 결과물로 남아있는 코드가 아니라서 그렇다.

사실 내가 머리가 좀 좋다. 그래서 난 어지간하면 내가 혼자 생각해내려고 노력한다. 그래서 swc에는 독창적인 시스템이 굉장히 많다. 그런데 이번에 코드를 본 건 이번에 구현하려는 게 이론 지식이 아예 없는 내가 혼자 생각해내기엔 지나치게 이론적인 배경 지식이 많이 필요할 것 같아서이다. 그리고 코드를 보니까 그 생각은 맞았다. 직관으로 때려맞추기엔 많이 복잡해보여서 제대로 읽고 글로 남기게 되었다.

프로젝트 구조 파악

내가 구현하려는 건 변수 이름을 재사용하는 패스였다. 구글 클로져 컴파일러 소스코드를 다 읽어볼 순 없으니까 일단 깃허브 기능으로 reuse를 검색했다. 소스코드에 주석으로 reuse가 들어가 있을 수도 있지만, 테스트 이름에 있을 확률이 더 높을 거라고 생각하고 보다보니까 CoalesceVariableNamesTest.java에 테스트가 존재하더라. 그래서 보니까 CoalesceVariableNames.java 가 있었다.

참고로 난 모든 걸 이해할 생각이 아니었고, 흐름만 완전히 파악하는 게 목표였다.

CoalesceVariableNames.java 분석 1

일단 클래스 주석부터 읽어봤다.

/**
 * Reuse variable names if possible.
 *
 * <p>For example, from <code>var x = 1; print(x); var y = 2; print(y); </code>
 * to <code>var x = 1; print(x); x = 2; print(x)</code>. The benefits are
 * slightly shorter code because of the removed <code>var<code> declaration,
 * less unique variables in hope for better renaming, and finally better gzip
 * compression.
 *
 * <p>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

  @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<Node> 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<Var, Void> 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<Var, Void> 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 인 것 같았다.

 @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<Var, Void> 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<String> 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

  private UndiGraph<Var, Void> computeVariableNamesInterferenceGraph(
      ControlFlowGraph<Node> cfg, Set<? extends Var> escaped) {
    UndiGraph<Var, Void> 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<Node, Branch> cfgNode : cfg.getNodes()) {
      if (cfg.isImplicitReturn(cfgNode)) {
        continue;
      }

      LinearFlowState<LiveVariableLattice> 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 관련 패스들의 흐름도를 안 뒤에 보는 게 좋을 것 같아서 미뤘다.

마지막 루프는 간단하다. 이름을 바꿀 수 있으면 바꾼다. 물론 파라미터 이름을 다른 파라미터의 이름으로 바꾸진 않는다.

function a(b, c) {}

를

function a(b, b) {}

처럼 바꾸지 않는다는 소리다.

DataFlowAnalysis.java 분석

일단 메인 파일 로직은 이해했고, 이걸 구현하려면 이제 control flow graph와 liveness 데이터를 분석하는 코드를 보면 된다. LiveVariablesAnalysis.java를 열었다. 그런데 로직이 많지 않았다. 그래서 부모 클래스인 DataFlowAnalysis.java를 먼저 분석했다.

analyze 분석

우선 메인 파일에서 호출했던 analyze()를 먼저 살펴봤다.

https://github.com/google/closure-compiler/blob/3a5d7f7d86867ba950f1a84d11d120bc4cf96de7/src/com/google/javascript/jscomp/DataFlowAnalysis.java#L215-L241

  final void analyze() {
    initialize();
    while (!this.workQueue.isEmpty()) {
      DiGraphNode<N, Branch> curNode = this.workQueue.removeFirst();
      LinearFlowState<L> 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<? extends DiGraphNode<N, Branch>> nextNodes =
            isForward() ? cfg.getDirectedSuccNodes(curNode) : cfg.getDirectedPredNodes(curNode);

        for (DiGraphNode<N, Branch> 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

  private void joinInputs(DiGraphNode<N, Branch> node) {
    LinearFlowState<L> state = node.getAnnotation();
    if (this.isForward() && cfg.getEntry() == node) {
      state.setIn(createEntryLattice());
      return;
    }

    List<? extends DiGraphEdge<N, Branch>> 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<L> joiner = this.createFlowJoiner();
          for (DiGraphEdge<N, Branch> 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

  /**
   * Performs a single flow through a node.
   *
   * @return {@code true} if the flow state differs from the previous state.
   */
  private boolean flow(DiGraphNode<N, Branch> node) {
    LinearFlowState<L> 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<L> brancher = this.createFlowBrancher(node.getValue(), state.getOut());
        for (DiGraphEdge<N, Branch> 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

  @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<? extends DiGraphEdge<Node, Branch>> edgeList = getCfg().getOutEdges(node);
    for (DiGraphEdge<Node, Branch> 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

    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

    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은 러스트로 구현할 때 분석해도 될 것 같아서 말았다. 어쩌면 글을 하나 더 쓸 수도 있다.

원래 최대한 작업을 줄일 생각이었는데 보니까 코드들이 전반적으로 유용해보여서 최대한 유사하게 구현할 생각이다.

그리고 글을 제대로 쓰려다가 귀찮아져서 그냥 분석한 걸 적었다. 그러다보니 글이라기보단 분석 노트처럼 됐는데... 알 게 뭐람.

---