$(BASIC_BLOCK_H) $(HASHTAB_H) $(TREE_GIMPLE_H) tree-inline.h

   $(BASIC_BLOCK_H) $(TREE_GIMPLE_H) tree-inline.h vec.h \

   alloc-pool.h

/* { dg-final { scan-tree-dump-times "a \\\+ b" 1 "optimized"} } */

/* { dg-final { scan-tree-dump-times "b \\\+ a" 1 "optimized"} } */

/* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-reassoc-details" } */

/* { dg-options "-O2 -fdump-tree-optimized" } */

extern int a0, a1, a2, a3, a4; 

int f (int a0,int a1,int a2,int a3,int a4)

int f () 

int b0, b1, b2, b3, b4; 

int b0, b1, b2, b3, b4,e;

  return b4 - b3 + b2 - b1 - a4 - a2;

  e = b4 - b3 + b2 - b1 - a4 - a2;

} 

  return e;

/* { dg-final { scan-tree-dump-times "Reassociating by rank" 3 "reassoc" } } */

}

/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* } } } */

/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */

/* { dg-do compile } */ 

int main(int a, int b, int c, int d)

/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */

float a, b, c, d;

extern int printf (const char *, ...);

int main(void)

  float e;

  int e = (a & ~b) & (~c & d);

  float f;

  int f = (~c & a) & (b & ~d);

  /* We should be able to transform these into the same expression, and only have two additions.  */

 return (e & f);

  e = a + b;

  e = e + c;

  f = c + a;

  f = f + b;

  printf ("%f %f\n", e, f);

/* { dg-options "-O2 -fdump-tree-optimized" } */

/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */

/* { dg-final { scan-tree-dump-times "\\\+" 4 "optimized"} } */

/* { dg-final { scan-tree-dump-times "\\\+" 2 "optimized"} } */

   main path, causing one reload. */

   main path, and one computation of v * i along the main path, causing

/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */

   two eliminations. */

/* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "pre"} } */

	cond = COND_EXPR_COND (stmt);

	{

	  canonicalize_comparison (stmt);

	  cond = COND_EXPR_COND (stmt);

	}

/*  This is a simple global reassociation pass that uses a combination

/*  This is a simple global reassociation pass.  It is, in part, based

    of heuristics and a hashtable to try to expose more operations to

    on the LLVM pass of the same name (They do some things more/less

    CSE.  

    than we do, in different orders, etc).

    The basic idea behind the heuristic is to rank expressions by

    depth of the computation tree and loop depth, and try to produce

    expressions consisting of small rank operations, as they are more

    likely to reoccur.  In addition, we use a hashtable to try to see

    if we can transpose an operation into something we have seen

    before.

    Note that the way the hashtable is structured will sometimes find

    matches that will not expose additional redundancies, since it is

    not unwound as we traverse back up one branch of the dominator

    tree and down another.  However, the cost of improving this is

    probably not worth the additional benefits it will bring.  */

/* Statistics */

    It consists of five steps:

static struct

{

  int reassociated_by_rank;

  int reassociated_by_match;

} reassociate_stats;

/* Seen binary operator hashtable.  */

    3. Optimization of the operand lists, eliminating things like a +

static htab_t seen_binops;

    -a, a & a, etc.

/* Binary operator struct. */

    4. Rewrite the expression trees we linearized and optimized so

    they are in proper rank order.

typedef struct seen_binop_d

    5. Repropagate negates, as nothing else will clean it up ATM.

{

  tree op1;

  tree op2;

} *seen_binop_t;

/* Return a SEEN_BINOP_T if we have seen an associative binary

    A bit of theory on #4, since nobody seems to write anything down

   operator with OP1 and OP2 in it.  */

    about why it makes sense to do it the way they do it:

static seen_binop_t

    We could do this much nicer theoretically, but don't (for reasons

find_seen_binop (tree op1, tree op2)

    explained after how to do it theoretically nice :P).

{

  void **slot;

  struct seen_binop_d sbd;

  sbd.op1 = op1;

  sbd.op2 = op2;

  slot = htab_find_slot (seen_binops, &sbd, NO_INSERT);

  if (!slot)

    return NULL;

  return ((seen_binop_t) *slot);

}

/* Insert a binary operator consisting of OP1 and OP2 into the

    In order to promote the most redundancy elimination, you want

   SEEN_BINOP table.  */

    binary expressions whose operands are the same rank (or

    preferrably, the same value) exposed to the redundancy eliminator,

    for possible elimination.

static void

    So the way to do this if we really cared, is to build the new op

insert_seen_binop (tree op1, tree op2)

    tree from the leaves to the roots, merging as you go, and putting the

{

    new op on the end of the worklist, until you are left with one

  void **slot;

    thing on the worklist.

  seen_binop_t new_pair = xmalloc (sizeof (*new_pair));

  new_pair->op1 = op1;

  new_pair->op2 = op2;

  slot = htab_find_slot (seen_binops, new_pair, INSERT);

  if (*slot != NULL)

    free (*slot);

  *slot = new_pair;

}

