Misbehaving >> and >>> operators. about cascade HOT 8 CLOSED

Confirmed. This is a bug in a couple of places:

1. The implementation of operator>>>
2. Sign inference for operator>>>

Both should be pretty quick to fix.

from cascade.

(I know where the fix needs to go, but I'm a bit busy this week. If anyone wants to dive in, I can point them in the right direction.)

from cascade.

Hey @eschkufz, I would love to take a crack at this. From what I can tell, The change will be in https://bit.ly/2rmh5bD, but I am not sure what a lot of the variables mean, probably because there are some architectural terms that I am unfamiliar with. I would love some pointers!

from cascade.

Great! Here's what you need to know ---

The bug is in two places. I'll start with the file you're looking at, since that's where most of the work needs to be done.

BitsBase is the core data structure that cascade uses for performing bit-arithmetic. Since shift arithmetic right isn't working, this is the natural place to look. Both shift arithmetic (bitwise_sar) and shift logical (bitwise_slr) right end up calling the method you're looking at (bitwise_sxr_const --- the x is for 'either l or a', arith is true if we're handling the arithmetic case, and the const means by a constant value, samt). All of the methods in this class take a trailing argument, res which is a reference to the BitsBase object to store their result in.

BitsBase objects have a few members you need to worry about: size_ is the bit-width of the object, signed_ is a flag indicating whether the value is signed, and val_ which is the underlying storage. val_ is templated on T, the native word-size of your machine. In most cases this will be 64 or 32. The important thing to remember is that it will often hold more bits than are necessary. For example: on a 64-bit machine, val_ would be two elements long to store a value of 108 bits. The top 20 bits would go unused. We'll worry about how size_ and signed_ are set. For now, just assume that they're correct.

The first thing bitwise_sxr_const does (after bailing out for the easy case where shift is zero) is calculate hob (high-order-bit). This is true if we're in the arithmetic case, and the highest order (size_-1'th) bit of val_ is true. If this flag is true, we'll need to pad the upper bits of res with 1s after we're done shifting.

At this point there's another corner case missing. If samt is greater or equal to size_ we'll need to replace the entire value with zeros or ones if hob is true. We should add a test case for this (more on that below).

The shift happens next on lines 1291-1298. We start with the lowest order word in val_ and start moving bits into it from the higher-order words that they appear in. There's a special case where bamt == 0 (the number of bits we're shifting evenly divides the word size of val_). In this case, we can copy words one at a time. Otherwise, each low-order word will be composed of bits from two higher-order words.

Once that's done, we have the corner case on lines 1300-1304. We've made it to the highest-order word in res which will contain bits from the original value. Everything above those bits should either be 0 or 1 depending on the value of hob. This is where the bug is. In the hob is true case, we're writing 1s in the space above where the shifted value began, rather than where it ended up.

The final corner case on lines 1306-1308 is correct. All that's happening here is that we're wholesale padding words with 1s and 0s as necessary. Finally, the call to trim() masks out any bits in val_ above the size_ of the value. This is necessary in the hob is true case, where we've filled up the highest order bits of val_ with 1s.

That's it for BitsBase. Next we need to take a look at Evaluate (src/verilog/analyze/evaluate.h). This class is responsible for making calls into BitsBase and setting signed_ and size_ appropriately. Currently, it's incorrectly concluding that any expression of the form (x >>> k) is unsigned. So even once we fix the bug in BitsBase, cascade is going to print out 4294967295 rather than -1.

The Verilog spec defines a two pass algorithm for determining sign and bit-width for expressions. The passes are called 'self-determination' and 'context-determination'. You can think of self-determination as the base case: we decide width and size based only on the operators and operands of an expression. Context-determination is the inductive case: we update those values based on the expressions that those expressions appear inside of. Fortunately, the bug is in self-determination, which is the easier case.

If you look at lines 587-594, you'll see the problem. The base case for every bit shift operation is to conclude unsigned and the width of the left-hand-side operand. Per the spec, what we should be doing is concluding that the sign of the expression is the same as the sign of the left-hand-side operand. So these lines should become:

    case BinaryExpression::GGT:
    case BinaryExpression::LLT:
      w = be->get_lhs()->bit_val_[0].size();
      s = be->get_lhs()->bit_val[0].is_signed();
      break;
    case BinaryExpression::TTIMES:
      w = be->get_lhs()->bit_val_[0].size();
      s = false;
      break;
    case BinaryExpression::GGGT:
    case BinaryExpression::LLLT:
      w = be->get_lhs()->bit_val_[0].size();
      s = be->get_lhs()->bit_val[0].is_signed();
      break;

That should do it! Once you've made the changes, you'll want to add some test cases.

1. Add a .v file to data/test/simple. Lately I've been naming test cases after the issues that they relate to (data/test/simple/issue_41.v), but it really doesn't matter.
2. Add a line to test/simple.cc corresponding to your new test case. The format of the file should be pretty straightforward. You add the name of the file you want to test, and the output that you expect.

Once you've done this, running make test should invoke your test.

Hope that helps! I'll be around email all week if something isn't making sense.

from cascade.

Hello Eric,

Thank you so much for such a detailed and complete response. I have been working on this and am running into a couple of issues, and might post some questions if they don't get resolved. Thanks again!!

from cascade.

Hey Eric,

While trying to fix this, there are still just a couple of things I am unsure about. I have put some code on the branch issue_41.

Ok, so here is my understanding of the bugs:

1. Sign inference is broken in evaluate.cc, which makes bitshift operators in bits.h break.
2. In line 1301, we have the line

res.val_[w++] = (bamt == 0) ? T(-1) : ((val_.back() >> bamt) | (mask << mamt));

Now looking at issue_41.v, where all registers are 68 bits, val_.back() will only contain 5 bits. In the case of the wire minus_one, the value of val_back() will be 0x000000000000001F. Thus, simply right shifting by 6 will make this 0. Therefore, first I left shift everything and right shift it again and thus store
v = 0xFFFFFFFFFFFFFFFF.

After this, I thought line 1305 on the branch issue_41 will do what we expect, but that does not seem to be the case. The output in the wire six_bits is expected to be -1, but instead it is -9223372036854775809, which in binary is 11110111111111111111111111111111111111111111111111111111111111111111. I am not sure where that 0 is coming from.

I am probably missing something quite simple here!

from cascade.

Actually, can you please add me as a collaborator so that I can push my changes to a separate branch?

from cascade.

Never mind, I see that the recommended way to do this is to fork the repo. I will post a link in a couple of hours. Sorry for the spam.

from cascade.