1/*
2 * Copyright (c) 2017 Lima Project
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sub license,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the
12 * next paragraph) shall be included in all copies or substantial portions
13 * of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 *
23 */
24
25#include <limits.h>
26
27#include "gpir.h"
28
29/* Linear scan register alloc for physical reg alloc of each
30 * load/store node
31 */
32
33static void regalloc_print_result(gpir_compiler *comp)
34{
35   if (!(lima_debug & LIMA_DEBUG_GP))
36      return;
37
38   int index = 0;
39   printf("======== physical regalloc ========\n");
40   list_for_each_entry(gpir_block, block, &comp->block_list, list) {
41      list_for_each_entry(gpir_node, node, &block->node_list, list) {
42         if (node->op == gpir_op_load_reg) {
43            gpir_load_node *load = gpir_node_to_load(node);
44            printf("%03d: load %d use reg %d\n", index, node->index, load->reg->index);
45         }
46         else if (node->op == gpir_op_store_reg) {
47            gpir_store_node *store = gpir_node_to_store(node);
48            printf("%03d: store %d use reg %d\n", index, node->index, store->reg->index);
49         }
50         index++;
51      }
52      printf("----------------------------\n");
53   }
54}
55
56bool gpir_physical_regalloc_prog(gpir_compiler *comp)
57{
58   int index = 0;
59   list_for_each_entry(gpir_block, block, &comp->block_list, list) {
60      list_for_each_entry(gpir_node, node, &block->node_list, list) {
61         node->preg.index = index++;
62      }
63   }
64
65   /* calculate each reg liveness interval */
66   list_for_each_entry(gpir_reg, reg, &comp->reg_list, list) {
67      reg->start = INT_MAX;
68      list_for_each_entry(gpir_store_node, store, &reg->defs_list, reg_link) {
69         if (store->node.preg.index < reg->start)
70            reg->start = store->node.preg.index;
71      }
72
73      reg->end = 0;
74      list_for_each_entry(gpir_load_node, load, &reg->uses_list, reg_link) {
75         if (load->node.preg.index > reg->end)
76            reg->end = load->node.preg.index;
77      }
78   }
79
80   /* sort reg list by start value */
81   struct list_head reg_list;
82   list_replace(&comp->reg_list, &reg_list);
83   list_inithead(&comp->reg_list);
84   list_for_each_entry_safe(gpir_reg, reg, &reg_list, list) {
85      struct list_head *insert_pos = &comp->reg_list;
86      list_for_each_entry(gpir_reg, creg, &comp->reg_list, list) {
87         if (creg->start > reg->start) {
88            insert_pos = &creg->list;
89            break;
90         }
91      }
92      list_del(&reg->list);
93      list_addtail(&reg->list, insert_pos);
94   }
95
96   /* do linear scan reg alloc */
97   gpir_reg *active[GPIR_PHYSICAL_REG_NUM] = {0};
98   list_for_each_entry(gpir_reg, reg, &comp->reg_list, list) {
99      int i;
100
101      /* if some reg is expired */
102      for (i = 0; i < GPIR_PHYSICAL_REG_NUM; i++) {
103         if (active[i] && active[i]->end <= reg->start)
104            active[i] = NULL;
105      }
106
107      /* find a free reg value for this reg */
108      for (i = 0; i < GPIR_PHYSICAL_REG_NUM; i++) {
109         if (!active[i]) {
110            active[i] = reg;
111            reg->index = i;
112            break;
113         }
114      }
115
116      /* TODO: support spill to temp memory */
117      assert(i < GPIR_PHYSICAL_REG_NUM);
118   }
119
120   /* update load/store node info for the real reg */
121   list_for_each_entry(gpir_reg, reg, &comp->reg_list, list) {
122      list_for_each_entry(gpir_store_node, store, &reg->defs_list, reg_link) {
123         store->index = reg->index >> 2;
124         store->component = reg->index % 4;
125      }
126
127      list_for_each_entry(gpir_load_node, load, &reg->uses_list, reg_link) {
128         load->index = reg->index >> 2;
129         load->index = reg->index % 4;
130      }
131   }
132
133   regalloc_print_result(comp);
134   return true;
135}
136