Hi everyone,

This is an idea that sprung to mind while looking at fixing an unrelated bug, and that's to do with nested functions.

In situations where a nested function has no parameters, is it feasible and beneficial to programmatically merge it into the main procedure in some circumstances (it wouldn't be possible if the nested routine has inline assembly language because RET won't behave the same, for example), using jumps to navigate to, from and around it? I know for one thing it will possibly free up a register in some calculations because it doesn't have to pass the base pointer (e.g. RBP) as a hidden parameter.

On a similar topic, one person mentioned that GCC and other compilers sometimes 'outline' conditional branches by effectively moving the branch into a nested procedure in order to help with caching.by giving the main procedure a smaller memory footprint.

Might this be something worth researching?

Gareth aka. Kit

On Oct 1, 2020, at 10:37 AM, J. Gareth Moreton via fpc-devel wrote: In situations where a nested function has no parameters, is it feasible and beneficial to programmatically merge it into the main procedure

What do you mean by "merge"? Like inlining?

Regards,
Ryan Joseph

In a way, yes, but not quite the same, since multiple calls to the nested function would still redirect to the same block of code rather than being inlined at each call.  I suppose more similar to the old GOSUB; RETURN combination in old versions of Basic, and the nested routine slotted either at the end of the parent function or, if the compiler is intelligent enough, right after one of the function calls (in effect, inlining it at this point) so the peephole optimizer can then remove a zero-distance jump.

Gareth aka. Kit

And how to you get back?

When you talk of jump instead of call, I imagine something like: nop
nop
jmp + 0 // to nested
mov // in nested
jmp ??? // back to outer
nop  // continue outer
nop
jmp -5 // to nested
nop // continue outer

What is the advantage over "call"?

----
Maybe the following (not sure if beneficial) goes into the same direction

If a "nested proc" (which can have its own locals, and params) does NOT recurse, then instead of generating a separate stack frame (enter/leave) space for the locals could be allocated at the end of the outer function. That means that the basepointer (rbp) can be kept as it is. And that also means, that the framepointer for the outer (access to outer variables) does not need to be passed, as it is the basepointer. (This kind of extends the recent "do not pass the outer-fp", if there is no access to outer vars, only this time outer vars may be accessed.)

Ah crumbs, I thought it was too easy!  I can't believe I missed the obvious there!  Not much of a saving if it has to store the return address somewhere (mov @return(%rip),%rcx; mov %rcx, (somewhere on the stack)).

The advantage would be reducing the chance of additional memory caching since it's all together, and not having additional stack unwinding and function prologues.  But the requirement of a return address... yeah that complicates it!  Sorry, I feel silly now.  I might play around with it as a personal research project to see if it's viable though.

Gareth aka. Kit

J. Gareth Moreton wrote

On a similar topic, one person mentioned that GCC and other compilers sometimes 'outline' conditional branches by effectively moving the branch into a nested procedure in order to help with caching.by giving the main procedure a smaller memory footprint.

There are actually at least two things you can do related to splitting hot and cold code (code that gets executed a lot and code that gets execute very little). And there are also two possible approaches to determine what is hot and what is cold code:

1a) use static properties: you use language knowledge to change the layout of code. E.g., you can assume with high confidence that exception code and code for failed run time checks will be executed very seldom.

1b) use dynamic properties: you first profile the code using representative inputs, and use that information to determine hot and cold code (or adjust your static assumptions)

Next, you can use this information in two ways:

2a) to improve code caching, "all" you need to do is separate the hot and cold code . This is generally done by placing all cold code together at the end of a procedure, so you don't need to perform any outlining here.

2b) to improve stack frame size (and data caching) and superfluous initialisation of (managed) variables that are only used in cold code, you can outline parts of the code (and the associated data).

I think that 1a + 2a would be the easiest to implement. One way would be to use two asmlists per procedure instead of one ("hotcodelist" and "coldcodelist", can be kept in tprocdef.implprocdefinfo), and set current_asmdata.CurrAsmList with the former or the latter as appropriate (probably in pass_generate_code of e.g. tcgtryexceptnode, and adapt g_rangecheck so it accepts two asmlists instead of one: one where to add to the check, and one where to add the "failed" code, ...).

Jonas

Sounds like a fun thing to research, that's for sure.  Thanks Jonas.

I'm under the impression that exception code tends to be separated anyway, so it can't easily be separated much further. Code that checks "IOResult" though could be possibly marked as cold code, so long as it isn't too large (e.g. you might get diminishing returns if the branch is simply "WriteLn('File not found'); Exit;").

Code that executes if, say, a LongInt variable equals "-1" might be cold code, especially as that's often an error flag and is otherwise just one value out of 2^32 possibilities (i.e. statistically unlikely to be True), although it's tricky to know if an assumption is correct or not given an arbitrary block of code, and what the penalty is if code that's marked as cold is actually hot.

Gareth aka. Kit

J. Gareth Moreton wrote

Sounds like a fun thing to research, that's for sure.  Thanks Jonas. I'm under the impression that exception code tends to be separated anyway, so it can't easily be separated much further.

Implicit exception code, yes, but explicit try/except blocks can appear anywhere.

There's a pretty famous paper that investigated what kind of checks often (in about 80% of the cases) result in taken/non-taken branches. You can find it at
https://www.classes.cs.uchicago.edu/archive/2017/fall/32001-1/papers/ball-larus-branch-predict.pdf

You will indeed get penalties from mispredictions, but you can be as conservative as you want.

Jonas

Useful theory.  I'll take a read.  Thank you again.

Gareth aka. Kit