JDK-8392942 기여기: ConvL2I의 놓친 Ideal 최적화

이슈 내용
배경지식: GVN과 IGVN
1. GVN과 IGVN
2. IGVN과 worklist
재현
원인 분석
1. ConvL2INode::Ideal
2. 그래프의 변화
수정 내용
마무리
기타
1. user란?

연휴로 시간이 남아 오랜만에 OpenJDK 에 기여를 시도해보았다. 이번에는 JDK-8392942에 기여해보기로 했다.

이슈의 제목은 다음과 같다.

C2: Missed Ideal optimization opportunity for ConvL2I

예전에 JDK-8377309를 하면서 봤던 유형의 버그이기도 하다. 그때는 이미 다른 사람이 고친 걸 확인하고 예외 처리를 지우는 작업이었다면, 이번에는 직접 원인을 찾아서 고쳐야 했다.

이슈 내용

이슈 본문은 다음과 같다.

Reproduced by a generated fuzzy test (attached), against Java 28+17-1259 There are similar bugs (JDK-8389579 for CompressBits and JDK-8385093 for RShiftI), but nothing for ConvL2I.

자동 생성된 퍼징 테스트(첨부)로 Java 28+17-1259에서 재현했다. 비슷한 버그(CompressBits는 JDK-8389579, RShiftI는 JDK-8385093)는 있지만, ConvL2I에 대한 것은 없다.

hs_err 로그에는 이런 assert가 찍혀 있었다.

# assert(false) failed: Missed Ideal optimization opportunity in PhaseIterGVN for ConvL2I

리포터가 첨부한 축소 재현 코드는 다음과 같다.

public class Test {
    static int iFld;

    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            test();
        }
    }

    static void test() {
        for (int i = 0; i < 2; i++) {
            iFld = (int) (iFld & i - 5L >>> 32);
        }
    }
}

i가 0 또는 1뿐이라 (i - 5L) >>> 32는 항상 0xFFFFFFFF가 되고 결국 iFld에 iFld를 그대로 다시 넣는 코드이다.

i가 0일 때 i - 5L은 -5이고, 이를 >>> 32 하면 0xFFFFFFFF가 된다

i가 1이면 -4(...1100)라 하위 비트만 다르고, 결과는 똑같이 0xFFFFFFFF다.

배경지식: GVN과 IGVN

원인을 보기 전에 용어를 먼저 정리해두자. (GVN 자체는 이전에 Value Numbering (GVN, LVN)에서, Ideal Graph와 노드는 OpenJDK C2 컴파일러의 노드 클래스 이해하기에서 정리해두었다.)

GVN과 IGVN

GVN은 같은 값을 계산하는 식을 찾아 하나로 합치는 최적화다. C2에서는 PhaseGVN이 이 역할을 하는데, 바이트코드를 파싱하면서 노드를 만들 때마다 그 자리에서 노드를 한 번씩 다듬고, 이미 같은 노드가 있으면 그걸 재사용한다.

문제는 노드를 만드는 시점에는 아직 그래프 전체가 완성되지 않았다는 점이다. 나중에 다른 노드가 바뀌면 앞서 만든 노드에도 새로 최적화할 거리가 생기는데, 한 번만 보고 지나가는 GVN은 이걸 놓친다. 그래서 그래프가 완성된 뒤에는 IGVN(Iterative GVN, PhaseIterGVN) 이 바뀐 노드 주변을 더 이상 변화가 없을 때까지 반복해서 다시 최적화한다. 즉 IGVN은 GVN을 한 번이 아니라 반복해서 돌리는 버전이다.

IGVN과 worklist

IGVN의 구조는 단순하다.

최적화해볼 노드들을 worklist에 넣는다.
worklist에서 노드를 하나 꺼내 Ideal()(더 나은 형태로 변환), Value()(타입 계산), Identity()(같은 값을 가진 기존 노드로 대체)를 호출한다.
노드가 바뀌면 그 노드를 사용하는 노드(user)들을 다시 worklist에 넣는다. 입력이 바뀌었으니 user 쪽에도 새로 최적화할 거리가 생겼을 수 있기 때문이다.
worklist가 빌 때까지 반복한다.

