#BEGIN_LEGAL # #Copyright (c) 2023 Intel Corporation # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # #END_LEGAL import math import collections import genutil import ildutil import codegen import hashmul import hashfks import hashlin import xedhash # phash means "perfect hash". _l1_bucket_max = 8 # FIXME: also in hashfks.py #FIXME: using 64 bits for _hkey_ctype because sometimes 16bi-UIMM00 is #a constraint and we are out of 32 bits for hashing. #However, this takes too much space. We can check how many bits #are used and decide based on that about the key type, and in most cases #that will be 32 bits. _notfound_str = '0' class phash_t(object): def __init__(self, cdict, hash_f): self.cdict = cdict self.hash_f = hash_f self.x2hx = {} self.hx2x = {} def is_minimal(self): return self.hash_f.get_table_size() == len(self.cdict.tuple2rule) #generate the operands getters def add_cgen_key_lines(self, fo): #declare hash key variable key_str = self.cdict.strings_dict['key_str'] key_type = self.cdict.strings_dict['key_type'] fo.add_code_eol('%s %s = 0' % (key_type,key_str)) bit_shift = 0 nt_lups = [] for i,cname in enumerate(self.cdict.cnames): access_str, lu_name = self.cdict.get_operand_accessor(cname) nt_lups.append(lu_name) #constraints might have 1,2 or 3 bit widths #and we allocate bits in the key vector appropriately #e.g REXB operand gets only 1 bit in the key #and RM gets 3 bits shift_val = ('(%s)' % bit_shift) bit_shift += self.cdict.op_widths[cname] code = 'key += ((%s) %s) << (%s)' % (key_type, access_str, shift_val) fo.add_code_eol(code) fo.add_code_eol('return %s' % key_str) return nt_lups def add_lookup_lines(self, fo): key_validation = self.hash_f.add_key_validation(self.cdict.strings_dict) fo.add_code('%s {' % key_validation) actions = self.cdict.action_codegen.emit_actions() for a in actions: fo.add_code_eol(" " + a) if self.cdict.action_codegen.has_fcall(): fo.add_code_eol(" return res") #FIXME: this is a temporary, when we will implement the iform encoding # we will be able to remove this code if genutil.field_check(self.cdict, 'ntluf') or \ genutil.field_check(self.cdict, 'nt'): fo.add_code_eol(" return 1") fo.add_code('}') # get the default action that will executed when we did not hit valid # look up table entry default = self.cdict.action_codegen.emit_default() fo.add_code('else{') for line in default: fo.add_code_eol(" %s" % line) fo.add_code('}') def add_find_lines(self, fo): #apply hash function on the key hash_expr = self.hash_f.emit_cexpr(self.cdict.strings_dict['key_str']) fo.add_code_eol('%s = %s' % (self.cdict.strings_dict['hidx_str'], hash_expr)) #lookup entry in the table self.add_lookup_lines(fo) #emit the operands lookup function def add_op_lu_function(self,fo,lu_function): if hasattr(self.hash_f,'emit_cvar_decl'): fo.add_code_eol(self.hash_f.emit_cvar_decl()) fo.add_code_eol('%s %s = 0' % (self.cdict.strings_dict['key_type'], self.cdict.strings_dict['key_str'])) fo.add_code_eol('%s %s = 0' % (self.cdict.strings_dict['hidx_type'], self.cdict.strings_dict['hidx_str'])) #Initializing res to 1 since it will not always be read. if self.cdict.action_codegen.has_fcall(): fo.add_code_eol('%s %s = 1' % (self.cdict.strings_dict['hidx_type'], 'res')) obj_str = self.cdict.strings_dict['obj_str'] #FIXME: this is a temporary, when we will implement the iform encoding # we will be able to remove this code if genutil.field_check(self.cdict, 'ntluf'): fo.add_code_eol('xed3_operand_set_outreg(%s,arg_reg)' % obj_str) lu_code = 'key = %s(%s)' % (lu_function, obj_str) fo.add_code_eol(lu_code) def add_lu_table(self, fo): need_validation = self.hash_f.need_hash_index_validation() if self.cdict.action_codegen.no_actions() and not need_validation: #if we do not have any actions and we do not need to do #hash index validation, we do not need to add a look up #table. return actions_str = self.cdict.action_codegen.get_actions_desc() entry_desc = 'typedef struct {' if need_validation: entry_desc += 'xed_uint32_t key;' entry_desc += ' %s} ' % actions_str entry_type = self.cdict.strings_dict['lu_entry'] entry_desc += '%s' % entry_type fo.add_code_eol(entry_desc) arr_def = 'static const %s %s[%d] = {' % ( entry_type, self.cdict.strings_dict['table_name'], self.hash_f.get_table_size() ) fo.add_code(arr_def) elems = [] for hx in range(0, self.hash_f.get_table_size()): if hx in self.hx2x: x = self.hx2x[hx] t = self.cdict.int2tuple[x] actions = self.cdict.action_codegen.get_values(t) ptrn = self.cdict.get_ptrn(t) if need_validation: elem = '/*h(%d)=%d %s*/ {%d, %s}' elem = elem % (x, hx, ptrn , x, actions) else: elem = '/*h(%d)=%d %s*/ {%s}' elem = elem % (x, hx, ptrn , actions) else: #FIXME: make hx signed int and fill empty #slots with -1? #Seems it is enough to set value=0, saying that it's an #illegal instruction # FIXME: x is always just one slot ['0']. That works # correctly but the code logic makes absolutely no # sense. x = self.cdict.action_codegen.get_empty_slots() empty_val = ['0'] + x elem = '/*empty slot1 */ {%s}' % (",".join(empty_val)) if hx != (self.hash_f.get_table_size()-1): elem += ',' fo.add_code(elem) fo.add_code_eol('}') def gen_find_fos(self, fname): # phash_t obj_str = self.cdict.strings_dict['obj_str'] obj_type = self.cdict.strings_dict['obj_type'] key_str= self.cdict.strings_dict['key_str'] hidx_str = self.cdict.strings_dict['hidx_str'] const = self.cdict.strings_dict['obj_const'] lu_namespace = self.cdict.strings_dict['lu_namespace'] #FIXME: this is a temporary, when we will implement the iform encoding # we will be able to remove this code if genutil.field_check(self.cdict, 'ntluf') or \ genutil.field_check(self.cdict, 'nt'): return_type = 'xed_uint32_t' elif self.hash_f.kind() == 'trivial': return_type = 'xed_uint32_t' else: return_type = self.cdict.action_codegen.get_return_type() static = self.cdict.strings_dict['static'] fo = codegen.function_object_t(fname, return_type=return_type, static=static, inline=False) lu_operands = '_'.join(self.cdict.cnames) # temporary function name. we override this later lu_operands_fn = 'xed_lu_%s' % lu_operands key_ctype = self.cdict.strings_dict['key_type'] ild_arg = "%s%s* %s" % (const, obj_type, obj_str) fo.add_arg(ild_arg) if self.hash_f.kind() == 'trivial': operand_lu_fo = None # avoid parmameter-not-used warnings with compilers that # care (like MSVS) fo.add_code_eol("(void)d") # rule is a pattern_t fo.add_code_eol("return {}".format(self.cdict.rule.ii.inum)) else: operand_lu_fo = codegen.function_object_t(lu_operands_fn, return_type=key_ctype, static=False, inline=False, force_no_inline=True) operand_lu_fo.add_arg(ild_arg) if genutil.field_check(self.cdict, 'ntluf'): fo.add_arg('xed_reg_enum_t arg_reg') #add key-computing code (constraints tuple to integer) nt_lups = self.add_cgen_key_lines(operand_lu_fo) #Several nonterminals have special getter functions. The #add_cgen_key_lines function returns a list of all the #nt_lups and regular cnames. (lu_operands is not always #the same as the underscore-joined nt_lups.) lu_operands_fn = 'xed_%s_lu_%s' % (lu_namespace,'_'.join(nt_lups)) operand_lu_fo.set_function_name(lu_operands_fn) #add the operands lookup function self.add_lu_table(fo) self.add_op_lu_function(fo,lu_operands_fn) self.add_find_lines(fo) return ([fo],operand_lu_fo) def __str__(self): lines = ['-----------PHASH-------------'] lines.append('tuple scheme:') line = '' lines.append(' '.join(self.cdict.cnames)) lines.append('m=%d' % self.hash_f.get_table_size()) lines.append('%s' % self.hash_f) lines.append('tuple x -> value') for tuple_val in self.tuple_dict.keys(): x = self.t2x[tuple_val] value = self.tuple_dict[tuple_val] line = '%s %s -> %s' % (tuple_val,x, str(value)) lines.append(line) lines.append('-------------------------------------') return '\n'.join(lines)+ '\n' def get_size(self): return self.hash_f.get_table_size() def update_stats(self, stats): stats['3. #hashes'] += 1 size = self.get_size() stats['2. #hentries'] += size stats['4. #min_hashes'] += self.is_minimal() if size <= 10: stats['5. #cdict_size_1_to_10'] += 1 elif 10 < size and size <= 20: stats['6. #cdict_size_10_to_20'] += 1 elif 20 < size and size <= 100: stats['7. #cdict_size_20_to_100'] += 1 else: stats['8. #cdict_size_at_least_100'] += 1 class l1_phash_t(phash_t): def __init__(self, cdict, hash_f): phash_t.__init__(self, cdict, hash_f) for t,x in cdict.tuple2int.items(): hash_val = self.hash_f.apply(x) if hash_val in list(self.x2hx.values()): msg = "l1_phash_t: %s\n function is not perfect!\n" msg += 'hashval=%d , x2hx: %s' % (hash_val, self.x2hx) ildutil.ild_err(msg) self.x2hx[x] = hash_val self.hx2x[hash_val] = x # the index attribute is used to determine the ordinal of the emit # rule, adding 1 since legal hash values starts in 0 but # legal ordinal starts at 1 self.cdict.tuple2rule[t].index = hash_val + 1 def __str__(self): lines = ['-----------1-LEVEL-PHASH-------------'] lines.append('tuple scheme:') line = '' lines.append(' '.join(self.cdict.cnames)) lines.append('m=%d' % self.hash_f.get_table_size()) lines.append('%s' % self.hash_f) lines.append('tuple x h(x) -> value') for tuple_val in sorted(self.cdict.tuple2rule.keys()): x = self.cdict.tuple2int[tuple_val] ptrn = self.cdict.get_ptrn(tuple_val) action = self.cdict.action_codegen.get_values(tuple_val) hx = self.x2hx[x] line = '%s %s %s -> %s, %s' % (tuple_val,x, hx, ptrn, action) lines.append(line) lines.append('-------------------------------------') return '\n'.join(lines) + '\n' class l2_phash_t(phash_t): def __init__(self, cdict, hash_f): global _l1_bucket_max phash_t.__init__(self, cdict, hash_f) hx2tuples = collections.defaultdict(list) for t,x in self.cdict.tuple2int.items(): hx = self.hash_f.apply(x) if len(hx2tuples[hx]) >= _l1_bucket_max: msg = "l2_phash_t: function does not distribute well!\n" msg += 'hashval=%d , hx2tuples: %s' % (hx, hx2tuples) ildutil.ild_err(msg) hx2tuples[hx].append(t) self.x2hx[x] = hx self.hx2x[hx] = x self.hx2phash = {} for hx,tuples in hx2tuples.items(): new_cdict = self.cdict.filter_tuples(tuples) # try (1)linear, then (2)hashmul then (3) fks for the 2nd # level of hash function. phash = None if _is_linear(list(new_cdict.int2tuple.keys())): phash = _get_linear_hash_function(new_cdict) if not phash: phash = _find_l1_phash_mul(new_cdict) if not phash: phash = _find_l1_phash_fks(new_cdict) if phash: self.hx2phash[hx] = phash else: lines = [] for k,v in list(new_cdict.tuple2rule.items()): lines.append('%s -> %s'% ((k,), v)) str = '\n'.join(lines) ildutil.ild_err("Failed to find l1 phash for dict %s" % str) def add_lu_type(self, fo): if genutil.field_check(self.cdict, 'ntluf') or \ genutil.field_check(self.cdict, 'nt'): ret_type = 'xed_uint32_t' else: ret_type = self.cdict.action_codegen.get_return_type() fname = self.cdict.strings_dict['luf_name'] param_name = "%s%s*" % (self.cdict.strings_dict['obj_const'], self.cdict.strings_dict['obj_type']) luf_type = "typedef %s (*%s)(%s)" % (ret_type, fname, param_name) fo.add_code_eol(luf_type) lu_entry = self.cdict.strings_dict['lu_entry'] entry_desc = 'typedef struct {xed_uint32_t key;' entry_desc += ' %s l2_func;} %s' % (fname, lu_entry) fo.add_code_eol(entry_desc) def add_lu_table(self, fo, hx2fo): self.add_lu_type(fo) tname = self.cdict.strings_dict['table_name'] entry = self.cdict.strings_dict['lu_entry'] arr_def = 'static const %s %s[%d] = {' % (entry, tname, self.hash_f.get_table_size()) fo.add_code(arr_def) elems = [] #invert the x2hx mapping hx2x = dict((hx,x) for x,hx in self.x2hx.items()) for hx in range(0, self.hash_f.get_table_size()): if hx in hx2fo: l1_fo = hx2fo[hx] x = hx2x[hx] elem = '/*h(%d)=%d */ {%d, %s},' elem = elem % (x, hx, x, l1_fo.function_name) else: #FIXME: make hx signed int and fill empty #slots with -1? #Seems it is enough to set value=0, saying that it's an #illegal instruction if self.cdict.strings_dict['obj_const']: elem = '/*empty slot2 */ {0, xed_phash_invalid_const},' else: elem = '/*empty slot2 */ {0, xed_phash_invalid},' fo.add_code(elem) fo.add_code_eol('}') def add_lookup_lines(self, fo): hentry_str ='%s[%s]' % (self.cdict.strings_dict['table_name'], self.cdict.strings_dict['hidx_str']) #fo.add_code('if(%s.key != 0) {' % hentry_str) fo.add_code_eol('return (*%s.l2_func)(%s)' % ( hentry_str, self.cdict.strings_dict['obj_str'] )) #fo.add_code('}') #fo.add_code_eol('return %s' % _notfound_str) def gen_find_fos(self, fname): # L2 phash obj_str = self.cdict.strings_dict['obj_str'] obj_type = self.cdict.strings_dict['obj_type'] const = self.cdict.strings_dict['obj_const'] hx2fo = {} for hx,phash in list(self.hx2phash.items()): fid = '%s_%d_l1' % (fname, hx) (hx2fo_list,operand_lu_fo) = phash.gen_find_fos(fid) if not operand_lu_fo: genutil.die("L2 hash cannot have trivial operand lu fn") hx2fo[hx] = hx2fo_list[0] fname = '%s' % fname if genutil.field_check(self.cdict, 'ntluf') or \ genutil.field_check(self.cdict, 'nt'): return_type = 'xed_uint32_t' else: return_type = self.cdict.action_codegen.get_return_type() static = self.cdict.strings_dict['static'] fo = codegen.function_object_t(fname, return_type=return_type, static=static, inline=False) fo.add_arg('%s%s* %s' % (const,obj_type,obj_str)) self.add_lu_table(fo, hx2fo) #we only need to override add_lookup_lines lu_fname = operand_lu_fo.function_name self.add_op_lu_function(fo, lu_fname) self.add_find_lines(fo) fos = list(hx2fo.values()) fos.append(fo) #all the operand_lu_fo going to be the same so we just take the last one return fos,operand_lu_fo def get_size(self): size = self.hash_f.get_table_size() for phash in list(self.hx2phash.values()): size += phash.get_size() return size def __str__(self): lines = ['-----------2-LEVEL-PHASH-------------'] lines.append('m=%d' % self.hash_f.get_table_size()) lines.append('%s' % self.hash_f) for tuple_val in self.cdict.tuple2rule.keys(): lines.append('-------------------------------------') lines.append('tuple x h(x) -> l1_phash') x = self.cdict.tuple2int[tuple_val] hx = self.hash_f.apply(x) phash = self.hx2phash[hx] line = '%s %s %s ->\n%s' % (tuple_val,x, hx, phash) lines.append(line) lines.append('-------------------------------------') return '\n'.join(lines) + '\n' def _zero_constraints(cdict): if len(cdict.cnames)==0: return True return False class trivial_hash_func_t(xedhash.hash_fun_interface_t): """This is a hash function that works with no inputs. Always returns true""" def __init__(self): pass def kind(self): return "trivial" def get_table_size(self): return 1 def apply(self,x): return 0 # not used def emit_cexpr(self, key_str='key'): return '0' # not used def need_hash_index_validation(self): return False def __str__(self): return "h(x) = always true" def _get_zero_constraint_hash(cdict): ''' returns a l1_phash_t that generate a trivial function that is always true''' hash_f = trivial_hash_func_t() return l1_phash_t(cdict, hash_f) def _is_linear(keys): ''' @param keys: list of keys @return: True is the keys in the input list are sequential ''' max_key = max(keys) min_key = min(keys) if (max_key - min_key + 1) == len(keys): return True return False def _get_linear_hash_function(cdict): ''' returns phash_t object with a linear_funct_t as the hash function''' keylist = list(cdict.int2tuple.keys()) hash_f = hashlin.get_linear_hash_function(keylist) return l1_phash_t(cdict, hash_f) def _find_l1_phash_fks(cdict): hashfn = hashfks.find_fks_perfect(list(cdict.tuple2int.values())) if hashfn: return l1_phash_t(cdict, hashfn) return None def _find_candidate_lengths_mul(lst): """Return integer lengths n, n*1.1, n*1.2, ... n*1.9, n*2""" n = len(lst) r = [ int(math.ceil((1 + x/10.0)*n)) for x in range(0,11)] # avoid duplicates s = set() for a in r: # we avoid length 1 tables for hashmul since they throw away # all the bits and should really use the linear hash function # stuff. if a > 1: s.add(a) return sorted(list(s)) def _find_l1_phash_mul(cdict): candidate_lengths = _find_candidate_lengths_mul(cdict.tuple2int) for p in candidate_lengths: hash_f = hashmul.hashmul_t(p) if hash_f.is_perfect(iter(cdict.tuple2int.values())): return l1_phash_t(cdict, hash_f) del hash_f return None def _find_l2_hash_mul(cdict): """Similar to the _find_l1_phash_mul, but not looking for perfection, just well distributed stuff""" global _l1_bucket_max candidate_lengths = _find_candidate_lengths_mul(cdict.tuple2int) for p in candidate_lengths: hash_f = hashmul.hashmul_t(p) if xedhash.is_well_distributed(cdict.tuple2int, hash_f, _l1_bucket_max): return hash_f del hash_f return None def _find_l2_phash(cdict): """Find a 2 level hash table for more complex cases""" # try hashmul first for the first level of the 2 level # hash function. hash_f = _find_l2_hash_mul(cdict) if hash_f: return l2_phash_t(cdict, hash_f) # otherwise try a FKS for the first level of the 2 level hash # function. hash_f = hashfks.find_fks_well_distributed(cdict.tuple2int) if hash_f: return l2_phash_t(cdict, hash_f) ildutil.ild_warn("Failed to find L2 hash function for %s" % cdict) return None def _gen_hash_one_level(cdict): """Generate a 1 level hash function or give up""" if _zero_constraints(cdict): return _get_zero_constraint_hash(cdict) # linear means all keys are sequential. not required to be zero-based. if _is_linear(list(cdict.int2tuple.keys())): return _get_linear_hash_function(cdict) phash = _find_l1_phash_mul(cdict) if phash: return phash phash = _find_l1_phash_fks(cdict) if phash: return phash return None def gen_hash(cdict): """ Main entry point for generating hash functions.""" phash = _gen_hash_one_level(cdict) if phash: return phash l2_phash = _find_l2_phash(cdict) if l2_phash: return l2_phash return None