• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Deoptimization
2
3## Overview
4
5Deoptimization is the process of taking action if compiled code cannot continue execution for some reason.
6
7The compiler may make some speculative assumptions about the execution of the method. Based on these assumptions, the compiler makes certain optimizations, inserting checks about the correctness of the assumptions. The special instruction `DeoptimizeIf` processes the result of the check and if the result is incorrect the output to the interpreter occurs.
8
9## Speculative optimizations
10
11 - [Devirtualization with Class Hierarchy Analysis](../compiler/docs/inlining.md#devirtualization-with-class-hierarchy-analysis)
12 - BoundCheck Elimination
13
14## Algorithm
15
16### DeoptimizeIf
17The instruction `DeoptimizeIf` is encoded as conditional branch to the slow path if input value is true.
18Details in [codegen.cpp](../compiler/optimizer/code_generator/codegen.cpp), function EncodeVisitor::VisitDeoptimizeIf
19
20### Slow path
21
22The slow path encodes a call to the runtime function `Deoptimize`. We do the following for this:
231. fill the `Frame`(saves pointer to current CFrame) and `is_compiled_frame_`(saves true) fields in the thread register.
242. save caller saved registers
253. create StateStamp(in compile time) for this address(np - native pc)
264. Call `Deoptimize` function
27
28Details in [slow_path.cpp](../compiler/optimizer/code_generator/slow_path.cpp) case RuntimeInterface::EntrypointId::DEOPTIMIZE
29
30### The function Deoptimize
31
32The function `Deoptimize` calculates bitecode pc where we should start executing code in the interpreter, restores interpreter frame from current CFrame.
33If deoptimization occurred in the inlined method, we restore all interpreter frames for all inlined methods and calculate the number of inlined methods.
34
35pseudocode:
36
37```
38voud Deoptimize(...) {
39    uint32_t num_inlined_methods = 0;
40    Frame* iframe = frame.ConvertToIFrame(&prev_frame_kind, &num_inlined_methods);
41    Frame* last_iframe = iframe;
42    while (num_inlined_methods-- != 0) {
43        last_iframe = last_iframe->GetPrevFrame();
44    }
45    if (IsIframe(last_iframe->GetPrevFrame())) {
46        DeoptimizeAfterIFrame(thread, pc, iframe, cframe, last_iframe);
47    } else {
48        DeoptimizeAfterCFrame(thread, pc, iframe, cframe, last_iframe);
49    }
50}
51
52Frame* StackWalker::ConvertToIFrame(CFrameType& cframe, uint32_t* num_inlined_methods) {
53    void* prev_frame;
54    if (cframe.IsInlined()) {
55        auto caller_cframe = cframe.GetCallerFrame();
56        *num_inlined_methods = *num_inlined_methods + 1;
57        prev_frame = ConvertToIFrame(caller_cframe, num_inlined_methods);
58    } else {
59        prev_frame = GetPrevFrame(cframe);
60    }
61    Frame* frame = CreateFrameAndSetsVRegs(cframe, prev_frame);
62    frame->SetBytecodeOffset(cframe.GetBytecodePc());
63```
64
65If the deoptimized method was called from interpreter, `Deoptimize` calls the bridge `DeoptimizeAfterIFrame`, otherwise `DeoptimizeAfterCFrame`.
66
67Both bridges have following parameters:
68* pointer to the current thread
69* bytecode pc of the entry
70* pointer to first restoring interpreter Frame
71* pointer to CFrame origin
72* pointer to last restoring interpreter Frame
73
74Details in [deoptimization.cpp](../runtime/deoptimization.cpp)
75
76### DeoptimizeAfterIFrame
77
78`DeoptimizeAfterIFrame` restores SP, FP and LR to values before calling the method, restores callee saved registers (which we saved in the method) and call `InvokeInterpreter` to execute the method in the interpreter. Since we changed return address (LR), we return from the function to the place in interpreter where the method was called.
79
80Details in [deoptimization_aarch64.S](../runtime/bridge/arch/aarch64/deoptimization_aarch64.S), [deoptimization_arm.S](../runtime/bridge/arch/arm/deoptimization_arm.S), [deoptimization_amd64.S](../runtime/bridge/arch/amd64/deoptimization_amd64.S)
81
82### DeoptimizeAfterCFrame
83
84`DeoptimizeAfterCFrame` changes current CFrame to I2C(Interpreter To Compile) bridge, set last IFrame's previous frame to this C2I bridge frame and call `InvokeInterpreter` for execute the method in the interpreter. After return from `InvokeInterpreter`, we restore callee saved registers(which we saved in the method), restore SP, FP and LR to values before calling the method and return to compiled code where the method was called.
85
86Details in [deoptimization_aarch64.S](../runtime/bridge/arch/aarch64/deoptimization_aarch64.S), [deoptimization_arm.S](../runtime/bridge/arch/arm/deoptimization_arm.S), [deoptimization_amd64.S](../runtime/bridge/arch/amd64/deoptimization_amd64.S)
87
88### InvokeInterpreter
89
90`InvokeInterpreter` has next parameters:
91* pointer to current thread
92* bytecode pc of the entry
93* pointer to first restoring interpreter Frame
94* pointer to last restoring interpreter Frame
95
96`InvokeInterpreter` change `Frame`(saves pointer to interpreter Frame) and `is_compiled_frame_`(saves false) fields in the thread register and calls interpreter from bytecode pc.
97If deoptimization occurred in the inlined method, we call interpreter for all inlined methods from bytecode pc which is taken from the corresponding interpreter frame.
98The last restoring interpreter Frame is used for limitation number of calls to the interpreter for inlined methods.
99
100pseudocode:
101
102```
103int64_t InvokeInterpreter(ManagedThread* thread, const uint8_t* pc, Frame* frame, Frame* last_frame) {
104    thread->SetCurrentFrame(frame);
105    thread->SetCurrentFrameIsCompiled(false);
106
107    interpreter::Execute(thread, pc, frame, thread->HasPendingException());
108
109    auto acc = frame->GetAcc();
110    auto prev_frame = frame->GetPrevFrame();
111    thread->SetCurrentFrame(prev_frame);
112    FreeFrame(frame);
113
114    while (prev_frame != nullptr && (last_frame != frame)) {
115        frame = prev_frame;
116        prev_frame = frame->GetPrevFrame();
117        pc = GetPcFromFrame(frame);
118        frame->GetAcc() = acc;
119        interpreter::Execute(thread, pc, frame, thread->HasPendingException());
120
121        acc = frame->GetAcc();
122
123        thread->SetCurrentFrame(prev_frame);
124        FreeFrame(frame);
125    }
126
127    return GetValue(acc);
128}
129```
130
131Details in [bridge.cpp](runtime/bridge/bridge.cpp)
132
133## Tests
134
135### deoptimization after wrong devirtualization:
136
137[inline_cha.pa](../tests/checked/inline_cha.pa)
138
139### deoptimization after BoundCheck Elimination:
140
141[deopt_true_test.pa](../tests/regression/deopt_true_test.pa)
142[deopt_true_call_test.pa](../tests/regression/deopt_true_call_test.pa)
143
144