/* Return the hash value for a seen binop structure pointed to by P.

  IE if you have to rewrite the following set of operands (listed with

   Because all the binops we consider are associative, we just add the

  rank in parentheses), with opcode PLUS_EXPR:

   hash value for op1 and op2.  */

static hashval_t

  a (1),  b (1),  c (1),  d (2), e (2)

seen_binop_hash (const void *p)

{

  const seen_binop_t sb = (seen_binop_t) p;

  return iterative_hash_expr (sb->op1, 0) + iterative_hash_expr (sb->op2, 0);

}

static int

We start with our merge worklist empty, and the ops list with all of

seen_binop_eq (const void *p1, const void *p2)

those on it.

{

  const seen_binop_t sb1 = (seen_binop_t) p1;

You want to first merge all leaves of the same rank, as much as

  const seen_binop_t sb2 = (seen_binop_t) p2;

possible.

  return (sb1->op1 == sb2->op1 && sb1->op2 == sb2->op2)

    || (sb1->op2 == sb2->op1 && sb1->op1 == sb2->op2);

So first build a binary op of

}

mergetmp = a + b, and put "mergetmp" on the merge worklist.

Because there is no three operand form of PLUS_EXPR, c is not going to

be exposed to redundancy elimination as a rank 1 operand.

So you might as well throw it on the merge worklist (you could also

consider it to now be a rank two operand, and merge it with d and e,

but in this case, you then have evicted e from a binary op. So at

least in this situation, you can't win.)

Then build a binary op of d + e

mergetmp2 = d + e

and put mergetmp2 on the merge worklist.

so merge worklist = {mergetmp, c, mergetmp2}

Continue building binary ops of these operations until you have only

one operation left on the worklist.

So we have

build binary op

mergetmp3 = mergetmp + c

/* Value rank structure.  */

worklist = {mergetmp2, mergetmp3}

typedef struct valrank_d

mergetmp4 = mergetmp2 + mergetmp3

worklist = {mergetmp4}

because we have one operation left, we can now just set the original

statement equal to the result of that operation.

This will at least expose a + b  and d + e to redundancy elimination

as binary operations.

For extra points, you can reuse the old statements to build the

mergetmps, since you shouldn't run out.

So why don't we do this?

Because it's expensive, and rarely will help.  Most trees we are

reassociating have 3 or less ops.  If they have 2 ops, they already

will be written into a nice single binary op.  If you have 3 ops, a

single simple check suffices to tell you whether the first two are of the

same rank.  If so, you know to order it

mergetmp = op1 + op2

newstmt = mergetmp + op3

instead of

mergetmp = op2 + op3

newstmt = mergetmp + op1

If all three are of the same rank, you can't expose them all in a

single binary operator anyway, so the above is *still* the best you

can do.

Thus, this is what we do.  When we have three ops left, we check to see

what order to put them in, and call it a day.  As a nod to vector sum

reduction, we check if any of ops are a really a phi node that is a

destructive update for the associating op, and keep the destructive

update together for vector sum reduction recognition.  */

/* Statistics */

static struct

{

  int linearized;

  int constants_eliminated;

  int ops_eliminated;

  int rewritten;

} reassociate_stats;

/* Operator, rank pair.  */

typedef struct operand_entry

  tree e;   

  unsigned int rank;

  unsigned int rank;  

  tree op;

} *valrank_t;

} *operand_entry_t;

static alloc_pool operand_entry_pool;

/* Value rank hashtable.  */

/* Operand->rank hashtable.  */

static htab_t value_rank;

static htab_t operand_rank;

/* Look up the value rank structure for expression E.  */

/* Look up the operand rank structure for expression E.  */

static valrank_t

static operand_entry_t

find_value_rank (tree e)

find_operand_rank (tree e)

  struct valrank_d vrd;

  struct operand_entry vrd;

  vrd.e = e;

  slot = htab_find_slot (value_rank, &vrd, NO_INSERT);

  vrd.op = e;

  slot = htab_find_slot (operand_rank, &vrd, NO_INSERT);

  return ((valrank_t) *slot);

  return ((operand_entry_t) *slot);

/* Insert {E,RANK} into the value rank hashtable.  */

/* Insert {E,RANK} into the operand rank hashtable.  */

insert_value_rank (tree e, unsigned int rank)

insert_operand_rank (tree e, unsigned int rank)

  valrank_t new_pair = xmalloc (sizeof (*new_pair));

  operand_entry_t new_pair = pool_alloc (operand_entry_pool);

  new_pair->e = e;

  new_pair->op = e;

  slot = htab_find_slot (value_rank, new_pair, INSERT);

  slot = htab_find_slot (operand_rank, new_pair, INSERT);

/* Return the hash value for a operand rank structure  */

/* Return the hash value for a value rank structure  */

valrank_hash (const void *p)

operand_entry_hash (const void *p)

  const valrank_t vr = (valrank_t) p;

  const operand_entry_t vr = (operand_entry_t) p;

  return iterative_hash_expr (vr->e, 0);

  return iterative_hash_expr (vr->op, 0);

/* Return true if two value rank structures are equal.  */

