Why are profile-implied niters capped at 99?

[Alex Coplan via Gcc]

Hi,

I've been looking at GCC's profile information recently.  I noticed that the
probabilities/counts effectively encode the expected niters of a loop, so e.g.
with the following testcase:

$ cat t.c
int *a;
void f() {
  for (int i = 0; i < N; i++)
a[i] = i;
}
$ ./xgcc -B . -c -S -o /dev/null t.c -DN=32 -O2 -fno-tree-vectorize 
-fdump-tree-optimized=-

;; Function f (f, funcdef_no=0, decl_uid=4417, cgraph_uid=1, symbol_order=1)

Removing basic block 5
void f ()
{
  unsigned long ivtmp.6;
  int i;
  int * a.0_1;

   [local count: 32534376]:
  a.0_1 = a;

   [local count: 1041207448]:
  # ivtmp.6_11 = PHI 
  i_12 = (int) ivtmp.6_11;
  MEM[(int *)a.0_1 + ivtmp.6_11 * 4] = i_12;
  ivtmp.6_10 = ivtmp.6_11 + 1;
  if (ivtmp.6_10 != 32)
goto ; [96.88%]
  else
goto ; [3.12%]

   [local count: 32534376]:
  return;

}

the counts effectively encode that the loop executes 32 times, since the count
of the header (bb 3) is 32 times the count of the preheader (bb 2):

$ python -c 'print(1041207448/32534376)'
32.003301615497406

however, I noticed that for larger values of N, the implied niters caps out at
99.  E.g. for N=128:

$ ./xgcc -B . -c t.c -S -o /dev/null -DN=128 -O2 -fno-tree-vectorize 
-fdump-tree-optimized=-

;; Function f (f, funcdef_no=0, decl_uid=4417, cgraph_uid=1, symbol_order=1)

Removing basic block 5
void f ()
{
  unsigned long ivtmp.6;
  int i;
  int * a.0_1;

   [local count: 10737416]:
  a.0_1 = a;

   [local count: 1063004408]:
  # ivtmp.6_11 = PHI 
  i_12 = (int) ivtmp.6_11;
  MEM[(int *)a.0_1 + ivtmp.6_11 * 4] = i_12;
  ivtmp.6_10 = ivtmp.6_11 + 1;
  if (ivtmp.6_10 != 128)
goto ; [98.99%]
  else
goto ; [1.01%]

   [local count: 10737416]:
  return;

}

here the ratio of the counts is:

$ python -c 'print(1063004408/10737416)'
99.2086163002

I wrote a script to try the same reproducer with various values of N,
and that shows the following (in the format "N : implied niters"):

$ ./profile_niters.py
90 : 89.9090913170256
91 : 90.7431340154603
92 : 91.59262212919725
93 : 93.3396171245259
94 : 94.2381049694668
95 : 95.15387181344315
96 : 96.08735052729118
97 : 97.03920319702912
98 : 98.00990484649222
99 : 99.2086163002
100 : 99.2086163002
101 : 99.2086163002
102 : 99.2086163002
103 : 99.2086163002
104 : 99.2086163002
105 : 99.2086163002
106 : 99.2086163002
107 : 99.2086163002
108 : 99.2086163002

I was just wondering if anyone knows what the rationale for this behaviour is,
and can point to the relevant bit in the source?

I can imagine it might be something to do with floating-point precision
and not wanting probabilities to get too small or large, but I'm not
sure.

Thanks,
Alex

[no subject]

[Zhang Zhang via Gcc]

ໄດ້ແລ້ວ

Educational question on compiling (analyzing) the C programming language

[Laurent Cimon via Gcc]

Hello,

I'm a computer science student at the Université Laval in Quebec City. I'm 
currently following a course on compilers. We're learning semantic analysis at 
this time and the course is based on the book Compilers: principles, 
techniques & tools by Alfred V. Aho.

While learning L-attributed SDD, where dependency trees are strictly built 
from left to right, I wondered if that is why the C programming language 
requires function prototypes at the top of a file to use functions that are 
implemented further down. The professor couldn't say and advised me to ask him 
to do further research on this in private. Instead of making him do the work 
of figuring out how C compilers work or have worked historically, I thought of 
coming to one of the most knowledgeable communities on the subject to ask 
about this. I will share the answers with my professor and classmates, so this 
is an opportunity to settle the question for many people.

I realize that compilers have evolved with time, and that many things required 
the use of function prototypes, but my question is, what is the historical 
reason that a function defined further down in a C file cannot be used without 
a 
function prototype?

A counter-example would be Java, where methods can be defined anywhere in a 
class and be called even from the constructor. I'm not very interested in 
Java, so I won't pry much further, but if you know about this, could you 
quickly explain what it does differently that allows it to do that?

Also, is C keeping this behavior to satisfy the standard, or do the modern 
language analyzers still have the same constraints that required this behavior 
in the first place?

Thank you for your answers,
Laurent Cimon