4 The current JIT implementation uses a tree matcher to generate code. We use a
5 simple algorithm to allocate registers in trees, and limit the number of used
6 temporary register to 4 when evaluating trees. So we can use 2 registers for
7 global register allocation.
9 Register Allocation for Trees
10 =============================
12 We always evaluate trees from left to right. When there are no more registers
13 available we need to spill values to memory. Here is the simplified algorithm.
16 tree_allocate_regs (tree, exclude_reg)
18 if (!tree_allocate_regs (tree->left, -1))
21 if (!tree_allocate_regs (tree->right, -1)) {
23 tree->left->spilled == TRUE;
25 free_used_regs (tree->left);
27 if (!tree_allocate_regs (tree->right, tree->left->reg))
31 free_used_regs (tree->left);
32 free_used_regs (tree->right);
34 /* try to allocate a register (reg != exclude_reg) */
35 if ((tree->reg = next_free_reg (exclude_reg)) != -1)
41 The emit routing actually spills the registers:
46 tree_emit (tree->left);
48 if (tree->left->spilled)
49 save_reg (tree->left->reg);
51 tree_emit (tree->right);
53 if (tree->left->spilled)
54 restore_reg (tree->left->reg);
61 Global Register Allocation
62 ==========================