/* Return true if two operand rank structures are equal.  */

valrank_eq (const void *p1, const void *p2)

operand_entry_eq (const void *p1, const void *p2)

{

  const valrank_t vr1 = (valrank_t) p1;

  const valrank_t vr2 = (valrank_t) p2;

  return vr1->e == vr2->e;

}

/* Initialize the reassociation pass.  */

static void

init_reassoc (void)

  int i;

  const operand_entry_t vr1 = (operand_entry_t) p1;

  unsigned int rank = 2;

  const operand_entry_t vr2 = (operand_entry_t) p2;

  return vr1->op == vr2->op;

  tree param;

  int *bbs = xmalloc ((last_basic_block + 1) * sizeof (int));

  memset (&reassociate_stats, 0, sizeof (reassociate_stats));

  /* Reverse RPO (Reverse Post Order) will give us something where

     deeper loops come later.  */

  flow_reverse_top_sort_order_compute (bbs);

  bb_rank = xcalloc (last_basic_block + 1, sizeof (unsigned int));

  value_rank = htab_create (511, valrank_hash,

			    valrank_eq, free);

  seen_binops = htab_create (511, seen_binop_hash,

			     seen_binop_eq, free);

  /* Give each argument a distinct rank.   */

  for (param = DECL_ARGUMENTS (current_function_decl);

       param;

       param = TREE_CHAIN (param))

    {

      if (default_def (param) != NULL)

	{

	  tree def = default_def (param);

	  insert_value_rank (def, ++rank);

	}

    }

  /* Give the chain decl a distinct rank. */

  if (cfun->static_chain_decl != NULL)

    {

      tree def = default_def (cfun->static_chain_decl);

      if (def != NULL)

        insert_value_rank (def, ++rank);

    }

  /* Set up rank for each BB  */

  for (i = 0; i < n_basic_blocks; i++)

    bb_rank[bbs[i]] = ++rank  << 16;

  free (bbs);

  calculate_dominance_info (CDI_DOMINATORS);

  valrank_t vr;

  operand_entry_t vr;

  /* Constants have rank 0.  */  

  /* Constants have rank 0.  */

      tree rhs;      

      tree rhs;

	return find_value_rank (e)->rank;

	return find_operand_rank (e)->rank;

      vr = find_value_rank (e);

      vr = find_operand_rank (e);

      else 

      else

	  for (i = 0; 

	  for (i = 0;

	       i < TREE_CODE_LENGTH (TREE_CODE (rhs)) 

	       i < TREE_CODE_LENGTH (TREE_CODE (rhs))

		 && rank != maxrank; i++)

		 && rank != maxrank;

	       i++)

      insert_value_rank (e, (rank + 1));

      insert_operand_rank (e, (rank + 1));

/* Decide whether we should transpose RHS and some operand of

/* Return true if STMT is reassociable operation containing a binary

   LHSDEFOP.

   operation with tree code CODE.  */

   If yes, then return true and set TAKEOP to the operand number of LHSDEFOP to

   switch RHS for.

   Otherwise, return false.  */

