[졸간분] 최적화 기법 on-stack replacement

 

'대강 이렇지 않을까?' 하는 온갖 추정이 포함된 졸라 간단한 분석 - 졸간분

 

0. OnStackReplacement란?

Stack에 Replacement하는 최적화 방식. 양놈들의 명명센스는 알다가도 모르겠다. 대충 3단어를 넘지 않는 선에서 축약어를 만드는데, 어쩔때는 이름만으로 그 의미가 파악되는데 어쩔때는 도통 뭔 소린지 이해가 안될때까 있다. 이 단어가 바로 그런 경우로, 대충 어떻게 느껴지냐면 일상 대화를 "오늘 날씨는 23.5도야 이런 날씨에는 영장류 세포가 활성화되기 좋은 온도지." 라고 대화할거 같은 공돌이 둘이서 소통할 때 쓰는 단어같다.

 

서론이 길어서 죄송합니다만, 내용이 별거 없어서 헛소리 좀 해봤습니다.

 

 

1. OnStackReplacement 어디서 사용되나?

OnStackReplacement는 사실 Stack에 기반한 function calling을 manipulate하는 하나의 방법론을 뜻한다. 여기서 배경지식이 없는 분들을 위해 간략하게 설명하자면, 프로그램의 실행 흐름에서 함수가 호출되고, 호출된 함수가 작업을 끝내면, 자신을 호출했던 지점으로 복귀되어 실행 흐름을 이어가게 된다. 어기서 함수가 호출되는 시점에 작업 후 복귀되기 위해 미리 복귀지점을 Stack에 만드는데 이것을 RET이라고 흔히 부르며 Return Address의 준말이다.

 

OnStackReplacement는 이런 메커니즘에 준하되, 일반적인 실행흐름이 아닌 상황. 예를 들자면, 함수 A가 B를 호출했다치면 B가 종료되고 A로 복귀해야 하는데 A가 아닌 C로 복귀하게 만들고 싶은 그런 상황이 있다. 대표적으로 v8과 같은 Interpreter들이 Loop문에서 활용한다.

 

 

2. 백문불여일견

이제부터 v8에서 이뤄지는 OnStackReplacement 과정을 짧게 보여주고자 한다.

function find_me_a() {
    return find_me_b() + 1;
}

function find_me_b() {
    return find_me_c() + 1;
}

function find_me_c() {
    return 1;
}

function origin() {
    for(var i = 0 ; i < 140000;)
    {
        i += find_me_a();
    }

    return i;
}


origin();

예제코드, 왜 이따구냐고는 묻지마시라. 이것저것 테스트하다 남은 코드이니... 주목할 것은 반복 횟수인데, 오버해서 많이 잡은 것이고 대강 4만 언저리면 된다. 실제 임계점에 들어가는 지점도 아래에 나올 것이다. 위의 Javascript를 --print-bytecode 옵션을 주고 실행해보면 다음과 같은 bytecode를 확인할 수 있다.

 

[generated bytecode for function: origin]

Parameter count 1

Register count 3

Frame size 24

  163 E> 0x1c929fc1ee72 @    0 : a5                StackCheck

  184 S> 0x1c929fc1ee73 @    1 : 0b                LdaZero

         0x1c929fc1ee74 @    2 : 26 fb             Star r0

  190 S> 0x1c929fc1ee76 @    4 : 01 0c e0 22 02 00 LdaSmi.ExtraWide [140000]

  190 E> 0x1c929fc1ee7c @   10 : 69 fb 00          TestLessThan r0, [0]

         0x1c929fc1ee7f @   13 : 99 16             JumpIfFalse [22] (0x1c929fc1ee95 @ 35)

  172 E> 0x1c929fc1ee81 @   15 : a5                StackCheck

  215 S> 0x1c929fc1ee82 @   16 : 13 00 02          LdaGlobal [0], [2]

         0x1c929fc1ee85 @   19 : 26 f9             Star r2

  220 E> 0x1c929fc1ee87 @   21 : 5c f9 04          CallUndefinedReceiver0 r2, [4]

         0x1c929fc1ee8a @   24 : 34 fb 01          Add r0, [1]

         0x1c929fc1ee8d @   27 : 27 fb fa          Mov r0, r1

         0x1c929fc1ee90 @   30 : 26 fb             Star r0

         0x1c929fc1ee92 @   32 : 8a 1c 00          JumpLoop [28], [0] (0x1c929fc1ee76 @ 4)

  244 S> 0x1c929fc1ee95 @   35 : 25 fb             Ldar r0

  253 S> 0x1c929fc1ee97 @   37 : a9                Return

