/* 함수를 고르는 길들 --- harness.c 가 잰다.
   - 종류마다 함수가 따로 있고(상수가 달라 합쳐지지 않는다), 어느 것도 인라인하지
     못한다: 재는 것은 일이 아니라 *고르기*다.
   - 하나의 예외는 마지막 길이다. 컴파일러가 인라인하게 둔다. */
#include "bench.h"

#define KIND(k, c)                                                              \
    [[gnu::noinline]] static uint64_t f##k(const struct obj *o)                 \
    { return o->x * (c) + (k); }                                                \
    static inline uint64_t g##k(const struct obj *o) { return o->x * (c) + (k); }
KIND(0, 3)  KIND(1, 5)  KIND(2, 7)  KIND(3, 11)
KIND(4, 13) KIND(5, 17) KIND(6, 19) KIND(7, 23)

[[gnu::noinline]] uint64_t other(const struct obj *o) { return o->x; }
const method fs[KMAX] = { f0, f1, f2, f3, f4, f5, f6, f7 };
const struct ops static_ops[KMAX] = {
    { f0, other }, { f1, other }, { f2, other }, { f3, other },
    { f4, other }, { f5, other }, { f6, other }, { f7, other },
};

#define EACH for (uint32_t r = 0; r < REPS; r++) for (uint32_t i = 0; i < N; i++)

uint64_t m_direct(void)          /* 기준: 종류 하나, 직접 호출 */
{ uint64_t s = 0; EACH s += f0(&arena[i]); return s; }

uint64_t m_grouped(void)         /* 종류별로 모아(종류마다 색인 목록) 직접 호출 */
{
    uint64_t s = 0;
    for (uint32_t r = 0; r < REPS; r++)
        for (uint32_t k = 0; k < kinds; k++) {
            const uint32_t *ix = by_kind[k];
            switch (k) {
#define GROUP(j) \
    case j: for (uint32_t i = 0; i < count[j]; i++) s += f##j(&arena[ix[i]]); break;
            GROUP(0) GROUP(1) GROUP(2) GROUP(3) GROUP(4) GROUP(5) GROUP(6) GROUP(7)
            }
        }
    return s;
}

uint64_t m_switch(void)          /* 종류 번호로 switch */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        switch (o->kind) {
        case 0: s += f0(o); break; case 1: s += f1(o); break;
        case 2: s += f2(o); break; case 3: s += f3(o); break;
        case 4: s += f4(o); break; case 5: s += f5(o); break;
        case 6: s += f6(o); break; case 7: s += f7(o); break;
        }
    }
    return s;
}

uint64_t m_binary(void)          /* 종류 번호로 이진 분기, 표 없음 */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        uint32_t k = o->kind;
        if (k < 4) s += k < 2 ? (k < 1 ? f0(o) : f1(o)) : (k < 3 ? f2(o) : f3(o));
        else       s += k < 6 ? (k < 5 ? f4(o) : f5(o)) : (k < 7 ? f6(o) : f7(o));
    }
    return s;
}

uint64_t m_static(void)          /* static const 표 */
{ uint64_t s = 0; EACH s += arena[i].sops->apply(&arena[i]); return s; }

uint64_t m_dynamic(void)         /* 실행 때 지은 표 */
{ uint64_t s = 0; EACH s += arena[i].dops->apply(&arena[i]); return s; }

uint64_t m_fat(void)             /* 뚱뚱한 포인터 */
{ uint64_t s = 0; EACH s += fats[i].ops->apply(fats[i].data); return s; }

/* ---- 셀렉터로: Objective-C 의 길, 캐시가 있을 때와 없을 때 ---- */
/* 목록을 훑고, 없으면 부모의 목록을 */
static method lookup_slow(const struct klass *c, uint32_t sel)
{
    for (; c; c = c->parent)
        for (uint32_t m = 0; m < c->n; m++)
            if (c->methods[m].sel == sel) return c->methods[m].fn;
    return nullptr;
}
/* 클래스별 캐시를 먼저 */
static method lookup_cached(struct klass *c, uint32_t sel)
{
    struct cache_entry *e = &c->cache[sel & 15];
    if (e->sel == sel) return e->fn;
    method m = lookup_slow(c, sel);
    *e = (struct cache_entry){ sel, m };
    return m;
}

uint64_t m_sel_slow(void)        /* 셀렉터, 캐시 없음: 목록을 끝까지 훑는다 */
{ uint64_t s = 0; EACH s += lookup_slow(arena[i].cls, SEL_APPLY)(&arena[i]); return s; }

uint64_t m_sel_cache(void)       /* 셀렉터, 클래스별 캐시 */
{ uint64_t s = 0; EACH s += lookup_cached(arena[i].cls, SEL_APPLY)(&arena[i]); return s; }

