Martok

2018-07-20 21:19:34 UTC

Hi all,

inspired by Kit's concept for pure functions, I had a deeper look at what inline

functions (and more importantly, the nodes involved in expanding them) can do.

Let me share my proof-of-concept (which may very well become a

'poof-of-concept'...). You can find my current working branch here

<https://github.com/martok/freepascal/compare/master...dev_inlining>.

Instead of marking a function as 'pure' at declaration, I took another way: make

normal inlining firstpass flexible enough that any "accidentally" pure function

can be collapsed at the call site.

As an extension, I then propose a new intrinsic:

function ConstExpr(X: AnyType): AnyType;

If the expression X can be reduced to a constant, the node simplifies to

that constant.

Otherwise, fail compilation with E3203 Illegal Expression.

ConstExpr is basically pass-through for most expressions, but it allows us to

"call" functions /at parse time/, as long as these functions are pure and the

arguments are constant at the point of declaration.

Let me illustrate with an example:

program tinline3;

Â function sinc(x: Real): Real; inline;

Â begin

Â Â Â if X = 0 then

Â Â Â Â Â Result:= 1

Â Â Â else

Â Â Â Â Â Result:= sin(x) / x;

Â end;

const

Â s1 = constexpr(sinc(0.3));

Â s2 = constexpr(sinc(0));

var

Â u, v: Real;

begin

Â u:= s1;

Â u:= s2;

end.

This gets processed into the node tree (right at parse time):

*******************************************************************************

after parsing

$main; Register;

*******************************************************************************