should_transpose (tree rhs ATTRIBUTE_UNUSED, 

is_reassociable_op (tree stmt, enum tree_code code)

		  unsigned int rhsrank,

{

		  tree lhsdefop, unsigned int *takeop)

  if (!IS_EMPTY_STMT (stmt)

{

      && TREE_CODE (stmt) == MODIFY_EXPR

  /* Attempt to expose the low ranked

      && TREE_CODE (TREE_OPERAND (stmt, 1)) == code

     arguments to CSE if we have something like:

      && has_single_use (TREE_OPERAND (stmt, 0)))

     a = <rank 2> + c (rank 1)

     b = a (rank 3) + d (rank 1)

     We want to transform this into:

     a = c + d

     b = <rank 2> + <rank 3>

     The op finding part wouldn't be necessary if

			 we could swap the operands above and not have

			 update_stmt change them back on us.

  */

  unsigned int lowrankop;

  unsigned int lowrank;

  unsigned int highrank;

  unsigned int highrankop;

  unsigned int temp;

  lowrankop = 0;

  *takeop = 1;

  lowrank = get_rank (TREE_OPERAND (lhsdefop, 0));

  temp = get_rank (TREE_OPERAND (lhsdefop, 1));

  highrank = temp;

  highrankop = 1;

  if (temp < lowrank)

    {

      lowrankop = 1;

      highrankop = 0;

      *takeop = 0;

      highrank = lowrank;

      lowrank = temp;

    }

  /* If highrank == lowrank, then we had something

     like:

     a = <rank 1> + <rank 1> 

     already, so there is no guarantee that

     swapping our argument in is going to be

     better.

     If we run reassoc twice, we could probably

     have a flag that switches this behavior on,

     so that we try once without it, and once with

     it, so that redundancy elimination sees it

     both ways.

  */		      

  if (lowrank == rhsrank && highrank != lowrank)

/* Attempt to reassociate the associative binary operator BEXPR, which

   is in the statement pointed to by CURRBSI.  Return true if we

/* Given NAME, if NAME is defined by a unary operation OPCODE, return the

   changed the statement.  */

   operand of the negate operation.  Otherwise, return NULL.  */

static tree

get_unary_op (tree name, enum tree_code opcode)

{

  tree stmt = SSA_NAME_DEF_STMT (name);

  tree rhs;

  if (TREE_CODE (stmt) != MODIFY_EXPR)

    return NULL_TREE;

  rhs = TREE_OPERAND (stmt, 1);

  if (TREE_CODE (rhs) == opcode)

    return TREE_OPERAND (rhs, 0);

  return NULL_TREE;

}

/* If CURR and LAST are a pair of ops that OPCODE allows us to

   eliminate through equivalences, do so, remove them from OPS, and

   return true.  Otherwise, return false.  */

reassociate_expr (tree bexpr, block_stmt_iterator *currbsi)

eliminate_duplicate_pair (enum tree_code opcode,

			  VEC (operand_entry_t, heap) **ops,

			  bool *all_done,

			  unsigned int i,

			  operand_entry_t curr,

			  operand_entry_t last)

  tree lhs = TREE_OPERAND (bexpr, 0);

  tree rhs = TREE_OPERAND (bexpr, 1);

  /* If we have two of the same op, and the opcode is & or |, we can

  tree lhsdef;

     eliminate one of them.

  tree lhsi;

     If we have two of the same op, and the opcode is ^, we can

  bool changed = false;

     eliminate both of them.  */

  unsigned int lhsrank = get_rank (lhs);

  unsigned int rhsrank = get_rank (rhs);

  if (last && last->op == curr->op)

  /* If unsafe math optimizations we can do reassociation for non-integral

     types.  */

  if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))

       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))

      && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))

	  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))

	  || !flag_unsafe_math_optimizations))

    return false;

  /* We want the greater ranked operand to be our "LHS" for simplicity

     sake.  There is no point in actually modifying the expression, as

     update_stmt will simply resort the operands anyway. */

  if (lhsrank < rhsrank)

      tree temp;

      switch (opcode)

      unsigned int temp1;

	{

      temp = lhs;

	case BIT_IOR_EXPR:

      lhs = rhs;

	case BIT_AND_EXPR:

      rhs = temp;

	  if (dump_file && (dump_flags & TDF_DETAILS))

      temp1 = lhsrank;

	    {

      lhsrank = rhsrank;

	      fprintf (dump_file, "Equivalence: ");

      rhsrank = temp1;

	      print_generic_expr (dump_file, curr->op, 0);

    }

	      fprintf (dump_file, " [&|] ");

	      print_generic_expr (dump_file, last->op, 0);

  /* If the high ranked operand is an SSA_NAME, and the binary

	      fprintf (dump_file, " -> ");

     operator is not something we've already seen somewhere else

	      print_generic_stmt (dump_file, last->op, 0);

     (i.e., it may be redundant), attempt to reassociate it.

	    }

     We can't reassociate expressions unless the expression we are

	  VEC_ordered_remove (operand_entry_t, *ops, i);

     going to reassociate with is only used in our current expression,

	  reassociate_stats.ops_eliminated ++;

     or else we may screw up other computations, like so:

	  return true;

     a = b + c

     e = a + d

	case BIT_XOR_EXPR:

	  if (dump_file && (dump_flags & TDF_DETAILS))

     g = a + f

	    {

	      fprintf (dump_file, "Equivalence: ");

     We cannot reassociate and rewrite the "a = ..." , 

	      print_generic_expr (dump_file, curr->op, 0);

     because that would change the value of the computation of 

	      fprintf (dump_file, " ^ ");

     "g = a + f".  */

	      print_generic_expr (dump_file, last->op, 0);

  if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))

	      fprintf (dump_file, " -> nothing\n");

    {

      lhsdef = SSA_NAME_DEF_STMT (lhs);

      if (TREE_CODE (lhsdef) == MODIFY_EXPR)

	{

	  lhsi = TREE_OPERAND (lhsdef, 1);

	  if (TREE_CODE (lhsi) == TREE_CODE (bexpr))

	    {

	      use_operand_p use;

	      tree usestmt;

	      if (single_imm_use (lhs, &use, &usestmt))

		{

		  unsigned int takeop = 0;

		  unsigned int otherop = 1;

		  bool foundmatch = false;

		  bool foundrank = false;

		  /* If we can easily transpose this into an operation

		     we've already seen, let's do that.

		     otherwise, let's try to expose low ranked ops to

		     CSE.  */

		  if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))

		    {

		      takeop = 0;

		      otherop = 1;

		      foundmatch = true;

		    }

		  else if (find_seen_binop (TREE_OPERAND (lhsi, 0),

					    rhs))

		    {

		      takeop = 1;

		      otherop = 0;

		      foundmatch = true;

		    }

		  else if (should_transpose (rhs, rhsrank, lhsi,

					     &takeop))

		    {

		      foundrank = true;

		    }		  

		  if (foundmatch || foundrank)

		    {

		      block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);

		      if (dump_file && (dump_flags & TDF_DETAILS))

			{

			  fprintf (dump_file, "Reassociating by %s\n",

				   foundmatch ? "match" : "rank");

			  fprintf (dump_file, "Before LHS:");

			  print_generic_stmt (dump_file, lhsi, 0);

			  fprintf (dump_file, "Before curr expr:");

			  print_generic_stmt (dump_file, bexpr, 0);

			}

		      TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);

		      TREE_OPERAND (lhsi, takeop) = rhs;

		      TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);

		      if (dump_file && (dump_flags & TDF_DETAILS))

			{

			  fprintf (dump_file, "After LHS:");

			  print_generic_stmt (dump_file, lhsi, 0);

			  fprintf (dump_file, "After curr expr:");

			  print_generic_stmt (dump_file, bexpr, 0);

			}

		      bsi_move_before (&lhsbsi, currbsi);

		      update_stmt (lhsdef);

		      update_stmt (bsi_stmt (*currbsi));

		      lhsbsi = bsi_for_stmt (lhsdef);

		      update_stmt (bsi_stmt (lhsbsi));

		      /* If update_stmt didn't reorder our operands,

			 we'd like to recurse on the expression we

			 just reassociated and reassociate it

			 top-down, exposing further opportunities.

			 Unfortunately, update_stmt does reorder them,

			 so we can't do this cheaply.  */

		      if (!foundmatch)

			reassociate_stats.reassociated_by_rank++;

		      else

			reassociate_stats.reassociated_by_match++;

		      return true;

		    }

		}

  return changed;

  return false;

