[PATCH][GCC] Algorithmic optimization in match and simplify

[Andre Vieira]

Two new algorithmic optimisations:
   1.((X op0 C0) op1 C1) op2 C2)
     with op0 = {&, >>, <<}, op1 = {|,^}, op2 = {|,^} and op1 != op2
     zero_mask has 1's for all bits that are sure to be 0 in (X op0 C0)
     and 0's otherwise.
     if (op1 == '^') C1 &= ~C2 (Only changed if actually emitted)
     if ((C1 & ~zero_mask) == 0) then emit (X op0 C0) op2 (C1 op2 C2)
     if ((C2 & ~zero_mask) == 0) then emit (X op0 C0) op1 (C1 op2 C2)
   2. (X {|,^,&} C0) {<<,>>} C1 -> (X {<<,>>} C1) {|,^,&} (C0 {<<,>>} C1)


This patch does two algorithmic optimisations that target patterns like:
(((x << 24) | 0x00FFFFFF) ^ 0xFF000000) and ((x ^ 0x40000002) >> 1) | 
0x80000000.

The transformation uses the knowledge of which bits are zero after 
operations like (X {&,<<,(unsigned)>>}) to combine constants, reducing 
run-time operations.
The two examples above would be transformed into (X << 24) ^ 0xFFFFFFFF 
and (X >> 1) ^ 0xa0000001 respectively.


gcc/ChangeLog:

2015-08-03  Andre Vieira  <andre.simoesdiasvieira@arm.com>

   * match.pd: Added new patterns:
     ((X {&,<<,>>} C0) {|,^} C1) {^,|} C2)
     (X {|,^,&} C0) {<<,>>} C1 -> (X {<<,>>} C1) {|,^,&} (C0 {<<,>>} C1)

gcc/testsuite/ChangeLog:

2015-08-03  Andre Vieira  <andre.simoesdiasvieira@arm.com>

   * gcc.dg/tree-ssa/forwprop-33.c: New test.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-algorithmic-optimization.patch
Type: text/x-patch
Size: 4398 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150828/b5104586/attachment.bin>