4 ms·

I am wondering: Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a wa

I am wondering: Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a way that is not possible with static code? Does anybody know? I would be very interested in an example.

deleted 5y ago
[deleted]
FastEatSlow 5y ago
It doesn't really, a NOP is equivalent to most jumps now, I'll try to dig up a source for that in a few hours. It used to be the case 10-20 years ago, I remember reading about it on an llvm thread.
neel_k 5y ago
Self-modifying code was useful for optimisation back in the 80s, but these days it's usually awful for performance (with JIT compilation as the main exception to this rule). Your CPU has an instruction cache and a data cache, and on ARM (and x86, too, but I'm not sure) these caches are not coherent. So if you modify your instruction stream with a write, you have to clear the instruction cache to ensure that your modified instructions are actually executed by the processor. If you do this a lot, this will make things S-L-O-W, because it forces you to go all the way to main memory to find the next instruction to execute. This means that if you do want to generate code at runtime, you want to batch the modifications into large groups, so that you have to invalidate the i-cache less frequently. This actually is useful -- it's what JIT compilation is! The reason that JIT can be helpful (even in statically typed languages like Java or Haskell) is that programs often get passed functions as arguments (eg, qsort in C). A static compiler can't optimise these functions much, because you have to know what the function argument will be to do much. But at runtime, you do know what the function is, and by inlining it your code can be made much faster.
- gpderetta 5y ago
  Inlining passed function pointer is not really a JIT only optimization. As long as the pointer is a constant it only requires interprocedural optimizations and/or link time optimization. The jit can help if the value of the pointer varies dynamically and in an unpredictable way (otherwise PGO would also help).
- zinxq 5y ago
  Came here to hope someone wrote this. Wasted many hours of my young life trying to figure out why my self-modifying assembler program worked perfect in the debugger but not without it.
  - bogomipz 5y ago
    Could you elaborate? I feel like the OP is saying that it works just painfully slowly but your comment/problem indicates it didn't work at all without the debugger. Can you say how these relate? Am I missing something obvious?
    - StillBored 5y ago
      Self modifying code on x86 has always been a bit microarch dependent as in the past there was a minimum distance required for the processor to notice the change. This is was one of the tricks anti piracy code used to keep people from reverse engineering it. Changes made close enough to the IP wouldn't be hazarded properly so the stale instruction would be executed anyway. If this code is run under a debugger the extra break/traps would change the behavior and the newer instruction would get executed rather than the stale one. Someone who plays with this on more recent x86's could talk about how this presumably works on modern x86's, but I would guess that if the CPU detects a hazard and has to roll back to a previous state, it probably goes into some kind of strong in order mode around the code in question. This might mean modern processors behave better than some older models, but likely there is a absolutely massive perf hit when this happens (think > 10x). On something like an arm or risc-v(?) without coherent I-D caches this "window" could basically be forever, it makes an interesting question around security because in theory its possible to have code being executed for extended periods of time which isn't actually visible anywhere due to page/cache invalidation not clearing stale cache lines.
      - bogomipz 5y ago
        This is really fascinating subject and seems like a rich area for research. I was curious about your comment regarding arm and risc-v not having coherent instruction and data caches. Is this a toggle on these chips hen for turning it on and off? I think I remember reading about some SoC that have this configurable.
- nneonneo 5y ago
  On x86 you can use self-modifying code without explicitly flushing caches. However, if you execute the modified code soon after writing it, the penalty can be tens to hundreds of cycles (source: Agner Fog’s optimization manual). ARM quite famously requires the explicit cache flush, and will usually fail to work without it. However, some emulators, e.g. QEMU, don’t require the cache flush, which can lead to confusion if you usually test on emulators.
pjc50 5y ago
Sibling answer about the cache is correct: there's very little benefit to doing this on a modern system. And it tends to trip security systems. Many exploits are some form of "trick code that wasn't self modifying into modifying itself, or jumping into this buffer in data space that I've just given you". There might be benefits to "modify-once" code in some circumstances because of how branch prediction works. If you determine that a branch is being consistently mispredicted you can speed it up by changing the code so that it is correctly predicted - invert the test, swap the branch targets, apply a prefix instruction, etc. It is not unusual to have CPU-specific bits of code gated behind a CPUID check; you could maybe gain a bit by doing the check and then hardwiring a branch or pasting the code into the middle of a loop. A related trick is the "micro-interpreter". You build a hyper-specialised language and run short programs in that - which can then use self-modification as well, because they're counted as "data" and not code. I think there was a game that used this (Flashback maybe?)
saagarjha 5y ago
Linux does this, actually. It's called "static calls", and it saves on an indirect branch by directly overwriting jmp instructions to point elsewhere: https://blog.yossarian.net/2020/12/16/Static-calls-in-Linux-5-10 https://blog.yossarian.net/2020/12/16/Static-calls-in-Linux-.... As others have mentioned, doing this repeatedly has performance implications.
jhgb 5y ago
> Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a way that is not possible with static code? That depends; how broad is your definition of "self"? Within a process, this is a fairly common approach already (JIT).