/* Reassociate expressions in basic block BB and its dominator as

/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,

   children , return true if any

   look in OPS for a corresponding positive operation to cancel it

   expressions changed.  */

   out.  If we find one, remove the other from OPS, replace

   OPS[CURRINDEX] with 0, and return true.  Otherwise, return

   false. */

reassociate_bb (basic_block bb)

eliminate_plus_minus_pair (enum tree_code opcode,

			   VEC (operand_entry_t, heap) **ops,

			   unsigned int currindex,

			   operand_entry_t curr)

  bool changed = false;

  tree negateop;

  block_stmt_iterator bsi;

  unsigned int i;

  basic_block son;

  operand_entry_t oe;

  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))

  if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)

    return false;

  negateop = get_unary_op (curr->op, NEGATE_EXPR);

  if (negateop == NULL_TREE)

    return false;

  /* Any non-negated version will have a rank that is one less than

     the current rank.  So once we hit those ranks, if we don't find

     one, we can stop.  */

  for (i = currindex;

       VEC_iterate (operand_entry_t, *ops, i, oe)  && oe->rank >= curr->rank - 1 ;

       i++)

      tree stmt = bsi_stmt (bsi);

      if (oe->op == negateop && i != currindex)

      if (TREE_CODE (stmt) == MODIFY_EXPR)

	  tree rhs = TREE_OPERAND (stmt, 1);

	  if (associative_tree_code (TREE_CODE (rhs)))

	  if (dump_file && (dump_flags & TDF_DETAILS))

	      if (reassociate_expr (rhs, &bsi))

	      fprintf (dump_file, "Equivalence: ");

		{

	      print_generic_expr (dump_file, negateop, 0);

		  changed = true;

	      fprintf (dump_file, " + -");

		  update_stmt (stmt);		  

	      print_generic_expr (dump_file, oe->op, 0);

		}

	      fprintf (dump_file, " -> 0\n");

	      insert_seen_binop (TREE_OPERAND (rhs, 0),

				 TREE_OPERAND (rhs, 1));

  for (son = first_dom_son (CDI_DOMINATORS, bb);

       son;

  return false;

       son = next_dom_son (CDI_DOMINATORS, son))

    {

      changed |= reassociate_bb (son);

    }

  return changed;  

/* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a

   bitwise not expression, look in OPS for a corresponding operand to

   cancel it out.  If we find one, remove the other from OPS, replace

   OPS[CURRINDEX] with 0, and return true.  Otherwise, return

   false. */

do_reassoc (void)

