Skip to content

[Refactor] Node traversal optimisation

J. Gareth "Kit" Moreton requested to merge CuriousKit/optimisations:node-traversal-optimisation into main

Summary

This merge request makes some speed optimisations to the compiler by updating the foreachnode and foreachnodestatic calls:

  • The versions of foreachnode and foreachnodestatic that don't have a process order parameter are now inlined, since these simply call the versions with the order parameter as pm_postprocess, passing through the other parameters unmodified.
  • If foreachnode and foreachnodetatic are called with a process order of pm_postandagain, the root node is not processed again if the process_children function returns False, since if the root node wasn't changed the first time (or even if it was), it shouldn't change again if the children weren't changed. As a side-effect, the return value of this 'again' call can be discarded because Result is always True at this point, thus removing a case block.

Especially with the second point, it reduces the number of times the nodes are unnecessarily traversed, although currently only the constant propagation code uses pm_postandagain traversals.

System

  • Processor architecture: Cross-platform

What is the current bug behavior?

N/A

What is the behavior after applying this patch?

The compiler should gain a small speed boost, especially if constant propagation is enabled (which uses pm_postandagain).

Relevant logs and/or screenshots

Places where the inlined foreachnode and foreachnodestatic functions are called gain an extra line of code, but in compensation, there is one fewer procedure jump in the chain. For example, for the nbas unit under aarch64-linux - before:

.section .text.n_nbas_$$_no_exit_statement_in_block$tnode$$boolean,"ax"
	.balign 8
.globl	NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN
	.hidden NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN
	.type	NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN,@function
NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN:
	...
	adrp	x1,:got:NBAS_$$_IS_EXIT_STATEMENT$TNODE$POINTER$$FOREACHNODERESULT
	ldr	x1,[x1, :got_lo12:NBAS_$$_IS_EXIT_STATEMENT$TNODE$POINTER$$FOREACHNODERESULT]
	mov	x0,sp
	movz	x2,#0
	bl	NUTILS_$$_FOREACHNODESTATIC$TNODE$STATICFOREACHNODEFUNCTION$POINTER$$BOOLEAN

After:

.section .text.n_nbas_$$_no_exit_statement_in_block$tnode$$boolean,"ax"
	.balign 8
.globl	NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN
	.hidden NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN
	.type	NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN,@function
NBAS_$$_NO_EXIT_STATEMENT_IN_BLOCK$TNODE$$BOOLEAN:
	...
	adrp	x2,:got:NBAS_$$_IS_EXIT_STATEMENT$TNODE$POINTER$$FOREACHNODERESULT
	ldr	x2,[x2, :got_lo12:NBAS_$$_IS_EXIT_STATEMENT$TNODE$POINTER$$FOREACHNODERESULT]
	mov	x1,sp
	movz	x3,#0
	movz	w0,#1 ; <-- Corresponds to pm_postprocess
	bl	NUTILS_$$_FOREACHNODESTATIC$hYWSyYihGjGH```

Merge request reports