17aec1d6eScindi /* 27aec1d6eScindi * CDDL HEADER START 37aec1d6eScindi * 47aec1d6eScindi * The contents of this file are subject to the terms of the 5*80ab886dSwesolows * Common Development and Distribution License (the "License"). 6*80ab886dSwesolows * You may not use this file except in compliance with the License. 77aec1d6eScindi * 87aec1d6eScindi * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 97aec1d6eScindi * or http://www.opensolaris.org/os/licensing. 107aec1d6eScindi * See the License for the specific language governing permissions 117aec1d6eScindi * and limitations under the License. 127aec1d6eScindi * 137aec1d6eScindi * When distributing Covered Code, include this CDDL HEADER in each 147aec1d6eScindi * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 157aec1d6eScindi * If applicable, add the following below this CDDL HEADER, with the 167aec1d6eScindi * fields enclosed by brackets "[]" replaced with your own identifying 177aec1d6eScindi * information: Portions Copyright [yyyy] [name of copyright owner] 187aec1d6eScindi * 197aec1d6eScindi * CDDL HEADER END 207aec1d6eScindi */ 21*80ab886dSwesolows 227aec1d6eScindi /* 237aec1d6eScindi * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 247aec1d6eScindi * Use is subject to license terms. 257aec1d6eScindi * 267aec1d6eScindi * iexpr.c -- instanced expression cache module 277aec1d6eScindi * 287aec1d6eScindi * this module provides a cache of fully instantized expressions. 297aec1d6eScindi */ 307aec1d6eScindi 317aec1d6eScindi #pragma ident "%Z%%M% %I% %E% SMI" 327aec1d6eScindi 337aec1d6eScindi #include <stdio.h> 347aec1d6eScindi #include <string.h> 357aec1d6eScindi #include "alloc.h" 367aec1d6eScindi #include "out.h" 377aec1d6eScindi #include "lut.h" 387aec1d6eScindi #include "tree.h" 397aec1d6eScindi #include "ptree.h" 407aec1d6eScindi #include "itree.h" 417aec1d6eScindi #include "ipath.h" 427aec1d6eScindi #include "iexpr.h" 437aec1d6eScindi #include "stats.h" 447aec1d6eScindi #include "eval.h" 457aec1d6eScindi #include "config.h" 467aec1d6eScindi 477aec1d6eScindi #define IEXPRSZ 1024 /* hash table size */ 487aec1d6eScindi 497aec1d6eScindi static struct stats *Niexpr; 507aec1d6eScindi 517aec1d6eScindi /* the cache is a hash table of these structs */ 527aec1d6eScindi static struct iexpr { 537aec1d6eScindi struct node *np; 547aec1d6eScindi struct iexpr *next; /* next entry in hash bucket */ 557aec1d6eScindi } *Cache[IEXPRSZ]; 567aec1d6eScindi 577aec1d6eScindi /* 587aec1d6eScindi * iexpr_init -- initialize the iexpr module 597aec1d6eScindi */ 607aec1d6eScindi void 617aec1d6eScindi iexpr_init(void) 627aec1d6eScindi { 637aec1d6eScindi Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1); 647aec1d6eScindi } 657aec1d6eScindi 667aec1d6eScindi /* 677aec1d6eScindi * iexpr_hash -- produce a simple hash from an instanced expression tree 687aec1d6eScindi */ 697aec1d6eScindi static unsigned 707aec1d6eScindi iexpr_hash(struct node *np) 717aec1d6eScindi { 727aec1d6eScindi if (np == NULL) 737aec1d6eScindi return (1); 747aec1d6eScindi 757aec1d6eScindi switch (np->t) { 767aec1d6eScindi case T_GLOBID: 777aec1d6eScindi return ((int)np->u.globid.s); 787aec1d6eScindi 797aec1d6eScindi case T_ASSIGN: 807aec1d6eScindi case T_CONDIF: 817aec1d6eScindi case T_CONDELSE: 827aec1d6eScindi case T_NE: 837aec1d6eScindi case T_EQ: 847aec1d6eScindi case T_LT: 857aec1d6eScindi case T_LE: 867aec1d6eScindi case T_GT: 877aec1d6eScindi case T_GE: 887aec1d6eScindi case T_BITAND: 897aec1d6eScindi case T_BITOR: 907aec1d6eScindi case T_BITXOR: 917aec1d6eScindi case T_BITNOT: 927aec1d6eScindi case T_LSHIFT: 937aec1d6eScindi case T_RSHIFT: 947aec1d6eScindi case T_LIST: 957aec1d6eScindi case T_AND: 967aec1d6eScindi case T_OR: 977aec1d6eScindi case T_NOT: 987aec1d6eScindi case T_ADD: 997aec1d6eScindi case T_SUB: 1007aec1d6eScindi case T_MUL: 1017aec1d6eScindi case T_DIV: 1027aec1d6eScindi case T_MOD: 1037aec1d6eScindi return ((int)np->t * 1047aec1d6eScindi (iexpr_hash(np->u.expr.left) + 1057aec1d6eScindi iexpr_hash(np->u.expr.right))); 1067aec1d6eScindi 1077aec1d6eScindi case T_NAME: 1087aec1d6eScindi return ((int)np->u.name.s); 1097aec1d6eScindi 1107aec1d6eScindi case T_EVENT: 1117aec1d6eScindi return (iexpr_hash(np->u.event.ename) + 1127aec1d6eScindi iexpr_hash(np->u.event.epname)); 1137aec1d6eScindi 1147aec1d6eScindi case T_FUNC: 1157aec1d6eScindi return ((int)np->u.func.s + 1167aec1d6eScindi iexpr_hash(np->u.func.arglist)); 1177aec1d6eScindi 1187aec1d6eScindi case T_QUOTE: 1197aec1d6eScindi return ((int)np->u.quote.s); 1207aec1d6eScindi 1217aec1d6eScindi case T_NUM: 1227aec1d6eScindi return ((int)np->u.ull); 1237aec1d6eScindi 1247aec1d6eScindi default: 1257aec1d6eScindi outfl(O_DIE, np->file, np->line, 1267aec1d6eScindi "iexpr_hash: unexpected node type: %s", 1277aec1d6eScindi ptree_nodetype2str(np->t)); 1287aec1d6eScindi } 1297aec1d6eScindi /*NOTREACHED*/ 130*80ab886dSwesolows return (1); 1317aec1d6eScindi } 1327aec1d6eScindi 1337aec1d6eScindi /* 1347aec1d6eScindi * iexpr_cmp -- compare two instanced expression trees 1357aec1d6eScindi */ 1367aec1d6eScindi static int 1377aec1d6eScindi iexpr_cmp(struct node *np1, struct node *np2) 1387aec1d6eScindi { 1397aec1d6eScindi int diff; 1407aec1d6eScindi 1417aec1d6eScindi if (np1 == np2) 1427aec1d6eScindi return (0); 1437aec1d6eScindi 1447aec1d6eScindi if (np1 == NULL) 1457aec1d6eScindi return (1); 1467aec1d6eScindi 1477aec1d6eScindi if (np2 == NULL) 1487aec1d6eScindi return (-1); 1497aec1d6eScindi 1507aec1d6eScindi if (np1->t != np2->t) 1517aec1d6eScindi return (np2->t - np1->t); 1527aec1d6eScindi 1537aec1d6eScindi /* types match, need to see additional info matches */ 1547aec1d6eScindi switch (np1->t) { 1557aec1d6eScindi case T_GLOBID: 1567aec1d6eScindi return (np2->u.globid.s - np1->u.globid.s); 1577aec1d6eScindi 1587aec1d6eScindi case T_ASSIGN: 1597aec1d6eScindi case T_CONDIF: 1607aec1d6eScindi case T_CONDELSE: 1617aec1d6eScindi case T_NE: 1627aec1d6eScindi case T_EQ: 1637aec1d6eScindi case T_LT: 1647aec1d6eScindi case T_LE: 1657aec1d6eScindi case T_GT: 1667aec1d6eScindi case T_GE: 1677aec1d6eScindi case T_BITAND: 1687aec1d6eScindi case T_BITOR: 1697aec1d6eScindi case T_BITXOR: 1707aec1d6eScindi case T_BITNOT: 1717aec1d6eScindi case T_LSHIFT: 1727aec1d6eScindi case T_RSHIFT: 1737aec1d6eScindi case T_LIST: 1747aec1d6eScindi case T_AND: 1757aec1d6eScindi case T_OR: 1767aec1d6eScindi case T_NOT: 1777aec1d6eScindi case T_ADD: 1787aec1d6eScindi case T_SUB: 1797aec1d6eScindi case T_MUL: 1807aec1d6eScindi case T_DIV: 1817aec1d6eScindi case T_MOD: 1827aec1d6eScindi diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left); 1837aec1d6eScindi if (diff != 0) 1847aec1d6eScindi return (diff); 1857aec1d6eScindi return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right)); 1867aec1d6eScindi 1877aec1d6eScindi case T_NAME: 1887aec1d6eScindi if (np2->u.name.s != np1->u.name.s) 1897aec1d6eScindi return (np2->u.name.s - np1->u.name.s); 1907aec1d6eScindi diff = iexpr_cmp(np1->u.name.child, np2->u.name.child); 1917aec1d6eScindi if (diff != 0) 1927aec1d6eScindi return (diff); 1937aec1d6eScindi return (iexpr_cmp(np1->u.name.next, np2->u.name.next)); 1947aec1d6eScindi 1957aec1d6eScindi case T_EVENT: 1967aec1d6eScindi diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename); 1977aec1d6eScindi if (diff != 0) 1987aec1d6eScindi return (diff); 1997aec1d6eScindi return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname)); 2007aec1d6eScindi 2017aec1d6eScindi case T_FUNC: 2027aec1d6eScindi if (np1->u.func.s != np2->u.func.s) 2037aec1d6eScindi return (np2->u.func.s - np1->u.func.s); 2047aec1d6eScindi return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist)); 2057aec1d6eScindi 2067aec1d6eScindi case T_QUOTE: 2077aec1d6eScindi return (np2->u.quote.s - np1->u.quote.s); 2087aec1d6eScindi 2097aec1d6eScindi case T_NUM: 2107aec1d6eScindi if (np2->u.ull > np1->u.ull) 2117aec1d6eScindi return (1); 2127aec1d6eScindi else if (np1->u.ull > np2->u.ull) 2137aec1d6eScindi return (-1); 2147aec1d6eScindi else 2157aec1d6eScindi return (0); 2167aec1d6eScindi 2177aec1d6eScindi default: 2187aec1d6eScindi outfl(O_DIE, np1->file, np1->line, 2197aec1d6eScindi "iexpr_cmp: unexpected node type: %s", 2207aec1d6eScindi ptree_nodetype2str(np1->t)); 2217aec1d6eScindi } 2227aec1d6eScindi /*NOTREACHED*/ 223*80ab886dSwesolows return (0); 2247aec1d6eScindi } 2257aec1d6eScindi 2267aec1d6eScindi /* 2277aec1d6eScindi * iexpr -- find instanced expr in cache, or add it if necessary 2287aec1d6eScindi */ 2297aec1d6eScindi struct node * 2307aec1d6eScindi iexpr(struct node *np) 2317aec1d6eScindi { 2327aec1d6eScindi unsigned idx = iexpr_hash(np) % IEXPRSZ; 2337aec1d6eScindi struct iexpr *bucketp = Cache[idx]; 2347aec1d6eScindi struct iexpr *cp; 2357aec1d6eScindi 2367aec1d6eScindi /* search cache */ 2377aec1d6eScindi for (cp = bucketp; cp != NULL; cp = cp->next) 2387aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 2397aec1d6eScindi /* found it */ 2407aec1d6eScindi tree_free(np); 2417aec1d6eScindi return (cp->np); 2427aec1d6eScindi } 2437aec1d6eScindi 2447aec1d6eScindi /* allocate new cache entry */ 2457aec1d6eScindi cp = MALLOC(sizeof (*cp)); 2467aec1d6eScindi cp->np = np; 2477aec1d6eScindi cp->next = bucketp; 2487aec1d6eScindi Cache[idx] = cp; 2497aec1d6eScindi 2507aec1d6eScindi stats_counter_bump(Niexpr); 2517aec1d6eScindi 2527aec1d6eScindi return (np); 2537aec1d6eScindi } 2547aec1d6eScindi 2557aec1d6eScindi /* 2567aec1d6eScindi * iexpr_cached -- return true if np is in the iexpr cache 2577aec1d6eScindi */ 2587aec1d6eScindi int 2597aec1d6eScindi iexpr_cached(struct node *np) 2607aec1d6eScindi { 2617aec1d6eScindi struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ]; 2627aec1d6eScindi 2637aec1d6eScindi /* search cache */ 2647aec1d6eScindi for (; cp != NULL; cp = cp->next) 2657aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 2667aec1d6eScindi /* found it */ 2677aec1d6eScindi return (1); 2687aec1d6eScindi } 2697aec1d6eScindi 2707aec1d6eScindi return (0); 2717aec1d6eScindi } 2727aec1d6eScindi 2737aec1d6eScindi /* 2747aec1d6eScindi * iexpr_fini -- free the iexpr cache 2757aec1d6eScindi */ 2767aec1d6eScindi void 2777aec1d6eScindi iexpr_fini(void) 2787aec1d6eScindi { 2797aec1d6eScindi int i; 2807aec1d6eScindi 2817aec1d6eScindi for (i = 0; i < IEXPRSZ; i++) { 2827aec1d6eScindi struct iexpr *cp; 2837aec1d6eScindi struct iexpr *ncp; 2847aec1d6eScindi 2857aec1d6eScindi for (cp = Cache[i]; cp != NULL; cp = ncp) { 2867aec1d6eScindi tree_free(cp->np); 2877aec1d6eScindi ncp = cp->next; 2887aec1d6eScindi FREE(cp); 2897aec1d6eScindi } 2907aec1d6eScindi Cache[i] = NULL; 2917aec1d6eScindi } 2927aec1d6eScindi } 293