eliminate_not_pairs (enum tree_code opcode,

{  

		     VEC (operand_entry_t, heap) **ops,

  bool changed = false;

		     unsigned int currindex,

		     operand_entry_t curr)

  changed = reassociate_bb (ENTRY_BLOCK_PTR);

{

  tree notop;

  unsigned int i;

  operand_entry_t oe;

  if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)

      || TREE_CODE (curr->op) != SSA_NAME)

    return false;

  notop = get_unary_op (curr->op, BIT_NOT_EXPR);

  if (notop == NULL_TREE)

    return false;

  /* Any non-not version will have a rank that is one less than

     the current rank.  So once we hit those ranks, if we don't find

     one, we can stop.  */

  for (i = currindex;

       VEC_iterate (operand_entry_t, *ops, i, oe)  && oe->rank >= curr->rank - 1 ;

       i++)

    {

      if (oe->op == notop && i != currindex)

	{

	  if (dump_file && (dump_flags & TDF_DETAILS))

	    {

	      fprintf (dump_file, "Equivalence: ");

	      print_generic_expr (dump_file, notop, 0);

	      if (opcode == BIT_AND_EXPR)

		fprintf (dump_file, " & ~");

	      else if (opcode == BIT_IOR_EXPR)

		fprintf (dump_file, " | ~");

	      print_generic_expr (dump_file, oe->op, 0);

	      if (opcode == BIT_AND_EXPR)

		fprintf (dump_file, " -> 0\n");

	      else if (opcode == BIT_IOR_EXPR)

		fprintf (dump_file, " -> -1\n");

	    }

	  if (opcode == BIT_AND_EXPR)

	    oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);

	  else if (opcode == BIT_IOR_EXPR)

	    oe->op = build_low_bits_mask (TREE_TYPE (oe->op),

					  TYPE_PRECISION (TREE_TYPE (oe->op)));

	  reassociate_stats.ops_eliminated += VEC_length (operand_entry_t, *ops) - 1;

	  VEC_free (operand_entry_t, heap, *ops);

	  *ops = NULL;

	  VEC_safe_push (operand_entry_t, heap, *ops, oe);

	  return true;

	}

    }

  return changed;  

  return false;

/* Gate and execute functions for Reassociation.  */

static void

eliminate_using_constants (enum tree_code opcode,

			   VEC(operand_entry_t, heap) **ops)

{

  operand_entry_t oelast = VEC_last (operand_entry_t, *ops);

  if (oelast->rank == 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast->op)))

    {

      switch (opcode)

	{

	case BIT_AND_EXPR:

	  if (integer_zerop (oelast->op))

	    {

	      if (VEC_length (operand_entry_t, *ops) != 1)

		{

		  if (dump_file && (dump_flags & TDF_DETAILS))

		    fprintf (dump_file, "Found & 0, removing all other ops\n");

		  reassociate_stats.ops_eliminated += VEC_length (operand_entry_t, *ops) - 1;

		  VEC_free (operand_entry_t, heap, *ops);

		  *ops = NULL;

		  VEC_safe_push (operand_entry_t, heap, *ops, oelast);

		  return;

		}

	    }

	  /* FALLTHRU */

	case BIT_IOR_EXPR:

	  if (integer_all_onesp (oelast->op))

	    {

	      if (VEC_length (operand_entry_t, *ops) != 1)

		{

		  if (dump_file && (dump_flags & TDF_DETAILS))

		    fprintf (dump_file, "Found [&|] -1, removing\n");

		  VEC_pop (operand_entry_t, *ops);

		  reassociate_stats.ops_eliminated++;

		}

	    }

	  break;

	case MULT_EXPR:

	  if (integer_zerop (oelast->op))

	    {

	      if (VEC_length (operand_entry_t, *ops) != 1)

		{

		  if (dump_file && (dump_flags & TDF_DETAILS))

		    fprintf (dump_file, "Found * 0, removing all other ops\n");

		  reassociate_stats.ops_eliminated += VEC_length (operand_entry_t, *ops) - 1;

		  VEC_free (operand_entry_t, heap, *ops);

		  *ops = NULL;

		  VEC_safe_push (operand_entry_t, heap, *ops, oelast);

		  return;

		}

	    }

	  else if (integer_onep (oelast->op))

	    {

	      if (VEC_length (operand_entry_t, *ops) != 1)

		{

		  if (dump_file && (dump_flags & TDF_DETAILS))

		    fprintf (dump_file, "Found * 1, removing\n");

		  VEC_pop (operand_entry_t, *ops);

		  reassociate_stats.ops_eliminated++;

		  return;

		}

	    }

	  break;

	case BIT_XOR_EXPR:

	case PLUS_EXPR:

	case MINUS_EXPR:

	  if (integer_zerop (oelast->op))

	    {

	      if (VEC_length (operand_entry_t, *ops) != 1)

		{

		  if (dump_file && (dump_flags & TDF_DETAILS))

		    fprintf (dump_file, "Found [|^+] 0, removing\n");

		  VEC_pop (operand_entry_t, *ops);

		  reassociate_stats.ops_eliminated++;

		  return;

		}

	    }

	  break;

	default:

	  break;

	}

    }

}

/* Perform various identities and other optimizations on the list of

   operand entries, stored in OPS.  The tree code for the binary

   operation between all the operands is OPCODE.  */

execute_reassoc (void)

