Implementation of def-use-chain

[fennecJ]

While reviewing ssa.c, I came across the comment:

/* TODO: simplify with def-use chain */

It made me wonder if the compiler already has a proper implementation of a def-use (DU) chain. The closest structure I found resembles a DU-chain, with some members inside the var struct:

struct var {
    ...
    struct var *base;
    int subscript;
    struct var *subscripts[64];
    int subscripts_idx;
    struct insn *last_assign;
    rename_t rename;
    ...
};

From what I understand：

• base stores the original definition of the variable before renaming during SSA construction.
• The subscript mirrors base->rename.counter to track how many times the variable has been renamed.
• The subscripts array records the history of all previous variable versions before renaming.
• The last_assign member seems to function like a use-def chain (i.e., the reverse of a DU chain), capturing the most recent assignment of the variable.
• Finally, the rename member appears to track the renaming information for variables.

Could you confirm whether this design is meant to serve as a DU-chain or if further improvements are needed to implement one more explicitly?

If a DU-chain still needs to be implemented, I propose the following approach:

For each fn->bbs, we introduce a new data structure, the DU-chain, which will be a hash map. The hash function will convert the string var->var_name and the rename count var->subscript into a hash value. Each DU-chain entry will store two pieces of data:

• insn_t var_def: the instruction defining the variable.
• insn_list_t var_use: a list of instructions where the variable is used.

Each DU-chain entry will be a linked list to handle potential hash collisions.

For every instruction:

• If it contains rd (a destination register), it will be inserted into the DU-chain based on the hashed key.
• If it contains rs1, rs2 (source registers), the corresponding definition will be searched for in the DU-chain. If found, the instruction will be appended to the var_use list of the relevant DU entry. If not found, we will check if var->is_global is true. If not, an error will be raised for the use of an undeclared variable.

Please let me know if I’ve misunderstood anything or if this approach doesn't meet your expectations. I’m also open to any suggestions for improvement.

Thanks in advance!