473,324 Members | 2,268 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Example of the optimiser recognising a pattern


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
Jun 27 '08 #1
8 1503
On May 2, 10:59*pm, Tomás Ó hÉilidhe <t...@lavabit.comwrote:
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.
Jun 27 '08 #2
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.
Jun 27 '08 #3
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.

Jun 27 '08 #4

"Tomás Ó hÉilidhe" <to*@lavabit.comwrote in message
news:85**********************************@l42g2000 hsc.googlegroups.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


Jun 27 '08 #5
On May 3, 11:12 am, "Bartc" <b...@freeuk.comwrote:
"Tomás Ó hÉilidhe" <t...@lavabit.comwrote in messagenews:85**********************************@l 42g2000hsc.googlegroups.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("unsigned int context: %u, %u\n", c & ~0x8u, c & 0xF7u); /*
different output */
printf("unsigned 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.
Jun 27 '08 #6
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
Jun 27 '08 #7
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.
Jun 27 '08 #8
vi******@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
Jun 27 '08 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: gsv2com | last post by:
One of my weaknesses has always been pattern matching. Something I definitely need to study up on and maybe you guys can give me a pointer here. I'm looking to remove all of this code and just...
5
by: Craig O'Shannessy | last post by:
Hi everyone, My performance on a big mission critical system has recently collapsed, and I've finally traced it down to the postgresql optimiser I think. I'm running postgresql-7.2.1-2PGDG ...
2
by: Paul Reddin | last post by:
Hi, I'm sure I read somewhere that the SELECTIVITY Clause cannot be used with static SQL, can anybody confirm/deny this? Also, at the risk of a philosophical war, when will the optimizer...
11
by: pemo | last post by:
If you were to compile/run the code below, and get the result '30', I'd be very interested to know what compiler you're using - and its optimisation settings #include <stdio.h> int test(int...
3
by: John Salerno | last post by:
Ok, I've been staring at this and figuring it out for a while. I'm close to getting it, but I'm confused by the examples: (?(id/name)yes-pattern|no-pattern) Will try to match with yes-pattern if...
31
by: Dave S | last post by:
Hi All, I have been given some code to wok on. It relies heavily on the optimiser to run at the correct speed. With this in mind I have been loking through it to see if I can help it out a bit. I...
4
by: Aaron Gray | last post by:
I am after opend source small, middle or large example programs thay use MVC pattern coded Javascript. Many thanks in advance, Aaron
5
by: Marc Gravell | last post by:
If you cannot understand such a simple post, then you don't understand Oh come on, that is a weak strawman even for you! Show me one way in which my post can be interpreted as that; then look at...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.