문제는 3번이다. 기본적으로는 바뀐 노드의 직접 user만 worklist에 들어간다. 그런데 어떤 노드의 Ideal()이 입력의 입력까지 들여다본다면 어떻게 될까? 입력의 입력이 바뀌어도 그 노드는 다시 방문되지 않는다.

그래서 HotSpot에는 이런 “두 단계 떨어진 관계”를 따로 챙겨주는 함수가 있다. PhaseIterGVN::add_users_of_use_to_worklist()다.

void PhaseIterGVN::add_users_to_worklist(Node* n, Unique_Node_List& worklist) {
  add_users_to_worklist0(n, worklist);

  // Move users of node to worklist
  for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
    Node* use = n->fast_out(i); // Get use
    add_users_of_use_to_worklist(n, use, worklist);
  }
}

n이 바뀐 노드, use가 n의 user다. add_users_of_use_to_worklist() 안에는 “use가 이런 종류의 노드면, use의 user 중 이런 종류도 worklist에 넣어라”라는 규칙이 수십 개 나열되어 있다. Ideal()에 입력의 입력을 보는 패턴을 하나 추가할 때마다 여기에도 규칙을 하나 추가해줘야 하는 구조고, 이걸 빠뜨리면 최적화 기회를 놓친다. 이번 이슈가 바로 그런 경우였는데, 잠시 후에 자세히 보겠다.

재현

fastdebug 빌드에서 리포터의 코드를 돌려보니 바로 재현됐다. 명령에 쓴 VerifyIterativeGVN은 IGVN이 끝난 뒤 놓친 최적화가 없는지 검사하는 디버그 플래그다.

java -Xbatch -XX:VerifyIterativeGVN=1110 \
     -XX:CompileCommand=quiet -XX:CompileCommand=compileonly,*Test*::* \
     -XX:-CreateCoredumpOnCrash Test.java

#  assert(false) failed: Missed Ideal optimization opportunity in PhaseIterGVN for ConvL2I
...
Current CompileTask:
C2:3468  104    b  4       Test::test (32 bytes)
...
V  [libjvm.dylib+0xfb6a2c]  PhaseIterGVN::verify_Ideal_for(Node*, bool, bool)+0x448

assert 바로 위, 표준 출력에는 이런 덤프가 함께 찍힌다.

Missed Ideal optimization (can_reshape=false):
The node was reshaped by Ideal.
The result after Ideal:
dist dump
---------------------------------------------
   1  103  ConvI2L  === _ 147  [[ 111 112 ]]  #long:minint..maxint, ... (line 12)
   0  112  ConvL2I  === _ 103  [[ 114 147 ]]  #int !jvms: Test::test @ bci:21 (line 12)

여기서 이슈를 해결하기 위해서는 이 덤프가 무엇을 출력하는지 이해해야 한다.

1. 덤프는 무엇을 출력하는가

이 메시지를 출력하는 곳은 PhaseIterGVN::verify_Ideal_for()(src/hotspot/share/opto/phaseX.cpp)다. IGVN이 끝나면 verify_optimize()가 그래프의 모든 노드를 돌면서 Ideal()을 can_reshape=false, true로 한 번씩 더 불러본다. 이때 nullptr이 아닌 값이 돌아오면 아래 코드로 넘어온다.

  // We just saw a new Idealization which was not done during IGVN.
  stringStream ss; // Print as a block without tty lock.
  ss.cr();
  ss.print_cr("Missed Ideal optimization (can_reshape=%s):", can_reshape ? "true": "false");
  if (i == n) {
    ss.print_cr("The node was reshaped by Ideal.");
  } else {
    ss.print_cr("The node was replaced by Ideal.");
    ss.print_cr("Old node:");
    n->dump_bfs(1, nullptr, "", &ss);
  }
  ss.print_cr("The result after Ideal:");
  i->dump_bfs(1, nullptr, "", &ss);

