Re: [patch 06/10] Immediate Value - i386 Optimization

Mathieu Desnoyers
2007-07-03T20:43:58Z

* H. Peter Anvin (hpa@zytor.com) wrote:
> Mathieu Desnoyers wrote:
> >
> > Hi Peter,
> >
> > I understand your concern. If you find a way to let the code be compiled
> > by gcc, put at the end of the functions (never being a branch target)
> > and then, dynamically, get the address of the branch instruction and
> > patch it, all that in cooperation with gcc, I would be glad to hear from
> > it. What I found is that gcc lets us do anything that touches
> > variables/registers in an inline assembly, but does not permit to place
> > branch instructions ourselves; it does not expect the execution flow to
> > be changed in inline asms.
> >
>
> I believe this is correct. It probably would require requesting a gcc
> builtin, which might be worthwhile to do if we
>
> > <branch site>
> > 77: b8 00 00 00 00 mov $0x0,%eax
> > 7c: 85 c0 test %eax,%eax
> > 7e: 0f 85 16 03 00 00 jne 39a <schedule+0x39a>
> > here, we just loaded 0 in eax (movl used to make sure we populate the
> > whole register so we do not stall the pipeline)
> > When we activate the site,
> > line 77 becomes: b8 01 00 00 00 mov $0x1,%eax
> > </branch site>
>
> One could, though, use an indirect jump to achieve, if not as good, at
> least most of the effect:
>
> movl $<patchable>,<reg>
> jmp *<reg>
>

Using a jmp *<reg> will instruct gcc not to inline inline functions and
restrict loop unrolling (but the latter is not used in the linux
kernel). We would have to compute different $<patchable> for every site
generated by putting an immediate in an inline function.

> Some x86 cores will be able to detect the movl...jmp forwarding, and
> collapse it into a known branch target; however, on the ones that can't,
> it might be worse, since one would have to rely on the indirect branch
> predictor.
>
> This would, however, provide infrastructure that could be combined with
> a future gcc builtin.
>

If we can change the compiler, here is what we could do:

Tell GCC to put NOPs that could be altered by a branch alternative to
some specified code. We should be able to get the instruction pointers
(think of inlines) to these nop/branch instructions so we can change
them dynamically.

Something like:

immediate_t myfunc_cond;

inline myfunction(void) {
static void *insn; /* pointer to nops/branch instruction */
static void *target_inactive, *target_active;

__builtin_polymorphic_if(&insn, &myfunc_cond) {
/* Do something */
} else {
...
}
}

I could then save all the insns into my immediate value section and
later activate them by looking up all of those who refer to myfunc_cond.

The default behavior would be to branch to the target_inactive, and we
could change insn to jump to target_active dynamically.

Note that we should align the jump instruction so the address could be
changed atomically in the general case (on x86 and x86_64, we have to
use an int3 bypass anyway, so we don't really care).

Also, we should fine a way to let gcc tell us what type of jump it had
to use depending on how far the target of the branch is.

I suspect this would be inherently tricky. If someone is ready to do
this and tells me "yes, it will be there in 1 month", I am more than
ready to switch my markers to this and help, but since the core of my
work is kernel tracing, I don't have the time nor the ressources to
tackle this problem.

In the event that someone answers "we'll do this in the following 3
years", I might consider to change the if (immediate(var)) into an
immediate_if (var) so we can later proceed to the change with simple
ifdefs without rewriting all the kernel code that would use it.

Mathieu

--
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68