docs/jit-regalloc

   1 Register Allocation
   2 ===================
   3
   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.
   8
   9 Register Allocation for Trees
  10 =============================
  11
  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.
  14
  15 gboolean
  16 tree_allocate_regs (tree, exclude_reg)
  17 {
  18         if (!tree_allocate_regs (tree->left, -1))
  19                 return FALSE;
  20
  21         if (!tree_allocate_regs (tree->right, -1)) {
  22
  23                 tree->left->spilled == TRUE;
  24
  25                 free_used_regs (tree->left);
  26
  27                 if (!tree_allocate_regs (tree->right, tree->left->reg))
  28                         return FALSE;
  29         }
  30
  31         free_used_regs (tree->left);
  32         free_used_regs (tree->right);
  33
  34         /* try to allocate a register (reg != exclude_reg) */
  35         if ((tree->reg = next_free_reg (exclude_reg)) != -1)
  36                 return TRUE;
  37
  38         return FALSE;
  39 }
  40
  41 The emit routing actually spills the registers:
  42
  43 tree_emit (tree)
  44 {
  45
  46         tree_emit (tree->left);
  47
  48         if (tree->left->spilled)
  49                 save_reg (tree->left->reg);
  50
  51         tree_emit (tree->right);
  52
  53         if (tree->left->spilled)
  54                 restore_reg (tree->left->reg);
  55
  56
  57         emit_code (tree);
  58 }
  59
  60
  61 Global Register Allocation
  62 ==========================
  63
  64 TODO.