Re: [Tinycc-devel] manually inlining functions

[Michael Matz]

Hello,

On Tue, 4 May 2021, uso ewin wrote:


Tinycc handle inline function like if they were macro, so using inline
in tcc always inline functions.


That's not accurate.  Inline functions in TCC are emitted like normal 
functions but only when there's reason to emit them (which are involved 
and depend on if they are called (or address-taken) or if they are c99 
inline or gnu inline semantics, and static or global).  But they are _not_ 
emitted like macros at every use, rather a normal argument setup and call 
is done, and the body is emitted only once as a normal function.


Either way, the discussion about speed of inline functions in TCC is 
fairly academic, code performance is low for many other, more important, 
reasons.  There is no optimizer, there is no intermediate representation 
that could be optimized, there is nothing that could benefit from inlining 
except the call instruction and the prologue/epilogue itself would be 
removed.


Not even the argument setup would be saved very often: TCCs compilation 
model would require evaluating the arguments to local temporaries which 
are often spilled to stack right soon, in the end needing exactly the same 
work as the argument setup for a call.


I somewhen wrote a simple function inliner for tcc handling most normal 
cases (those when the inline doesn't contain a local static variable, and 
when no variadic args are used), but the result was somewhat so-and-so, 
there simply wasn't much point to having it before having a better 
single-pass optimizer / register allocator.



Ciao,
Michael.

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[uso ewin]

On Sat, May 1, 2021 at 5:35 PM Vincent Lefevre  wrote:
>
> On 2021-04-30 20:50:36 -0700, Elijah Stone wrote:
> > On Sat, 1 May 2021, Yakov wrote:
> >
> > > having to write macros for performance feels so obsolete, double
> > > evaluation hiding in dark corners etc. And function calls are so
> > > expensive in tight loops.
> >
> > Calls are fairly cheap, on modern architectures.  The performance impact of
> > an inliner would be fairly marginal for tcc, compared with, say, a register
> > allocator.
>
> Inline functions have (at least) 3 advantages:
>
> 1. They eliminate the call, which is rather useful in case a call
>to a function of a shared library, as such calls can be very
>expensive. For very simple functions (e.g. accessing a field
>of a structure), there would be much overhead.
>
> 2. With the inline definition, the compiler can know what the function
>does (e.g. enabling value range propagation), so that it may be
>able optimize the code around.
>
> 3. A call to an inline function may have specific arguments, such
>as constant ones, so that the compiler may be able to optimize
>the code of the instantiated function, e.g. avoiding tests and
>eliminating dead code via constant propagation.
>
> I think that tcc could benefit from these 3 points.
>
> --
> Vincent Lefèvre  - Web: 
> 100% accessible validated (X)HTML - Blog: 
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
>
Tinycc handle inline function like if they were macro, so using inline
in tcc always inline functions.
The doc is outdated I think.

> ___
> Tinycc-devel mailing list
> Tinycc-devel@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/tinycc-devel

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Vincent Lefevre]

On 2021-04-30 20:50:36 -0700, Elijah Stone wrote:
> On Sat, 1 May 2021, Yakov wrote:
> 
> > having to write macros for performance feels so obsolete, double
> > evaluation hiding in dark corners etc. And function calls are so
> > expensive in tight loops.
> 
> Calls are fairly cheap, on modern architectures.  The performance impact of
> an inliner would be fairly marginal for tcc, compared with, say, a register
> allocator.

Inline functions have (at least) 3 advantages:

1. They eliminate the call, which is rather useful in case a call
   to a function of a shared library, as such calls can be very
   expensive. For very simple functions (e.g. accessing a field
   of a structure), there would be much overhead.

2. With the inline definition, the compiler can know what the function
   does (e.g. enabling value range propagation), so that it may be
   able optimize the code around.

3. A call to an inline function may have specific arguments, such
   as constant ones, so that the compiler may be able to optimize
   the code of the instantiated function, e.g. avoiding tests and
   eliminating dead code via constant propagation.

I think that tcc could benefit from these 3 points.

-- 
Vincent Lefèvre  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Vincent Lefevre]

On 2021-05-01 00:43:27 +, Kyryl Melekhin wrote:
> Yakov  wrote:
> 
> > Kyryl you cannot inline everything because you will get code
> > explosion, often infinite code explosion when functions have a
> > circular dependency on each other. I am just talking about inlining
> > certain functions carefully chosen by a programmer.
> 
> Yeah, I get that. That's why it is so hard to make such a tool.
> Because recursion is hard to decompose, so the inliner has to be
> smart enough to actually rewrite the recursive solution iteratively
> otherwise it will blow up.

