1 /*
2 * Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 */
17
18 /** \file
19 *
20 * \brief Utility functions for optimizer submodule responsible for performing
21 * flow analysis. Used by the optimizer and vectorizer in the frontend and
22 * backend.
23 */
24
25 #include "flow_util.h"
26
27 /*
28 * Hash of new uses. We were previously using a linear search of opt.useb each
29 * time a new use was added for O(N^2), which was impacting compile times.
30 * Replacing the linear search with a hash lookup results in O(N).
31 */
32 static hashmap_t use_hash = NULL;
33
34 /*
35 * Allocate a new use_hash.
36 */
37 void
use_hash_alloc()38 use_hash_alloc()
39 {
40 use_hash = hashmap_alloc(hash_functions_direct);
41 } /* use_hash_alloc */
42
43 /*
44 * Clear and free the use_hash.
45 */
46 void
use_hash_free()47 use_hash_free()
48 {
49 if (use_hash) {
50 hashmap_clear(use_hash);
51 hashmap_free(use_hash);
52 use_hash = NULL;
53 }
54 } /* use_hash_free */
55
56 /*
57 * Clear, free, and reallocate the use_hash.
58 */
59 void
use_hash_reset()60 use_hash_reset()
61 {
62 if (use_hash) {
63 use_hash_free();
64 }
65 use_hash_alloc();
66 } /* use_hash_reset */
67
68 /*
69 * Turn the fields of the use into a hash_key_t. Hash function requires to
70 * avoid clustering in lower bits of hash.
71 *
72 * high: In the backend is ilix, frontend is addrx
73 * mid: In the backend is nmex, frontend is nmex
74 * low: In the backend is iltx, frontend is stdx
75 */
76 static hash_key_t
use_hash_key(bool high_bit,bool use_high,int high,int mid,int low)77 use_hash_key(bool high_bit, bool use_high, int high, int mid, int low)
78 {
79 long long key;
80 // lower USE_HASH_BITS bits of mask set, upper bits cleared.
81 long long mask = ((long long)1 << USE_HASH_BITS)-1;
82
83 // This only works if the number of nme, ili, and ilt are each less than 2^USE_HASH_BITS
84 if (use_high)
85 assert(high < (int)mask, "too many ILIs to hash", high, ERR_Fatal);
86 assert(mid < (int)mask, "too many NMEs to hash", mid, ERR_Fatal);
87 assert(low < (int)mask, "too many ILTs to hash", low, ERR_Fatal);
88
89 key = 0;
90 if (high_bit)
91 key |= (long long)1; // top bit high_bit flag
92 key <<= 1;
93 if (use_high && !high_bit)
94 key |= ((long long)high & mask);
95 key <<= USE_HASH_BITS;
96 key |= (mid & mask);
97 key <<= USE_HASH_BITS;
98 key |= (low & mask);
99
100 assert((void*)key != NULL, "NULL key computed", key, ERR_Fatal);
101 assert((void*)key != (void*)~0UL, "~0UL key computed", key, ERR_Fatal);
102
103 return (hash_key_t)key;
104 } /* use_hash_key */
105
106 /*
107 * From the fields of a new use, create a hash key, and insert the use into the
108 * use_hash with the key.
109 */
110 void
use_hash_insert(int usex,bool high_bit,bool use_match_ili,int ilix,int nmex,int iltx)111 use_hash_insert(int usex, bool high_bit, bool use_match_ili, int ilix, int nmex, int iltx)
112 {
113 hash_key_t key = use_hash_key(high_bit, use_match_ili, ilix, nmex, iltx);
114 hash_data_t data = INT2HKEY(usex);
115 hashmap_replace(use_hash, key, &data);
116 } /* use_hash_insert */
117
118 /*
119 * From the fields of a potential new use, create a hash key, and check the
120 * use_hash to see of that potential use has already been inserted. Return the
121 * existing use, if it exists.
122 *
123 * We were previously using a linear search of opt.useb each time a new use was
124 * added for O(N^2), which was impacting compile times. Replacing the linear
125 * search with a hash lookup results in O(N).
126 */
127 int
use_hash_lookup(bool high_bit,bool use_match_ili,int ilix,int nmex,int iltx)128 use_hash_lookup(bool high_bit, bool use_match_ili, int ilix, int nmex, int iltx)
129 {
130 hash_data_t usex = NULL;
131 hash_key_t key = use_hash_key(high_bit, use_match_ili, ilix, nmex, iltx);
132 if (hashmap_lookup(use_hash, key, &usex)) {
133 return HKEY2INT(usex);
134 }
135 return 0;
136 } /* use_hash_lookup */
137
138 #if DEBUG
139 /*
140 * Helper function to use_hash_dump() to dump a single use_hash entry.
141 */
142 static void
use_hash_dump_one(hash_key_t key,hash_data_t data,void * context)143 use_hash_dump_one(hash_key_t key, hash_data_t data, void *context)
144 {
145 FILE* dfile = stderr;
146 fprintf(dfile, "use_hash key:%zu data:%zu\n", (size_t)key, (size_t)data);
147 //_dumpuse(HKEY2INT(data), true);
148 fprintf(dfile, "\n");
149 } /* use_hash_dump_one */
150
151 /*
152 * Dump routine for the use_hash designed to be called from a debugger.
153 */
154 void
use_hash_dump()155 use_hash_dump()
156 {
157 hashmap_iterate(use_hash, use_hash_dump_one, NULL);
158 } /* use_hash_dump */
159
160 /*
161 * use_hash utility function to compare the results of the hash search (usex)
162 * to the results of the older and slower linear search (lusex).
163 */
164 void
use_hash_check(int usex,int lusex,bool found)165 use_hash_check(int usex, int lusex, bool found)
166 {
167 if (found && (usex == lusex)) {
168 // Success. Both methods found the same use.
169 } else if (found && !usex) {
170 // Failure. Linear search found a use, but the hash lookup found nothing.
171 assert(0, "use_hash failed should be found", lusex, ERR_Fatal);
172 } else if (!found && usex) {
173 // Failure. Linear search found nothing, but hash lookup found a use.
174 assert(0, "use_hash failed shouldn't be found", usex, ERR_Fatal);
175 } else {
176 // Success. Boh methods found no use.
177 }
178 } /* use_hash_check */
179 #endif /* DEBUG */
180