#2458 shift operation gives incorrect error and emits bad code

[Peter Dons Tychsen]

Hello SDCC team,

Found this in some of my code:

uint32_t global;
void func(void)
{
  uint8_t i=18;
  uint8_t bit;

  bit = (BOOL)((global & (((uint32_t)1) << i)) && TRUE);
  if(bit)
  {
      while(1);
  }

Compiling this gives: "unreachable code"

The reason is the "i" variable which is only 8 bit. However, as the "1" is already casted, this should not matter.

What is worse, if the "i" variable is not a constant (e.g. comes from a function call), the code can build, but bad code is emitted. All bits above 8 are broken.

I think there are some general rules for casts that do not work here.

Thanks,

/pedro

[Peter Dons Tychsen]

I should probably mention i only tried this for the STM8 target.

[Peter Dons Tychsen]

And BOOL=uint8_t and TRUE=1

[Ben Shi]

I did not see any bugs and will explain it in details.

First,

typedef unsigned long uint32_t;
typedef unsigned char uint8_t;
typedef unsigned char BOOL;
#define TRUE 1
uint32_t global;
void func(void)
{
  uint8_t i=18;
  uint8_t bit;

  bit = (BOOL)((global & (((uint32_t)1) << i)) && TRUE);
  if(bit)
  {
      while(1);
  }
  global = 23;
}

The expression bit = (BOOL)((global & (((uint32_t)1) << i)) && TRUE) is optimized by copy propagation and constant folding, so it becomes bit = 0, and the code changes to

typedef unsigned long uint32_t;
typedef unsigned char uint8_t;
typedef unsigned char BOOL;
#define TRUE 1
uint32_t global;
void func(void)
{
  uint8_t i=18;
  uint8_t bit;

  bit = 0;
  if(bit)
  {
      while(1);
  }
  global = 23;
}

Of course the while(1) is unreachable.

[Ben Shi]

The second case,

typedef unsigned long uint32_t;
typedef unsigned char uint8_t;
typedef unsigned char BOOL;
typedef unsigned long BOOL32;

#define TRUE 1

uint32_t global;

uint8_t get(void);

void func (void)
{
  uint8_t bit;
  uint32_t bit32;

  bit = (BOOL)((global & (((uint32_t)1) << get ())) && TRUE);
  bit32 = (BOOL32)((global & (((uint32_t)1) << get ())) && TRUE);

  if(bit)
  {
      while(1);
  }
  global = bit32;
}

Though upper bytes are omitted in calculation of the variable bit, but they are correctly processed in bit32.

This is also due to some earlier arch-independant optimization. Since omitting upper bytes does not affect final result.

[Ben Shi]

Sorry, a typo. It should be constant propagation and constant folding above.

[Ben Shi]

I suggest you build your program with

sdcc a.c -c -mstm8 --dump-ast --dump-i-code

and check what happens in each optimization step.

[Maarten Brock]

Ben,

I think Peter is right and this really is a bug.

uint32_t global;
uint8_t i=18;
uint8_t bit;

bit = (BOOL)((global & (((uint32_t)1) << i)) && TRUE);

Changes into:

bit = (BOOL)((global & (((uint32_t)1) << (uint8_t)18)) && TRUE);

Then it should upcast to uint32_t and change into:

bit = (BOOL)((global & (((uint32_t)1) << (uint32_t)18)) && TRUE);

And thus:

bit = (BOOL)((global & (uint32_t)0x00040000) && TRUE);

[Ben Shi]

OK. I will check it later.

[Peter Dons Tychsen]

Yes, it is exactly the missing upcast that causes this IMHO.

[Maarten Brock]

This should not be fixed by adding the upcast in the frontend as that will only create a bigger register pressure. All useful shift values fit in a uint8_t type. All optimizations and all backends should be smart enough to handle this special case.

[Peter Dons Tychsen]

OK i think i figured out whats wrong here (i hope) :-)

It was not the missing upcast of "i" that caused the problem, but a simple bug in the AST tree generator. It cannot be fixed in the back-end as the bug is not where we thought it was.

Consider the simpler code:

static unsigned char i;
static unsigned char bit;
void main(void)
{
  bit = (((unsigned long)1) << i);
}

This yields the following AST:

FUNCTION (_main=02CBECC0) type (void fixed) args (void)
tree (02CBEC30) not decorated
(null):0:{ L1 B0
../bin/main.c:5:  ASSIGN(=) (02CBDC88) type (unsigned-char fixed)
../bin/main.c:5:    SYMBOL (L0 B0 bit=02CBC588 @ 02CBBB10) type (unsigned-char f
ixed)
../bin/main.c:5:    LEFT_SHIFT (02CBDBF8) type (unsigned-char register)
../bin/main.c:5:      CONSTANT (02CBE460) value = 1, 0x1, 1.000000 type (unsigne
d-char literal)
../bin/main.c:5:      SYMBOL (L0 B0 i=02CBDB68 @ 02CBB3C8) type (unsigned-char f
ixed)
(null):0:}

Note the the constant "1" has been recorded as being "unsigned-char literal". At this point the optimizers will later (of-course) make dog-food of it and optimize it away. No matter what the backend does, the code is dead at this point, and all bits above bit 7 must and will be dead.

The reason it fails is that "((unsigned long)1)" is a CAST op which is then replaced completely with a new entry. This happens in "case CAST:" at "SDCCast" line 4317. The comment also states " if the right is a literal replace the tree". This is all fine. It creates a new tree element which becomes the left side of the "LEFT_OP" element later.

Now the code does this:

/* After decorating the left branch there's type information available
       in tree->left->?type. If the op is e.g. '=' we extract the type
       information from there and propagate it to the right branch. */
    resultTypeProp = getLeftResultType (tree, resultTypeProp);

It expects the getLeftResultType() to get the left result type of the newly replaced "left". This is where the bug is. getLeftResultType() does not treat SHIFT ops correctly and just returns the type of the current tree entry which is wrong. Now "unsigned char" is returned and not the "unsigned long" as was intended. getLeftResultType() simply does not work for this type.

A small patch to fixup getLeftResultType() makes it all work.

The reason it does not fail with variable entries is that this does not cause the tree replacement, so the type is calculated around a "CAST" op instead which does work in getLeftResultType().

Here is a patch with tests that fixes it up.

It does not AFAIK increase the register pressure for other cases other than this special case where more registers (for long instead of char) might be need, which is completely valid as the calculation would fail badly (and does) without it.

Please review/apply/reject.

Thanks,

/pedro

[Peter Dons Tychsen]

Please not that the example code above in itself does not make sense. Its only to debug the AST problem. For the code to make sense it looks like this:

static unsigned char i;
static unsigned char bit;
void main(void)
{
  bit = (((unsigned long)1) << i) && 1;
}

This makes setting "bit" possible. The bug in the tree generator is however just a visible with any of them.

[Maarten Brock]

I disagree with your conclusion here. There is a huge difference between the last two example codes.

bit = (((unsigned long)1) << i);

equals

bit = (((unsigned char)1) << i);

But that is not the case for

bit = (((unsigned long)1) << i) && 1;

and

bit = (((unsigned char)1) << i) && 1;

[Peter Dons Tychsen]

I disagree with your conclusion here. There is a huge difference between the last two example >>codes.

Exactly. I know. That is why i wrote the extra comment. The first and second case gives a completely different result, and the bug is only visible to the user in the second. I just used these examples for debugging as the initial steps and the problematic AST generation is the same.

Sorry for the confusion. I did not think straight when i posted it as it allowed me to debug the problem in simpler code, but does not expose the bug to the user. I know.

Use the test case to view the bug properly and forget the other examples:

static unsigned long testLong = 0x40000;
static unsigned char testResult;
static unsigned char testShift = 0x12;

void testBug (void)
{
  testResult = ((((unsigned long)1) << testShift) & testLong) && 1; 
  ASSERT(testResult);  
}

Without the fix this fails because of the "1" never getting cast properly. With the fix this works and the AST tree is now the same, but showing the constant as "unsigned long" as it should be.

Please review the patch if possible.

Thanks,

/pedro

[Peter Dons Tychsen]

Also, i am not sure why you write:

Quote:

bit = (((unsigned long)1) << i);

equals

bit = (((unsigned char)1) << i);

They are not the same as "i" is also a char type. Only the top one will work. Either "i" has to be unsigned long or the cast needs to be (unsigned long). Something has to promote the result to "unsigned long", or the expression will fail. I think this is in its essence what this bug is about.

edit: this does however depend on what "bit" is. If its also char, then you are right....