(blockn, resultdef = $void = "untyped", pos = (16,1), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 4

Â Â (statementn, resultdef = <nil>, pos = (17,9), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 4

Â Â Â Â Â (assignn, resultdef = $void = "untyped", pos = (17,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â (loadn, resultdef = Real = "Double", pos = (17,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1

Â Â Â Â Â Â Â Â Â Â Â nil

Â Â Â Â Â Â Â Â Â Â Â symbol = U

Â Â Â Â Â Â Â Â )

Â Â Â Â Â Â Â Â (realconstn, resultdef = Real = "Double", pos = (17,7), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â Â Â Â value =Â 9.85067355537798561294E-0001

Â Â Â Â Â Â Â Â )

Â Â Â Â Â )

Â Â )

Â Â (statementn, resultdef = <nil>, pos = (18,9), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â (assignn, resultdef = $void = "untyped", pos = (18,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â (loadn, resultdef = Real = "Double", pos = (18,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1

Â Â Â Â Â Â Â Â Â Â Â nil

Â Â Â Â Â Â Â Â Â Â Â symbol = U

Â Â Â Â Â Â Â Â )

Â Â Â Â Â Â Â Â (realconstn, resultdef = Real = "Double", pos = (18,7), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â Â Â Â value =Â 1.00000000000000000000E+0000

Â Â Â Â Â Â Â Â )

Â Â Â Â Â )

Â Â )

)

As you can see, the expressions have been simplified into (the correct)

constants of type Double (Real for x86 is Double). Intermediate type conversions

(including potential loss of FP-precision) are handled correctly (there's a

sneaky int(0)<>real in the example).

This is already really useful for the most common application of macros with

parameters in C: calculating constants (like #define _IOC(inout,group,num,len)

(inout | ((len & IOCPARM_MASK) << 16) | ((group) << 8) | (num))).

There are currently a few issues:

1. I extended the const propagation optimisation pass a bit. It had

restrictions on inlinen and realconstn that probably had a reason, but I

can't see it...

2. calln now does an automatic internal optconstpropagate pass when inlining.

This is to carry refs to constant temps a bit further down. That might in

fact be problematic because it could increase code size with multiple loads

and should probably not be done in general. But for this PoC, that was the

simplest way.

3. procs can only be inlined if their body has been fully parsed before the

call. This is actually kind of a problem because it limits usefulness for

the C-style constant-macro application.

4. The tricky part (same goes for pure functions) is actually finding out if

parameters of an inlined function are constants. optconstpropagate can track

that after the fact, but at that point the fun is already over. The best

solution I could think of is running some very primitive DFA along while

parsing, so that the firstpass can refer to that. Basically, if a symbol is

known to be constant, loads of it could be treated as constants of its

stored value for the purposes of simplify(). This is of course limited to

only local symbols, but still doesn't seem very practical...

So, it's far from perfect, but shows that there is some potential for

metaprogramming without the need for much new complexity (numstat is +59-5 at

the time of writing this). I suspect there is quite a lot that could be gained

from better constant propagation in general: most nodes can already simplify

themselves efficiently, but only if they know the arguments are constant.

What do you think?

Regards,

Martok

inspired by Kit's concept for pure functions, I had a deeper look at what inline

functions (and more importantly, the nodes involved in expanding them) can do.

Let me share my proof-of-concept (which may very well become a

'poof-of-concept'...). You can find my current working branch here

<https://github.com/martok/freepascal/compare/master...dev_inlining>.

Instead of marking a function as 'pure' at declaration, I took another way: make

normal inlining firstpass flexible enough that any "accidentally" pure function

can be collapsed at the call site.

As an extension, I then propose a new intrinsic:

function ConstExpr(X: AnyType): AnyType;

If the expression X can be reduced to a constant, the node simplifies to

that constant.

Otherwise, fail compilation with E3203 Illegal Expression.

ConstExpr is basically pass-through for most expressions, but it allows us to

"call" functions /at parse time/, as long as these functions are pure and the

arguments are constant at the point of declaration.

Let me illustrate with an example:

program tinline3;

Â function sinc(x: Real): Real; inline;

Â begin

Â Â Â if X = 0 then

Â Â Â Â Â Result:= 1

Â Â Â else

Â Â Â Â Â Result:= sin(x) / x;

Â end;

const

Â s1 = constexpr(sinc(0.3));

Â s2 = constexpr(sinc(0));

var

Â u, v: Real;

begin

Â u:= s1;

Â u:= s2;

end.

This gets processed into the node tree (right at parse time):

*******************************************************************************

after parsing

$main; Register;

*******************************************************************************

(blockn, resultdef = $void = "untyped", pos = (16,1), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 4

Â Â (statementn, resultdef = <nil>, pos = (17,9), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 4

Â Â Â Â Â (assignn, resultdef = $void = "untyped", pos = (17,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â (loadn, resultdef = Real = "Double", pos = (17,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1

Â Â Â Â Â Â Â Â Â Â Â nil

Â Â Â Â Â Â Â Â Â Â Â symbol = U

Â Â Â Â Â Â Â Â )

Â Â Â Â Â Â Â Â (realconstn, resultdef = Real = "Double", pos = (17,7), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â Â Â Â value =Â 9.85067355537798561294E-0001

Â Â Â Â Â Â Â Â )

Â Â Â Â Â )

Â Â )

Â Â (statementn, resultdef = <nil>, pos = (18,9), loc = LOC_INVALID,

expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â (assignn, resultdef = $void = "untyped", pos = (18,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â (loadn, resultdef = Real = "Double", pos = (18,3), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1

Â Â Â Â Â Â Â Â Â Â Â nil

Â Â Â Â Â Â Â Â Â Â Â symbol = U

Â Â Â Â Â Â Â Â )

Â Â Â Â Â Â Â Â (realconstn, resultdef = Real = "Double", pos = (18,7), loc =

LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2

Â Â Â Â Â Â Â Â Â Â Â value =Â 1.00000000000000000000E+0000

Â Â Â Â Â Â Â Â )

Â Â Â Â Â )

Â Â )

)

As you can see, the expressions have been simplified into (the correct)

constants of type Double (Real for x86 is Double). Intermediate type conversions

(including potential loss of FP-precision) are handled correctly (there's a

sneaky int(0)<>real in the example).

This is already really useful for the most common application of macros with

parameters in C: calculating constants (like #define _IOC(inout,group,num,len)

(inout | ((len & IOCPARM_MASK) << 16) | ((group) << 8) | (num))).

There are currently a few issues:

1. I extended the const propagation optimisation pass a bit. It had

restrictions on inlinen and realconstn that probably had a reason, but I

can't see it...

2. calln now does an automatic internal optconstpropagate pass when inlining.

This is to carry refs to constant temps a bit further down. That might in

fact be problematic because it could increase code size with multiple loads

and should probably not be done in general. But for this PoC, that was the

simplest way.

3. procs can only be inlined if their body has been fully parsed before the

call. This is actually kind of a problem because it limits usefulness for

the C-style constant-macro application.

4. The tricky part (same goes for pure functions) is actually finding out if

parameters of an inlined function are constants. optconstpropagate can track

that after the fact, but at that point the fun is already over. The best

solution I could think of is running some very primitive DFA along while

parsing, so that the firstpass can refer to that. Basically, if a symbol is

known to be constant, loads of it could be treated as constants of its

stored value for the purposes of simplify(). This is of course limited to

only local symbols, but still doesn't seem very practical...

So, it's far from perfect, but shows that there is some potential for

metaprogramming without the need for much new complexity (numstat is +59-5 at

the time of writing this). I suspect there is quite a lot that could be gained

from better constant propagation in general: most nodes can already simplify

themselves efficiently, but only if they know the arguments are constant.

What do you think?

Regards,

Martok