uint64_t m_sel_ic(void)          /* 셀렉터, 호출 자리의 한 칸 인라인 캐시 */
{
    uint64_t s = 0;
    struct { const struct klass *cls; method fn; } ic = {};
    EACH {
        struct klass *c = arena[i].cls;
        if (c != ic.cls) { ic.cls = c; ic.fn = lookup_slow(c, SEL_APPLY); }   /* 놓침 */
        s += ic.fn(&arena[i]);
    }
    return s;
}

uint64_t m_sel_pic(void)         /* 셀렉터, 네 칸 다형 인라인 캐시 */
{
    uint64_t s = 0;
    struct { const struct klass *cls; method fn; } pic[4] = {};
    uint32_t next = 0;
    EACH {
        struct klass *c = arena[i].cls;
        method m;
        if      (pic[0].cls == c) m = pic[0].fn;
        else if (pic[1].cls == c) m = pic[1].fn;
        else if (pic[2].cls == c) m = pic[2].fn;
        else if (pic[3].cls == c) m = pic[3].fn;
        else {                                       /* 놓침: 찾고, 한 칸을 바꾼다 */
            m = lookup_slow(c, SEL_APPLY);
            pic[next].cls = c;
            pic[next].fn = m;
            next = (next + 1) & 3;
        }
        s += m(&arena[i]);
    }
    return s;
}

uint64_t m_inlined(void)         /* 다시 switch --- 이번에는 몸통을 인라인해도 된다 */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        switch (o->kind) {
        case 0: s += g0(o); break; case 1: s += g1(o); break;
        case 2: s += g2(o); break; case 3: s += g3(o); break;
        case 4: s += g4(o); break; case 5: s += g5(o); break;
        case 6: s += g6(o); break; case 7: s += g7(o); break;
        }
    }
    return s;
}

/* 컴파일러가 표를 알 때와 모를 때 --- 같은 shape_area 를 다섯 자리에서 부른다.
   run.sh 가 함수마다 간접 호출이 남았는지 기계어로 본다. */
#include <stdlib.h>

struct shape;
struct shape_ops { double (*area)(const struct shape *); };
struct shape { const struct shape_ops *ops; double r; };

static double circle_area(const struct shape *s) { return 3.0 * s->r * s->r; }
static inline double shape_area(const struct shape *s) { return s->ops->area(s); }

static const struct shape_ops circle_ops = { circle_area };  /* static const 표 */
static struct shape_ops quiet_ops = { circle_area };   /* const 없음, 고치는 곳 없음 */
struct shape_ops open_ops = { circle_area };           /* 바깥에서 보이는 표 */
const struct shape_ops *built_ops;                     /* 실행 때 지은 표 */

double known_object(double r)          /* 객체도 표도 여기서 보인다 */
{
    struct shape s = { &circle_ops, r };
    return shape_area(&s);
}
double never_written(double r)         /* const 는 없어도 이 파일에서 쓰는 곳은 없다 */
{
    struct shape s = { &quiet_ops, r };
    return shape_area(&s);
}
double visible_outside(double r)       /* 다른 파일이 고칠 수 있다 */
{
    struct shape s = { &open_ops, r };
    return shape_area(&s);
}
double built_at_run_time(double r)     /* 표가 실행 때 정해진다 */
{
    struct shape s = { built_ops, r };
    return shape_area(&s);
}
/* static const 표 하나뿐이나 객체가 밖에서 온다 */
double from_caller(const struct shape *s)
{
    return shape_area(s);
}

void build(void)
{
    struct shape_ops *t = malloc(sizeof *t);
    if (t) { *t = circle_ops; built_ops = t; }
}

/* 인라인 캐시와 다형 인라인 캐시 --- 호출 자리마다 캐시를 둔다.
   Smalltalk 와 JIT 런타임은 호출하는 기계어 자체를 고쳐 쓴다. C 는 제 코드를
   고쳐 쓸 수 없으므로, 호출 옆에 static 변수를 두고 그 호출만 그것을 쓴다.
   - 한 칸(IC): 「지난번 클래스 → 함수」 하나.
   - 네 칸(PIC): 그런 칸 넷. 놓치면 칸을 차례로 바꾼다.
   - 메가모픽: 다 찬 PIC 가 놓치면 그 자리는 비교를 그만두고
     클래스별 캐시로 간다.
   칸마다 세대 번호를 적는다. 72장의 lookup.c 와 같은 까닭이다 ---
   실행 때 바뀐 메서드가 캐시에 남으면 안 된다. */
#include <stdio.h>

struct object;
typedef double (*imp)(const struct object *self);

struct method { unsigned sel; imp fn; };
struct entry { const struct class *cls; imp fn; unsigned epoch; };
struct class {
    const struct class *parent;
    struct method methods[2];
    unsigned n_methods;
    double factor;
    struct entry cache;                  /* 클래스별 캐시, 여기서는 셀렉터 하나 */
};
struct object { struct class *isa; double size; };

