1*7aec1d6eScindi /* 2*7aec1d6eScindi * CDDL HEADER START 3*7aec1d6eScindi * 4*7aec1d6eScindi * The contents of this file are subject to the terms of the 5*7aec1d6eScindi * Common Development and Distribution License, Version 1.0 only 6*7aec1d6eScindi * (the "License"). You may not use this file except in compliance 7*7aec1d6eScindi * with the License. 8*7aec1d6eScindi * 9*7aec1d6eScindi * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*7aec1d6eScindi * or http://www.opensolaris.org/os/licensing. 11*7aec1d6eScindi * See the License for the specific language governing permissions 12*7aec1d6eScindi * and limitations under the License. 13*7aec1d6eScindi * 14*7aec1d6eScindi * When distributing Covered Code, include this CDDL HEADER in each 15*7aec1d6eScindi * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*7aec1d6eScindi * If applicable, add the following below this CDDL HEADER, with the 17*7aec1d6eScindi * fields enclosed by brackets "[]" replaced with your own identifying 18*7aec1d6eScindi * information: Portions Copyright [yyyy] [name of copyright owner] 19*7aec1d6eScindi * 20*7aec1d6eScindi * CDDL HEADER END 21*7aec1d6eScindi */ 22*7aec1d6eScindi /* 23*7aec1d6eScindi * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 24*7aec1d6eScindi * Use is subject to license terms. 25*7aec1d6eScindi * 26*7aec1d6eScindi * iexpr.c -- instanced expression cache module 27*7aec1d6eScindi * 28*7aec1d6eScindi * this module provides a cache of fully instantized expressions. 29*7aec1d6eScindi */ 30*7aec1d6eScindi 31*7aec1d6eScindi #pragma ident "%Z%%M% %I% %E% SMI" 32*7aec1d6eScindi 33*7aec1d6eScindi #include <stdio.h> 34*7aec1d6eScindi #include <string.h> 35*7aec1d6eScindi #include "alloc.h" 36*7aec1d6eScindi #include "out.h" 37*7aec1d6eScindi #include "lut.h" 38*7aec1d6eScindi #include "tree.h" 39*7aec1d6eScindi #include "ptree.h" 40*7aec1d6eScindi #include "itree.h" 41*7aec1d6eScindi #include "ipath.h" 42*7aec1d6eScindi #include "iexpr.h" 43*7aec1d6eScindi #include "stats.h" 44*7aec1d6eScindi #include "eval.h" 45*7aec1d6eScindi #include "config.h" 46*7aec1d6eScindi 47*7aec1d6eScindi #define IEXPRSZ 1024 /* hash table size */ 48*7aec1d6eScindi 49*7aec1d6eScindi static struct stats *Niexpr; 50*7aec1d6eScindi 51*7aec1d6eScindi /* the cache is a hash table of these structs */ 52*7aec1d6eScindi static struct iexpr { 53*7aec1d6eScindi struct node *np; 54*7aec1d6eScindi struct iexpr *next; /* next entry in hash bucket */ 55*7aec1d6eScindi } *Cache[IEXPRSZ]; 56*7aec1d6eScindi 57*7aec1d6eScindi /* 58*7aec1d6eScindi * iexpr_init -- initialize the iexpr module 59*7aec1d6eScindi */ 60*7aec1d6eScindi void 61*7aec1d6eScindi iexpr_init(void) 62*7aec1d6eScindi { 63*7aec1d6eScindi Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1); 64*7aec1d6eScindi } 65*7aec1d6eScindi 66*7aec1d6eScindi /* 67*7aec1d6eScindi * iexpr_hash -- produce a simple hash from an instanced expression tree 68*7aec1d6eScindi */ 69*7aec1d6eScindi static unsigned 70*7aec1d6eScindi iexpr_hash(struct node *np) 71*7aec1d6eScindi { 72*7aec1d6eScindi if (np == NULL) 73*7aec1d6eScindi return (1); 74*7aec1d6eScindi 75*7aec1d6eScindi switch (np->t) { 76*7aec1d6eScindi case T_GLOBID: 77*7aec1d6eScindi return ((int)np->u.globid.s); 78*7aec1d6eScindi 79*7aec1d6eScindi case T_ASSIGN: 80*7aec1d6eScindi case T_CONDIF: 81*7aec1d6eScindi case T_CONDELSE: 82*7aec1d6eScindi case T_NE: 83*7aec1d6eScindi case T_EQ: 84*7aec1d6eScindi case T_LT: 85*7aec1d6eScindi case T_LE: 86*7aec1d6eScindi case T_GT: 87*7aec1d6eScindi case T_GE: 88*7aec1d6eScindi case T_BITAND: 89*7aec1d6eScindi case T_BITOR: 90*7aec1d6eScindi case T_BITXOR: 91*7aec1d6eScindi case T_BITNOT: 92*7aec1d6eScindi case T_LSHIFT: 93*7aec1d6eScindi case T_RSHIFT: 94*7aec1d6eScindi case T_LIST: 95*7aec1d6eScindi case T_AND: 96*7aec1d6eScindi case T_OR: 97*7aec1d6eScindi case T_NOT: 98*7aec1d6eScindi case T_ADD: 99*7aec1d6eScindi case T_SUB: 100*7aec1d6eScindi case T_MUL: 101*7aec1d6eScindi case T_DIV: 102*7aec1d6eScindi case T_MOD: 103*7aec1d6eScindi return ((int)np->t * 104*7aec1d6eScindi (iexpr_hash(np->u.expr.left) + 105*7aec1d6eScindi iexpr_hash(np->u.expr.right))); 106*7aec1d6eScindi 107*7aec1d6eScindi case T_NAME: 108*7aec1d6eScindi return ((int)np->u.name.s); 109*7aec1d6eScindi 110*7aec1d6eScindi case T_EVENT: 111*7aec1d6eScindi return (iexpr_hash(np->u.event.ename) + 112*7aec1d6eScindi iexpr_hash(np->u.event.epname)); 113*7aec1d6eScindi 114*7aec1d6eScindi case T_FUNC: 115*7aec1d6eScindi return ((int)np->u.func.s + 116*7aec1d6eScindi iexpr_hash(np->u.func.arglist)); 117*7aec1d6eScindi 118*7aec1d6eScindi case T_QUOTE: 119*7aec1d6eScindi return ((int)np->u.quote.s); 120*7aec1d6eScindi 121*7aec1d6eScindi case T_NUM: 122*7aec1d6eScindi return ((int)np->u.ull); 123*7aec1d6eScindi 124*7aec1d6eScindi default: 125*7aec1d6eScindi outfl(O_DIE, np->file, np->line, 126*7aec1d6eScindi "iexpr_hash: unexpected node type: %s", 127*7aec1d6eScindi ptree_nodetype2str(np->t)); 128*7aec1d6eScindi } 129*7aec1d6eScindi /*NOTREACHED*/ 130*7aec1d6eScindi } 131*7aec1d6eScindi 132*7aec1d6eScindi /* 133*7aec1d6eScindi * iexpr_cmp -- compare two instanced expression trees 134*7aec1d6eScindi */ 135*7aec1d6eScindi static int 136*7aec1d6eScindi iexpr_cmp(struct node *np1, struct node *np2) 137*7aec1d6eScindi { 138*7aec1d6eScindi int diff; 139*7aec1d6eScindi 140*7aec1d6eScindi if (np1 == np2) 141*7aec1d6eScindi return (0); 142*7aec1d6eScindi 143*7aec1d6eScindi if (np1 == NULL) 144*7aec1d6eScindi return (1); 145*7aec1d6eScindi 146*7aec1d6eScindi if (np2 == NULL) 147*7aec1d6eScindi return (-1); 148*7aec1d6eScindi 149*7aec1d6eScindi if (np1->t != np2->t) 150*7aec1d6eScindi return (np2->t - np1->t); 151*7aec1d6eScindi 152*7aec1d6eScindi /* types match, need to see additional info matches */ 153*7aec1d6eScindi switch (np1->t) { 154*7aec1d6eScindi case T_GLOBID: 155*7aec1d6eScindi return (np2->u.globid.s - np1->u.globid.s); 156*7aec1d6eScindi 157*7aec1d6eScindi case T_ASSIGN: 158*7aec1d6eScindi case T_CONDIF: 159*7aec1d6eScindi case T_CONDELSE: 160*7aec1d6eScindi case T_NE: 161*7aec1d6eScindi case T_EQ: 162*7aec1d6eScindi case T_LT: 163*7aec1d6eScindi case T_LE: 164*7aec1d6eScindi case T_GT: 165*7aec1d6eScindi case T_GE: 166*7aec1d6eScindi case T_BITAND: 167*7aec1d6eScindi case T_BITOR: 168*7aec1d6eScindi case T_BITXOR: 169*7aec1d6eScindi case T_BITNOT: 170*7aec1d6eScindi case T_LSHIFT: 171*7aec1d6eScindi case T_RSHIFT: 172*7aec1d6eScindi case T_LIST: 173*7aec1d6eScindi case T_AND: 174*7aec1d6eScindi case T_OR: 175*7aec1d6eScindi case T_NOT: 176*7aec1d6eScindi case T_ADD: 177*7aec1d6eScindi case T_SUB: 178*7aec1d6eScindi case T_MUL: 179*7aec1d6eScindi case T_DIV: 180*7aec1d6eScindi case T_MOD: 181*7aec1d6eScindi diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left); 182*7aec1d6eScindi if (diff != 0) 183*7aec1d6eScindi return (diff); 184*7aec1d6eScindi return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right)); 185*7aec1d6eScindi 186*7aec1d6eScindi case T_NAME: 187*7aec1d6eScindi if (np2->u.name.s != np1->u.name.s) 188*7aec1d6eScindi return (np2->u.name.s - np1->u.name.s); 189*7aec1d6eScindi diff = iexpr_cmp(np1->u.name.child, np2->u.name.child); 190*7aec1d6eScindi if (diff != 0) 191*7aec1d6eScindi return (diff); 192*7aec1d6eScindi return (iexpr_cmp(np1->u.name.next, np2->u.name.next)); 193*7aec1d6eScindi 194*7aec1d6eScindi case T_EVENT: 195*7aec1d6eScindi diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename); 196*7aec1d6eScindi if (diff != 0) 197*7aec1d6eScindi return (diff); 198*7aec1d6eScindi return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname)); 199*7aec1d6eScindi 200*7aec1d6eScindi case T_FUNC: 201*7aec1d6eScindi if (np1->u.func.s != np2->u.func.s) 202*7aec1d6eScindi return (np2->u.func.s - np1->u.func.s); 203*7aec1d6eScindi return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist)); 204*7aec1d6eScindi 205*7aec1d6eScindi case T_QUOTE: 206*7aec1d6eScindi return (np2->u.quote.s - np1->u.quote.s); 207*7aec1d6eScindi 208*7aec1d6eScindi case T_NUM: 209*7aec1d6eScindi if (np2->u.ull > np1->u.ull) 210*7aec1d6eScindi return (1); 211*7aec1d6eScindi else if (np1->u.ull > np2->u.ull) 212*7aec1d6eScindi return (-1); 213*7aec1d6eScindi else 214*7aec1d6eScindi return (0); 215*7aec1d6eScindi 216*7aec1d6eScindi default: 217*7aec1d6eScindi outfl(O_DIE, np1->file, np1->line, 218*7aec1d6eScindi "iexpr_cmp: unexpected node type: %s", 219*7aec1d6eScindi ptree_nodetype2str(np1->t)); 220*7aec1d6eScindi } 221*7aec1d6eScindi /*NOTREACHED*/ 222*7aec1d6eScindi } 223*7aec1d6eScindi 224*7aec1d6eScindi /* 225*7aec1d6eScindi * iexpr -- find instanced expr in cache, or add it if necessary 226*7aec1d6eScindi */ 227*7aec1d6eScindi struct node * 228*7aec1d6eScindi iexpr(struct node *np) 229*7aec1d6eScindi { 230*7aec1d6eScindi unsigned idx = iexpr_hash(np) % IEXPRSZ; 231*7aec1d6eScindi struct iexpr *bucketp = Cache[idx]; 232*7aec1d6eScindi struct iexpr *cp; 233*7aec1d6eScindi 234*7aec1d6eScindi /* search cache */ 235*7aec1d6eScindi for (cp = bucketp; cp != NULL; cp = cp->next) 236*7aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 237*7aec1d6eScindi /* found it */ 238*7aec1d6eScindi tree_free(np); 239*7aec1d6eScindi return (cp->np); 240*7aec1d6eScindi } 241*7aec1d6eScindi 242*7aec1d6eScindi /* allocate new cache entry */ 243*7aec1d6eScindi cp = MALLOC(sizeof (*cp)); 244*7aec1d6eScindi cp->np = np; 245*7aec1d6eScindi cp->next = bucketp; 246*7aec1d6eScindi Cache[idx] = cp; 247*7aec1d6eScindi 248*7aec1d6eScindi stats_counter_bump(Niexpr); 249*7aec1d6eScindi 250*7aec1d6eScindi return (np); 251*7aec1d6eScindi } 252*7aec1d6eScindi 253*7aec1d6eScindi /* 254*7aec1d6eScindi * iexpr_cached -- return true if np is in the iexpr cache 255*7aec1d6eScindi */ 256*7aec1d6eScindi int 257*7aec1d6eScindi iexpr_cached(struct node *np) 258*7aec1d6eScindi { 259*7aec1d6eScindi struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ]; 260*7aec1d6eScindi 261*7aec1d6eScindi /* search cache */ 262*7aec1d6eScindi for (; cp != NULL; cp = cp->next) 263*7aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 264*7aec1d6eScindi /* found it */ 265*7aec1d6eScindi return (1); 266*7aec1d6eScindi } 267*7aec1d6eScindi 268*7aec1d6eScindi return (0); 269*7aec1d6eScindi } 270*7aec1d6eScindi 271*7aec1d6eScindi /* 272*7aec1d6eScindi * iexpr_fini -- free the iexpr cache 273*7aec1d6eScindi */ 274*7aec1d6eScindi void 275*7aec1d6eScindi iexpr_fini(void) 276*7aec1d6eScindi { 277*7aec1d6eScindi int i; 278*7aec1d6eScindi 279*7aec1d6eScindi for (i = 0; i < IEXPRSZ; i++) { 280*7aec1d6eScindi struct iexpr *cp; 281*7aec1d6eScindi struct iexpr *ncp; 282*7aec1d6eScindi 283*7aec1d6eScindi for (cp = Cache[i]; cp != NULL; cp = ncp) { 284*7aec1d6eScindi tree_free(cp->np); 285*7aec1d6eScindi ncp = cp->next; 286*7aec1d6eScindi FREE(cp); 287*7aec1d6eScindi } 288*7aec1d6eScindi Cache[i] = NULL; 289*7aec1d6eScindi } 290*7aec1d6eScindi } 291