Constant pool (size = 1)

0x1c929fc1ee21: [FixedArray] in OldSpace

 - map: 0x07b959a807b1 <Map>

 - length: 1

           0: 0x1c929fc1e741 <String[#9]: find_me_a>

Handler Table (size = 0)

 

 

여기서 잠깐, Interpreter가 동작하는 방식도 간략히 살펴보고 넘어가자.

개발중인 v8 Interpreting Tracing

 

Interpreter에는 기본적으로 Bytecode(명령어)와 Bytecode의 Handler가 pair로 존재하며, Interpreter가 bytecode를 Dispatch하여 bytecode에 적합한 Handler를 호출하는 방식으로 실행되게 된다.

 

여기서 필요한 부분만 콕 집어 얘기하자면, 요부분

         0x1c929fc1ee92 @   32 : 8a 1c 00          JumpLoop [28], [0] (0x1c929fc1ee76 @ 4)

 

JumpLoop라는 bytecode는 Builtins_JumpLoopHandler라는 함수를 호출해서 처리해준다는 것이다.

 

$ objdump -tT out.gn/x64.debug/libv8.so | grep Builtins | grep JumpLoop
0000000002456840 l     F .text  0000000000000000              Builtins_JumpLoopExtraWideHandler
00000000023666c0 l     F .text  0000000000000000              Builtins_JumpLoopHandler
00000000023dec80 l     F .text  0000000000000000              Builtins_JumpLoopWideHandler

 

먼저 Builtins_JumpLoop를 보자.

// JumpLoop <imm> <loop_depth>
//
// Jump by the number of bytes represented by the immediate operand |imm|. Also
// performs a loop nesting check and potentially triggers OSR in case the
// current OSR level matches (or exceeds) the specified |loop_depth|.
IGNITION_HANDLER(JumpLoop, InterpreterAssembler) {
  Node* relative_jump = BytecodeOperandUImmWord(0);
  Node* loop_depth = BytecodeOperandImm(1);
  Node* osr_level = LoadOSRNestingLevel();

  // Check if OSR points at the given {loop_depth} are armed by comparing it to
  // the current {osr_level} loaded from the header of the BytecodeArray.
  Label ok(this), osr_armed(this, Label::kDeferred);
  Node* condition = Int32GreaterThanOrEqual(loop_depth, osr_level);
  Branch(condition, &ok, &osr_armed);

  BIND(&ok);
  JumpBackward(relative_jump);

  BIND(&osr_armed);
  {
    Callable callable = CodeFactory::InterpreterOnStackReplacement(isolate());
    Node* target = HeapConstant(callable.code());
    Node* context = GetContext();
    CallStub(callable.descriptor(), target, context);
    JumpBackward(relative_jump);
  }
}

아!! 거, 뭔 소리인지 난 모르겠고~~ 대충 보니까 현재 loop의 depth와 osr_level을 비교해서 osr_level을 넘기면, 그 시점에는 OSR_ARMED로 와서 InterpreterOnStackReplacement를 호출하는 것 같다 이말이야.

 

Builtins_JumpLoopHandler의 중간에서 다음처럼 InterpreterOnStackReplacement를 호출하는 구문을 찾을 수 있다. (소스코드 라인으로는 breakpoint가 안잡히니 유의)

 

(gdb) disas Builtins_JumpLoopHandler  

...

0x00007ffff7b3982e <+366>:   callq  0x7ffff7602f00 <Builtins_InterpreterOnStackReplacement>

...

 

여기에 breakpoint를 잡고 들어가면 된다.

소스코드로는 다음과 같다.

// src/code-factory.cc
// static
Callable CodeFactory::InterpreterOnStackReplacement(Isolate* isolate) {
  return Builtins::CallableFor(isolate,
                               Builtins::kInterpreterOnStackReplacement);
}


// src/builtins/x64/builtins-x64.cc
void Builtins::Generate_InterpreterOnStackReplacement(MacroAssembler* masm) {
  // Lookup the function in the JavaScript frame.
  __ movq(rax, Operand(rbp, StandardFrameConstants::kCallerFPOffset));
  __ movq(rax, Operand(rax, JavaScriptFrameConstants::kFunctionOffset));

  {
    FrameScope scope(masm, StackFrame::INTERNAL);
    // Pass function as argument.
    __ Push(rax);
    __ CallRuntime(Runtime::kCompileForOnStackReplacement);
  }

  Label skip;
  // If the code object is null, just return to the caller.
  __ testq(rax, rax);
  __ j(not_equal, &skip, Label::kNear);
  __ ret(0);

  __ bind(&skip);

  // Drop the handler frame that is be sitting on top of the actual
  // JavaScript frame. This is the case then OSR is triggered from bytecode.
  __ leave();

  // Load deoptimization data from the code object.
  __ LoadTaggedPointerField(rbx,
                            FieldOperand(rax, Code::kDeoptimizationDataOffset));

  // Load the OSR entrypoint offset from the deoptimization data.
  __ SmiUntagField(
      rbx, FieldOperand(rbx, FixedArray::OffsetOfElementAt(
                                 DeoptimizationData::kOsrPcOffsetIndex)));

  // Compute the target address = code_obj + header_size + osr_offset
  __ leaq(rax, FieldOperand(rax, rbx, times_1, Code::kHeaderSize));

  // Overwrite the return address on the stack.
  __ movq(StackOperandForReturnAddress(0), rax);

  // And "return" to the OSR entry point of the function.
  __ ret(0);
}

마지막 __ ret 바로 앞 __ movq에 bp를 걸고 확인해보자.

 

(gdb) br *0x00007ffff7602f51    

│=> 0x00007ffff7602f51 <+81>:    mov    QWORD PTR [rsp],rax

        0x00007ffff7602f55 <+85>:    ret      

 

(gdb) p/x $rax 

$3 = 0x249501383096     

 

(gdb) jco $rax    

kind = OPTIMIZED_FUNCTION 

stack_slots = 11         

compiler = turbofan  

address = 0x7fffffffcba0     

 

Instructions (size = 1088)     

0x249501383040     0  488d1df9ffffff REX.W leaq rbx,[rip+0xfffffff9]
0x249501383047     7  483bd9         REX.W cmpq rbx,rcx
0x24950138304a     a  7418           jz 0x249501383064  <+0x24>
0x24950138304c     c  48ba0000000037000000 REX.W movq rdx,0x3700000000
0x249501383056    16  49baa0bd6cf7ff7f0000 REX.W movq r10,0x7ffff76cbda0  (Abort)    ;; off heap target
0x249501383060    20  41ffd2         call r10
0x249501383063    23  cc             int3l
0x249501383064    24  488b59e0       REX.W movq rbx,[rcx-0x20]
0x249501383068    28  f6430f01       testb [rbx+0xf],0x1
0x24950138306c    2c  740d           jz 0x24950138307b  <+0x3b>
0x24950138306e    2e  49ba404560f7ff7f0000 REX.W movq r10,0x7ffff7604540  (CompileLazyDeoptimizedCode)    ;; off heap target
0x249501383078    38  41ffe2         jmp r10
0x249501383095    55  cc             int3l
0x249501383096    56  4883ec10       REX.W subq rsp,0x10  

...생략...

 

 

여기까지의 중간 정리를 하자면,

1. v8 Interpreter는 Loop 문을 JumpLoop로 Compiler하고 이를 Builtins_JumpLoopHandler로 처리하는데

2. Builtins_JumpLoopHandler에서는 OSR 임계점을 넘으면 OSR 을 진행하게 된다.

3. OSR에서는 JavaScript StackFrame의 최상단에 존재하는 Javascript Function을 인자로 컴파일을 진행하고

4. 최종적으로 컴파일된 Optimized Function Code를 Javascript StackFrame의 최상단에 교체한다.

 

 

이를 통해 마지막 Bytecode로 실행되던 마지막 JumpLoop이 Javascript StackFrame의 최상단에 남겨놓은 복귀주소는 Bytecode로 되어 있는 Code Chunk가 아닌 Optimized된 Machine code chunk로 변경된다. 이처럼 어떤 handling하는 과정에서 필요에 의해 Stack을 조작하는 것을 OnStackReplacement라고 부른다.

 

   0x00007ffff7602f51 <+81>:    mov    QWORD PTR [rsp],rax
=> 0x00007ffff7602f55 <+85>:    ret

 

(gdb) si

0x0000249501383096 in ?? ()

 

ret 된 뒤에 위치하게 되는 주소는 위에서 봤던 Optimized 된 function이다.

여기서부터 Optimized 된 code가 bytecode 대신 실행되며 bytecode의 Handler는 호출되지 않게 된다.

 

- 끗 -