Ideal()이 돌려주는 값에 따라 메시지가 갈린다.

replaced: 새 노드를 만들어 돌려준 경우다. 이때는 Old node:로 이전 상태도 같이 출력된다.
reshaped: 새 노드를 만들지 않고 자기 자신의 입력만 바꾼 뒤 this를 돌려준 경우다. 이전 상태는 출력되지 않고, 바뀐 뒤의 모습만 남는다.

이번에는 reshaped 다. 그래서 덤프만으로는 ConvL2I의 입력이 원래 무엇이었는지 바로 알 수 없다.

2. 바뀌기 전 입력 추측하기

1번에서 본 것처럼 이번 덤프는 reshaped, 즉 112번이 자기 입력만 바꾼 경우다. 그러니 덤프의 112 ConvL2I === _ 103(112번의 입력이 103번)은 원래 있던 연결이 아니라 검증 단계에서 새로 생긴 것이다.

바뀌기 전:  112 ConvL2I ──▶ ??? ──▶ 103 ConvI2L
바뀐 후:    112 ConvL2I ──────────▶ 103 ConvI2L

가운데 노드(???)를 건너뛰고 그 입력에 바로 붙었다면, ???도 원래 103번을 입력으로 쓰고 있었을 것이다. 112번이 입력을 바꿨다고 ???가 바로 지워지지는 않으니, 103번의 user 목록에도 아직 남아 있을 수 있다. 덤프의 103 ConvI2L === _ 147 [[ 111 112 ]]를 보면 103번을 쓰는 노드(user)는 111번과 112번이다. 112번을 빼면 남는 건 111번뿐이다. 그래서 111번이 그 가운데 노드일 가능성이 높다. 물론 아직은 추측이라, 아래 3번과 4번에서 확인해본다.

3. reshaped를 돌려주는 경로는 하나뿐이다

ConvL2INode::Ideal() 이 nullptr이 아닌 값을 돌려주는 경로는 세 가지다. (1단계에서 이야기한 것처럼 nullptr이 아닌 값이 돌아왔을 때만 지금과 같은 덤프가 찍힌다.)

경로	돌려주는 값	덤프 메시지
`TypeNode::Ideal()`	`top` 노드 (아니면 `nullptr`)	replaced
`ConvL2I(AddL(x, y))` 분배	새로 만든 `AddI`	replaced
`ConvL2I(AndL(x, 0xFFFFFFFF))` 마스크 제거	`set_req_X()`로 입력을 바꾼 뒤 `this`	reshaped

reshaped가 나올 수 있는 건 마스크 제거 경로뿐이다. 이 경로는 입력을 andl->in(1)로 바꾼다. 따라서 바뀌기 전의 ConvL2I는 AndL(103, 0xFFFFFFFF)를 입력으로 받고 있었다는 결론이 나온다. 2번에서 본 111번이 바로 그 AndL이다.

4. 그래프를 직접 찍어서 확인

여기까지는 코드를 보고 추론한 것이라, 실제 그래프로 한 번 더 확인했다. PrintIdealPhase를 쓰면 원하는 컴파일 단계마다 Ideal Graph를 출력할 수 있다.

java -Xbatch -XX:VerifyIterativeGVN=1110 \
     -XX:CompileCommand=quiet -XX:CompileCommand=compileonly,*Test*::* \
     -XX:CompileCommand=PrintIdealPhase,Test::test,BEFORE_ITER_GVN,AFTER_ITER_GVN \
     -XX:-CreateCoredumpOnCrash Test.java

assert가 나기 직전에 출력된 BEFORE_ITER_GVN 그래프에서 관련 노드만 추리면 다음과 같다.

