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