1 /* 2 * Copyright (C) 2019 Collabora, Ltd. 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, sublicense, 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 next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * 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 NONINFRINGEMENT. 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 FROM, 20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 21 * SOFTWARE. 22 * 23 * Authors (Collabora): 24 * Alyssa Rosenzweig <[email protected]> 25 */ 26 27 #ifndef __LCRA_H 28 #define __LCRA_H 29 30 #include <stdbool.h> 31 #include <stdint.h> 32 33 struct lcra_state { 34 unsigned node_count; 35 36 /* Alignment for node in log2(bytes)+1. Since alignment must be 37 * non-negative power-of-two, the elements are strictly positive 38 * integers. Zero is the sentinel for a missing node. In upper word, 39 * bound. */ 40 unsigned *alignment; 41 42 /* Linear constraints imposed. Nested array sized upfront, organized as 43 * linear[node_left][node_right]. That is, calculate indices as: 44 * 45 * Each element is itself a bit field denoting whether (c_j - c_i) bias 46 * is present or not, including negative biases. 47 * 48 * Note for Midgard, there are 16 components so the bias is in range 49 * [-15, 15] so encoded by 32-bit field. */ 50 51 uint32_t *linear; 52 53 /* Per node max modulus constraints */ 54 uint8_t *modulus; 55 56 /* Classes allow nodes to be partitioned with a starting register. 57 * Classes cannot interfere; that is, they are true partitions in the 58 * usual sense of the word. class_count is the number of classes. 59 * class[] is indexed by a node to get the mapped class. class_start is 60 * biased to all solutions in the class. */ 61 62 unsigned class_count; 63 unsigned *class; 64 unsigned *class_start; 65 unsigned *class_size; 66 bool *class_disjoint; 67 68 /* Before solving, forced registers; after solving, solutions. */ 69 unsigned *solutions; 70 71 /* For register spilling, the costs to spill nodes (as set by the user) 72 * are in spill_cost[], negative if a node is unspillable. Internally, 73 * spill_class specifies which class to spill (whichever class failed 74 * to allocate) */ 75 76 signed *spill_cost; 77 unsigned spill_class; 78 }; 79 80 struct lcra_state *lcra_alloc_equations(unsigned node_count, 81 unsigned class_count); 82 83 void lcra_free(struct lcra_state *l); 84 85 void lcra_set_disjoint_class(struct lcra_state *l, unsigned c1, unsigned c2); 86 87 void lcra_set_alignment(struct lcra_state *l, unsigned node, 88 unsigned align_log2, unsigned bound); 89 90 void lcra_restrict_range(struct lcra_state *l, unsigned node, unsigned len); 91 92 void lcra_add_node_interference(struct lcra_state *l, unsigned i, 93 unsigned cmask_i, unsigned j, unsigned cmask_j); 94 95 bool lcra_solve(struct lcra_state *l); 96 97 void lcra_set_node_spill_cost(struct lcra_state *l, unsigned node, signed cost); 98 99 signed lcra_get_best_spill_node(struct lcra_state *l); 100 101 #endif 102