「内联缓存与动态语言优化」

// C 里的属性访问：编译期完全确定，生成 movsd 0(%rdi), %xmm0
struct Point { double x; double y; };
double get_x(struct Point *p) { return p->x; }

# Python：obj.field 的含义在运行时才确定
def get_x(obj):
    return obj.x

get_x(Point(1.0, 2.0))   # 读实例字典或槽位
get_x({"x": 1.0})        # 字典查找
get_x(SomeProxy())       # 可能触发 __getattr__ 走属性协议

# 朴素属性查找的等价过程（概念示意）
def getattr_naive(obj, name):
    cls = type(obj)                      # 1. 拿到类型
    if name in cls.__dict__:             # 2. 查类字典（哈希查找）
        desc = cls.__dict__[name]
        if isinstance(desc, SlotDescriptor):
            return obj.slots[desc.offset]   # 3. 槽位直接读
        return desc.__get__(obj, cls)       # 4. 描述符协议
    if name in obj.__dict__:
        return obj.__dict__[name]        # 5. 查实例字典
    raise AttributeError(name)           # 6. 失败

# 隐藏类与对象布局的对应关系
p1, p2 = Point(1.0, 2.0), Point(3.0, 4.0)
# p1 与 p2 的隐藏类相同，都是 PointShape{x@0, y@8}
# 于是 p1.x 与 p2.x 都能编译成「基址 + 0」的读取

p3 = Point(1.0, 2.0); p3.z = 5.0    # 添加新属性
# p3 的隐藏类变成 PointShape{x@0, y@8, z@16}
# p1、p2 仍然是 PointShape{x@0, y@8}，不受影响

// 隐藏类的内部表示（简化）
typedef struct Shape {
    uint32_t id;                    // 唯一标识，用于快速比较
    struct { uint32_t name_hash; uint32_t offset; } props[64];
    struct Shape *transitions;      // 从本 Shape 出发的转移表
} Shape;

typedef struct JSObject {
    Shape *shape;                   // 每个对象指向一个 Shape
    void  *slots[8];                // 属性按 Shape 给出的偏移存放
} JSObject;

// 优化后的属性读取：比较 shape 指针 + 固定偏移读取
static inline Value load_x(JSObject *o) {
    if (o->shape != cached_shape) return slow_path(o, "x");
    return o->slots[SHAPE_OFFSET_X];
}

# 添加顺序影响隐藏类，进而影响内联缓存的命中率
def make_a(): o = {}; o.x = 1; o.y = 2; return o   # {} -> {x} -> {x, y}
def make_b(): o = {}; o.y = 2; o.x = 1; return o   # {} -> {y} -> {y, x}
# 两者返回的对象属性相同，但隐藏类不同！混用会让 IC 变成多态

// 转移树的查找：从当前 Shape 出发，按属性名找下一个 Shape
Shape *transition(Shape *from, uint32_t name_hash) {
    for (Shape *t = from->transitions; t; t = t->next) {
        if (t->name_hash == name_hash) return t;   // 已有转移，复用
    }
    return create_new_shape(from, name_hash);      // 新建并挂到树上
}

# 单态内联缓存：只有一条类型守卫
def get_x_monomorphic(obj):
    if type(obj) is Point:          # 类型守卫
        return obj.slots[0]         # 命中，直接读
    return getattr_slow(obj, "x")   # 未命中，走慢路径并更新缓存

# 多态内联缓存：缓存若干条 (形状, 目标) 对
class PolymorphicIC:
    def __init__(self, limit=4):
        self.entries, self.limit = [], limit

    def lookup(self, obj, name):
        sid = obj.shape.id
        for shape_id, handler in self.entries:   # 线性扫描
            if shape_id == sid:
                return handler(obj)              # 命中
        handler = resolve(obj, name)             # 未命中，解析
        if len(self.entries) >= self.limit:
            return getattr_naive(obj, name)      # 超出上限，退化为超态
        self.entries.append((sid, handler))      # 提升为多态
        return handler(obj)

// 触发超态的典型写法：同一个调用点被几十种类型调用
function getValue(obj) { return obj.value; }

// 改善方式一：把热点路径上的调用点按类型拆分，保持单态
function getValueFast(point) { return point.value; }

// 改善方式二：统一对象形状（构造函数里一次性建好所有属性）
class Point { constructor(x, y, z) { this.x = x; this.y = y; this.z = z; } }

# 从属性访问到方法内联的完整链条
# 1) obj.method -> 调用 IC 命中，得到已知函数地址
# 2) 方法体小且被调用频繁 -> 内联进调用点
# 3) 内联后暴露常量与类型信息 -> 触发更多优化（寄存器分配、指令调度）

