Example of the optimiser recognising a pattern

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

I'm working with a microcontroller at the moment that has a single
instruction for clearing a bit in a byte.

I started off with the following line of code:

x &= ~0x8u; /* Clear the 4th bit */

But then I changed it to the following because I thought I might get
more efficient assembler out of it:

x &= 0xF7u; /* Clear the 4th bit */

Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.

Anyway just thought I'd give an example of someone winding up with
less efficient code when their aim was to make the code more
efficient :-D

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

Re: Example of the optimiser recognising a pattern

On May 2, 10:59 pm, Tomás Ó hÉilidhe <t...@lavabit.c omwrote:

Suprisingly, the compiler produced more efficient code for the latter,

Obviously that should be "former". That's what I get for writing
constructs that I don't use in my everyday speech.

[Ian Collins]

Re: Example of the optimiser recognising a pattern

Tomás Ó hÉilidhe wrote:

I'm working with a microcontroller at the moment that has a single
instruction for clearing a bit in a byte.
>
I started off with the following line of code:
>
x &= ~0x8u; /* Clear the 4th bit */
>
But then I changed it to the following because I thought I might get
more efficient assembler out of it:
>
x &= 0xF7u; /* Clear the 4th bit */
>
Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.
>

Odd, is x an unsigned 8 bit type? If so, the two expressions should
generate identical code.

--
Ian Collins.

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

Re: Example of the optimiser recognising a pattern

Ian Collins:

Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.

>
Odd, is x an unsigned 8 bit type?

Yes, it is.

If so, the two expressions should
generate identical code.

If I do:

y &= ~0x08u;

then I get the following assembler:

BCF y, 0x3 /* Clear the 4th bit of y */

If I do:

y &= 0x7Fu;

then I get the following assembler:

MOVLW 0x7f /* Load the accumulator with 0x7f */
ANDWF y, F /* AND y with the accumulator
and store the result in y */

The former is one instruction, while the latter is two, and as all
instructions take the same amount of CPU cycles, the latter version is
exactly twice as slow.

Not only that, but things get even worse if you do the following:

if (whatever) y &= ~0x08u;

versus:

if (whatever) y &= 0x7Fu;

On the PIC micrcontroller, there's an instruction that does the
following: "Check whether the last arithmetic operation resulted in
zero, and if so, skip the next instruction". Since the former version
is comprised of a single instruction, this single instruction can be
skipped by the conditional. However, in the case of the latter form
which consists of two instructions, there has to be an interleaving
goto statement. Result: WAY slower.

[Bartc]

Re: Example of the optimiser recognising a pattern


"Tomás Ó hÉilidhe" <toe@lavabit.co mwrote in message
news:851bdee4-c15c-4e07-bc62-166b346d2651@l4 2g2000hsc.googl egroups.com...

Ian Collins:
>

Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.

>>
>Odd, is x an unsigned 8 bit type?

>
>
Yes, it is.
>
>

>If so, the two expressions should
>generate identical code.

>
>
If I do:
>
y &= ~0x08u;
>
then I get the following assembler:
>
BCF y, 0x3 /* Clear the 4th bit of y */
>
If I do:
>
y &= 0x7Fu;
>
then I get the following assembler:
>
MOVLW 0x7f /* Load the accumulator with 0x7f */
ANDWF y, F /* AND y with the accumulator
and store the result in y */

(You meant 0xF7 here?)

Typically a compiler will reduce ~0x8u down to 0xF7u anyway, so there
shouldn't be a difference.

Unless ~0x8u actually generates 0xFFF7u? What's the default uint size on
this compiler? What does y &= 0xFFF7u compile to, if anything? What about y
&= 0x0A?

Or possibly it's just a quirk in the compiler's optimiser. File a bug
report.

-- Bartc

[vippstar@gmail.com]

Re: Example of the optimiser recognising a pattern

On May 3, 11:12 am, "Bartc" <b...@freeuk.co mwrote:

"Tomás Ó hÉilidhe" <t...@lavabit.c omwrote in messagenews:851 bdee4-c15c-4e07-bc62-166b346d2651@l4 2g2000hsc.googl egroups.com...
>
>
>

Ian Collins:

>

Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.

>

Odd, is x an unsigned 8 bit type?

>

Yes, it is.

>

If so, the two expressions should
generate identical code.

>

If I do:

>

y &= ~0x08u;

>

then I get the following assembler:

>

BCF y, 0x3 /* Clear the 4th bit of y */

>

If I do:

>

y &= 0x7Fu;

>

then I get the following assembler:

>

MOVLW 0x7f /* Load the accumulator with 0x7f */
ANDWF y, F /* AND y with the accumulator
and store the result in y */

>
(You meant 0xF7 here?)
>
Typically a compiler will reduce ~0x8u down to 0xF7u anyway, so there
shouldn't be a difference.
>
Unless ~0x8u actually generates 0xFFF7u? What's the default uint size on