deleted 5y ago

[deleted]

FastEatSlow 5y ago

It doesn't really, a NOP is equivalent to most jumps now, I'll try to dig up a source for that in a few hours. It used to be the case 10-20 years ago, I remember reading about it on an llvm thread.

neel_k 5y ago

Self-modifying code was useful for optimisation back in the 80s, but these days it's usually awful for performance (with JIT compilation as the main exception to this rule). Your CPU has an instruction cache and a data cache, and on ARM (and x86, too, but I'm not sure) these caches are not coherent. So if you modify your instruction stream with a write, you have to clear the instruction cache to ensure that your modified instructions are actually executed by the processor. If you do this a lot, this will make things S-L-O-W, because it forces you to go all the way to main memory to find the next instruction to execute. This means that if you do want to generate code at runtime, you want to batch the modifications into large groups, so that you have to invalidate the i-cache less frequently. This actually is useful -- it's what JIT compilation is! The reason that JIT can be helpful (even in statically typed languages like Java or Haskell) is that programs often get passed functions as arguments (eg, qsort in C). A static compiler can't optimise these functions much, because you have to know what the function argument will be to do much. But at runtime, you do know what the function is, and by inlining it your code can be made much faster.

gpderetta 5y ago
Inlining passed function pointer is not really a JIT only optimization. As long as the pointer is a constant it only requires interprocedural optimizations and/or link time optimization. The jit can help if the value of the pointer varies dynamically and in an unpredictable way (otherwise PGO would also help).
zinxq 5y ago
Came here to hope someone wrote this. Wasted many hours of my young life trying to figure out why my self-modifying assembler program worked perfect in the debugger but not without it.
- bogomipz 5y ago
  Could you elaborate? I feel like the OP is saying that it works just painfully slowly but your comment/problem indicates it didn't work at all without the debugger. Can you say how these relate? Am I missing something obvious?
  - StillBored 5y ago
    Self modifying code on x86 has always been a bit microarch dependent as in the past there was a minimum distance required for the processor to notice the change. This is was one of the tricks anti piracy code used to keep people from reverse engineering it. Changes made close enough to the IP wouldn't be hazarded properly so the stale instruction would be executed anyway. If this code is run under a debugger the extra break/traps would change the behavior and the newer instruction would get executed rather than the stale one. Someone who plays with this on more recent x86's could talk about how this presumably works on modern x86's, but I would guess that if the CPU detects a hazard and has to roll back to a previous state, it probably goes into some kind of strong in order mode around the code in question. This might mean modern processors behave better than some older models, but likely there is a absolutely massive perf hit when this happens (think > 10x). On something like an arm or risc-v(?) without coherent I-D caches this "window" could basically be forever, it makes an interesting question around security because in theory its possible to have code being executed for extended periods of time which isn't actually visible anywhere due to page/cache invalidation not clearing stale cache lines.
    - bogomipz 5y ago
      This is really fascinating subject and seems like a rich area for research. I was curious about your comment regarding arm and risc-v not having coherent instruction and data caches. Is this a toggle on these chips hen for turning it on and off? I think I remember reading about some SoC that have this configurable.
nneonneo 5y ago
On x86 you can use self-modifying code without explicitly flushing caches. However, if you execute the modified code soon after writing it, the penalty can be tens to hundreds of cycles (source: Agner Fog’s optimization manual). ARM quite famously requires the explicit cache flush, and will usually fail to work without it. However, some emulators, e.g. QEMU, don’t require the cache flush, which can lead to confusion if you usually test on emulators.

pjc50 5y ago

Sibling answer about the cache is correct: there's very little benefit to doing this on a modern system. And it tends to trip security systems. Many exploits are some form of "trick code that wasn't self modifying into modifying itself, or jumping into this buffer in data space that I've just given you". There might be benefits to "modify-once" code in some circumstances because of how branch prediction works. If you determine that a branch is being consistently mispredicted you can speed it up by changing the code so that it is correctly predicted - invert the test, swap the branch targets, apply a prefix instruction, etc. It is not unusual to have CPU-specific bits of code gated behind a CPUID check; you could maybe gain a bit by doing the check and then hardwiring a branch or pasting the code into the middle of a loop. A related trick is the "micro-interpreter". You build a hyper-specialised language and run short programs in that - which can then use self-modification as well, because they're counted as "data" and not code. I think there was a game that used this (Flashback maybe?)

saagarjha 5y ago

Linux does this, actually. It's called "static calls", and it saves on an indirect branch by directly overwriting jmp instructions to point elsewhere: https://blog.yossarian.net/2020/12/16/Static-calls-in-Linux-5-10 https://blog.yossarian.net/2020/12/16/Static-calls-in-Linux-.... As others have mentioned, doing this repeatedly has performance implications.

jhgb 5y ago

> Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a way that is not possible with static code? That depends; how broad is your definition of "self"? Within a process, this is a fairly common approach already (JIT).