Thanks,

/pedro

[Maarten Brock]

Peter,

I'm glad you found out yourself that the wrong example depends on the type of bit. You made it an unsigned char and the fact that you name it bit does not turn it into a bool. Had you changed its type I would not have complained.

Maarten

[Peter Dons Tychsen]

All tests seem to be OK with this change.

[Philipp Klaus Krause]

Do we have regression tests for all the cases discussed here?

Philipp

[Peter Dons Tychsen]

There really is only one case here. I again apolagize for confusing with my other examples. Please disregard them. I am not aware of any other case with problems.

There is only one case, one test case and one fix (in this report).

Any bugs that look like this, but are not this should go in another report.

Thanks,

/pedro

[Ben Shi]

Dear Peter,

Thanks for helping improving SDCC recently.

I would like to explain something to you,

1. There is a test precedure called regression test and there are thounsands of c files in sdcc/support/regression/tests . All of them must pass before each commit to the SVN repository. You can do it by

cd sdcc
./configure
make all
make install
cd support/regression/
make test-ports

You may get "warnings" and "non-fatal internal compiler errors" while during the test, however we asset if it is OK by if there are "failures" or not. If there is no "failure" then we can commit.

1. This bug might be related to the && operation not the shift operation. For example,

char s;
int q;

void asdas(void)
{
  s = ((char) (q + 0xa000)) && 1;
}

sdcc test.c -c --dump-ast

FUNCTION (_asdas=0x7fc9baebbe20) type (void fixed) args (void)
tree (0x7fc9baebbd80) not decorated
(null):0:{ L1 B0
a.c:6:  ASSIGN(=) (0x7fc9baebb210) type (char fixed)
a.c:6:    SYMBOL (L0 B0 s=0x7fc9baeb9cc0 @ 0x7fc9baeb8ff0) type (char fixed)
a.c:6:    ANDAND (0x7fc9baebb170) type (char fixed)
a.c:6:      CAST (0x7fc9baebaeb0) from type (char register) to type (char fixed)
a.c:6:        ADD (0x7fc9baebad70) type (char register)
a.c:6:          CAST (0x7fc9baebb480) from type (int fixed) to type (char fixed)
a.c:6:            SYMBOL (L0 B0 q=0x7fc9baebaab0 @ 0x7fc9baeb9520) type (int fixed)
a.c:6:          CONSTANT (0x7fc9baebb650) value = 0, 0x0, 0.000000 type (unsigned-char literal)
a.c:6:      CONSTANT (0x7fc9baebb0d0) value = 1, 0x1, 1.000000 type (const-unsigned-char literal)
(null):0:}

You can see the 0xa000 is also casted to 0x00 as a char value.

[Ben Shi]

I have not found the root cause of this bug. But I guess taking a deep look into the function decorateType() might be necessary.

[Ben Shi]

Dear Peter,

Besides all regression test cases pass, space/time efficiency is also a concern before commit to SVN. A large increment in bytes / ticks cost in the regression test is not acceptable.

[Peter Dons Tychsen]

Hi Ben,

There is a test precedure called regression test and there are thounsands of c files in sdcc/support/regression/tests . All of them must pass before each commit to the SVN repository. You can do it by

That is why i sent in a patch containing a test case and wrote "All tests seem to be OK with this change". I did not use a magic wand to state this :-). I ran all tests on Linux and Cygwin.

Besides all regression test cases pass, space/time efficiency is also a concern before commit to SVN. A large increment in bytes / ticks cost in the regression test is not acceptable.

I will double check the results for this before/after the change.

s = ((char) (q + 0xa000)) && 1;

No, that is a completely different case. The cast to "char" causes right propagation of the type "char" so all the elements in (q + 0xa000) are downgraded. That is not the case in my example.

This bug might be related to the && operation not the shift operation. For example,
I do not think this is the case, as problem seems very specific to the replacement of the literal constant that is casted in combination with a shift.

I have not found the root cause of this bug. But I guess taking a deep look into the function decorateType() might be necessary.

Have you read the analysis of "getLeftResultType()" i tried to make above? I might very well have missed something (likely :-)), but something is wrong with either this functions comments or its implementation. The comments state that its purpose is to return the type of left side, but it does not do this for all types including the "shift opererators". Either the function fails or its comments do.

Thanks,

/pedro