contrib/gcc/tree-ssa-loop-ivopts.c

304 /* If there are at most this number of ivs in the set, try removing unnecessary
305    ivs from the set always.  */
578 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
613   /* Scan the block from the end, since the original ivs are usually
960 /* Finds basic ivs.  */
996 /* Marks basic ivs.  */
1058 /* Finds general ivs in statement STMT.  */
1071 /* Finds general ivs in basic block BB.  */
1082 /* Finds general ivs.  */
1275       /* Eliminating condition based on two ivs would be nontrivial.
2230 	  /* Just add the ivs based on the value of the iv used here.  */
2284   /* Add commonly used ivs.  */
3060       /* This may happen with the original ivs.  */
4359      this is not really relevant for artificial ivs created by other
4432 	make a lot of ivs without a reason).
4475       fprintf (dump_file, "  ivs\tcost\n");
4510 iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4514   cost += ivs->cand_use_cost;
4515   cost += ivs->cand_cost;
4516   cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4518   ivs->cost = cost;
4524 iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4534       ivs->n_invariant_uses[iid]--;
4535       if (ivs->n_invariant_uses[iid] == 0)
4536 	ivs->n_regs--;
4543 iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4549   cp = ivs->cand_for_use[uid];
4554   ivs->bad_uses++;
4555   ivs->cand_for_use[uid] = NULL;
4556   ivs->n_cand_uses[cid]--;
4558   if (ivs->n_cand_uses[cid] == 0)
4560       bitmap_clear_bit (ivs->cands, cid);
4563 	ivs->n_regs--;
4564       ivs->n_cands--;
4565       ivs->cand_cost -= cp->cand->cost;
4567       iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4570   ivs->cand_use_cost -= cp->cost;
4572   iv_ca_set_remove_invariants (ivs, cp->depends_on);
4573   iv_ca_recount_cost (data, ivs);
4579 iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4589       ivs->n_invariant_uses[iid]++;
4590       if (ivs->n_invariant_uses[iid] == 1)
4591 	ivs->n_regs++;
4598 iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4603   if (ivs->cand_for_use[uid] == cp)
4606   if (ivs->cand_for_use[uid])
4607     iv_ca_set_no_cp (data, ivs, use);
4613       ivs->bad_uses--;
4614       ivs->cand_for_use[uid] = cp;
4615       ivs->n_cand_uses[cid]++;
4616       if (ivs->n_cand_uses[cid] == 1)
4618 	  bitmap_set_bit (ivs->cands, cid);
4621 	    ivs->n_regs++;
4622 	  ivs->n_cands++;
4623 	  ivs->cand_cost += cp->cand->cost;
4625 	  iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4628       ivs->cand_use_cost += cp->cost;
4629       iv_ca_set_add_invariants (ivs, cp->depends_on);
4630       iv_ca_recount_cost (data, ivs);
4638 iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4645   gcc_assert (ivs->upto >= use->id);
4647   if (ivs->upto == use->id)
4649       ivs->upto++;
4650       ivs->bad_uses++;
4653   EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4661   iv_ca_set_cp (data, ivs, use, best_cp);
4667 iv_ca_cost (struct iv_ca *ivs)
4669   return (ivs->bad_uses ? INFTY : ivs->cost);
4675 iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4685       if (ivs->n_invariant_uses[i] == 0)
4733 iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4735   return ivs->cand_for_use[use->id];
4764 iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4777       gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4778       iv_ca_set_cp (data, ivs, act->use, to);
4788 iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4790   return ivs->n_cand_uses[cand->id] > 0;
4796 iv_ca_n_cands (struct iv_ca *ivs)
4798   return ivs->n_cands;
4842 iv_ca_free (struct iv_ca **ivs)
4844   free ((*ivs)->cand_for_use);
4845   free ((*ivs)->n_cand_uses);
4846   BITMAP_FREE ((*ivs)->cands);
4847   free ((*ivs)->n_invariant_uses);
4848   free (*ivs);
4849   *ivs = NULL;
4855 iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4860   fprintf (file, "  cost %d\n", iv_ca_cost (ivs));
4861   bitmap_print (file, ivs->cands, "  candidates ","\n");
4864     if (ivs->n_invariant_uses[i])
4877 iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4886   for (i = 0; i < ivs->upto; i++)
4889       old_cp = iv_ca_cand_for_use (ivs, use);
4899       if (!iv_ca_has_deps (ivs, new_cp))
4908   iv_ca_delta_commit (data, ivs, *delta, true);
4909   cost = iv_ca_cost (ivs);
4911     *n_ivs = iv_ca_n_cands (ivs);
4912   iv_ca_delta_commit (data, ivs, *delta, false);
4921 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4936       old_cp = iv_ca_cand_for_use (ivs, use);
4944 	  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4954 	      if (!iv_ca_has_deps (ivs, cp))
4965 	  EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4975 	      if (!iv_ca_has_deps (ivs, cp))
4994   iv_ca_delta_commit (data, ivs, *delta, true);
4995   cost = iv_ca_cost (ivs);
4996   iv_ca_delta_commit (data, ivs, *delta, false);
5006 iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
5015   best_cost = iv_ca_cost (ivs);
5017   EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
5024       acost = iv_ca_narrow (data, ivs, cand, &act_delta);
5042   /* Recurse to possibly remove other unnecessary ivs.  */
5043   iv_ca_delta_commit (data, ivs, best_delta, true);
5044   best_cost = iv_ca_prune (data, ivs, except_cand, delta);
5045   iv_ca_delta_commit (data, ivs, best_delta, false);
5054 try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
5064   iv_ca_add_use (data, ivs, use);
5065   best_cost = iv_ca_cost (ivs);
5067   cp = iv_ca_cand_for_use (ivs, use);
5071       iv_ca_set_no_cp (data, ivs, use);
5076      just one generic biv.  If we added here many ivs specific to the uses,
5078      minimum, thus causing us to create too many ivs.  The approach from
5079      few ivs to more seems more likely to be successful -- starting from few
5080      ivs, replacing an expensive use by a specific iv should always be a
5086       if (iv_ca_cand_used_p (ivs, cand))
5093       iv_ca_set_cp (data, ivs, use, cp);
5094       act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5095       iv_ca_set_no_cp (data, ivs, use);
5122 	  if (iv_ca_cand_used_p (ivs, cand))
5126 	  iv_ca_set_cp (data, ivs, use, cp);
5127 	  act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5128 	  iv_ca_set_no_cp (data, ivs, use);
5129 	  act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
5145   iv_ca_delta_commit (data, ivs, best_delta, true);
5156   struct iv_ca *ivs = iv_ca_new (data);
5160     if (!try_add_cand_for (data, ivs, iv_use (data, i)))
5162 	iv_ca_free (&ivs);
5166   return ivs;
5172 try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
5174   unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
5183       if (iv_ca_cand_used_p (ivs, cand))
5186       acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
5194 	  iv_ca_delta_commit (data, ivs, act_delta, true);
5195 	  acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
5196 	  iv_ca_delta_commit (data, ivs, act_delta, false);
5213       best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
5220   iv_ca_delta_commit (data, ivs, best_delta, true);
5221   gcc_assert (best_cost == iv_ca_cost (ivs));
5228    solution and remove the unused ivs while this improves the cost.  */
5242 	fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
5694 /* Removes the ivs that are not used after rewriting.  */
5858   /* Remove the ivs that are unused after rewriting.  */