Yes, ~0x8u, 0x8u would be 0xF...7 and not 0xF7. (I chose to put
ellipsis and not a number of F's because it's not possible to know how
many F's)
In the latter, 0xF7 would be int, and thus 0x00F7 and not 0xFFF7. Most
likely what the optimizer actually recognizes is all bits except one.
In the latter case it's not clear whether you're trying to clear the
4'th bit only or the other bits too (9-16th bit)

To understand,

unsigned int c;
c = UINT_MAX; /* all bits 1 */
printf("unsigne d int context: %u, %u\n", c & ~0x8u, c & 0xF7u); /*
different output */
printf("unsigne d char context: %hhu, %hhu\n", (unsigned char)(c &
~0x8u), (unsigned char)(c & 0xF7u)); /* same output */


So they are different, depending on type context. The compiler
optimizer just isn't that advanced to recognize that.

[Andrey Tarasevich]

Re: Example of the optimiser recognising a pattern

Tomás Ó hÉilidhe wrote:

I'm working with a microcontroller at the moment that has a single
instruction for clearing a bit in a byte.
>
I started off with the following line of code:
>
x &= ~0x8u; /* Clear the 4th bit */
>
But then I changed it to the following because I thought I might get
more efficient assembler out of it:
>
x &= 0xF7u; /* Clear the 4th bit */
>
Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.
>
Anyway just thought I'd give an example of someone winding up with
less efficient code when their aim was to make the code more
efficient :-D

What the other are saying here is that if size of 'int' on your platform is
greater than 1 byte, then these two pieces of code are not equivalent.

In the first one

x &= ~0x8u;

the rhs evaluates to an 'int'-sized 0xF...F7. The optimizer might be smart
enough to understand that the effect of the '&=' operation is limited to the
least-significant byte of 'x' and translate it into a [presumedly more
efficient] byte-sized machine operation, which is what you see in practice.

In the second one

x &= 0xF7u;

the effect of the '&=' operation applies to _all_ bytes if 'x' (if there are
more than 1), which means that a word-size operation might be more efficient in
this case.

Just for the sake of experiment, could you try

x &= 0xFFFF7u;

(i.e. add as many 'F's as necessary to make the rhs constant to "cover" the
entire with of 'x') and see what code it generates?

--
Best regards,
Andrey Tarasevich

[vippstar@gmail.com]

Re: Example of the optimiser recognising a pattern

On May 3, 7:45 pm, Andrey Tarasevich <andreytarasev. ..@hotmail.com>
wrote:

Tomás Ó hÉilidhe wrote:

I'm working with a microcontroller at the moment that has a single
instruction for clearing a bit in a byte.

>

I started off with the following line of code:

>

x &= ~0x8u; /* Clear the 4th bit */

>

But then I changed it to the following because I thought I might get
more efficient assembler out of it:

>

x &= 0xF7u; /* Clear the 4th bit */

>

Suprisingly, the compiler produced more efficient code for the latter,
presumably because it recognises the pattern of " x &= ~y" for
clearing a single bit.

>

Anyway just thought I'd give an example of someone winding up with
less efficient code when their aim was to make the code more
efficient :-D

>
What the other are saying here is that if size of 'int' on your platform is
greater than 1 byte, then these two pieces of code are not equivalent.

Actually that's not the case.
It doesn't matter whether int is 1 byte or more, since int is at least
16 bits, the operators are well-defined, et cetera.

[Andrey Tarasevich]

Re: Example of the optimiser recognising a pattern

vippstar@gmail. com wrote:

>>I'm working with a microcontroller at the moment that has a single
>>instruction for clearing a bit in a byte.
>>I started off with the following line of code:
>> x &= ~0x8u; /* Clear the 4th bit */
>>But then I changed it to the following because I thought I might get
>>more efficient assembler out of it:
>> x &= 0xF7u; /* Clear the 4th bit */
>>Suprisingly , the compiler produced more efficient code for the latter,
>>presumably because it recognises the pattern of " x &= ~y" for
>>clearing a single bit.
>>Anyway just thought I'd give an example of someone winding up with
>>less efficient code when their aim was to make the code more
>>efficient :-D

>What the other are saying here is that if size of 'int' on your platform is
>greater than 1 byte, then these two pieces of code are not equivalent.

Actually that's not the case.
It doesn't matter whether int is 1 byte or more, since int is at least
16 bits, the operators are well-defined, et cetera.

Yes and no.

When I'm taking about 'byte' in this case, I'm referring to the minimal unit of
storage the OP's platform can handle with a single application of its 'BCF'
machine operation. If the size of 'x' is small enough to be processed by a
single 'BCF', then, as the OP said already, the optimizer should have generated
a 'BCF' in both cases (relying on the OP's assertion that this is more efficient).

Meanwhile, you must be referring to the C 'byte'. You are right, but I'd note
that it is pretty safe to assume that the two are the same, especially taking
into account the fact that the OP already stated that 'x' is actually an
unsigned _8-bit_ value.

If we take into account that lhs operand is in fact an 8-bit value, then the two
original operations are equivalent and the optimizer's behavior does indeed
reveal a deficiency.

--
Best regards,
Andrey Tarasevich