optimize_ops_list (enum tree_code opcode,

		   VEC (operand_entry_t, heap) **ops)

  init_reassoc ();

  unsigned int length = VEC_length (operand_entry_t, *ops);

  do_reassoc ();

  unsigned int i;

  operand_entry_t oe;

  int fconstcount = 0;

  int iconstcount = 0;

  int oconstcount = 0;

  operand_entry_t oelast = NULL;

  bool iterate = false;

  if (length == 1)

    return;

  oelast = VEC_last (operand_entry_t, *ops);

  /* If the last two are constants, pop the constants off, merge them

     and try the next two.  */

  if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))

    {

      operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);

      if (oelm1->rank == 0

	  && is_gimple_min_invariant (oelm1->op)

	  && lang_hooks.types_compatible_p (TREE_TYPE (oelm1->op),

					    TREE_TYPE (oelast->op)))

	{

	  tree folded = fold_build2 (opcode, TREE_TYPE (oelm1->op),

				     oelm1->op, oelast->op);

	  if (is_gimple_min_invariant (folded))

	    {

	      if (dump_file && (dump_flags & TDF_DETAILS))

		fprintf (dump_file, "Merging constants\n");

	      VEC_pop (operand_entry_t, *ops);

	      VEC_pop (operand_entry_t, *ops);

	      add_to_ops_vec (ops, folded);

	      reassociate_stats.constants_eliminated++;

	      optimize_ops_list (opcode, ops);

	      return;

	    }

	}

    }

  eliminate_using_constants (opcode, ops);

  oelast = NULL;

  for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)

    {

      bool done = false;

      if (eliminate_not_pairs (opcode, ops, i, oe))

	return;

      if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)

	  || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))

	{

	  if (done)

	    return;

	  iterate = true;

	  oelast = NULL;

	  continue;

	}

      if (oe->rank == 0 && is_gimple_min_invariant (oe->op))

	{

	  switch (constant_type (oe->op))

	    {

	    case INTEGER_CONST_TYPE:

	      iconstcount++;

	      break;

	    case FLOAT_CONST_TYPE:

	      fconstcount++;

	      break;

	    case OTHER_CONST_TYPE:

	      oconstcount++;

	      break;

	    default:

	      break;

	    }

	}

      oelast = oe;

      i++;

    }

  if (iconstcount > 0 && dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "iconstcount is %d\n", iconstcount);

  if (fconstcount > 0 && dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "fconstcount is %d\n", fconstcount);

  if (oconstcount> 0 && dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "oconstcount is %d\n", oconstcount);

  length  = VEC_length (operand_entry_t, *ops);

  oelast = VEC_last (operand_entry_t, *ops);

  if (iterate)

    optimize_ops_list (opcode, ops);

}

#if 0

static tree

merge_two_ops (enum tree_code code, tree op1, tree op2)

{

  tree temp;

  tree name;

  tree newexpr;

  temp = create_tmp_var (TREE_TYPE (op1), "mergetmp");

  add_referenced_tmp_var (temp);

  newexpr = fold_build2 (code, TREE_TYPE (op1), op1, op2);

  newexpr = build (MODIFY_EXPR, TREE_TYPE (op1), temp, newexpr);

  name = make_ssa_name (temp, newexpr);

  TREE_OPERAND (newexpr, 0) = name;

  return name;

}

static void

merge_leaves_of_rank (enum tree_code opcode, VEC (tree, heap) *worklist,

		      VEC (tree, heap) **results)

{

  unsigned int length = VEC_length (tree, worklist);

  if (length % 2 ==  1)

    {

      VEC_safe_push (tree, heap, *results, VEC_pop (tree, worklist));

      length--;

    }

  while (length != 0)

    {

      tree oe1 = VEC_pop (tree, worklist);

      tree oe2 = VEC_pop (tree, worklist);

      length -= 2;

      VEC_safe_push (tree, heap, *results, merge_two_ops (opcode, oe1, oe2));

    }

  VEC_free (tree, heap, worklist);

}

static void

rewrite_expr_tree_new (tree stmt, enum tree_code opcode,

		       VEC (operand_entry_t, heap) **ops)

{

  VEC(tree, heap) *initial_merge_worklist = NULL;

  VEC(tree, heap) *merge_worklist = NULL;

  VEC(tree, heap) *stmtsforsale = NULL;

  operand_entry_t oe;

  unsigned int opslength = VEC_length (operand_entry_t, *ops);

  if (opslength < 4)

    return;

  /* Initialize the worklist */

  while (VEC_length (operand_entry_t, *ops) != 0)

    {

      initial_merge_worklist = NULL;

      oe = VEC_pop (operand_entry_t, *ops);

      while (!VEC_empty (operand_entry_t, *ops)

	     && VEC_last (operand_entry_t, *ops)->rank == oe->rank)

	{

	  VEC_safe_push (tree, heap, initial_merge_worklist, oe->op);

	  oe = VEC_pop (operand_entry_t, *ops);

	}

      VEC_safe_push (tree, heap, initial_merge_worklist, oe->op);

      merge_leaves_of_rank (opcode, initial_merge_worklist, &merge_worklist);

    }

  gcc_assert (VEC_length (tree, merge_worklist) <= opslength);

  while (VEC_length (tree, merge_worklist) != 0)

    add_to_ops_vec (ops, VEC_pop (tree, merge_worklist));

}

#endif

static bool

is_phi_for_stmt (tree stmt, tree operand)

{

  tree def_stmt;

  tree lhs = TREE_OPERAND (stmt, 0);

  use_operand_p arg_p;

  ssa_op_iter i;

  if (TREE_CODE (operand) != SSA_NAME)

    return false;

  def_stmt = SSA_NAME_DEF_STMT (operand);

  if (TREE_CODE (def_stmt) != PHI_NODE)

    return false;

  FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)

    if (lhs == USE_FROM_PTR (arg_p))

      return true;

  return false;

}