ConvI2L  === _ 147  [[ 111 ]]
ConvI2L  === _ 93  [[ 108 ]]
ConL  === 0  [[ 108 ]]  #long:-5
AddL  === _ 104 107  [[ 110 ]]
ConI  === 0  [[ 110 ]]  #int:32
URShiftL  === _ 108 109  [[ 111 ]]
AndL  === _ 103 110  [[ 112 ]]
ConvL2I  === _ 111  [[ 114 147 ]]

예상대로 112 ConvL2I의 입력은 111 AndL이고, AndL의 입력은 103 ConvI2L과 110 URShiftL이다. 정리하면 이 덤프는 “ConvL2I의 입력이 원래 AndL이었는데, 검증 단계에서 Ideal()을 부르니 AndL을 건너뛰고 103 ConvI2L에 바로 붙어버렸다”는 뜻이다. IGVN 도중에 했어야 할 변환을 검증 단계에서 처음 한 것이다.

남은 질문은 이 IGVN 동안 110 URShiftL에 무슨 일이 있었길래 0xFFFFFFFF가 되었느냐인데, 아래에서 이어서 보겠다.

원인 분석

ConvL2INode::Ideal

ConvL2I는 long을 int로 바꾸는 (int) 캐스트에 해당하는 노드다. Ideal()은 다음과 같다. (src/hotspot/share/opto/convertnode.cpp)

Node* ConvL2INode::Ideal(PhaseGVN* phase, bool can_reshape) {
  ...
  Node *andl = in(1);
  uint andl_op = andl->Opcode();
  if( andl_op == Op_AndL ) {
    // Blow off prior masking to int
    if( phase->type(andl->in(2)) == TypeLong::make( 0xFFFFFFFF ) ) {
      set_req_X(1,andl->in(1), phase);
      return this;
    }
  }
  ...
}

이 변환은 Java로 치면 (int)(x & 0xFFFFFFFFL) 같은 코드에 해당한다. 여기서 & 0xFFFFFFFFL은 하위 32비트만 남기는 마스크다. 어차피 (int)로 자르면 하위 32비트만 남으니 마스크는 의미가 없다. 그래서 ConvL2I(AndL(x, 0xFFFFFFFF))를 ConvL2I(x)로 바꾼다. 재현 코드에서는 iFld가 x, (i - 5L) >>> 32가 마스크 자리에 있다.

여기서 중요한 점은 이 변환이 andl->in(2)의 타입, 즉 ConvL2I 입장에서 입력의 입력의 타입을 본다는 것이다. 코드를 따라가 보면 이렇다.

ConvL2I ──in(1)──▶ AndL ──in(2)──▶ 마스크 (110 URShiftL)
        └ andl = in(1) ┘   └ andl->in(2) ┘

andl은 ConvL2I의 입력(in(1))이고, andl->in(2)는 그 AndL의 두 번째 입력인 마스크다. ConvL2I에서 출발해 입력을 두 번 따라가야 닿는 노드라서 “입력의 입력”이다. 이 마스크 노드가 바뀌어도 ConvL2I와는 직접 연결되어 있지 않다는 점이 이번 버그의 핵심이다.

그래프의 변화

앞에서 본 ConvL2I → AndL → 마스크 경로를 재현 코드의 표현식 전체로 그리면 대략 이렇다.

ConvL2I
  └─ AndL
       ├─ ConvI2L(iFld)
       └─ URShiftL
            ├─ AddL(ConvI2L(i), -5)
            └─ 32

처음에는 i의 범위가 넓기 때문에 (i - 5L) >>> 32는 상수가 아니다. i - 5L이 음수일 수도 양수일 수도 있으니 결과가 0일 수도 0xFFFFFFFF일 수도 있다.

그런데 루프 최적화를 거치면서 루프 변수 i의 타입이 [0, 1]로 좁혀진다. 그러면 i - 5L은 항상 -5 또는 -4, 즉 항상 음수가 된다. 음수 long을 부호 없이 32비트 오른쪽으로 밀면 상위 32비트가 전부 1이었으므로 결과는 항상 0xFFFFFFFF다. URShiftL이 상수 0xFFFFFFFF로 접힌다.

