1/* Branch prediction routines for the GNU compiler.
2   Copyright (C) 2000-2014 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20/* References:
21
22   [1] "Branch Prediction for Free"
23       Ball and Larus; PLDI '93.
24   [2] "Static Branch Frequency and Program Profile Analysis"
25       Wu and Larus; MICRO-27.
26   [3] "Corpus-based Static Branch Prediction"
27       Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
28
29
30#include "config.h"
31#include "system.h"
32#include "coretypes.h"
33#include "tm.h"
34#include "tree.h"
35#include "calls.h"
36#include "rtl.h"
37#include "tm_p.h"
38#include "hard-reg-set.h"
39#include "predict.h"
40#include "vec.h"
41#include "hashtab.h"
42#include "hash-set.h"
43#include "machmode.h"
44#include "input.h"
45#include "function.h"
46#include "dominance.h"
47#include "cfg.h"
48#include "cfganal.h"
49#include "basic-block.h"
50#include "insn-config.h"
51#include "regs.h"
52#include "flags.h"
53#include "profile.h"
54#include "except.h"
55#include "diagnostic-core.h"
56#include "recog.h"
57#include "expr.h"
58#include "coverage.h"
59#include "sreal.h"
60#include "params.h"
61#include "target.h"
62#include "cfgloop.h"
63#include "hash-map.h"
64#include "tree-ssa-alias.h"
65#include "internal-fn.h"
66#include "gimple-expr.h"
67#include "is-a.h"
68#include "gimple.h"
69#include "gimple-iterator.h"
70#include "gimple-ssa.h"
71#include "plugin-api.h"
72#include "ipa-ref.h"
73#include "cgraph.h"
74#include "tree-cfg.h"
75#include "tree-phinodes.h"
76#include "ssa-iterators.h"
77#include "tree-ssa-loop-niter.h"
78#include "tree-ssa-loop.h"
79#include "tree-pass.h"
80#include "tree-scalar-evolution.h"
81#include "cfgloop.h"
82
83/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
84		   1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
85static sreal real_almost_one, real_br_prob_base,
86	     real_inv_br_prob_base, real_one_half, real_bb_freq_max;
87
88static void combine_predictions_for_insn (rtx_insn *, basic_block);
89static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
90static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
91static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
92static bool can_predict_insn_p (const rtx_insn *);
93
94/* Information we hold about each branch predictor.
95   Filled using information from predict.def.  */
96
97struct predictor_info
98{
99  const char *const name;	/* Name used in the debugging dumps.  */
100  const int hitrate;		/* Expected hitrate used by
101				   predict_insn_def call.  */
102  const int flags;
103};
104
105/* Use given predictor without Dempster-Shaffer theory if it matches
106   using first_match heuristics.  */
107#define PRED_FLAG_FIRST_MATCH 1
108
109/* Recompute hitrate in percent to our representation.  */
110
111#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
112
113#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114static const struct predictor_info predictor_info[]= {
115#include "predict.def"
116
117  /* Upper bound on predictors.  */
118  {NULL, 0, 0}
119};
120#undef DEF_PREDICTOR
121
122/* Return TRUE if frequency FREQ is considered to be hot.  */
123
124static inline bool
125maybe_hot_frequency_p (struct function *fun, int freq)
126{
127  struct cgraph_node *node = cgraph_node::get (fun->decl);
128  if (!profile_info
129      || !opt_for_fn (fun->decl, flag_branch_probabilities))
130    {
131      if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
132        return false;
133      if (node->frequency == NODE_FREQUENCY_HOT)
134        return true;
135    }
136  if (profile_status_for_fn (fun) == PROFILE_ABSENT)
137    return true;
138  if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
139      && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3))
140    return false;
141  if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
142    return false;
143  if (freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency
144	      / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
145    return false;
146  return true;
147}
148
149static gcov_type min_count = -1;
150
151/* Determine the threshold for hot BB counts.  */
152
153gcov_type
154get_hot_bb_threshold ()
155{
156  gcov_working_set_t *ws;
157  if (min_count == -1)
158    {
159      ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
160      gcc_assert (ws);
161      min_count = ws->min_counter;
162    }
163  return min_count;
164}
165
166/* Set the threshold for hot BB counts.  */
167
168void
169set_hot_bb_threshold (gcov_type min)
170{
171  min_count = min;
172}
173
174/* Return TRUE if frequency FREQ is considered to be hot.  */
175
176bool
177maybe_hot_count_p (struct function *fun, gcov_type count)
178{
179  if (fun && profile_status_for_fn (fun) != PROFILE_READ)
180    return true;
181  /* Code executed at most once is not hot.  */
182  if (profile_info->runs >= count)
183    return false;
184  return (count >= get_hot_bb_threshold ());
185}
186
187/* Return true in case BB can be CPU intensive and should be optimized
188   for maximal performance.  */
189
190bool
191maybe_hot_bb_p (struct function *fun, const_basic_block bb)
192{
193  gcc_checking_assert (fun);
194  if (profile_status_for_fn (fun) == PROFILE_READ)
195    return maybe_hot_count_p (fun, bb->count);
196  return maybe_hot_frequency_p (fun, bb->frequency);
197}
198
199/* Return true in case BB can be CPU intensive and should be optimized
200   for maximal performance.  */
201
202bool
203maybe_hot_edge_p (edge e)
204{
205  if (profile_status_for_fn (cfun) == PROFILE_READ)
206    return maybe_hot_count_p (cfun, e->count);
207  return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e));
208}
209
210/* Return true if profile COUNT and FREQUENCY, or function FUN static
211   node frequency reflects never being executed.  */
212
213static bool
214probably_never_executed (struct function *fun,
215                         gcov_type count, int frequency)
216{
217  gcc_checking_assert (fun);
218  if (profile_status_for_fn (fun) == PROFILE_READ)
219    {
220      int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
221      if (count * unlikely_count_fraction >= profile_info->runs)
222	return false;
223      if (!frequency)
224	return true;
225      if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
226	return false;
227      if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
228	{
229          gcov_type computed_count;
230          /* Check for possibility of overflow, in which case entry bb count
231             is large enough to do the division first without losing much
232             precision.  */
233	  if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE *
234	      REG_BR_PROB_BASE)
235            {
236              gcov_type scaled_count
237		  = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
238	     unlikely_count_fraction;
239	      computed_count = RDIV (scaled_count,
240				     ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
241            }
242          else
243            {
244	      computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count,
245				     ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
246              computed_count *= frequency * unlikely_count_fraction;
247            }
248          if (computed_count >= profile_info->runs)
249            return false;
250	}
251      return true;
252    }
253  if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
254      && (cgraph_node::get (fun->decl)->frequency
255	  == NODE_FREQUENCY_UNLIKELY_EXECUTED))
256    return true;
257  return false;
258}
259
260
261/* Return true in case BB is probably never executed.  */
262
263bool
264probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
265{
266  return probably_never_executed (fun, bb->count, bb->frequency);
267}
268
269
270/* Return true in case edge E is probably never executed.  */
271
272bool
273probably_never_executed_edge_p (struct function *fun, edge e)
274{
275  return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
276}
277
278/* Return true when current function should always be optimized for size.  */
279
280bool
281optimize_function_for_size_p (struct function *fun)
282{
283  if (!fun || !fun->decl)
284    return optimize_size;
285  cgraph_node *n = cgraph_node::get (fun->decl);
286  return n && n->optimize_for_size_p ();
287}
288
289/* Return true when current function should always be optimized for speed.  */
290
291bool
292optimize_function_for_speed_p (struct function *fun)
293{
294  return !optimize_function_for_size_p (fun);
295}
296
297/* Return TRUE when BB should be optimized for size.  */
298
299bool
300optimize_bb_for_size_p (const_basic_block bb)
301{
302  return (optimize_function_for_size_p (cfun)
303	  || (bb && !maybe_hot_bb_p (cfun, bb)));
304}
305
306/* Return TRUE when BB should be optimized for speed.  */
307
308bool
309optimize_bb_for_speed_p (const_basic_block bb)
310{
311  return !optimize_bb_for_size_p (bb);
312}
313
314/* Return TRUE when BB should be optimized for size.  */
315
316bool
317optimize_edge_for_size_p (edge e)
318{
319  return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
320}
321
322/* Return TRUE when BB should be optimized for speed.  */
323
324bool
325optimize_edge_for_speed_p (edge e)
326{
327  return !optimize_edge_for_size_p (e);
328}
329
330/* Return TRUE when BB should be optimized for size.  */
331
332bool
333optimize_insn_for_size_p (void)
334{
335  return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
336}
337
338/* Return TRUE when BB should be optimized for speed.  */
339
340bool
341optimize_insn_for_speed_p (void)
342{
343  return !optimize_insn_for_size_p ();
344}
345
346/* Return TRUE when LOOP should be optimized for size.  */
347
348bool
349optimize_loop_for_size_p (struct loop *loop)
350{
351  return optimize_bb_for_size_p (loop->header);
352}
353
354/* Return TRUE when LOOP should be optimized for speed.  */
355
356bool
357optimize_loop_for_speed_p (struct loop *loop)
358{
359  return optimize_bb_for_speed_p (loop->header);
360}
361
362/* Return TRUE when LOOP nest should be optimized for speed.  */
363
364bool
365optimize_loop_nest_for_speed_p (struct loop *loop)
366{
367  struct loop *l = loop;
368  if (optimize_loop_for_speed_p (loop))
369    return true;
370  l = loop->inner;
371  while (l && l != loop)
372    {
373      if (optimize_loop_for_speed_p (l))
374        return true;
375      if (l->inner)
376        l = l->inner;
377      else if (l->next)
378        l = l->next;
379      else
380        {
381	  while (l != loop && !l->next)
382	    l = loop_outer (l);
383	  if (l != loop)
384	    l = l->next;
385	}
386    }
387  return false;
388}
389
390/* Return TRUE when LOOP nest should be optimized for size.  */
391
392bool
393optimize_loop_nest_for_size_p (struct loop *loop)
394{
395  return !optimize_loop_nest_for_speed_p (loop);
396}
397
398/* Return true when edge E is likely to be well predictable by branch
399   predictor.  */
400
401bool
402predictable_edge_p (edge e)
403{
404  if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
405    return false;
406  if ((e->probability
407       <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
408      || (REG_BR_PROB_BASE - e->probability
409          <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
410    return true;
411  return false;
412}
413
414
415/* Set RTL expansion for BB profile.  */
416
417void
418rtl_profile_for_bb (basic_block bb)
419{
420  crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
421}
422
423/* Set RTL expansion for edge profile.  */
424
425void
426rtl_profile_for_edge (edge e)
427{
428  crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
429}
430
431/* Set RTL expansion to default mode (i.e. when profile info is not known).  */
432void
433default_rtl_profile (void)
434{
435  crtl->maybe_hot_insn_p = true;
436}
437
438/* Return true if the one of outgoing edges is already predicted by
439   PREDICTOR.  */
440
441bool
442rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
443{
444  rtx note;
445  if (!INSN_P (BB_END (bb)))
446    return false;
447  for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
448    if (REG_NOTE_KIND (note) == REG_BR_PRED
449	&& INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
450      return true;
451  return false;
452}
453
454/*  Structure representing predictions in tree level. */
455
456struct edge_prediction {
457    struct edge_prediction *ep_next;
458    edge ep_edge;
459    enum br_predictor ep_predictor;
460    int ep_probability;
461};
462
463/* This map contains for a basic block the list of predictions for the
464   outgoing edges.  */
465
466static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
467
468/* Return true if the one of outgoing edges is already predicted by
469   PREDICTOR.  */
470
471bool
472gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
473{
474  struct edge_prediction *i;
475  edge_prediction **preds = bb_predictions->get (bb);
476
477  if (!preds)
478    return false;
479
480  for (i = *preds; i; i = i->ep_next)
481    if (i->ep_predictor == predictor)
482      return true;
483  return false;
484}
485
486/* Return true when the probability of edge is reliable.
487
488   The profile guessing code is good at predicting branch outcome (ie.
489   taken/not taken), that is predicted right slightly over 75% of time.
490   It is however notoriously poor on predicting the probability itself.
491   In general the profile appear a lot flatter (with probabilities closer
492   to 50%) than the reality so it is bad idea to use it to drive optimization
493   such as those disabling dynamic branch prediction for well predictable
494   branches.
495
496   There are two exceptions - edges leading to noreturn edges and edges
497   predicted by number of iterations heuristics are predicted well.  This macro
498   should be able to distinguish those, but at the moment it simply check for
499   noreturn heuristic that is only one giving probability over 99% or bellow
500   1%.  In future we might want to propagate reliability information across the
501   CFG if we find this information useful on multiple places.   */
502static bool
503probability_reliable_p (int prob)
504{
505  return (profile_status_for_fn (cfun) == PROFILE_READ
506	  || (profile_status_for_fn (cfun) == PROFILE_GUESSED
507	      && (prob <= HITRATE (1) || prob >= HITRATE (99))));
508}
509
510/* Same predicate as above, working on edges.  */
511bool
512edge_probability_reliable_p (const_edge e)
513{
514  return probability_reliable_p (e->probability);
515}
516
517/* Same predicate as edge_probability_reliable_p, working on notes.  */
518bool
519br_prob_note_reliable_p (const_rtx note)
520{
521  gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
522  return probability_reliable_p (XINT (note, 0));
523}
524
525static void
526predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
527{
528  gcc_assert (any_condjump_p (insn));
529  if (!flag_guess_branch_prob)
530    return;
531
532  add_reg_note (insn, REG_BR_PRED,
533		gen_rtx_CONCAT (VOIDmode,
534				GEN_INT ((int) predictor),
535				GEN_INT ((int) probability)));
536}
537
538/* Predict insn by given predictor.  */
539
540void
541predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
542		  enum prediction taken)
543{
544   int probability = predictor_info[(int) predictor].hitrate;
545
546   if (taken != TAKEN)
547     probability = REG_BR_PROB_BASE - probability;
548
549   predict_insn (insn, predictor, probability);
550}
551
552/* Predict edge E with given probability if possible.  */
553
554void
555rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
556{
557  rtx_insn *last_insn;
558  last_insn = BB_END (e->src);
559
560  /* We can store the branch prediction information only about
561     conditional jumps.  */
562  if (!any_condjump_p (last_insn))
563    return;
564
565  /* We always store probability of branching.  */
566  if (e->flags & EDGE_FALLTHRU)
567    probability = REG_BR_PROB_BASE - probability;
568
569  predict_insn (last_insn, predictor, probability);
570}
571
572/* Predict edge E with the given PROBABILITY.  */
573void
574gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
575{
576  gcc_assert (profile_status_for_fn (cfun) != PROFILE_GUESSED);
577  if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && EDGE_COUNT (e->src->succs) >
578       1)
579      && flag_guess_branch_prob && optimize)
580    {
581      struct edge_prediction *i = XNEW (struct edge_prediction);
582      edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
583
584      i->ep_next = preds;
585      preds = i;
586      i->ep_probability = probability;
587      i->ep_predictor = predictor;
588      i->ep_edge = e;
589    }
590}
591
592/* Remove all predictions on given basic block that are attached
593   to edge E.  */
594void
595remove_predictions_associated_with_edge (edge e)
596{
597  if (!bb_predictions)
598    return;
599
600  edge_prediction **preds = bb_predictions->get (e->src);
601
602  if (preds)
603    {
604      struct edge_prediction **prediction = preds;
605      struct edge_prediction *next;
606
607      while (*prediction)
608	{
609	  if ((*prediction)->ep_edge == e)
610	    {
611	      next = (*prediction)->ep_next;
612	      free (*prediction);
613	      *prediction = next;
614	    }
615	  else
616	    prediction = &((*prediction)->ep_next);
617	}
618    }
619}
620
621/* Clears the list of predictions stored for BB.  */
622
623static void
624clear_bb_predictions (basic_block bb)
625{
626  edge_prediction **preds = bb_predictions->get (bb);
627  struct edge_prediction *pred, *next;
628
629  if (!preds)
630    return;
631
632  for (pred = *preds; pred; pred = next)
633    {
634      next = pred->ep_next;
635      free (pred);
636    }
637  *preds = NULL;
638}
639
640/* Return true when we can store prediction on insn INSN.
641   At the moment we represent predictions only on conditional
642   jumps, not at computed jump or other complicated cases.  */
643static bool
644can_predict_insn_p (const rtx_insn *insn)
645{
646  return (JUMP_P (insn)
647	  && any_condjump_p (insn)
648	  && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
649}
650
651/* Predict edge E by given predictor if possible.  */
652
653void
654predict_edge_def (edge e, enum br_predictor predictor,
655		  enum prediction taken)
656{
657   int probability = predictor_info[(int) predictor].hitrate;
658
659   if (taken != TAKEN)
660     probability = REG_BR_PROB_BASE - probability;
661
662   predict_edge (e, predictor, probability);
663}
664
665/* Invert all branch predictions or probability notes in the INSN.  This needs
666   to be done each time we invert the condition used by the jump.  */
667
668void
669invert_br_probabilities (rtx insn)
670{
671  rtx note;
672
673  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
674    if (REG_NOTE_KIND (note) == REG_BR_PROB)
675      XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0);
676    else if (REG_NOTE_KIND (note) == REG_BR_PRED)
677      XEXP (XEXP (note, 0), 1)
678	= GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
679}
680
681/* Dump information about the branch prediction to the output file.  */
682
683static void
684dump_prediction (FILE *file, enum br_predictor predictor, int probability,
685		 basic_block bb, int used)
686{
687  edge e;
688  edge_iterator ei;
689
690  if (!file)
691    return;
692
693  FOR_EACH_EDGE (e, ei, bb->succs)
694    if (! (e->flags & EDGE_FALLTHRU))
695      break;
696
697  fprintf (file, "  %s heuristics%s: %.1f%%",
698	   predictor_info[predictor].name,
699	   used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
700
701  if (bb->count)
702    {
703      fprintf (file, "  exec %"PRId64, bb->count);
704      if (e)
705	{
706	  fprintf (file, " hit %"PRId64, e->count);
707	  fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
708	}
709    }
710
711  fprintf (file, "\n");
712}
713
714/* We can not predict the probabilities of outgoing edges of bb.  Set them
715   evenly and hope for the best.  */
716static void
717set_even_probabilities (basic_block bb)
718{
719  int nedges = 0;
720  edge e;
721  edge_iterator ei;
722
723  FOR_EACH_EDGE (e, ei, bb->succs)
724    if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
725      nedges ++;
726  FOR_EACH_EDGE (e, ei, bb->succs)
727    if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
728      e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
729    else
730      e->probability = 0;
731}
732
733/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
734   note if not already present.  Remove now useless REG_BR_PRED notes.  */
735
736static void
737combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
738{
739  rtx prob_note;
740  rtx *pnote;
741  rtx note;
742  int best_probability = PROB_EVEN;
743  enum br_predictor best_predictor = END_PREDICTORS;
744  int combined_probability = REG_BR_PROB_BASE / 2;
745  int d;
746  bool first_match = false;
747  bool found = false;
748
749  if (!can_predict_insn_p (insn))
750    {
751      set_even_probabilities (bb);
752      return;
753    }
754
755  prob_note = find_reg_note (insn, REG_BR_PROB, 0);
756  pnote = &REG_NOTES (insn);
757  if (dump_file)
758    fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
759	     bb->index);
760
761  /* We implement "first match" heuristics and use probability guessed
762     by predictor with smallest index.  */
763  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
764    if (REG_NOTE_KIND (note) == REG_BR_PRED)
765      {
766	enum br_predictor predictor = ((enum br_predictor)
767				       INTVAL (XEXP (XEXP (note, 0), 0)));
768	int probability = INTVAL (XEXP (XEXP (note, 0), 1));
769
770	found = true;
771	if (best_predictor > predictor)
772	  best_probability = probability, best_predictor = predictor;
773
774	d = (combined_probability * probability
775	     + (REG_BR_PROB_BASE - combined_probability)
776	     * (REG_BR_PROB_BASE - probability));
777
778	/* Use FP math to avoid overflows of 32bit integers.  */
779	if (d == 0)
780	  /* If one probability is 0% and one 100%, avoid division by zero.  */
781	  combined_probability = REG_BR_PROB_BASE / 2;
782	else
783	  combined_probability = (((double) combined_probability) * probability
784				  * REG_BR_PROB_BASE / d + 0.5);
785      }
786
787  /* Decide which heuristic to use.  In case we didn't match anything,
788     use no_prediction heuristic, in case we did match, use either
789     first match or Dempster-Shaffer theory depending on the flags.  */
790
791  if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
792    first_match = true;
793
794  if (!found)
795    dump_prediction (dump_file, PRED_NO_PREDICTION,
796		     combined_probability, bb, true);
797  else
798    {
799      dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
800		       bb, !first_match);
801      dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
802		       bb, first_match);
803    }
804
805  if (first_match)
806    combined_probability = best_probability;
807  dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
808
809  while (*pnote)
810    {
811      if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
812	{
813	  enum br_predictor predictor = ((enum br_predictor)
814					 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
815	  int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
816
817	  dump_prediction (dump_file, predictor, probability, bb,
818			   !first_match || best_predictor == predictor);
819	  *pnote = XEXP (*pnote, 1);
820	}
821      else
822	pnote = &XEXP (*pnote, 1);
823    }
824
825  if (!prob_note)
826    {
827      add_int_reg_note (insn, REG_BR_PROB, combined_probability);
828
829      /* Save the prediction into CFG in case we are seeing non-degenerated
830	 conditional jump.  */
831      if (!single_succ_p (bb))
832	{
833	  BRANCH_EDGE (bb)->probability = combined_probability;
834	  FALLTHRU_EDGE (bb)->probability
835	    = REG_BR_PROB_BASE - combined_probability;
836	}
837    }
838  else if (!single_succ_p (bb))
839    {
840      int prob = XINT (prob_note, 0);
841
842      BRANCH_EDGE (bb)->probability = prob;
843      FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
844    }
845  else
846    single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
847}
848
849/* Combine predictions into single probability and store them into CFG.
850   Remove now useless prediction entries.  */
851
852static void
853combine_predictions_for_bb (basic_block bb)
854{
855  int best_probability = PROB_EVEN;
856  enum br_predictor best_predictor = END_PREDICTORS;
857  int combined_probability = REG_BR_PROB_BASE / 2;
858  int d;
859  bool first_match = false;
860  bool found = false;
861  struct edge_prediction *pred;
862  int nedges = 0;
863  edge e, first = NULL, second = NULL;
864  edge_iterator ei;
865
866  FOR_EACH_EDGE (e, ei, bb->succs)
867    if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
868      {
869	nedges ++;
870	if (first && !second)
871	  second = e;
872	if (!first)
873	  first = e;
874      }
875
876  /* When there is no successor or only one choice, prediction is easy.
877
878     We are lazy for now and predict only basic blocks with two outgoing
879     edges.  It is possible to predict generic case too, but we have to
880     ignore first match heuristics and do more involved combining.  Implement
881     this later.  */
882  if (nedges != 2)
883    {
884      if (!bb->count)
885	set_even_probabilities (bb);
886      clear_bb_predictions (bb);
887      if (dump_file)
888	fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
889		 nedges, bb->index);
890      return;
891    }
892
893  if (dump_file)
894    fprintf (dump_file, "Predictions for bb %i\n", bb->index);
895
896  edge_prediction **preds = bb_predictions->get (bb);
897  if (preds)
898    {
899      /* We implement "first match" heuristics and use probability guessed
900	 by predictor with smallest index.  */
901      for (pred = *preds; pred; pred = pred->ep_next)
902	{
903	  enum br_predictor predictor = pred->ep_predictor;
904	  int probability = pred->ep_probability;
905
906	  if (pred->ep_edge != first)
907	    probability = REG_BR_PROB_BASE - probability;
908
909	  found = true;
910	  /* First match heuristics would be widly confused if we predicted
911	     both directions.  */
912	  if (best_predictor > predictor)
913	    {
914              struct edge_prediction *pred2;
915	      int prob = probability;
916
917	      for (pred2 = (struct edge_prediction *) *preds;
918		   pred2; pred2 = pred2->ep_next)
919	       if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
920	         {
921	           int probability2 = pred->ep_probability;
922
923		   if (pred2->ep_edge != first)
924		     probability2 = REG_BR_PROB_BASE - probability2;
925
926		   if ((probability < REG_BR_PROB_BASE / 2) !=
927		       (probability2 < REG_BR_PROB_BASE / 2))
928		     break;
929
930		   /* If the same predictor later gave better result, go for it! */
931		   if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
932		       || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
933		     prob = probability2;
934		 }
935	      if (!pred2)
936	        best_probability = prob, best_predictor = predictor;
937	    }
938
939	  d = (combined_probability * probability
940	       + (REG_BR_PROB_BASE - combined_probability)
941	       * (REG_BR_PROB_BASE - probability));
942
943	  /* Use FP math to avoid overflows of 32bit integers.  */
944	  if (d == 0)
945	    /* If one probability is 0% and one 100%, avoid division by zero.  */
946	    combined_probability = REG_BR_PROB_BASE / 2;
947	  else
948	    combined_probability = (((double) combined_probability)
949				    * probability
950		    		    * REG_BR_PROB_BASE / d + 0.5);
951	}
952    }
953
954  /* Decide which heuristic to use.  In case we didn't match anything,
955     use no_prediction heuristic, in case we did match, use either
956     first match or Dempster-Shaffer theory depending on the flags.  */
957
958  if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
959    first_match = true;
960
961  if (!found)
962    dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
963  else
964    {
965      dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
966		       !first_match);
967      dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
968		       first_match);
969    }
970
971  if (first_match)
972    combined_probability = best_probability;
973  dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
974
975  if (preds)
976    {
977      for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
978	{
979	  enum br_predictor predictor = pred->ep_predictor;
980	  int probability = pred->ep_probability;
981
982	  if (pred->ep_edge != EDGE_SUCC (bb, 0))
983	    probability = REG_BR_PROB_BASE - probability;
984	  dump_prediction (dump_file, predictor, probability, bb,
985			   !first_match || best_predictor == predictor);
986	}
987    }
988  clear_bb_predictions (bb);
989
990  if (!bb->count)
991    {
992      first->probability = combined_probability;
993      second->probability = REG_BR_PROB_BASE - combined_probability;
994    }
995}
996
997/* Check if T1 and T2 satisfy the IV_COMPARE condition.
998   Return the SSA_NAME if the condition satisfies, NULL otherwise.
999
1000   T1 and T2 should be one of the following cases:
1001     1. T1 is SSA_NAME, T2 is NULL
1002     2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1003     3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4]  */
1004
1005static tree
1006strips_small_constant (tree t1, tree t2)
1007{
1008  tree ret = NULL;
1009  int value = 0;
1010
1011  if (!t1)
1012    return NULL;
1013  else if (TREE_CODE (t1) == SSA_NAME)
1014    ret = t1;
1015  else if (tree_fits_shwi_p (t1))
1016    value = tree_to_shwi (t1);
1017  else
1018    return NULL;
1019
1020  if (!t2)
1021    return ret;
1022  else if (tree_fits_shwi_p (t2))
1023    value = tree_to_shwi (t2);
1024  else if (TREE_CODE (t2) == SSA_NAME)
1025    {
1026      if (ret)
1027        return NULL;
1028      else
1029        ret = t2;
1030    }
1031
1032  if (value <= 4 && value >= -4)
1033    return ret;
1034  else
1035    return NULL;
1036}
1037
1038/* Return the SSA_NAME in T or T's operands.
1039   Return NULL if SSA_NAME cannot be found.  */
1040
1041static tree
1042get_base_value (tree t)
1043{
1044  if (TREE_CODE (t) == SSA_NAME)
1045    return t;
1046
1047  if (!BINARY_CLASS_P (t))
1048    return NULL;
1049
1050  switch (TREE_OPERAND_LENGTH (t))
1051    {
1052    case 1:
1053      return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1054    case 2:
1055      return strips_small_constant (TREE_OPERAND (t, 0),
1056				    TREE_OPERAND (t, 1));
1057    default:
1058      return NULL;
1059    }
1060}
1061
1062/* Check the compare STMT in LOOP. If it compares an induction
1063   variable to a loop invariant, return true, and save
1064   LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1065   Otherwise return false and set LOOP_INVAIANT to NULL.  */
1066
1067static bool
1068is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1069				     tree *loop_invariant,
1070				     enum tree_code *compare_code,
1071				     tree *loop_step,
1072				     tree *loop_iv_base)
1073{
1074  tree op0, op1, bound, base;
1075  affine_iv iv0, iv1;
1076  enum tree_code code;
1077  tree step;
1078
1079  code = gimple_cond_code (stmt);
1080  *loop_invariant = NULL;
1081
1082  switch (code)
1083    {
1084    case GT_EXPR:
1085    case GE_EXPR:
1086    case NE_EXPR:
1087    case LT_EXPR:
1088    case LE_EXPR:
1089    case EQ_EXPR:
1090      break;
1091
1092    default:
1093      return false;
1094    }
1095
1096  op0 = gimple_cond_lhs (stmt);
1097  op1 = gimple_cond_rhs (stmt);
1098
1099  if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1100       || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1101    return false;
1102  if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1103    return false;
1104  if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1105    return false;
1106  if (TREE_CODE (iv0.step) != INTEGER_CST
1107      || TREE_CODE (iv1.step) != INTEGER_CST)
1108    return false;
1109  if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1110      || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1111    return false;
1112
1113  if (integer_zerop (iv0.step))
1114    {
1115      if (code != NE_EXPR && code != EQ_EXPR)
1116	code = invert_tree_comparison (code, false);
1117      bound = iv0.base;
1118      base = iv1.base;
1119      if (tree_fits_shwi_p (iv1.step))
1120	step = iv1.step;
1121      else
1122	return false;
1123    }
1124  else
1125    {
1126      bound = iv1.base;
1127      base = iv0.base;
1128      if (tree_fits_shwi_p (iv0.step))
1129	step = iv0.step;
1130      else
1131	return false;
1132    }
1133
1134  if (TREE_CODE (bound) != INTEGER_CST)
1135    bound = get_base_value (bound);
1136  if (!bound)
1137    return false;
1138  if (TREE_CODE (base) != INTEGER_CST)
1139    base = get_base_value (base);
1140  if (!base)
1141    return false;
1142
1143  *loop_invariant = bound;
1144  *compare_code = code;
1145  *loop_step = step;
1146  *loop_iv_base = base;
1147  return true;
1148}
1149
1150/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.  */
1151
1152static bool
1153expr_coherent_p (tree t1, tree t2)
1154{
1155  gimple stmt;
1156  tree ssa_name_1 = NULL;
1157  tree ssa_name_2 = NULL;
1158
1159  gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1160  gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1161
1162  if (t1 == t2)
1163    return true;
1164
1165  if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1166    return true;
1167  if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1168    return false;
1169
1170  /* Check to see if t1 is expressed/defined with t2.  */
1171  stmt = SSA_NAME_DEF_STMT (t1);
1172  gcc_assert (stmt != NULL);
1173  if (is_gimple_assign (stmt))
1174    {
1175      ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1176      if (ssa_name_1 && ssa_name_1 == t2)
1177	return true;
1178    }
1179
1180  /* Check to see if t2 is expressed/defined with t1.  */
1181  stmt = SSA_NAME_DEF_STMT (t2);
1182  gcc_assert (stmt != NULL);
1183  if (is_gimple_assign (stmt))
1184    {
1185      ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1186      if (ssa_name_2 && ssa_name_2 == t1)
1187	return true;
1188    }
1189
1190  /* Compare if t1 and t2's def_stmts are identical.  */
1191  if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1192    return true;
1193  else
1194    return false;
1195}
1196
1197/* Predict branch probability of BB when BB contains a branch that compares
1198   an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1199   loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1200
1201   E.g.
1202     for (int i = 0; i < bound; i++) {
1203       if (i < bound - 2)
1204	 computation_1();
1205       else
1206	 computation_2();
1207     }
1208
1209  In this loop, we will predict the branch inside the loop to be taken.  */
1210
1211static void
1212predict_iv_comparison (struct loop *loop, basic_block bb,
1213		       tree loop_bound_var,
1214		       tree loop_iv_base_var,
1215		       enum tree_code loop_bound_code,
1216		       int loop_bound_step)
1217{
1218  gimple stmt;
1219  tree compare_var, compare_base;
1220  enum tree_code compare_code;
1221  tree compare_step_var;
1222  edge then_edge;
1223  edge_iterator ei;
1224
1225  if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1226      || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
1227      || predicted_by_p (bb, PRED_LOOP_EXIT))
1228    return;
1229
1230  stmt = last_stmt (bb);
1231  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1232    return;
1233  if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1234					    loop, &compare_var,
1235					    &compare_code,
1236					    &compare_step_var,
1237					    &compare_base))
1238    return;
1239
1240  /* Find the taken edge.  */
1241  FOR_EACH_EDGE (then_edge, ei, bb->succs)
1242    if (then_edge->flags & EDGE_TRUE_VALUE)
1243      break;
1244
1245  /* When comparing an IV to a loop invariant, NE is more likely to be
1246     taken while EQ is more likely to be not-taken.  */
1247  if (compare_code == NE_EXPR)
1248    {
1249      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1250      return;
1251    }
1252  else if (compare_code == EQ_EXPR)
1253    {
1254      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1255      return;
1256    }
1257
1258  if (!expr_coherent_p (loop_iv_base_var, compare_base))
1259    return;
1260
1261  /* If loop bound, base and compare bound are all constants, we can
1262     calculate the probability directly.  */
1263  if (tree_fits_shwi_p (loop_bound_var)
1264      && tree_fits_shwi_p (compare_var)
1265      && tree_fits_shwi_p (compare_base))
1266    {
1267      int probability;
1268      bool overflow, overall_overflow = false;
1269      widest_int compare_count, tem;
1270
1271      /* (loop_bound - base) / compare_step */
1272      tem = wi::sub (wi::to_widest (loop_bound_var),
1273		     wi::to_widest (compare_base), SIGNED, &overflow);
1274      overall_overflow |= overflow;
1275      widest_int loop_count = wi::div_trunc (tem,
1276					     wi::to_widest (compare_step_var),
1277					     SIGNED, &overflow);
1278      overall_overflow |= overflow;
1279
1280      if (!wi::neg_p (wi::to_widest (compare_step_var))
1281          ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1282	{
1283	  /* (loop_bound - compare_bound) / compare_step */
1284	  tem = wi::sub (wi::to_widest (loop_bound_var),
1285			 wi::to_widest (compare_var), SIGNED, &overflow);
1286	  overall_overflow |= overflow;
1287	  compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1288					 SIGNED, &overflow);
1289	  overall_overflow |= overflow;
1290	}
1291      else
1292        {
1293	  /* (compare_bound - base) / compare_step */
1294	  tem = wi::sub (wi::to_widest (compare_var),
1295			 wi::to_widest (compare_base), SIGNED, &overflow);
1296	  overall_overflow |= overflow;
1297          compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1298					 SIGNED, &overflow);
1299	  overall_overflow |= overflow;
1300	}
1301      if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1302	++compare_count;
1303      if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1304	++loop_count;
1305      if (wi::neg_p (compare_count))
1306        compare_count = 0;
1307      if (wi::neg_p (loop_count))
1308        loop_count = 0;
1309      if (loop_count == 0)
1310	probability = 0;
1311      else if (wi::cmps (compare_count, loop_count) == 1)
1312	probability = REG_BR_PROB_BASE;
1313      else
1314        {
1315	  tem = compare_count * REG_BR_PROB_BASE;
1316	  tem = wi::udiv_trunc (tem, loop_count);
1317	  probability = tem.to_uhwi ();
1318	}
1319
1320      if (!overall_overflow)
1321        predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1322
1323      return;
1324    }
1325
1326  if (expr_coherent_p (loop_bound_var, compare_var))
1327    {
1328      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1329	  && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1330	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1331      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1332	       && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1333	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1334      else if (loop_bound_code == NE_EXPR)
1335	{
1336	  /* If the loop backedge condition is "(i != bound)", we do
1337	     the comparison based on the step of IV:
1338	     * step < 0 : backedge condition is like (i > bound)
1339	     * step > 0 : backedge condition is like (i < bound)  */
1340	  gcc_assert (loop_bound_step != 0);
1341	  if (loop_bound_step > 0
1342	      && (compare_code == LT_EXPR
1343		  || compare_code == LE_EXPR))
1344	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1345	  else if (loop_bound_step < 0
1346		   && (compare_code == GT_EXPR
1347		       || compare_code == GE_EXPR))
1348	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1349	  else
1350	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1351	}
1352      else
1353	/* The branch is predicted not-taken if loop_bound_code is
1354	   opposite with compare_code.  */
1355	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1356    }
1357  else if (expr_coherent_p (loop_iv_base_var, compare_var))
1358    {
1359      /* For cases like:
1360	   for (i = s; i < h; i++)
1361	     if (i > s + 2) ....
1362	 The branch should be predicted taken.  */
1363      if (loop_bound_step > 0
1364	  && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1365	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1366      else if (loop_bound_step < 0
1367	       && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1368	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1369      else
1370	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1371    }
1372}
1373
1374/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1375   exits are resulted from short-circuit conditions that will generate an
1376   if_tmp. E.g.:
1377
1378   if (foo() || global > 10)
1379     break;
1380
1381   This will be translated into:
1382
1383   BB3:
1384     loop header...
1385   BB4:
1386     if foo() goto BB6 else goto BB5
1387   BB5:
1388     if global > 10 goto BB6 else goto BB7
1389   BB6:
1390     goto BB7
1391   BB7:
1392     iftmp = (PHI 0(BB5), 1(BB6))
1393     if iftmp == 1 goto BB8 else goto BB3
1394   BB8:
1395     outside of the loop...
1396
1397   The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1398   From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1399   exits. This function takes BB7->BB8 as input, and finds out the extra loop
1400   exits to predict them using PRED_LOOP_EXIT.  */
1401
1402static void
1403predict_extra_loop_exits (edge exit_edge)
1404{
1405  unsigned i;
1406  bool check_value_one;
1407  gimple lhs_def_stmt;
1408  gphi *phi_stmt;
1409  tree cmp_rhs, cmp_lhs;
1410  gimple last;
1411  gcond *cmp_stmt;
1412
1413  last = last_stmt (exit_edge->src);
1414  if (!last)
1415    return;
1416  cmp_stmt = dyn_cast <gcond *> (last);
1417  if (!cmp_stmt)
1418    return;
1419
1420  cmp_rhs = gimple_cond_rhs (cmp_stmt);
1421  cmp_lhs = gimple_cond_lhs (cmp_stmt);
1422  if (!TREE_CONSTANT (cmp_rhs)
1423      || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1424    return;
1425  if (TREE_CODE (cmp_lhs) != SSA_NAME)
1426    return;
1427
1428  /* If check_value_one is true, only the phi_args with value '1' will lead
1429     to loop exit. Otherwise, only the phi_args with value '0' will lead to
1430     loop exit.  */
1431  check_value_one = (((integer_onep (cmp_rhs))
1432		    ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1433		    ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1434
1435  lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1436  if (!lhs_def_stmt)
1437    return;
1438
1439  phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1440  if (!phi_stmt)
1441    return;
1442
1443  for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1444    {
1445      edge e1;
1446      edge_iterator ei;
1447      tree val = gimple_phi_arg_def (phi_stmt, i);
1448      edge e = gimple_phi_arg_edge (phi_stmt, i);
1449
1450      if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1451	continue;
1452      if ((check_value_one ^ integer_onep (val)) == 1)
1453	continue;
1454      if (EDGE_COUNT (e->src->succs) != 1)
1455	{
1456	  predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN);
1457	  continue;
1458	}
1459
1460      FOR_EACH_EDGE (e1, ei, e->src->preds)
1461	predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN);
1462    }
1463}
1464
1465/* Predict edge probabilities by exploiting loop structure.  */
1466
1467static void
1468predict_loops (void)
1469{
1470  struct loop *loop;
1471
1472  /* Try to predict out blocks in a loop that are not part of a
1473     natural loop.  */
1474  FOR_EACH_LOOP (loop, 0)
1475    {
1476      basic_block bb, *bbs;
1477      unsigned j, n_exits;
1478      vec<edge> exits;
1479      struct tree_niter_desc niter_desc;
1480      edge ex;
1481      struct nb_iter_bound *nb_iter;
1482      enum tree_code loop_bound_code = ERROR_MARK;
1483      tree loop_bound_step = NULL;
1484      tree loop_bound_var = NULL;
1485      tree loop_iv_base = NULL;
1486      gcond *stmt = NULL;
1487
1488      exits = get_loop_exit_edges (loop);
1489      n_exits = exits.length ();
1490      if (!n_exits)
1491	{
1492          exits.release ();
1493	  continue;
1494	}
1495
1496      FOR_EACH_VEC_ELT (exits, j, ex)
1497	{
1498	  tree niter = NULL;
1499	  HOST_WIDE_INT nitercst;
1500	  int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1501	  int probability;
1502	  enum br_predictor predictor;
1503
1504	  predict_extra_loop_exits (ex);
1505
1506	  if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1507	    niter = niter_desc.niter;
1508	  if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1509	    niter = loop_niter_by_eval (loop, ex);
1510
1511	  if (TREE_CODE (niter) == INTEGER_CST)
1512	    {
1513	      if (tree_fits_uhwi_p (niter)
1514		  && max
1515		  && compare_tree_int (niter, max - 1) == -1)
1516		nitercst = tree_to_uhwi (niter) + 1;
1517	      else
1518		nitercst = max;
1519	      predictor = PRED_LOOP_ITERATIONS;
1520	    }
1521	  /* If we have just one exit and we can derive some information about
1522	     the number of iterations of the loop from the statements inside
1523	     the loop, use it to predict this exit.  */
1524	  else if (n_exits == 1)
1525	    {
1526	      nitercst = estimated_stmt_executions_int (loop);
1527	      if (nitercst < 0)
1528		continue;
1529	      if (nitercst > max)
1530		nitercst = max;
1531
1532	      predictor = PRED_LOOP_ITERATIONS_GUESSED;
1533	    }
1534	  else
1535	    continue;
1536
1537	  /* If the prediction for number of iterations is zero, do not
1538	     predict the exit edges.  */
1539	  if (nitercst == 0)
1540	    continue;
1541
1542	  probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
1543	  predict_edge (ex, predictor, probability);
1544	}
1545      exits.release ();
1546
1547      /* Find information about loop bound variables.  */
1548      for (nb_iter = loop->bounds; nb_iter;
1549	   nb_iter = nb_iter->next)
1550	if (nb_iter->stmt
1551	    && gimple_code (nb_iter->stmt) == GIMPLE_COND)
1552	  {
1553	    stmt = as_a <gcond *> (nb_iter->stmt);
1554	    break;
1555	  }
1556      if (!stmt && last_stmt (loop->header)
1557	  && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
1558	stmt = as_a <gcond *> (last_stmt (loop->header));
1559      if (stmt)
1560	is_comparison_with_loop_invariant_p (stmt, loop,
1561					     &loop_bound_var,
1562					     &loop_bound_code,
1563					     &loop_bound_step,
1564					     &loop_iv_base);
1565
1566      bbs = get_loop_body (loop);
1567
1568      for (j = 0; j < loop->num_nodes; j++)
1569	{
1570	  int header_found = 0;
1571	  edge e;
1572	  edge_iterator ei;
1573
1574	  bb = bbs[j];
1575
1576	  /* Bypass loop heuristics on continue statement.  These
1577	     statements construct loops via "non-loop" constructs
1578	     in the source language and are better to be handled
1579	     separately.  */
1580	  if (predicted_by_p (bb, PRED_CONTINUE))
1581	    continue;
1582
1583	  /* Loop branch heuristics - predict an edge back to a
1584	     loop's head as taken.  */
1585	  if (bb == loop->latch)
1586	    {
1587	      e = find_edge (loop->latch, loop->header);
1588	      if (e)
1589		{
1590		  header_found = 1;
1591		  predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1592		}
1593	    }
1594
1595	  /* Loop exit heuristics - predict an edge exiting the loop if the
1596	     conditional has no loop header successors as not taken.  */
1597	  if (!header_found
1598	      /* If we already used more reliable loop exit predictors, do not
1599		 bother with PRED_LOOP_EXIT.  */
1600	      && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1601	      && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1602	    {
1603	      /* For loop with many exits we don't want to predict all exits
1604	         with the pretty large probability, because if all exits are
1605		 considered in row, the loop would be predicted to iterate
1606		 almost never.  The code to divide probability by number of
1607		 exits is very rough.  It should compute the number of exits
1608		 taken in each patch through function (not the overall number
1609		 of exits that might be a lot higher for loops with wide switch
1610		 statements in them) and compute n-th square root.
1611
1612		 We limit the minimal probability by 2% to avoid
1613		 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1614		 as this was causing regression in perl benchmark containing such
1615		 a wide loop.  */
1616
1617	      int probability = ((REG_BR_PROB_BASE
1618		                  - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1619				 / n_exits);
1620	      if (probability < HITRATE (2))
1621		probability = HITRATE (2);
1622	      FOR_EACH_EDGE (e, ei, bb->succs)
1623		if (e->dest->index < NUM_FIXED_BLOCKS
1624		    || !flow_bb_inside_loop_p (loop, e->dest))
1625		  predict_edge (e, PRED_LOOP_EXIT, probability);
1626	    }
1627	  if (loop_bound_var)
1628	    predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
1629				   loop_bound_code,
1630				   tree_to_shwi (loop_bound_step));
1631	}
1632
1633      /* Free basic blocks from get_loop_body.  */
1634      free (bbs);
1635    }
1636}
1637
1638/* Attempt to predict probabilities of BB outgoing edges using local
1639   properties.  */
1640static void
1641bb_estimate_probability_locally (basic_block bb)
1642{
1643  rtx_insn *last_insn = BB_END (bb);
1644  rtx cond;
1645
1646  if (! can_predict_insn_p (last_insn))
1647    return;
1648  cond = get_condition (last_insn, NULL, false, false);
1649  if (! cond)
1650    return;
1651
1652  /* Try "pointer heuristic."
1653     A comparison ptr == 0 is predicted as false.
1654     Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1655  if (COMPARISON_P (cond)
1656      && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1657	  || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1658    {
1659      if (GET_CODE (cond) == EQ)
1660	predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1661      else if (GET_CODE (cond) == NE)
1662	predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1663    }
1664  else
1665
1666  /* Try "opcode heuristic."
1667     EQ tests are usually false and NE tests are usually true. Also,
1668     most quantities are positive, so we can make the appropriate guesses
1669     about signed comparisons against zero.  */
1670    switch (GET_CODE (cond))
1671      {
1672      case CONST_INT:
1673	/* Unconditional branch.  */
1674	predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1675			  cond == const0_rtx ? NOT_TAKEN : TAKEN);
1676	break;
1677
1678      case EQ:
1679      case UNEQ:
1680	/* Floating point comparisons appears to behave in a very
1681	   unpredictable way because of special role of = tests in
1682	   FP code.  */
1683	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1684	  ;
1685	/* Comparisons with 0 are often used for booleans and there is
1686	   nothing useful to predict about them.  */
1687	else if (XEXP (cond, 1) == const0_rtx
1688		 || XEXP (cond, 0) == const0_rtx)
1689	  ;
1690	else
1691	  predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1692	break;
1693
1694      case NE:
1695      case LTGT:
1696	/* Floating point comparisons appears to behave in a very
1697	   unpredictable way because of special role of = tests in
1698	   FP code.  */
1699	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1700	  ;
1701	/* Comparisons with 0 are often used for booleans and there is
1702	   nothing useful to predict about them.  */
1703	else if (XEXP (cond, 1) == const0_rtx
1704		 || XEXP (cond, 0) == const0_rtx)
1705	  ;
1706	else
1707	  predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1708	break;
1709
1710      case ORDERED:
1711	predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1712	break;
1713
1714      case UNORDERED:
1715	predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1716	break;
1717
1718      case LE:
1719      case LT:
1720	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1721	    || XEXP (cond, 1) == constm1_rtx)
1722	  predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1723	break;
1724
1725      case GE:
1726      case GT:
1727	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1728	    || XEXP (cond, 1) == constm1_rtx)
1729	  predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1730	break;
1731
1732      default:
1733	break;
1734      }
1735}
1736
1737/* Set edge->probability for each successor edge of BB.  */
1738void
1739guess_outgoing_edge_probabilities (basic_block bb)
1740{
1741  bb_estimate_probability_locally (bb);
1742  combine_predictions_for_insn (BB_END (bb), bb);
1743}
1744
1745static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
1746
1747/* Helper function for expr_expected_value.  */
1748
1749static tree
1750expr_expected_value_1 (tree type, tree op0, enum tree_code code,
1751		       tree op1, bitmap visited, enum br_predictor *predictor)
1752{
1753  gimple def;
1754
1755  if (predictor)
1756    *predictor = PRED_UNCONDITIONAL;
1757
1758  if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1759    {
1760      if (TREE_CONSTANT (op0))
1761	return op0;
1762
1763      if (code != SSA_NAME)
1764	return NULL_TREE;
1765
1766      def = SSA_NAME_DEF_STMT (op0);
1767
1768      /* If we were already here, break the infinite cycle.  */
1769      if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1770	return NULL;
1771
1772      if (gimple_code (def) == GIMPLE_PHI)
1773	{
1774	  /* All the arguments of the PHI node must have the same constant
1775	     length.  */
1776	  int i, n = gimple_phi_num_args (def);
1777	  tree val = NULL, new_val;
1778
1779	  for (i = 0; i < n; i++)
1780	    {
1781	      tree arg = PHI_ARG_DEF (def, i);
1782	      enum br_predictor predictor2;
1783
1784	      /* If this PHI has itself as an argument, we cannot
1785		 determine the string length of this argument.  However,
1786		 if we can find an expected constant value for the other
1787		 PHI args then we can still be sure that this is
1788		 likely a constant.  So be optimistic and just
1789		 continue with the next argument.  */
1790	      if (arg == PHI_RESULT (def))
1791		continue;
1792
1793	      new_val = expr_expected_value (arg, visited, &predictor2);
1794
1795	      /* It is difficult to combine value predictors.  Simply assume
1796		 that later predictor is weaker and take its prediction.  */
1797	      if (predictor && *predictor < predictor2)
1798		*predictor = predictor2;
1799	      if (!new_val)
1800		return NULL;
1801	      if (!val)
1802		val = new_val;
1803	      else if (!operand_equal_p (val, new_val, false))
1804		return NULL;
1805	    }
1806	  return val;
1807	}
1808      if (is_gimple_assign (def))
1809	{
1810	  if (gimple_assign_lhs (def) != op0)
1811	    return NULL;
1812
1813	  return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1814					gimple_assign_rhs1 (def),
1815					gimple_assign_rhs_code (def),
1816					gimple_assign_rhs2 (def),
1817					visited, predictor);
1818	}
1819
1820      if (is_gimple_call (def))
1821	{
1822	  tree decl = gimple_call_fndecl (def);
1823	  if (!decl)
1824	    {
1825	      if (gimple_call_internal_p (def)
1826		  && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
1827		{
1828		  gcc_assert (gimple_call_num_args (def) == 3);
1829		  tree val = gimple_call_arg (def, 0);
1830		  if (TREE_CONSTANT (val))
1831		    return val;
1832		  if (predictor)
1833		    {
1834		      tree val2 = gimple_call_arg (def, 2);
1835		      gcc_assert (TREE_CODE (val2) == INTEGER_CST
1836				  && tree_fits_uhwi_p (val2)
1837				  && tree_to_uhwi (val2) < END_PREDICTORS);
1838		      *predictor = (enum br_predictor) tree_to_uhwi (val2);
1839		    }
1840		  return gimple_call_arg (def, 1);
1841		}
1842	      return NULL;
1843	    }
1844	  if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1845	    switch (DECL_FUNCTION_CODE (decl))
1846	      {
1847	      case BUILT_IN_EXPECT:
1848		{
1849		  tree val;
1850		  if (gimple_call_num_args (def) != 2)
1851		    return NULL;
1852		  val = gimple_call_arg (def, 0);
1853		  if (TREE_CONSTANT (val))
1854		    return val;
1855		  if (predictor)
1856		    *predictor = PRED_BUILTIN_EXPECT;
1857		  return gimple_call_arg (def, 1);
1858		}
1859
1860	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
1861	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
1862	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
1863	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
1864	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
1865	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
1866	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
1867	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
1868	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
1869	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
1870	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
1871	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
1872	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
1873		/* Assume that any given atomic operation has low contention,
1874		   and thus the compare-and-swap operation succeeds.  */
1875		if (predictor)
1876		  *predictor = PRED_COMPARE_AND_SWAP;
1877		return boolean_true_node;
1878	      default:
1879		break;
1880	    }
1881	}
1882
1883      return NULL;
1884    }
1885
1886  if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1887    {
1888      tree res;
1889      enum br_predictor predictor2;
1890      op0 = expr_expected_value (op0, visited, predictor);
1891      if (!op0)
1892	return NULL;
1893      op1 = expr_expected_value (op1, visited, &predictor2);
1894      if (predictor && *predictor < predictor2)
1895	*predictor = predictor2;
1896      if (!op1)
1897	return NULL;
1898      res = fold_build2 (code, type, op0, op1);
1899      if (TREE_CONSTANT (res))
1900	return res;
1901      return NULL;
1902    }
1903  if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1904    {
1905      tree res;
1906      op0 = expr_expected_value (op0, visited, predictor);
1907      if (!op0)
1908	return NULL;
1909      res = fold_build1 (code, type, op0);
1910      if (TREE_CONSTANT (res))
1911	return res;
1912      return NULL;
1913    }
1914  return NULL;
1915}
1916
1917/* Return constant EXPR will likely have at execution time, NULL if unknown.
1918   The function is used by builtin_expect branch predictor so the evidence
1919   must come from this construct and additional possible constant folding.
1920
1921   We may want to implement more involved value guess (such as value range
1922   propagation based prediction), but such tricks shall go to new
1923   implementation.  */
1924
1925static tree
1926expr_expected_value (tree expr, bitmap visited,
1927		     enum br_predictor *predictor)
1928{
1929  enum tree_code code;
1930  tree op0, op1;
1931
1932  if (TREE_CONSTANT (expr))
1933    {
1934      if (predictor)
1935	*predictor = PRED_UNCONDITIONAL;
1936      return expr;
1937    }
1938
1939  extract_ops_from_tree (expr, &code, &op0, &op1);
1940  return expr_expected_value_1 (TREE_TYPE (expr),
1941				op0, code, op1, visited, predictor);
1942}
1943
1944/* Predict using opcode of the last statement in basic block.  */
1945static void
1946tree_predict_by_opcode (basic_block bb)
1947{
1948  gimple stmt = last_stmt (bb);
1949  edge then_edge;
1950  tree op0, op1;
1951  tree type;
1952  tree val;
1953  enum tree_code cmp;
1954  bitmap visited;
1955  edge_iterator ei;
1956  enum br_predictor predictor;
1957
1958  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1959    return;
1960  FOR_EACH_EDGE (then_edge, ei, bb->succs)
1961    if (then_edge->flags & EDGE_TRUE_VALUE)
1962      break;
1963  op0 = gimple_cond_lhs (stmt);
1964  op1 = gimple_cond_rhs (stmt);
1965  cmp = gimple_cond_code (stmt);
1966  type = TREE_TYPE (op0);
1967  visited = BITMAP_ALLOC (NULL);
1968  val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited,
1969			       &predictor);
1970  BITMAP_FREE (visited);
1971  if (val && TREE_CODE (val) == INTEGER_CST)
1972    {
1973      if (predictor == PRED_BUILTIN_EXPECT)
1974	{
1975	  int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
1976
1977	  gcc_assert (percent >= 0 && percent <= 100);
1978	  if (integer_zerop (val))
1979	    percent = 100 - percent;
1980	  predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
1981	}
1982      else
1983	predict_edge (then_edge, predictor,
1984		      integer_zerop (val) ? NOT_TAKEN : TAKEN);
1985    }
1986  /* Try "pointer heuristic."
1987     A comparison ptr == 0 is predicted as false.
1988     Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1989  if (POINTER_TYPE_P (type))
1990    {
1991      if (cmp == EQ_EXPR)
1992	predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1993      else if (cmp == NE_EXPR)
1994	predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1995    }
1996  else
1997
1998  /* Try "opcode heuristic."
1999     EQ tests are usually false and NE tests are usually true. Also,
2000     most quantities are positive, so we can make the appropriate guesses
2001     about signed comparisons against zero.  */
2002    switch (cmp)
2003      {
2004      case EQ_EXPR:
2005      case UNEQ_EXPR:
2006	/* Floating point comparisons appears to behave in a very
2007	   unpredictable way because of special role of = tests in
2008	   FP code.  */
2009	if (FLOAT_TYPE_P (type))
2010	  ;
2011	/* Comparisons with 0 are often used for booleans and there is
2012	   nothing useful to predict about them.  */
2013	else if (integer_zerop (op0) || integer_zerop (op1))
2014	  ;
2015	else
2016	  predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2017	break;
2018
2019      case NE_EXPR:
2020      case LTGT_EXPR:
2021	/* Floating point comparisons appears to behave in a very
2022	   unpredictable way because of special role of = tests in
2023	   FP code.  */
2024	if (FLOAT_TYPE_P (type))
2025	  ;
2026	/* Comparisons with 0 are often used for booleans and there is
2027	   nothing useful to predict about them.  */
2028	else if (integer_zerop (op0)
2029		 || integer_zerop (op1))
2030	  ;
2031	else
2032	  predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2033	break;
2034
2035      case ORDERED_EXPR:
2036	predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2037	break;
2038
2039      case UNORDERED_EXPR:
2040	predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2041	break;
2042
2043      case LE_EXPR:
2044      case LT_EXPR:
2045	if (integer_zerop (op1)
2046	    || integer_onep (op1)
2047	    || integer_all_onesp (op1)
2048	    || real_zerop (op1)
2049	    || real_onep (op1)
2050	    || real_minus_onep (op1))
2051	  predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2052	break;
2053
2054      case GE_EXPR:
2055      case GT_EXPR:
2056	if (integer_zerop (op1)
2057	    || integer_onep (op1)
2058	    || integer_all_onesp (op1)
2059	    || real_zerop (op1)
2060	    || real_onep (op1)
2061	    || real_minus_onep (op1))
2062	  predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2063	break;
2064
2065      default:
2066	break;
2067      }
2068}
2069
2070/* Try to guess whether the value of return means error code.  */
2071
2072static enum br_predictor
2073return_prediction (tree val, enum prediction *prediction)
2074{
2075  /* VOID.  */
2076  if (!val)
2077    return PRED_NO_PREDICTION;
2078  /* Different heuristics for pointers and scalars.  */
2079  if (POINTER_TYPE_P (TREE_TYPE (val)))
2080    {
2081      /* NULL is usually not returned.  */
2082      if (integer_zerop (val))
2083	{
2084	  *prediction = NOT_TAKEN;
2085	  return PRED_NULL_RETURN;
2086	}
2087    }
2088  else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2089    {
2090      /* Negative return values are often used to indicate
2091         errors.  */
2092      if (TREE_CODE (val) == INTEGER_CST
2093	  && tree_int_cst_sgn (val) < 0)
2094	{
2095	  *prediction = NOT_TAKEN;
2096	  return PRED_NEGATIVE_RETURN;
2097	}
2098      /* Constant return values seems to be commonly taken.
2099         Zero/one often represent booleans so exclude them from the
2100	 heuristics.  */
2101      if (TREE_CONSTANT (val)
2102	  && (!integer_zerop (val) && !integer_onep (val)))
2103	{
2104	  *prediction = TAKEN;
2105	  return PRED_CONST_RETURN;
2106	}
2107    }
2108  return PRED_NO_PREDICTION;
2109}
2110
2111/* Find the basic block with return expression and look up for possible
2112   return value trying to apply RETURN_PREDICTION heuristics.  */
2113static void
2114apply_return_prediction (void)
2115{
2116  greturn *return_stmt = NULL;
2117  tree return_val;
2118  edge e;
2119  gphi *phi;
2120  int phi_num_args, i;
2121  enum br_predictor pred;
2122  enum prediction direction;
2123  edge_iterator ei;
2124
2125  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2126    {
2127      gimple last = last_stmt (e->src);
2128      if (last
2129	  && gimple_code (last) == GIMPLE_RETURN)
2130	{
2131	  return_stmt = as_a <greturn *> (last);
2132	  break;
2133	}
2134    }
2135  if (!e)
2136    return;
2137  return_val = gimple_return_retval (return_stmt);
2138  if (!return_val)
2139    return;
2140  if (TREE_CODE (return_val) != SSA_NAME
2141      || !SSA_NAME_DEF_STMT (return_val)
2142      || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2143    return;
2144  phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2145  phi_num_args = gimple_phi_num_args (phi);
2146  pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2147
2148  /* Avoid the degenerate case where all return values form the function
2149     belongs to same category (ie they are all positive constants)
2150     so we can hardly say something about them.  */
2151  for (i = 1; i < phi_num_args; i++)
2152    if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2153      break;
2154  if (i != phi_num_args)
2155    for (i = 0; i < phi_num_args; i++)
2156      {
2157	pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2158	if (pred != PRED_NO_PREDICTION)
2159	  predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2160				         direction);
2161      }
2162}
2163
2164/* Look for basic block that contains unlikely to happen events
2165   (such as noreturn calls) and mark all paths leading to execution
2166   of this basic blocks as unlikely.  */
2167
2168static void
2169tree_bb_level_predictions (void)
2170{
2171  basic_block bb;
2172  bool has_return_edges = false;
2173  edge e;
2174  edge_iterator ei;
2175
2176  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2177    if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
2178      {
2179        has_return_edges = true;
2180	break;
2181      }
2182
2183  apply_return_prediction ();
2184
2185  FOR_EACH_BB_FN (bb, cfun)
2186    {
2187      gimple_stmt_iterator gsi;
2188
2189      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2190	{
2191	  gimple stmt = gsi_stmt (gsi);
2192	  tree decl;
2193
2194	  if (is_gimple_call (stmt))
2195	    {
2196	      if ((gimple_call_flags (stmt) & ECF_NORETURN)
2197	          && has_return_edges)
2198		predict_paths_leading_to (bb, PRED_NORETURN,
2199					  NOT_TAKEN);
2200	      decl = gimple_call_fndecl (stmt);
2201	      if (decl
2202		  && lookup_attribute ("cold",
2203				       DECL_ATTRIBUTES (decl)))
2204		predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2205					  NOT_TAKEN);
2206	    }
2207	  else if (gimple_code (stmt) == GIMPLE_PREDICT)
2208	    {
2209	      predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2210					gimple_predict_outcome (stmt));
2211	      /* Keep GIMPLE_PREDICT around so early inlining will propagate
2212	         hints to callers.  */
2213	    }
2214	}
2215    }
2216}
2217
2218#ifdef ENABLE_CHECKING
2219
2220/* Callback for hash_map::traverse, asserts that the pointer map is
2221   empty.  */
2222
2223bool
2224assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2225		 void *)
2226{
2227  gcc_assert (!value);
2228  return false;
2229}
2230#endif
2231
2232/* Predict branch probabilities and estimate profile for basic block BB.  */
2233
2234static void
2235tree_estimate_probability_bb (basic_block bb)
2236{
2237  edge e;
2238  edge_iterator ei;
2239  gimple last;
2240
2241  FOR_EACH_EDGE (e, ei, bb->succs)
2242    {
2243      /* Predict edges to user labels with attributes.  */
2244      if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2245	{
2246	  gimple_stmt_iterator gi;
2247	  for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
2248	    {
2249	      glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
2250	      tree decl;
2251
2252	      if (!label_stmt)
2253		break;
2254	      decl = gimple_label_label (label_stmt);
2255	      if (DECL_ARTIFICIAL (decl))
2256		continue;
2257
2258	      /* Finally, we have a user-defined label.  */
2259	      if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
2260		predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
2261	      else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
2262		predict_edge_def (e, PRED_HOT_LABEL, TAKEN);
2263	    }
2264	}
2265
2266      /* Predict early returns to be probable, as we've already taken
2267	 care for error returns and other cases are often used for
2268	 fast paths through function.
2269
2270	 Since we've already removed the return statements, we are
2271	 looking for CFG like:
2272
2273	 if (conditional)
2274	 {
2275	 ..
2276	 goto return_block
2277	 }
2278	 some other blocks
2279	 return_block:
2280	 return_stmt.  */
2281      if (e->dest != bb->next_bb
2282	  && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2283	  && single_succ_p (e->dest)
2284	  && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2285	  && (last = last_stmt (e->dest)) != NULL
2286	  && gimple_code (last) == GIMPLE_RETURN)
2287	{
2288	  edge e1;
2289	  edge_iterator ei1;
2290
2291	  if (single_succ_p (bb))
2292	    {
2293	      FOR_EACH_EDGE (e1, ei1, bb->preds)
2294		if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
2295		    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
2296		    && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
2297		  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2298	    }
2299	  else
2300	    if (!predicted_by_p (e->src, PRED_NULL_RETURN)
2301		&& !predicted_by_p (e->src, PRED_CONST_RETURN)
2302		&& !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
2303	      predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2304	}
2305
2306      /* Look for block we are guarding (ie we dominate it,
2307	 but it doesn't postdominate us).  */
2308      if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2309	  && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2310	  && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2311	{
2312	  gimple_stmt_iterator bi;
2313
2314	  /* The call heuristic claims that a guarded function call
2315	     is improbable.  This is because such calls are often used
2316	     to signal exceptional situations such as printing error
2317	     messages.  */
2318	  for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2319	       gsi_next (&bi))
2320	    {
2321	      gimple stmt = gsi_stmt (bi);
2322	      if (is_gimple_call (stmt)
2323		  /* Constant and pure calls are hardly used to signalize
2324		     something exceptional.  */
2325		  && gimple_has_side_effects (stmt))
2326		{
2327		  predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2328		  break;
2329		}
2330	    }
2331	}
2332    }
2333  tree_predict_by_opcode (bb);
2334}
2335
2336/* Predict branch probabilities and estimate profile of the tree CFG.
2337   This function can be called from the loop optimizers to recompute
2338   the profile information.  */
2339
2340void
2341tree_estimate_probability (void)
2342{
2343  basic_block bb;
2344
2345  add_noreturn_fake_exit_edges ();
2346  connect_infinite_loops_to_exit ();
2347  /* We use loop_niter_by_eval, which requires that the loops have
2348     preheaders.  */
2349  create_preheaders (CP_SIMPLE_PREHEADERS);
2350  calculate_dominance_info (CDI_POST_DOMINATORS);
2351
2352  bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2353  tree_bb_level_predictions ();
2354  record_loop_exits ();
2355
2356  if (number_of_loops (cfun) > 1)
2357    predict_loops ();
2358
2359  FOR_EACH_BB_FN (bb, cfun)
2360    tree_estimate_probability_bb (bb);
2361
2362  FOR_EACH_BB_FN (bb, cfun)
2363    combine_predictions_for_bb (bb);
2364
2365#ifdef ENABLE_CHECKING
2366  bb_predictions->traverse<void *, assert_is_empty> (NULL);
2367#endif
2368  delete bb_predictions;
2369  bb_predictions = NULL;
2370
2371  estimate_bb_frequencies (false);
2372  free_dominance_info (CDI_POST_DOMINATORS);
2373  remove_fake_exit_edges ();
2374}
2375
2376/* Predict edges to successors of CUR whose sources are not postdominated by
2377   BB by PRED and recurse to all postdominators.  */
2378
2379static void
2380predict_paths_for_bb (basic_block cur, basic_block bb,
2381		      enum br_predictor pred,
2382		      enum prediction taken,
2383		      bitmap visited)
2384{
2385  edge e;
2386  edge_iterator ei;
2387  basic_block son;
2388
2389  /* We are looking for all edges forming edge cut induced by
2390     set of all blocks postdominated by BB.  */
2391  FOR_EACH_EDGE (e, ei, cur->preds)
2392    if (e->src->index >= NUM_FIXED_BLOCKS
2393	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2394    {
2395      edge e2;
2396      edge_iterator ei2;
2397      bool found = false;
2398
2399      /* Ignore fake edges and eh, we predict them as not taken anyway.  */
2400      if (e->flags & (EDGE_EH | EDGE_FAKE))
2401	continue;
2402      gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2403
2404      /* See if there is an edge from e->src that is not abnormal
2405	 and does not lead to BB.  */
2406      FOR_EACH_EDGE (e2, ei2, e->src->succs)
2407	if (e2 != e
2408	    && !(e2->flags & (EDGE_EH | EDGE_FAKE))
2409	    && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
2410	  {
2411	    found = true;
2412	    break;
2413	  }
2414
2415      /* If there is non-abnormal path leaving e->src, predict edge
2416	 using predictor.  Otherwise we need to look for paths
2417	 leading to e->src.
2418
2419	 The second may lead to infinite loop in the case we are predicitng
2420	 regions that are only reachable by abnormal edges.  We simply
2421	 prevent visiting given BB twice.  */
2422      if (found)
2423        predict_edge_def (e, pred, taken);
2424      else if (bitmap_set_bit (visited, e->src->index))
2425	predict_paths_for_bb (e->src, e->src, pred, taken, visited);
2426    }
2427  for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
2428       son;
2429       son = next_dom_son (CDI_POST_DOMINATORS, son))
2430    predict_paths_for_bb (son, bb, pred, taken, visited);
2431}
2432
2433/* Sets branch probabilities according to PREDiction and
2434   FLAGS.  */
2435
2436static void
2437predict_paths_leading_to (basic_block bb, enum br_predictor pred,
2438			  enum prediction taken)
2439{
2440  bitmap visited = BITMAP_ALLOC (NULL);
2441  predict_paths_for_bb (bb, bb, pred, taken, visited);
2442  BITMAP_FREE (visited);
2443}
2444
2445/* Like predict_paths_leading_to but take edge instead of basic block.  */
2446
2447static void
2448predict_paths_leading_to_edge (edge e, enum br_predictor pred,
2449			       enum prediction taken)
2450{
2451  bool has_nonloop_edge = false;
2452  edge_iterator ei;
2453  edge e2;
2454
2455  basic_block bb = e->src;
2456  FOR_EACH_EDGE (e2, ei, bb->succs)
2457    if (e2->dest != e->src && e2->dest != e->dest
2458	&& !(e->flags & (EDGE_EH | EDGE_FAKE))
2459	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
2460      {
2461	has_nonloop_edge = true;
2462	break;
2463      }
2464  if (!has_nonloop_edge)
2465    {
2466      bitmap visited = BITMAP_ALLOC (NULL);
2467      predict_paths_for_bb (bb, bb, pred, taken, visited);
2468      BITMAP_FREE (visited);
2469    }
2470  else
2471    predict_edge_def (e, pred, taken);
2472}
2473
2474/* This is used to carry information about basic blocks.  It is
2475   attached to the AUX field of the standard CFG block.  */
2476
2477struct block_info
2478{
2479  /* Estimated frequency of execution of basic_block.  */
2480  sreal frequency;
2481
2482  /* To keep queue of basic blocks to process.  */
2483  basic_block next;
2484
2485  /* Number of predecessors we need to visit first.  */
2486  int npredecessors;
2487};
2488
2489/* Similar information for edges.  */
2490struct edge_prob_info
2491{
2492  /* In case edge is a loopback edge, the probability edge will be reached
2493     in case header is.  Estimated number of iterations of the loop can be
2494     then computed as 1 / (1 - back_edge_prob).  */
2495  sreal back_edge_prob;
2496  /* True if the edge is a loopback edge in the natural loop.  */
2497  unsigned int back_edge:1;
2498};
2499
2500#define BLOCK_INFO(B)	((block_info *) (B)->aux)
2501#undef EDGE_INFO
2502#define EDGE_INFO(E)	((edge_prob_info *) (E)->aux)
2503
2504/* Helper function for estimate_bb_frequencies.
2505   Propagate the frequencies in blocks marked in
2506   TOVISIT, starting in HEAD.  */
2507
2508static void
2509propagate_freq (basic_block head, bitmap tovisit)
2510{
2511  basic_block bb;
2512  basic_block last;
2513  unsigned i;
2514  edge e;
2515  basic_block nextbb;
2516  bitmap_iterator bi;
2517
2518  /* For each basic block we need to visit count number of his predecessors
2519     we need to visit first.  */
2520  EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
2521    {
2522      edge_iterator ei;
2523      int count = 0;
2524
2525      bb = BASIC_BLOCK_FOR_FN (cfun, i);
2526
2527      FOR_EACH_EDGE (e, ei, bb->preds)
2528	{
2529	  bool visit = bitmap_bit_p (tovisit, e->src->index);
2530
2531	  if (visit && !(e->flags & EDGE_DFS_BACK))
2532	    count++;
2533	  else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
2534	    fprintf (dump_file,
2535		     "Irreducible region hit, ignoring edge to %i->%i\n",
2536		     e->src->index, bb->index);
2537	}
2538      BLOCK_INFO (bb)->npredecessors = count;
2539      /* When function never returns, we will never process exit block.  */
2540      if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2541	bb->count = bb->frequency = 0;
2542    }
2543
2544  BLOCK_INFO (head)->frequency = 1;
2545  last = head;
2546  for (bb = head; bb; bb = nextbb)
2547    {
2548      edge_iterator ei;
2549      sreal cyclic_probability = 0;
2550      sreal frequency = 0;
2551
2552      nextbb = BLOCK_INFO (bb)->next;
2553      BLOCK_INFO (bb)->next = NULL;
2554
2555      /* Compute frequency of basic block.  */
2556      if (bb != head)
2557	{
2558#ifdef ENABLE_CHECKING
2559	  FOR_EACH_EDGE (e, ei, bb->preds)
2560	    gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
2561			|| (e->flags & EDGE_DFS_BACK));
2562#endif
2563
2564	  FOR_EACH_EDGE (e, ei, bb->preds)
2565	    if (EDGE_INFO (e)->back_edge)
2566	      {
2567		cyclic_probability += EDGE_INFO (e)->back_edge_prob;
2568	      }
2569	    else if (!(e->flags & EDGE_DFS_BACK))
2570	      {
2571		/*  frequency += (e->probability
2572				  * BLOCK_INFO (e->src)->frequency /
2573				  REG_BR_PROB_BASE);  */
2574
2575		sreal tmp = e->probability;
2576		tmp *= BLOCK_INFO (e->src)->frequency;
2577		tmp *= real_inv_br_prob_base;
2578		frequency += tmp;
2579	      }
2580
2581	  if (cyclic_probability == 0)
2582	    {
2583	      BLOCK_INFO (bb)->frequency = frequency;
2584	    }
2585	  else
2586	    {
2587	      if (cyclic_probability > real_almost_one)
2588		cyclic_probability = real_almost_one;
2589
2590	      /* BLOCK_INFO (bb)->frequency = frequency
2591					      / (1 - cyclic_probability) */
2592
2593	      cyclic_probability = sreal (1) - cyclic_probability;
2594	      BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
2595	    }
2596	}
2597
2598      bitmap_clear_bit (tovisit, bb->index);
2599
2600      e = find_edge (bb, head);
2601      if (e)
2602	{
2603	  /* EDGE_INFO (e)->back_edge_prob
2604	     = ((e->probability * BLOCK_INFO (bb)->frequency)
2605	     / REG_BR_PROB_BASE); */
2606
2607	  sreal tmp = e->probability;
2608	  tmp *= BLOCK_INFO (bb)->frequency;
2609	  EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
2610	}
2611
2612      /* Propagate to successor blocks.  */
2613      FOR_EACH_EDGE (e, ei, bb->succs)
2614	if (!(e->flags & EDGE_DFS_BACK)
2615	    && BLOCK_INFO (e->dest)->npredecessors)
2616	  {
2617	    BLOCK_INFO (e->dest)->npredecessors--;
2618	    if (!BLOCK_INFO (e->dest)->npredecessors)
2619	      {
2620		if (!nextbb)
2621		  nextbb = e->dest;
2622		else
2623		  BLOCK_INFO (last)->next = e->dest;
2624
2625		last = e->dest;
2626	      }
2627	  }
2628    }
2629}
2630
2631/* Estimate frequencies in loops at same nest level.  */
2632
2633static void
2634estimate_loops_at_level (struct loop *first_loop)
2635{
2636  struct loop *loop;
2637
2638  for (loop = first_loop; loop; loop = loop->next)
2639    {
2640      edge e;
2641      basic_block *bbs;
2642      unsigned i;
2643      bitmap tovisit = BITMAP_ALLOC (NULL);
2644
2645      estimate_loops_at_level (loop->inner);
2646
2647      /* Find current loop back edge and mark it.  */
2648      e = loop_latch_edge (loop);
2649      EDGE_INFO (e)->back_edge = 1;
2650
2651      bbs = get_loop_body (loop);
2652      for (i = 0; i < loop->num_nodes; i++)
2653	bitmap_set_bit (tovisit, bbs[i]->index);
2654      free (bbs);
2655      propagate_freq (loop->header, tovisit);
2656      BITMAP_FREE (tovisit);
2657    }
2658}
2659
2660/* Propagates frequencies through structure of loops.  */
2661
2662static void
2663estimate_loops (void)
2664{
2665  bitmap tovisit = BITMAP_ALLOC (NULL);
2666  basic_block bb;
2667
2668  /* Start by estimating the frequencies in the loops.  */
2669  if (number_of_loops (cfun) > 1)
2670    estimate_loops_at_level (current_loops->tree_root->inner);
2671
2672  /* Now propagate the frequencies through all the blocks.  */
2673  FOR_ALL_BB_FN (bb, cfun)
2674    {
2675      bitmap_set_bit (tovisit, bb->index);
2676    }
2677  propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
2678  BITMAP_FREE (tovisit);
2679}
2680
2681/* Drop the profile for NODE to guessed, and update its frequency based on
2682   whether it is expected to be hot given the CALL_COUNT.  */
2683
2684static void
2685drop_profile (struct cgraph_node *node, gcov_type call_count)
2686{
2687  struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
2688  /* In the case where this was called by another function with a
2689     dropped profile, call_count will be 0. Since there are no
2690     non-zero call counts to this function, we don't know for sure
2691     whether it is hot, and therefore it will be marked normal below.  */
2692  bool hot = maybe_hot_count_p (NULL, call_count);
2693
2694  if (dump_file)
2695    fprintf (dump_file,
2696             "Dropping 0 profile for %s/%i. %s based on calls.\n",
2697             node->name (), node->order,
2698             hot ? "Function is hot" : "Function is normal");
2699  /* We only expect to miss profiles for functions that are reached
2700     via non-zero call edges in cases where the function may have
2701     been linked from another module or library (COMDATs and extern
2702     templates). See the comments below for handle_missing_profiles.
2703     Also, only warn in cases where the missing counts exceed the
2704     number of training runs. In certain cases with an execv followed
2705     by a no-return call the profile for the no-return call is not
2706     dumped and there can be a mismatch.  */
2707  if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
2708      && call_count > profile_info->runs)
2709    {
2710      if (flag_profile_correction)
2711        {
2712          if (dump_file)
2713            fprintf (dump_file,
2714                     "Missing counts for called function %s/%i\n",
2715                     node->name (), node->order);
2716        }
2717      else
2718        warning (0, "Missing counts for called function %s/%i",
2719                 node->name (), node->order);
2720    }
2721
2722  profile_status_for_fn (fn)
2723      = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
2724  node->frequency
2725      = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
2726}
2727
2728/* In the case of COMDAT routines, multiple object files will contain the same
2729   function and the linker will select one for the binary. In that case
2730   all the other copies from the profile instrument binary will be missing
2731   profile counts. Look for cases where this happened, due to non-zero
2732   call counts going to 0-count functions, and drop the profile to guessed
2733   so that we can use the estimated probabilities and avoid optimizing only
2734   for size.
2735
2736   The other case where the profile may be missing is when the routine
2737   is not going to be emitted to the object file, e.g. for "extern template"
2738   class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2739   all other cases of non-zero calls to 0-count functions.  */
2740
2741void
2742handle_missing_profiles (void)
2743{
2744  struct cgraph_node *node;
2745  int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
2746  vec<struct cgraph_node *> worklist;
2747  worklist.create (64);
2748
2749  /* See if 0 count function has non-0 count callers.  In this case we
2750     lost some profile.  Drop its function profile to PROFILE_GUESSED.  */
2751  FOR_EACH_DEFINED_FUNCTION (node)
2752    {
2753      struct cgraph_edge *e;
2754      gcov_type call_count = 0;
2755      gcov_type max_tp_first_run = 0;
2756      struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
2757
2758      if (node->count)
2759        continue;
2760      for (e = node->callers; e; e = e->next_caller)
2761      {
2762        call_count += e->count;
2763
2764	if (e->caller->tp_first_run > max_tp_first_run)
2765	  max_tp_first_run = e->caller->tp_first_run;
2766      }
2767
2768      /* If time profile is missing, let assign the maximum that comes from
2769	 caller functions.  */
2770      if (!node->tp_first_run && max_tp_first_run)
2771	node->tp_first_run = max_tp_first_run + 1;
2772
2773      if (call_count
2774          && fn && fn->cfg
2775          && (call_count * unlikely_count_fraction >= profile_info->runs))
2776        {
2777          drop_profile (node, call_count);
2778          worklist.safe_push (node);
2779        }
2780    }
2781
2782  /* Propagate the profile dropping to other 0-count COMDATs that are
2783     potentially called by COMDATs we already dropped the profile on.  */
2784  while (worklist.length () > 0)
2785    {
2786      struct cgraph_edge *e;
2787
2788      node = worklist.pop ();
2789      for (e = node->callees; e; e = e->next_caller)
2790        {
2791          struct cgraph_node *callee = e->callee;
2792          struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
2793
2794          if (callee->count > 0)
2795            continue;
2796          if (DECL_COMDAT (callee->decl) && fn && fn->cfg
2797              && profile_status_for_fn (fn) == PROFILE_READ)
2798            {
2799              drop_profile (node, 0);
2800              worklist.safe_push (callee);
2801            }
2802        }
2803    }
2804  worklist.release ();
2805}
2806
2807/* Convert counts measured by profile driven feedback to frequencies.
2808   Return nonzero iff there was any nonzero execution count.  */
2809
2810int
2811counts_to_freqs (void)
2812{
2813  gcov_type count_max, true_count_max = 0;
2814  basic_block bb;
2815
2816  /* Don't overwrite the estimated frequencies when the profile for
2817     the function is missing.  We may drop this function PROFILE_GUESSED
2818     later in drop_profile ().  */
2819  if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
2820    return 0;
2821
2822  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2823    true_count_max = MAX (bb->count, true_count_max);
2824
2825  count_max = MAX (true_count_max, 1);
2826  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2827    bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2828
2829  return true_count_max;
2830}
2831
2832/* Return true if function is likely to be expensive, so there is no point to
2833   optimize performance of prologue, epilogue or do inlining at the expense
2834   of code size growth.  THRESHOLD is the limit of number of instructions
2835   function can execute at average to be still considered not expensive.  */
2836
2837bool
2838expensive_function_p (int threshold)
2839{
2840  unsigned int sum = 0;
2841  basic_block bb;
2842  unsigned int limit;
2843
2844  /* We can not compute accurately for large thresholds due to scaled
2845     frequencies.  */
2846  gcc_assert (threshold <= BB_FREQ_MAX);
2847
2848  /* Frequencies are out of range.  This either means that function contains
2849     internal loop executing more than BB_FREQ_MAX times or profile feedback
2850     is available and function has not been executed at all.  */
2851  if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0)
2852    return true;
2853
2854  /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
2855  limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold;
2856  FOR_EACH_BB_FN (bb, cfun)
2857    {
2858      rtx_insn *insn;
2859
2860      FOR_BB_INSNS (bb, insn)
2861	if (active_insn_p (insn))
2862	  {
2863	    sum += bb->frequency;
2864	    if (sum > limit)
2865	      return true;
2866	}
2867    }
2868
2869  return false;
2870}
2871
2872/* Estimate and propagate basic block frequencies using the given branch
2873   probabilities.  If FORCE is true, the frequencies are used to estimate
2874   the counts even when there are already non-zero profile counts.  */
2875
2876void
2877estimate_bb_frequencies (bool force)
2878{
2879  basic_block bb;
2880  sreal freq_max;
2881
2882  if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ())
2883    {
2884      static int real_values_initialized = 0;
2885
2886      if (!real_values_initialized)
2887        {
2888	  real_values_initialized = 1;
2889	  real_br_prob_base = REG_BR_PROB_BASE;
2890	  real_bb_freq_max = BB_FREQ_MAX;
2891	  real_one_half = sreal (1, -1);
2892	  real_inv_br_prob_base = sreal (1) / real_br_prob_base;
2893	  real_almost_one = sreal (1) - real_inv_br_prob_base;
2894	}
2895
2896      mark_dfs_back_edges ();
2897
2898      single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
2899	 REG_BR_PROB_BASE;
2900
2901      /* Set up block info for each basic block.  */
2902      alloc_aux_for_blocks (sizeof (block_info));
2903      alloc_aux_for_edges (sizeof (edge_prob_info));
2904      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2905	{
2906	  edge e;
2907	  edge_iterator ei;
2908
2909	  FOR_EACH_EDGE (e, ei, bb->succs)
2910	    {
2911	      EDGE_INFO (e)->back_edge_prob = e->probability;
2912	      EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
2913	    }
2914	}
2915
2916      /* First compute frequencies locally for each loop from innermost
2917         to outermost to examine frequencies for back edges.  */
2918      estimate_loops ();
2919
2920      freq_max = 0;
2921      FOR_EACH_BB_FN (bb, cfun)
2922	if (freq_max < BLOCK_INFO (bb)->frequency)
2923	  freq_max = BLOCK_INFO (bb)->frequency;
2924
2925      freq_max = real_bb_freq_max / freq_max;
2926      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2927	{
2928	  sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
2929	  bb->frequency = tmp.to_int ();
2930	}
2931
2932      free_aux_for_blocks ();
2933      free_aux_for_edges ();
2934    }
2935  compute_function_frequency ();
2936}
2937
2938/* Decide whether function is hot, cold or unlikely executed.  */
2939void
2940compute_function_frequency (void)
2941{
2942  basic_block bb;
2943  struct cgraph_node *node = cgraph_node::get (current_function_decl);
2944
2945  if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2946      || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2947    node->only_called_at_startup = true;
2948  if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2949    node->only_called_at_exit = true;
2950
2951  if (profile_status_for_fn (cfun) != PROFILE_READ)
2952    {
2953      int flags = flags_from_decl_or_type (current_function_decl);
2954      if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2955	  != NULL)
2956        node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2957      else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2958	       != NULL)
2959        node->frequency = NODE_FREQUENCY_HOT;
2960      else if (flags & ECF_NORETURN)
2961        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2962      else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2963        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2964      else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2965	       || DECL_STATIC_DESTRUCTOR (current_function_decl))
2966        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2967      return;
2968    }
2969
2970  /* Only first time try to drop function into unlikely executed.
2971     After inlining the roundoff errors may confuse us.
2972     Ipa-profile pass will drop functions only called from unlikely
2973     functions to unlikely and that is most of what we care about.  */
2974  if (!cfun->after_inlining)
2975    node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2976  FOR_EACH_BB_FN (bb, cfun)
2977    {
2978      if (maybe_hot_bb_p (cfun, bb))
2979	{
2980	  node->frequency = NODE_FREQUENCY_HOT;
2981	  return;
2982	}
2983      if (!probably_never_executed_bb_p (cfun, bb))
2984	node->frequency = NODE_FREQUENCY_NORMAL;
2985    }
2986}
2987
2988/* Build PREDICT_EXPR.  */
2989tree
2990build_predict_expr (enum br_predictor predictor, enum prediction taken)
2991{
2992  tree t = build1 (PREDICT_EXPR, void_type_node,
2993		   build_int_cst (integer_type_node, predictor));
2994  SET_PREDICT_EXPR_OUTCOME (t, taken);
2995  return t;
2996}
2997
2998const char *
2999predictor_name (enum br_predictor predictor)
3000{
3001  return predictor_info[predictor].name;
3002}
3003
3004/* Predict branch probabilities and estimate profile of the tree CFG. */
3005
3006namespace {
3007
3008const pass_data pass_data_profile =
3009{
3010  GIMPLE_PASS, /* type */
3011  "profile_estimate", /* name */
3012  OPTGROUP_NONE, /* optinfo_flags */
3013  TV_BRANCH_PROB, /* tv_id */
3014  PROP_cfg, /* properties_required */
3015  0, /* properties_provided */
3016  0, /* properties_destroyed */
3017  0, /* todo_flags_start */
3018  0, /* todo_flags_finish */
3019};
3020
3021class pass_profile : public gimple_opt_pass
3022{
3023public:
3024  pass_profile (gcc::context *ctxt)
3025    : gimple_opt_pass (pass_data_profile, ctxt)
3026  {}
3027
3028  /* opt_pass methods: */
3029  virtual bool gate (function *) { return flag_guess_branch_prob; }
3030  virtual unsigned int execute (function *);
3031
3032}; // class pass_profile
3033
3034unsigned int
3035pass_profile::execute (function *fun)
3036{
3037  unsigned nb_loops;
3038
3039  loop_optimizer_init (LOOPS_NORMAL);
3040  if (dump_file && (dump_flags & TDF_DETAILS))
3041    flow_loops_dump (dump_file, NULL, 0);
3042
3043  mark_irreducible_loops ();
3044
3045  nb_loops = number_of_loops (fun);
3046  if (nb_loops > 1)
3047    scev_initialize ();
3048
3049  tree_estimate_probability ();
3050
3051  if (nb_loops > 1)
3052    scev_finalize ();
3053
3054  loop_optimizer_finalize ();
3055  if (dump_file && (dump_flags & TDF_DETAILS))
3056    gimple_dump_cfg (dump_file, dump_flags);
3057 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3058    profile_status_for_fn (fun) = PROFILE_GUESSED;
3059  return 0;
3060}
3061
3062} // anon namespace
3063
3064gimple_opt_pass *
3065make_pass_profile (gcc::context *ctxt)
3066{
3067  return new pass_profile (ctxt);
3068}
3069
3070namespace {
3071
3072const pass_data pass_data_strip_predict_hints =
3073{
3074  GIMPLE_PASS, /* type */
3075  "*strip_predict_hints", /* name */
3076  OPTGROUP_NONE, /* optinfo_flags */
3077  TV_BRANCH_PROB, /* tv_id */
3078  PROP_cfg, /* properties_required */
3079  0, /* properties_provided */
3080  0, /* properties_destroyed */
3081  0, /* todo_flags_start */
3082  0, /* todo_flags_finish */
3083};
3084
3085class pass_strip_predict_hints : public gimple_opt_pass
3086{
3087public:
3088  pass_strip_predict_hints (gcc::context *ctxt)
3089    : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3090  {}
3091
3092  /* opt_pass methods: */
3093  opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3094  virtual unsigned int execute (function *);
3095
3096}; // class pass_strip_predict_hints
3097
3098/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3099   we no longer need.  */
3100unsigned int
3101pass_strip_predict_hints::execute (function *fun)
3102{
3103  basic_block bb;
3104  gimple ass_stmt;
3105  tree var;
3106
3107  FOR_EACH_BB_FN (bb, fun)
3108    {
3109      gimple_stmt_iterator bi;
3110      for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3111	{
3112	  gimple stmt = gsi_stmt (bi);
3113
3114	  if (gimple_code (stmt) == GIMPLE_PREDICT)
3115	    {
3116	      gsi_remove (&bi, true);
3117	      continue;
3118	    }
3119	  else if (is_gimple_call (stmt))
3120	    {
3121	      tree fndecl = gimple_call_fndecl (stmt);
3122
3123	      if ((fndecl
3124		   && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3125		   && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3126		   && gimple_call_num_args (stmt) == 2)
3127		  || (gimple_call_internal_p (stmt)
3128		      && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3129		{
3130		  var = gimple_call_lhs (stmt);
3131		  if (var)
3132		    {
3133		      ass_stmt
3134			= gimple_build_assign (var, gimple_call_arg (stmt, 0));
3135		      gsi_replace (&bi, ass_stmt, true);
3136		    }
3137		  else
3138		    {
3139		      gsi_remove (&bi, true);
3140		      continue;
3141		    }
3142		}
3143	    }
3144	  gsi_next (&bi);
3145	}
3146    }
3147  return 0;
3148}
3149
3150} // anon namespace
3151
3152gimple_opt_pass *
3153make_pass_strip_predict_hints (gcc::context *ctxt)
3154{
3155  return new pass_strip_predict_hints (ctxt);
3156}
3157
3158/* Rebuild function frequencies.  Passes are in general expected to
3159   maintain profile by hand, however in some cases this is not possible:
3160   for example when inlining several functions with loops freuqencies might run
3161   out of scale and thus needs to be recomputed.  */
3162
3163void
3164rebuild_frequencies (void)
3165{
3166  timevar_push (TV_REBUILD_FREQUENCIES);
3167
3168  /* When the max bb count in the function is small, there is a higher
3169     chance that there were truncation errors in the integer scaling
3170     of counts by inlining and other optimizations. This could lead
3171     to incorrect classification of code as being cold when it isn't.
3172     In that case, force the estimation of bb counts/frequencies from the
3173     branch probabilities, rather than computing frequencies from counts,
3174     which may also lead to frequencies incorrectly reduced to 0. There
3175     is less precision in the probabilities, so we only do this for small
3176     max counts.  */
3177  gcov_type count_max = 0;
3178  basic_block bb;
3179  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3180    count_max = MAX (bb->count, count_max);
3181
3182  if (profile_status_for_fn (cfun) == PROFILE_GUESSED
3183      || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ
3184	  && count_max < REG_BR_PROB_BASE/10))
3185    {
3186      loop_optimizer_init (0);
3187      add_noreturn_fake_exit_edges ();
3188      mark_irreducible_loops ();
3189      connect_infinite_loops_to_exit ();
3190      estimate_bb_frequencies (true);
3191      remove_fake_exit_edges ();
3192      loop_optimizer_finalize ();
3193    }
3194  else if (profile_status_for_fn (cfun) == PROFILE_READ)
3195    counts_to_freqs ();
3196  else
3197    gcc_unreachable ();
3198  timevar_pop (TV_REBUILD_FREQUENCIES);
3199}
3200