contrib/gcc/cse.c

64    a hash table for most expressions, and a vector of "quantity
74    is to keep it in a hash table.
103    REG expressions with qty_table `mode' must be in the hash table for both
107    any mode, two REG expressions might be equivalent in the hash table
115    putting the constant in the hash table as is usual for non-regs.
128    is recorded in the hash table along with the actual RTL
134    we use a hash table called `table'.  It has a fixed number of buckets
137    hash codes.
144    The hash code of a register reference is computed using the quantity
148    hash table not just that expression but all expressions whose values
168    Because searching the entire hash table for expressions that contain
171    entered in the hash table using this register, and then the value has
187    Registers themselves are entered in the hash table as well as in
268 /* For machines that have a CC0, we do not record its value in the hash
319      valid in the hash table.  If this does not equal the current
320      reg_tick value, such expressions existing in the hash table are
347    currently a REG expression in the hash table.  Note the difference
384 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
399 /* The hash table contains buckets which are chains of `struct table_elt's,
406    Those elements with the same hash code are chained in both directions
464    things stored in the hash table, and a lot of buckets slows
470 /* Compute hash code of X in mode M.  Special-case case where X is a pseudo
531 /* Number of elements in the hash table.  */
931 /* Clear the hash table and initialize each register with its own quantity,
944   /* Clear out hash table state for this pass.  */
964 	  /* Now relink this hash entire chain into
1097 /* Remove any invalid expressions from the hash table
1106    Return 1 if we have done something that may have changed the hash code
1171      hash code and not found in the table after that call.
1208 /* Update the register quantities for inserting X into the hash table
1216    so X's hash code may be different.  */
1291      not be accessible because its hash code will have changed.  So assign
1306 /* Look in or update the hash table.  */
1309    HASH is its hash code, made using the HASH macro.
1314 remove_from_table (struct table_elt *elt, unsigned int hash)
1344   /* Remove the table element from its hash bucket.  */
1355     else if (table[hash] == elt)
1356       table[hash] = next;
1359 	/* This entry is not in the proper hash bucket.  This can happen
1361 	   for the hash bucket that it heads.  This happens only very
1363 	for (hash = 0; hash < HASH_SIZE; hash++)
1364 	  if (table[hash] == elt)
1365 	    table[hash] = next;
1392 remove_pseudo_from_table (rtx x, unsigned int hash)
1398   while ((elt = lookup_for_remove (x, hash, VOIDmode)))
1399     remove_from_table (elt, hash);
1402 /* Look up X in the hash table and return its table element,
1412 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1416   for (p = table[hash]; p; p = p->next_same_hash)
1428 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1438       for (p = table[hash]; p; p = p->next_same_hash)
1445       for (p = table[hash]; p; p = p->next_same_hash)
1486 /* Insert X in the hash table, assuming HASH is its hash code
1501    The in_memory field in the hash table element is set to 0.
1506    you must then recompute its hash code before calling here.
1514 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1533   /* Put an element for X into the right hash bucket.  */
1547   elt->next_same_hash = table[hash];
1554   if (table[hash])
1555     table[hash]->prev_same_hash = elt;
1556   table[hash] = elt;
1658 	  /* Get the integer-free subexpression in the hash table.  */
1707       unsigned int hash;
1715 	 hash code (it also isn't necessary).  */
1721 	  hash = HASH (exp, mode);
1730 	    remove_pseudo_from_table (exp, hash);
1732 	    remove_from_table (elt, hash);
1737 	      hash = HASH (exp, mode);
1739 	  new = insert (exp, class1, hash, mode);
1746 /* Flush the entire hash table.  */
1758 	   after P in the current hash chain.  */
1787 /* Remove from the hash table, or mark as invalid, all expressions whose
1815 	unsigned int hash = HASH (x, GET_MODE (x));
1819 	   entry from the hash table.
1831 	  remove_pseudo_from_table (x, hash);
1853 	      for (hash = 0; hash < HASH_SIZE; hash++)
1854 		for (p = table[hash]; p; p = next)
1866 		      remove_from_table (p, hash);
1893       /* Remove all hash table elements that refer to overlapping pieces of
1981 /* Recompute the hash codes of any valid entries in the hash table that
1991   unsigned hash;
2004   /* Scan all hash chains looking for valid entries that mention X.
2005      If we find one and it is in the wrong hash chain, move it.  */
2013 	    && i != (hash = SAFE_HASH (p->exp, p->mode)))
2023 	    p->next_same_hash = table[hash];
2025 	    if (table[hash])
2026 	      table[hash]->prev_same_hash = p;
2027 	    table[hash] = p;
2033 /* Remove from the hash table any expression that is a call-clobbered
2041   unsigned hash;
2068     for (hash = 0; hash < HASH_SIZE; hash++)
2069       for (p = table[hash]; p; p = next)
2083 		remove_from_table (p, hash);
2092    is not in the hash table),
2168   unsigned hash = 0;
2173       hash += *p++;
2175   return hash;
2179    Equivalent registers hash identically.
2188    Note that cse_insn knows that the hash code of a MEM expression
2189    is just (int) MEM plus the hash code of the address.  */
2196   unsigned hash = 0;
2205     return hash;
2257 	hash += ((unsigned int) REG << 7);
2258         hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2259 	return hash;
2263        reg changes its hash value with every value change; we don't
2269 	    hash += (((unsigned int) SUBREG << 7)
2272 	    return hash;
2278       hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2280       return hash;
2285       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2287 	hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2289 	hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2291       return hash;
2303 	    hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
2307 	return hash;
2312       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2314 	 hash += (((unsigned int) LABEL_REF << 7)
2316       return hash;
2320 	/* Don't hash on the symbol's address to avoid bootstrap differences.
2321 	   Different hash values may cause expressions to be recorded in
2331 	hash += ((unsigned int) SYMBOL_REF << 7) + h;
2332 	return hash;
2348       hash += (unsigned) MEM;
2361 	  hash += (unsigned) USE;
2369 	  hash += (unsigned) MEM;
2397 	  hash += (unsigned) code + (unsigned) GET_MODE (x)
2406 		  hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
2414 	      hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2420 	  return hash;
2429   hash += (unsigned) code + (unsigned) GET_MODE (x);
2445 	  hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
2451 	    hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
2456 	  hash += hash_rtx_string (XSTR (x, i));
2460 	  hash += (unsigned int) XINT (x, i);
2472   return hash;
2501    and Y was found in the hash table.  We check register refs
2880   unsigned hash;
2928   /* If this address is not in the hash table, we can't look for equivalences
2932   hash = HASH (addr, Pmode);
2940   elt = lookup (addr, hash, Pmode);
3004       hash = HASH (XEXP (*loc, 0), Pmode);
3008       elt = lookup (XEXP (*loc, 0), hash, Pmode);
3081    operation (EQ, NE, GT, etc.), follow it back through the hash table and
3155 	/* Look up ARG1 in the hash table and see if it has an equivalence
3669      of expressions recorded in the hash table.  We also leave some
4512      is a constant-pool reference.  Then try to look it up in the hash table
4736       /* Put OP0 in the hash table if it isn't already.  This gives it a
4745 	      /* If OP0 is contained in OP1, this changes its hash code
4765 	  /* Put OP1 in the hash table so it gets a new quantity number.  */
4839   /* The hash-table element for the SET_SRC of the SET.  */
5098      Nothing in this loop changes the hash table or the register chains.  */
5128 	 hash it with the destination's machine mode.
5187       /* Compute SRC's hash code, and also notice if it
5203 	 opportunities by not having SRC in the hash table.  */
5289 	 hash code and look it up.  */
5517          possibilities.  Prefer items not in the hash table to ones
5609 	     src_folded, src, src_eqv, src_related and hash table entry.  */
5855       /* Compute the hash code of the destination now,
5861       /* Don't enter a bit-field in the hash table
5988   /* Now enter all non-volatile source expressions in the hash table
6042 	    /* Insert source and constant equivalent into hash table, if not
6092       /* If we did not insert the source into the hash table (e.g., it was
6097   /* Record destination addresses in the hash table.  This allows us to
6106 	  unsigned hash;
6112 	      hash = HASH (x, mode);
6113 	      elt = lookup (x, hash, mode);
6121 		      hash = HASH (x, mode);
6124 		  elt = insert (x, NULL, hash, mode);
6179      This removes from the hash table
6183      we are going to hash the SET_DEST values unconditionally.  */
6197 		 since that changes the hash code.  However, that is not
6199 		 hash 'collision' of a register with its own invalid
6201 		 change their hash code with the hash code of the register,
6225   /* We may have just removed some of the src_elt's from the hash table.
6277 	    /* If we didn't put a REG_EQUAL value or a source into the hash
6302 	      /* If `insert_regs' changes something, the hash code must be
6382 		/* Put the new source in the hash table is if isn't
6512 /* Remove from the hash table all expressions that reference memory.  */
7105       /* If we have processed 1,000 insns, flush the hash table to