ConvL2I
  └─ AndL
       ├─ ConvI2L(iFld)
       └─ ConL 0xFFFFFFFF     ← URShiftL이 상수로 바뀜

이제 ConvL2I의 Ideal()이 마스크를 걷어낼 조건이 갖춰졌다. 하지만 IGVN은 이렇게 동작한다.

URShiftL이 바뀌었으니 그 user인 AndL을 worklist에 넣는다.
AndL을 꺼내 최적화해본다. x & 0xFFFFFFFF 자체로는 더 줄일 게 없으니 AndL은 바뀌지 않는다.
AndL이 바뀌지 않았으니 AndL의 user인 ConvL2I는 worklist에 들어가지 않는다.
worklist가 비고 IGVN이 끝난다.

ConvL2I 입장에서는 입력의 입력이 바뀌었는데 아무도 알려주지 않은 것이다. 그래서 적절한 최적화를 타지 못했다.

최적화를 타지 못하는 것은 결과가 틀리는 버그는 아니다. 마스크는 원래 의미 없는 연산이라, 남아 있어도 계산 결과는 같다. 그 IGVN에서 할 수 있던 최적화를 놓쳐 불필요한 마스크가 남을 수 있는 정도이고, 디버그 빌드의 VerifyIterativeGVN이 이 누락을 잡아낸 것이다.

수정 내용

파일: src/hotspot/share/opto/phaseX.cpp

add_users_of_use_to_worklist()에 “AndL의 입력이 바뀌면 user 중 ConvL2I를 worklist에 넣는다”는 규칙을 추가했다. use가 AndL이면 use의 user 중 ConvL2I만 골라 worklist에 넣는다. 위의 그래프로 보면, URShiftL(n)이 바뀌었을 때 AndL(use)을 거쳐 user의 user인 ConvL2I까지 다시 방문하게 만드는 것이다.

  // If changed AndL inputs, check ConvL2I users for
  // "ConvL2I(AndL(x, 0xFFFFFFFF))" => "ConvL2I(x)" optimization in ConvL2INode::Ideal.
  if (use_op == Op_AndL) {
    add_users_to_worklist_if(worklist, use, [](Node* u) {
      return u->Opcode() == Op_ConvL2I;
    });
  }

이 코드에는 노드가 세 단계로 등장한다.

이름	역할	이번 경우
`n`	바뀐 노드	`URShiftL` (상수로 바뀜)
`use`	`n`의 user, 즉 입력이 바뀐 노드	`AndL` ← `use_op == Op_AndL` 조건
`u`	`use`의 user	`ConvL2I` ← 람다 조건, worklist에 추가

마무리

수정 후 테스트를 돌렸고, 정상적으로 통과하는 것을 확인하였다.

수정한 코드는 7줄뿐이지만, 거기까지 가려면 assert에서 시작해서 덤프를 읽고, ConvL2I가 입력의 입력을 본다는 사실을 찾고, 그 노드가 루프 최적화 이후에야 상수가 된다는 흐름을 이해해야 했다.

지난번에 간접적으로 다뤘던 GVN을 다시 만나서 반가웠다. 오랜만에 OpenJDK에 기여하려니까 머리가 아팠다. 컴파일러 공부도 깊게 해보고 싶은데, 공부할 게 너무 많다.

기타

user란?

컴파일러에서는 값을 만드는 쪽을 def(definition), 그 값을 쓰는 쪽을 use라고 부르고, 이 연결을 def-use 관계라고 한다. 어떤 노드의 결과값을 입력으로 쓰는 노드를 그 노드의 user라고 한다.

October 4, 2026

categories: 개발

tags: JDK , OpenJDK , HotSpot , C2 , GVN , 오픈소스 기여