Common sub-expression elimination and loop-invariant code motion.

[plusvic]

In complex YARA conditions there are many cases in which the same sub-expression is repeated more than once, and its results could be reused instead of re-computed. For instance, consider this condition:

uint16(0) == 0x15FF or uint16(0) == 0x25FF 

The sub-expression uint16(0) is used twice, and the current implementation calls the uint16 function twice with the same argument. However, the result from the first invocation could be stored in a temporary variable and reused when uint16 is called for the second time, instead of invoking the function again, which is an expensive operation.

Additionally, when a sub-expression is contained in the body of a loop, it can be moved out of the loop if the sub-expression doesn't depend on the loop variables. For instance,

for any offset in (0..filesize-1): (
   ((uint16(offset) == 0x15FF or uint16(offset) == 0x25FF) and 
      uint32(offset+2) == pe.sections[0].virtual_address + pe.image_base)
)

In the example above, the sub-expression pe.sections[0].virtual_address+pe.image_base doesn't depend on the offset variable, and therefore produces the same result on each loop iteration. This expression could be evaluated once outside the loop, and its value reused inside the loop.

Common sub-expression elimination (CSE) and loop-invariant code motion (LICM) are well-known techniques used in compilers.