// 去优化点的元数据（简化）
typedef struct DeoptInfo {
    uint32_t pc_offset;             // 优化代码里的位置
    uint32_t frame_size;            // 栈帧大小
    uint32_t slot_count;
    struct {
        uint8_t kind;               // 值在寄存器 / 栈上 / 常量
        uint8_t index;              // 寄存器号或栈偏移
        uint8_t target_slot;        // 重建后放到解释器帧的哪个槽
    } slots[32];
} DeoptInfo;

// 守卫失败时触发：把寄存器与栈上的值搬回解释器帧，从对应字节码位置继续
void deoptimize(DeoptInfo *info, void *frame) {
    InterpFrame *f = alloc_interp_frame(info->frame_size);
    for (int i = 0; i < info->slot_count; i++)
        f->slots[info->slots[i].target_slot] = read_value(info->slots[i], frame);
    resume_interpreter(f, info->pc_offset);
}

// 一段会触发去优化的代码
function add(a, b) { return a + b; }   // 被 JIT 编译时假设 a、b 都是整数
for (let i = 0; i < 100000; i++) add(i, i);   // 触发 JIT，编译为整数加法
add("hello", "world");   // 类型守卫失败 -> 去优化 -> 回退解释执行
                         // 之后可能重新编译为「字符串拼接」版本

# 排查去优化循环：统计每个函数被去优化的次数，最多的那个就是元凶
node --trace-deopt app.js | grep -c "deoptimizing"          # 事件总数
node --trace-deopt app.js | awk '/deoptimizing/ {print $5}' \
  | sort | uniq -c | sort -rn | head                        # 按函数聚合
# 修复方向：拆分函数、统一类型、避免运行中修改原型

// 逃逸分析的经典收益：临时对象被完全消除
class Point { double x, y; Point(double x, double y) { this.x = x; this.y = y; } }

double distance(double x1, double y1, double x2, double y2) {
    Point p = new Point(x2 - x1, y2 - y1);   // 未逃逸
    return Math.sqrt(p.x * p.x + p.y * p.y);
}
// 逃逸分析后等价于 double dx = x2-x1, dy = y2-y1; return sqrt(dx*dx+dy*dy);
// 完全没有对象分配，也没有 GC 压力

# 逃逸分析的三档结论
# 1) NoEscape     对象不逃出函数 -> 标量替换，最优
# 2) ArgEscape    传给别的函数但不存下来 -> 可做栈分配
# 3) GlobalEscape 被存入全局或返回 -> 必须堆分配
def classify(uses):
    for u in uses:
        if u.kind in ("store_global", "return"):
            return "GlobalEscape"
        if u.kind == "call" and not u.inlined:
            return "ArgEscape"
    return "NoEscape"

# 元追踪的思想：JIT 观察解释器执行，把热循环编译成机器码
def interp_loop(code, pc):
    while True:
        op = code[pc]
        if op == LOAD_ATTR:
            obj = stack.pop()
            stack.append(getattr_slow(obj, code[pc+1]))   # 字典查找
            pc += 2
        elif op == ADD:
            b, a = stack.pop(), stack.pop()
            stack.append(a + b)                            # 动态分派
            pc += 1

# 元追踪后，JIT 观察到的热路径被编译成：
#   load type_ptr, [obj]           ; 类型守卫
#   cmp  type_ptr, const_Point
#   jne  trace_exit
#   mov  rax, [obj + 16]           ; 直接偏移读属性
#   add  rax, rbx                  ; 整数加法
# 解释器里的 getattr_slow 与动态分派完全消失

// 反例：类型不稳定，arr 混有整数与字符串时 s 在两种类型间切换
function sum(arr) { let s = 0; for (const x of arr) s += x; return s; }

// 正例：按类型拆分，各自保持单态
function sumInts(arr) { let s = 0; for (const x of arr) s += x; return s; }
function sumStrs(arr) { let s = ""; for (const x of arr) s += x; return s; }

# 反例：属性添加顺序不一致，两个函数产生的字典形状不同
def make_user_v1(name, age): u = {}; u["name"] = name; u["age"] = age; return u
def make_user_v2(name, age): u = {}; u["age"] = age; u["name"] = name; return u

# 正例：固定形状的类，槽位唯一
class User:
    __slots__ = ("name", "age")
    def __init__(self, name, age): self.name, self.age = name, age

# V8 的 IC 与去优化观测手段
node --trace-ic app.js | grep -i megamorphic     # 定位超态调用点
node --trace-deopt app.js | head -50             # 观察去优化原因
node --allow-natives-syntax -e 'function f(o){return o.x;}
  %PrepareFunctionForOptimization(f); f({x:1}); f({x:2});
  %OptimizeFunctionOnNextCall(f); f({x:3});
  console.log(%GetOptimizationStatus(f));'       # 查看优化状态