In general, programmers mark functions as inline only when this
does not involve a recursion, though they are not obliged to do so.
With function-like macros, the preprocessor automatically disables
recursion. I suppose that the compiler can do the same thing with
inline functions (but it may also choose a higher recursion level).
Since tcc obviously supports function-like macros, handling recursion
for inline functions would not introduce a new difficulty.

-- 
Vincent Lefèvre  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Elijah Stone]

On Sat, 1 May 2021, Yakov wrote:


On this sample using macros speeds the program up 400%


Be that as it may, it's not representative of most application.  For 
instance, cpython's performance increases by only 10-15% with the inliner 
turned on.


(And actually that's misleading, because inlining enables many other 
optimizations.  The impact for tcc if it _only_ added inlining would 
probably be much less.  Unfortunately gcc doesn't seem to be willing to 
inline at -O0.)



I have recently read a paper about a Linear Scan Register Allocator[1], 
they claim it gives you 95% performance or Graph Coloring Register 
Allocator in basically no time, and requires no SSA.


Yes, linear scan is quite nice.  It's not really compatible with tcc's 
compilation model--nor are most other optimizations, including 
inlining--but I mentioned it because it's probably the most worthwhile 
optimization a compiler can perform and it's not too difficult.


In the context of a compiler like gcc or llvm, linear scan takes almost no 
time at all.  However it depends on a certain model of code that tcc does 
not provide currently.  Gcc already produces such a model, even without 
optimizations, and linear scan takes advantage of the information which is 
already there; a big part of the reason why tcc is so fast is that it 
produces no such model.  For gcc this is a sunk cost; for tcc, not.


 -E

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Kyryl Melekhin]

Well, I may take that back, recursion may be useful if you
have a 5000 loc function that you need to invoke
on some very rare occasion once. And if you care about
the size of your executable a lot for some reason. 
But on hotpath, it makes no sense. Unless you are trying
to satisfy your academia, which likely aren't teaching
you useful stuff anyways... But even in those cases, recursion
can be a goto statement, with little state dublication. 
I tried actually cracking this problem before, (about rewriting
recursion iteratively) and the aspect of your analyzer to keep
track of every data that is actually relevant (to get the optimal
solution) is hard to achieve. I had some sucesses, until I got
tired of trying to solve this. Sorry this a bit off topic, carry on.

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Kyryl Melekhin]

Yakov  wrote:

> Kyryl you cannot inline everything because you will get code
> explosion, often infinite code explosion when functions have a
> circular dependency on each other. I am just talking about inlining
> certain functions carefully chosen by a programmer.

Yeah, I get that. That's why it is so hard to make such a tool.
Because recursion is hard to decompose, so the inliner has to be
smart enough to actually rewrite the recursive solution iteratively
otherwise it will blow up. But that actually opens up a massive
opportunity for optimizations, because lets be real - recursion 
sucks and there is never ever a situation where it's actually 
useful for the cpu to do. And yes, the unary() function in tcc
which is recursive sucks a lot too, there is just so much 
state in there that it's very difficult to understand what is
going on. Luckly I have been looking at that code for more
than a year, so my grasp got better, but if that were iterative,
I be loving it even more.

--

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Yakov]

I have recently read a paper about a Linear Scan Register Allocator[1],
they claim it gives you 95% performance or Graph Coloring Register
Allocator in basically no time, and requires no SSA.
1.  http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf



сб, 1 мая 2021 г. в 10:51, Elijah Stone :

> On Sat, 1 May 2021, Yakov wrote:
>
> > having to write macros for performance feels so obsolete, double
> > evaluation hiding in dark corners etc. And function calls are so
> > expensive in tight loops.
>
> Calls are fairly cheap, on modern architectures.  The performance impact
> of an inliner would be fairly marginal for tcc, compared with, say, a
> register allocator.
>
> ___
> Tinycc-devel mailing list
> Tinycc-devel@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/tinycc-devel
>
___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Yakov]

Saying that calls are cheap may be right for many cases but definitely not
for me, here is a tiny example I made by copying/pasting from my actual
project which is a compiler that uses TinyC as a backend. On this sample
using macros speeds the program up 400% i.e. 4 times on my AMD Ryzen5. In a
real compiler it is even worse.