enum { SEL_AREA = 1 };

static unsigned epoch = 1;               /* 메서드가 바뀔 때마다 오른다 */
static unsigned slow_lookups;

static imp lookup_slow(const struct class *c, unsigned sel)
{
    slow_lookups++;
    for (; c; c = c->parent)
        for (unsigned i = 0; i < c->n_methods; i++)
            if (c->methods[i].sel == sel) return c->methods[i].fn;
    return nullptr;
}
static imp lookup_class_cache(struct class *c, unsigned sel)
{
    if (c->cache.epoch != epoch)
        c->cache = (struct entry){ c, lookup_slow(c, sel), epoch };
    return c->cache.fn;
}

/* ---- 호출 자리 하나의 캐시 ---- */
/* 셀렉터는 적지 않는다: 한 자리에서 보내는 메시지는 늘 같다. */
struct site {
    struct entry e[4];
    unsigned ways, next;                 /* 쓰는 칸 수(1 또는 4), 다음에 바꿀 칸 */
    bool megamorphic;
    unsigned sends, misses;
};

static double send_at(struct site *s, struct object *o, unsigned sel)
{
    s->sends++;
    if (s->megamorphic)                  /* 비교를 그만둠: 클래스별 캐시 */
        return lookup_class_cache(o->isa, sel)(o);
    for (unsigned i = 0; i < s->ways; i++)
        if (s->e[i].cls == o->isa && s->e[i].epoch == epoch)
            return s->e[i].fn(o);        /* 맞음: 칸마다 비교 하나, 찾기 없음 */
    s->misses++;
    if (s->ways > 1 && s->e[s->next].cls && s->e[s->next].epoch == epoch) {
        s->megamorphic = true;           /* 다 찼는데 놓침: 비교를 접는다 */
        return lookup_class_cache(o->isa, sel)(o);
    }
    imp fn = lookup_slow(o->isa, sel);
    s->e[s->next] = (struct entry){ o->isa, fn, epoch };
    s->next = (s->next + 1) % s->ways;
    return fn(o);
}

static const char *state(const struct site *s)
{
    if (s->megamorphic) return "megamorphic";
    unsigned used = 0;
    for (unsigned i = 0; i < s->ways; i++) used += s->e[i].epoch == epoch;
    return used == 0 ? "empty" : used == 1 ? "monomorphic" : "polymorphic";
}
static void report(const char *label, struct site *s, double sum)
{
    printf("  %-12s sum %5g, %2u sends, %2u misses, %-11s (slow lookups %u)\n",
           label, sum, s->sends, s->misses, state(s), slow_lookups);
    s->sends = s->misses = 0;
    slow_lookups = 0;
}

/* 호출 자리 둘. 블록 안의 static 이 그 아래 호출 하나의 캐시다. */
static void total_area_ic(struct object *xs, size_t n)
{
    static struct site here = { .ways = 1 };   /* 이 호출 자리만의 캐시 */
    double sum = 0;
    for (size_t i = 0; i < n; i++) sum += send_at(&here, &xs[i], SEL_AREA);
    report("1-entry IC", &here, sum);
}
static void total_area_pic(struct object *xs, size_t n)
{
    static struct site here = { .ways = 4 };   /* 이 자리의 것 */
    double sum = 0;
    for (size_t i = 0; i < n; i++) sum += send_at(&here, &xs[i], SEL_AREA);
    report("4-entry PIC", &here, sum);
}

/* ---- 클래스들: 넓이는 모두 계수 × 크기 × 크기 ---- */
static double scaled_area(const struct object *self)
{ return self->isa->factor * self->size * self->size; }
static double circle_area(const struct object *self)
{ return 3 * self->size * self->size; }
static double circle_area_2(const struct object *self)      /* 실행 때 바꿔 넣는다 */
{ return 3.14 * self->size * self->size; }

static struct class shape = {
    .methods = { { SEL_AREA, scaled_area } }, .n_methods = 1, .factor = 1 };
static struct class circle = {
    .parent = &shape, .methods = { { SEL_AREA, circle_area } }, .n_methods = 1 };
#define KIND(var, f) static struct class var = { .parent = &shape, .factor = f }
KIND(square, 1); KIND(triangle, 0.5); KIND(hexagon, 2.5);
KIND(kite, 0.5); KIND(star, 4);

static void scene(const char *title, struct object *xs, size_t n)
{
    puts(title);
    total_area_ic(xs, n);
    total_area_pic(xs, n);
}