/* Recursively rewrite our linearized statements so that the operators

   match those in OPS[OPINDEX], putting the computation in rank

   order.  */

static void

rewrite_expr_tree (tree stmt, unsigned int opindex,

		   VEC(operand_entry_t, heap) * ops)

{

  tree rhs = TREE_OPERAND (stmt, 1);

  operand_entry_t oe;

  /* If we have three operands left, then we want to make sure the one

     that gets the double binary op are the ones with the same rank.

     The alternative we try is to see if this is a destructive

     update style statement, which is like:

     b = phi (a, ...)

     a = c + b;

     In that case, we want to use the destructive update form to

     expose the possible vectorizer sum reduction opportunity.

     In that case, the third operand will be the phi node.

     We could, of course, try to be better as noted above, and do a

     lot of work to try to find these opportunities in >3 operand

     cases, but it is unlikely to be worth it.  */

  if (opindex + 3 == VEC_length (operand_entry_t, ops))

    {

      operand_entry_t oe1, oe2, oe3;

      oe1 = VEC_index (operand_entry_t, ops, opindex);

      oe2 = VEC_index (operand_entry_t, ops, opindex + 1);

      oe3 = VEC_index (operand_entry_t, ops, opindex + 2);

      if ((oe1->rank == oe2->rank

	   && oe2->rank != oe3->rank)

	  || (is_phi_for_stmt (stmt, oe3->op)

	      && !is_phi_for_stmt (stmt, oe1->op)

	      && !is_phi_for_stmt (stmt, oe2->op)))

	{

	  struct operand_entry temp = *oe3;

	  oe3->op = oe1->op;

	  oe3->rank = oe1->rank;

	  oe1->op = temp.op;

	  oe1->rank= temp.rank;

	}

    }

  /* The final recursion case for this function is that you have

     exactly two operations left.

     If we had one exactly one op in the entire list to start with, we

     would have never called this function, and the tail recursion

     rewrites them one at a time.  */

  if (opindex + 2 == VEC_length (operand_entry_t, ops))

    {

      operand_entry_t oe1, oe2;

      oe1 = VEC_index (operand_entry_t, ops, opindex);

      oe2 = VEC_index (operand_entry_t, ops, opindex + 1);

      if (TREE_OPERAND (rhs, 0) != oe1->op

	  || TREE_OPERAND (rhs, 1) != oe2->op)

	{

	  if (dump_file && (dump_flags & TDF_DETAILS))

	    {

	      fprintf (dump_file, "Transforming ");

	      print_generic_expr (dump_file, rhs, 0);

	    }

	  TREE_OPERAND (rhs, 0) = oe1->op;

	  TREE_OPERAND (rhs, 1) = oe2->op;

	  update_stmt (stmt);

	  if (dump_file && (dump_flags & TDF_DETAILS))

	    {

	      fprintf (dump_file, " into ");

	      print_generic_stmt (dump_file, rhs, 0);

	    }

	}

      return;

    }

  /* If we hit here, we should have 3 or more ops left.  */

  gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));

  /* Rewrite the next operator.  */

  oe = VEC_index (operand_entry_t, ops, opindex);

  if (oe->op != TREE_OPERAND (rhs, 1))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

	{

	  fprintf (dump_file, "Transforming ");

	  print_generic_expr (dump_file, rhs, 0);

	}

      TREE_OPERAND (rhs, 1) = oe->op;

      update_stmt (stmt);

      if (dump_file && (dump_flags & TDF_DETAILS))

	{

	  fprintf (dump_file, " into ");

	  print_generic_stmt (dump_file, rhs, 0);

	}

    }

  /* Recurse on the LHS of the binary operator, which is guaranteed to

     be the non-leaf side.  */

  rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)),

		     opindex + 1, ops);

}

/* Transform STMT, which is really (A +B) + (C + D) into the left

   linear form, ((A+B)+C)+D.

   Recurse on D if necessary.  */

static void

linearize_expr (tree stmt)

{

  block_stmt_iterator bsinow, bsirhs;

  tree rhs = TREE_OPERAND (stmt, 1);

  enum tree_code rhscode = TREE_CODE (rhs);

  tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));

  tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));

  tree newbinrhs = NULL_TREE;

  gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs))

	      && is_reassociable_op (binrhs, TREE_CODE (rhs)));

  bsinow = bsi_for_stmt (stmt);

  bsirhs = bsi_for_stmt (binrhs);

  bsi_move_before (&bsirhs, &bsinow);

  TREE_OPERAND (rhs, 1) = TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0);

  if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME)

    newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));

  TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0) = TREE_OPERAND (binlhs, 0);

  TREE_OPERAND (rhs, 0) = TREE_OPERAND (binrhs, 0);

  if (dump_file && (dump_flags & TDF_DETAILS))

    {

      fprintf (dump_file, "Linearized: ");

      print_generic_stmt (dump_file, rhs, 0);

    }

  reassociate_stats.linearized++;

  update_stmt (binrhs);

  update_stmt (binlhs);