#define USE_MACROS

#include 
#include 

typedef uint64_t val;
#define HEAP_FLAG 0x0001ULL
#define INT_MASK 0x
#define PTR_MASK 0xULL
#define __nil HEAP_FLAG

#ifdef USE_MACROS
#define __is_int(a) (((a) & HEAP_FLAG) == 0)
#define __int(a) (a & INT_MASK)
#define __let(a) (a & INT_MASK)
#define __dec(a) (*a)--
#define __eq(a, b) (__is_int(a) && __is_int(b) ? __int(a) == __int(b) :
__nil)
#define __mod(a, b) (__is_int(a) && __is_int(b) ? __int(a) % __int(b) :
__nil)
#define __cout(a) if (__is_int(a)) printf("%i", __int(a))
#else
int __is_int(val a) { return (a & HEAP_FLAG) == 0; }
int __int(val a) { return a & INT_MASK; }
val __let(int a) { return a & INT_MASK; }
void __dec(val *x) { (*x)--; };
int __eq(val a, val b) { return __is_int(a) && __is_int(b) ? __int(a)
== __int(b) : __nil; }
int __mod(val a, val b) { return __is_int(a) && __is_int(b) ? __int(a)
% __int(b) : __nil; }
void __cout(val a) { if (__is_int(a)) printf("%i", __int(a)); }
#endif

void test_loop() {
val a = __let(300);
while (1) {
__dec(&a);
if (__eq(a, __let(0))) break;
if (__eq(__mod(a, __let(10)), __let(0))) { __cout(a); printf("
"); }
}
}

long time1000() {
struct timeval val;
gettimeofday(&val, 0);
return val.tv_sec * 1000 + val.tv_usec / 1000;
}

int main() {
int T;
T = time1000();
test_loop();
T = time1000() - T;
printf("<%i ms test_loop>\n", (int)T);
}


сб, 1 мая 2021 г. в 10:51, Elijah Stone :

> On Sat, 1 May 2021, Yakov wrote:
>
> > having to write macros for performance feels so obsolete, double
> > evaluation hiding in dark corners etc. And function calls are so
> > expensive in tight loops.
>
> Calls are fairly cheap, on modern architectures.  The performance impact
> of an inliner would be fairly marginal for tcc, compared with, say, a
> register allocator.
>
> ___
> Tinycc-devel mailing list
> Tinycc-devel@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/tinycc-devel
>
___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Yakov]

Kyryl you cannot inline everything because you will get code
explosion, often infinite code explosion when functions have a
circular dependency on each other. I am just talking about inlining
certain functions carefully chosen by a programmer.


сб, 1 мая 2021 г. в 11:13, Kyryl Melekhin :
>
> Yakov  wrote:
>
> > Manual inlining seems to be a straightforward thing, just clone the
> > node into the ast and rename all variables to something unique so I
> > thought maybe that's what tcc supports with some pragma or what not.
>
> If you create such a tool which can take any C code and straight up
> inline everything into main() function you would be revolutionary
> genious in my eyes. I don't know why, but seems like nobody tried
> creating such tool before or I am not aware of it's existance. If
> you find any, let me know. Thanks.
>
> Regards,
> Kyryl.
>
> ___
> Tinycc-devel mailing list
> Tinycc-devel@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/tinycc-devel

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Kyryl Melekhin]

Yakov  wrote:

> Manual inlining seems to be a straightforward thing, just clone the
> node into the ast and rename all variables to something unique so I
> thought maybe that's what tcc supports with some pragma or what not.

If you create such a tool which can take any C code and straight up
inline everything into main() function you would be revolutionary
genious in my eyes. I don't know why, but seems like nobody tried
creating such tool before or I am not aware of it's existance. If
you find any, let me know. Thanks.

Regards,
Kyryl.

___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel

Re: [Tinycc-devel] manually inlining functions

[Elijah Stone]

On Sat, 1 May 2021, Yakov wrote:

having to write macros for performance feels so obsolete, double 
evaluation hiding in dark corners etc. And function calls are so 
expensive in tight loops.


Calls are fairly cheap, on modern architectures.  The performance impact 
of an inliner would be fairly marginal for tcc, compared with, say, a 
register allocator.


___
Tinycc-devel mailing list
Tinycc-devel@nongnu.org
https://lists.nongnu.org/mailman/listinfo/tinycc-devel