Memoized DFS: tld(id) = loop_depth(id) + max over CALLS-callees of tld(callee). * state: 0=unvisited, 1=in-progress (back-edge -> cycle), 2=done. */
| 234 | /* Memoized DFS: tld(id) = loop_depth(id) + max over CALLS-callees of tld(callee). |
| 235 | * state: 0=unvisited, 1=in-progress (back-edge -> cycle), 2=done. */ |
| 236 | static int tld_dfs(tld_ctx_t *cx, int64_t id, int depth) { |
| 237 | tld_graph_t *g = cx->g; |
| 238 | if (id < 1 || id > g->maxid) { |
| 239 | return 0; |
| 240 | } |
| 241 | if (cx->state[id] == 2) { |
| 242 | return cx->tld[id]; |
| 243 | } |
| 244 | if (cx->state[id] == 1) { |
| 245 | g->recursive[id] = true; /* back edge -> call-graph cycle */ |
| 246 | return 0; |
| 247 | } |
| 248 | if (depth > CBM_TLD_MAX_DEPTH) { |
| 249 | return g->loop_depth[id]; |
| 250 | } |
| 251 | int ne = g->first[id + 1] - g->first[id]; |
| 252 | if (ne > cx->callee_cap - cx->callee_top) { |
| 253 | return g->loop_depth[id]; /* unreachable by construction; same as the depth cap */ |
| 254 | } |
| 255 | cx->state[id] = 1; |
| 256 | tld_callee_t *callees = cx->callees + cx->callee_top; |
| 257 | int nc = 0; |
| 258 | for (int i = g->first[id]; i < g->first[id + 1]; i++) { |
| 259 | int64_t c = g->callee[i]; |
| 260 | if (c == id) { |
| 261 | g->recursive[id] = true; /* direct self-recursion */ |
| 262 | continue; |
| 263 | } |
| 264 | callees[nc].id = c; |
| 265 | callees[nc].key = c >= 1 && c <= g->maxid && g->present[c] ? &g->keys[c] : NULL; |
| 266 | nc++; |
| 267 | } |
| 268 | cx->callee_top += nc; |
| 269 | qsort(callees, (size_t)nc, sizeof(*callees), cmp_callee_canonical); |
| 270 | int best = 0; |
| 271 | for (int i = 0; i < nc; i++) { |
| 272 | int ct = tld_dfs(cx, callees[i].id, depth + 1); |
| 273 | if (ct > best) { |
| 274 | best = ct; |
| 275 | } |
| 276 | } |
| 277 | cx->callee_top -= nc; |
| 278 | cx->tld[id] = g->loop_depth[id] + best; |
| 279 | cx->state[id] = 2; |
| 280 | return cx->tld[id]; |
| 281 | } |
| 282 | |
| 283 | /* Runs the traversal from every seed in canonical order; *tld_out[id] and |
| 284 | * g->recursive[id] then hold each seed's result. */ |