int main(void)
{
    struct object same[8], two[8], six[12];
    struct class *six_kinds[] = { &circle, &square, &triangle, &hexagon, &kite, &star };
    for (size_t i = 0; i < 8; i++) {
        same[i] = (struct object){ &circle, 1 };
        two[i] = (struct object){ i % 2 ? &square : &circle, 1 };
    }
    for (size_t i = 0; i < 12; i++) six[i] = (struct object){ six_kinds[i % 6], 1 };

    scene("one class only (8 circles):", same, 8);
    scene("two classes taking turns (circle, square, ...):", two, 8);
    scene("two classes again, after the first round:", two, 8);
    scene("six classes taking turns:", six, 12);

    puts("change Circle's area at run time (generation rises), then two classes:");
    circle.methods[0].fn = circle_area_2;
    epoch++;
    total_area_ic(two, 8);
    total_area_pic(two, 8);
    return 0;
}

#!/bin/sh
# 같은 측정(../bench)을 완화 기법 둘 아래에서, 견줄 빌드와 나란히 돌린다:
#   retpoline  GCC -mindirect-branch=thunk, Clang -mretpoline
#              (견줄 것은 보통 -O2, 곧 ../bench)
#   CFI        Clang -flto -fvisibility=hidden -fsanitize=cfi-icall
#              (견줄 것은 CFI 만 뺀 같은 LTO 빌드 --- 먼저 찍는다)
# 넷 다 C 가 아니라 컴파일러 옵션이다. 툴체인이 거절한 빌드는 돌리지 않고
# 그렇다고 알린다.
set -u
cd "$(dirname "$0")"
tmp=$(mktemp -d)
trap 'rm -rf "$tmp"' EXIT INT TERM
pin=""
if command -v taskset >/dev/null 2>&1 && [ "$(nproc 2>/dev/null || echo 1)" -gt 2 ]; then
    pin="taskset -c 2"
fi
src="../bench/ways.c ../bench/harness.c"
w="-std=c23 -Wall -Wextra -Werror -O2"
lto="-flto -fvisibility=hidden -fuse-ld=lld"
shape() {   # 컴파일러가 m_switch 를 점프 표(간접 점프 하나)로 냈는가?
    command -v objdump >/dev/null 2>&1 || return 0
    objdump -d --no-show-raw-insn "$1" |
        awk '/<m_switch>:/ { p = 1; next } /^$/ { p = 0 } p' > "$tmp/s.s"
    [ -s "$tmp/s.s" ] || return 0
    if grep -Eq 'jmp[a-z]* +\*|thunk|retpoline|[[:space:]]br[[:space:]]' "$tmp/s.s"; then
        echo "switch compiled to: a jump table (one indirect jump)"
    else
        echo "switch compiled to: a chain of compares (no indirect jump)"
    fi
}
run() {   # label, compiler, options...
    label=$1; cc=$2; shift 2
    echo "== $label"
    # shellcheck disable=SC2086
    if command -v "$cc" >/dev/null 2>&1 && $cc $w "$@" $src -o "$tmp/b" 2>/dev/null; then
        $pin "$tmp/b" short
        case $label in *retpoline*) shape "$tmp/b" ;; esac
    else
        echo "this toolchain cannot build it, skipped"
    fi
}
run "gcc -O2 -mindirect-branch=thunk (retpoline)" gcc -mindirect-branch=thunk
run "clang -O2 -mretpoline" clang -mretpoline
# shellcheck disable=SC2086
run "clang -O2 -flto (the control for CFI)" clang $lto
# shellcheck disable=SC2086
run "clang -O2 -flto -fsanitize=cfi-icall" clang $lto -fsanitize=cfi-icall

/* 표의 칸에 타입이 틀린 함수가 들어갔다. C 로는 정의되지 않은 동작이다(6.3.2.3p8).
   보통 빌드는 그냥 부르고, Clang 의 CFI 빌드는 부르기 전에 멈춘다. */
#include <stdio.h>

struct shape;
struct shape_ops { double (*area)(const struct shape *); };
struct shape { const struct shape_ops *ops; double r; };

static double circle_area(const struct shape *s) { return 3.0 * s->r * s->r; }
static long   count_lines(const char *text)          /* 타입이 다른 함수 */
{
    long n = 0;
    for (; text && *text; text++) n += *text == '\n';
    return n;
}

/* void (*)(void) 를 거치는 변환은 -Wcast-function-type 을 피한다 ---
   컴파일러가 잡지 못하는 실수를 흉내 낸다 */
static struct shape_ops ops = { circle_area };

int main(void)
{
    struct shape s = { &ops, 2.0 };
    printf("right slot: %.1f\n", s.ops->area(&s));
    fflush(stdout);
    ops.area = (double (*)(const struct shape *))(void (*)(void))count_lines;
    printf("wrong slot: ");
    fflush(stdout);
    double a = s.ops->area(&s);     /* 돌아온 값은 쓰레기다 --- 찍지 않는다 */
    (void)a;
    puts("the call went through --- nothing stopped it");
    return 0;
}