bluespec.com Forum Index bluespec.com
Bluespec Forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Convert values containing don't-cares during elaboration

 
Post new topic   Reply to topic    bluespec.com Forum Index -> Designing with BSV's Rules, Interfaces, ...
View previous topic :: View next topic  
Author Message
lirio



Joined: 04 Sep 2008
Posts: 1

PostPosted: Mon Nov 11, 2013 11:08 am    Post subject: Convert values containing don't-cares during elaboration Reply with quote

Hi all,

(Note: I am posting on behalf of one of our students - "matias" - which is currently waiting approval of his registration in the forum)

We need to interface with an Altera module (alt_sourceprobe) which only accepts an initial value constant (Verilog parameter) provided as a string containing hex digits.

In principle, we could ask the user of our Bluespec module to pass the initial value as a String, but it would be cumbersome, because it does not allow the Bluespec compiler to do static type checking of these values.

We want to be able to pass any type belonging to the Bits typeclass. So far so good, we can pack() the value and convert it to a hex string using a simple recursive function.

However, we have found it difficult to deal with values containing don't-care bits, because the reference guide does not explain exactly their behavior during elaboration. Don't-care bits can arise, for example, if someone instantiates our module using a "tagged Invalid" value as the initial value for a Maybe type.

I have devised the code below, which appears to work in all situations we have tested so far:

Code:

function Bit#(n) removeDontCares(Bit#(n) num);
    Bit#(n) res = 0;
    for(Integer i = 0; i < valueOf(n); i = i + 1)
        res[i] = (case(num[i]) matches
            1'b0: 1'b0;
            1'b1: 1'b1;
            default: 1'b0;
        endcase);
    return res;
endfunction

function String toHex(Bit#(n) num);
    function String f(Bit#(n) x);
        String dig[16] = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};
        return (x == 0) ? "" : f(x / 16) + dig[x % 16];
    endfunction
    Bit#(n) clean = removeDontCares(num);
    return (clean == 0) ? "0" : f(clean);
endfunction


However, I am not sure if it is guaranteed it will always work, because previous tentative implementations of "removeDontCares" initially appeared to work, but then failed in other situations. For example:

Code:
res[i] = ((num[i] == 1'b1) ? 1'b1 : 1'b0);


Using this instead of pattern matching appeared to work, but failed miserably when used on a more complex test case.

So, could my current "toHex" implementation still fail in some situation? How do don't-cares exactly work in the Bluespec compiler during the elaboration phase? Is there a way to test for them? Is there at least a guaranteed way to match e.g. 11x001 (where x is a don't-care) to either 111001 or 110001 so that some of the matches always works?

Thanks and best regards
Back to top
View user's profile Send private message
quark
Site Admin


Joined: 02 Nov 2007
Posts: 499

PostPosted: Mon Nov 11, 2013 8:17 pm    Post subject: Re: Convert values containing don't-cares during elaboration Reply with quote

Ah, good question. The issue is that, when you try to call your original "toHex" function on a packed value that contains a don't-care, the elaboration seems to take forever.

This is because of the way that don't-care values are handled. The elaborator does not pick a value for don't-care expressions; it merely optimizes some expressions that contain a don't-care value. For example, an if-statement with a don't-care branch:
Code:
if (cond) then e else ?

would simplify to just "e". And some operators are simplified if the argument is a don't care value. So, for example, "1+?" is evaluated to be "?". And similarly, "?==1" becomes just "?".

But not all expressions with a don't-care value can be reduced. And that's what's happening in your original code: you have written a recursive function that ends the recursion when the value finally reaches 0; but BSC can't figure out whether the value reaches 0, so it loops forever. Specifically, when the input is a concatenation of 1 and a don't-care:
Code:
{1'b1, _}

BSC can tell that this is not equal to 0 (because it has a non-zero bit), but when it recursively calls "f", the new value is this:
Code:
{1'b1, _} / 16

and BSC can't reduce this value any further, so it doesn't know how to resolve the branch:
Code:
return (({1'b1,_}/16) == 0) ? "" : f(…) + dig;

And so BSC has to keep the if-statement and, instead, moves on to elaborating the arms. And so BSC loops forever, because there's always a next recursive arm to elaborate.

Unfortunately, there is no way to force the don't-care value to be picked during the elaboration phase. BSC does not natively provide a function like "removeDontCares", and I cannot think of a way to write such a function. So I will submit an enhancement request to add a native function to BSC.

Your function seems to work because of a bug in BSC! As you discovered, it does not work for if-expressions. It only works for a case-expression, where the result is 1 bit, and it has a redundant default arm, and the value of the default arm is 0. If you change it at all -- no default arm, or have the default arm return 1 -- then it no longer works. Because it only works in this one situation, I am assuming that it is triggering a bug in BSC's optimizer; I will investigate. But it also means that you should NOT rely on this function to work in future versions of BSC.

There are a few workarounds that I can think of:

(1) Write a Verilog wrapper around the Altera module, and import that wrapper into BSV. The wrapper will take a Bit#(n) value, convert it to a string, and instantiate the Altera module with the string parameter. Any don't-care in the expression for the Bit#(n) parameter would be untouched during elaboration; it would get converted to a specific value when generating Verilog; and the Verilog elaboration stage would take care of converting it to a string.

This workaround requires writing the "toHex" function as a Verilog function and using it in the assignment of one parameter based on another:
Code:
module mkWrapper (…);
   parameter init_bits = 0;
   parameter init_string = toHex(init_bits);
   …
endmodule

However, I do not know if this is possible in Verilog. Some Verilog tools may complain that the assignment is not a constant expression?

(2) Use a script to post-process the generated Verilog. Specifically: import the Altera module with a Bit#(n) parameter. BSC will generate an instantiation with a specific value:
Code:
mkMod #(32`h1234) (…);

Then, use the -verilog-filter option to BSC to call a script (such as a Perl script) that will search for instantiations of the module and replace the number with a string:
Code:
mkMod #("1234") (…);

The -verilog-filter option is not documented in previous releases, although it will be documented in the next release. The argument is a command to run, which will be executed with one argument, which is the name of the generated Verilog file.

(3) You said that, in principle, you could ask the user to pass the initial value as a String, but one downside is that there would be no static check of the value. You could have the user pass a string and still have a static check if you ask the user to pass both the string and the value that the string should represent:
Code:
module mkMod #(parameter String str, parameter ty val) ()
provisos (Bits#(ty, tysize));
   Bit#(tysize) str_bits = fromHex(str);
   if (unpack(str_bits) != val)
      error("mkMod: String does not match value");
   …
endmodule

In this code, we don't try to convert an arbitrary value to bits and then the bits to a string. Therefore, we don't encounter the problem of converting a dont-care. Instead, we convert in the other direction: we write a function "fromHex" that converts the string back to bits and then we unpack those bits into a value. We use the equality operator on the original type to detect whether they represent the same value.

This still has the inconvenience of writing the String, but at least BSC will check the value for you.

(4) The problem is that the don't-care value is created in the "pack" function in the Bits instance for the type. So, how about avoiding using "pack" for the Maybe type? Instead, create a new typeclass:
Code:
typeclass ToBits#(type ty, type sz) provisos (Bits#(ty,sz));
   function Bit#(sz) toBits(ty val);
endtypeclass

In your "toHex" function, you'll use "toBits" instead of "pack". For most types, "toBits" will be the same as "pack", by writing this default instance:
Code:
instance ToBits#(ty,sz);
   function Bit#(sz) toHex(ty val);
      return pack(val);
   endfunction
endinstance

But for types that use don't-care in their packing, you can give a different conversion:
Code:
instance ToBits#(Maybe#(ty),msz)
provisos(ToBits#(ty,sz), Add#(sz,1,msz));
   function Bit#(msz) toHex(Maybe#(ty) val);
      if (val matches tagged Valid .v2)
         return {1'b1, toBits(v2)};
      else
         return 0;
   endfunction
endinstance

Anyway, those are the workarounds that I can think of. They are not pretty, I apologize. Hopefully we can add a "removeDontCares" function to BSC soon.

By the way: new BSC releases now have a Printf package. So you won't need to write the "toHex" function. You can use:
Code:
sprintf("%0d", num)

However, this also fails if the argument contains a don't-care value.
Back to top
View user's profile Send private message
matias



Joined: 11 Nov 2013
Posts: 6

PostPosted: Tue Nov 12, 2013 7:51 am    Post subject: Reply with quote

(Now posting with my own account)

Thank you very much, quark. Your suggestions are very useful.

The second suggestion seems to be the cleanest for now. Nice to know about that "-verilog-filter" option.

The first suggestion would be ever cleaner, and in fact was the first way we tried to implement it, but we were not able to implement toHex in Verilog. The problem was as you expected - the synthesis tool complains that it is not a constant expression. Maybe there are other ways to implement it which could be feasible, but we are not proficient enough in Verilog to carry this.

A "removeDontCares"-like function will certainly be a very useful addition to BSC. We are looking very forward to it. Will the beta versions (like "Bluespec-2013.05.beta2") continue to be made available here to the forum users?

Continuing the discussion about don't-cares, we have found some semantics related to them in the language that, we think, are very strange.

For instance, one of our previous attempts to implement "toHex" was something like:

Code:

function String toHex(Bit#(n) num)
provisos (
    Div#(n   , 4, ndig),
    Mul#(ndig, 4, nadj),
    Add#(pad , n, nadj)
);
    Bit#(nadj) numadj = extend(num);
    String res = "";
    for(Integer i = valueOf(nadj) - 1; i >= 0; i = i - 4) begin
        Bit#(4) dign = numadj[i:i-3];
        res = res + (case (dign) matches
            4'h0: "0";
            4'h1: "1";
            4'h2: "2";
            4'h3: "3";
            4'h4: "4";
            4'h5: "5";
            4'h6: "6";
            4'h7: "7";
            4'h8: "8";
            4'h9: "9";
            4'ha: "a";
            4'hb: "b";
            4'hc: "c";
            4'hd: "d";
            4'he: "e";
            4'hf: "f";
            default: "x";
        endcase);
    end
    return res;
endfunction

typedef struct {
    Bit#(1) a;
    Bit#(3) b;
    Bit#(1) c;
    Bit#(3) d;
} TestStruct deriving(Eq, Bits);

(* synthesize *)
module mkTest();
    rule display_finish;
        TestStruct s;
        s.a = 1;
        s.b = 3'b111;
        s.c = ?;
        s.d = 3'b111;
        $display(toHex(pack(s)));
        $finish();
    endrule
endmodule


The code above outputs "fx". Problem is: due to the case expression, a single don't-care bit contaminates the entire Bit#(4) containing it.

The most optimizing (and consistent) behavior would be for BSC to consider both the 4'h7 and 4'hf branches (which match "?111"), and later in elaboration, BSC would check if this was leading to a combinational circuit expression, and in the affirmative case, would choose the path leading to the smallest circuit (according to some metric). But I realize it would be very complex to implement in the compiler.

Another consistent behavior would be to choose the first pattern of the case matching with "?111". That is, 4'h7. However, I realize that it would led to missing optimization opportunities if the "case" expression were synthesizing to logic.

The current "case" behavior is treating '?' like it was a different entity from '0' and '1', and this is somewhat inconsistent with the semantics adopted for '?' in other expressions. But contaminating the entire "case" expression, i.e. making it evaluate to a '?' String, does not seem right, also. IMHO, when a designer puts a don't-care into some bit, she does not expect it to turn every expression ever touching that bit into a don't-care itself. It can led to inconsistent behavior in modules very far away from the place where the don't-care was declared. Does not seem to be a easy issue to solve :(

Another question, when you said "BSC has to keep the if-statement and, instead, moves on to elaborating the arms", it seems to imply that Bluespec uses lazy evaluation, like its parent Haskell. Is there some way to force strict evaluation, equivalent to the "seq :: a -> b -> b" function in Haskell? It would ease a lot debugging this kind of stuff. Also, it could potentially permit some tricks to detect '?' in pure BSV. If I understand correctly, something like the code below would then be possible.

Code:

function is_dontcare(Bit#(1) b);
   Bool is_zero = (b == 0);
   Bool is_not_zero = (b != 0);
   return seq(is_zero, seq(is_not_zero, ! (is_zero || is_not_zero) ));
endfunction


Of course, another name would need to be chosen instead of "seq", because it is already a keyword in BSV.

Edit: Hm, perhaps the trick above would not work, even if something like "seq" was available. By reading about it again, it looks like '?' in Bluespec behaves much like 'undefined' in Haskell. So the "is_dontcare" function above would also return '?'.

Edit 2: Ok, so by reading documentation about Bluespec Classic's '_' (cited below), which is equivalent to '?' in BSV, it seems to be clear that it is probably implemented internally like Haskell's "undefined" (a ⊥ value).

Quote:
If a "don't-care" value is part of any computation (such as an argument to an addition function) the result will be a new "don't care" value.


I think it should be made more clear in BSV documentation. Even calling these values "don't cares" is itself a little misleading, because the concept is very different from what is normally called a "don't care" in the hardware and EDA context.

Other problem is that, contrary to what happens in Haskell, where the concrete realization of ⊥ causes an Exception, the only way to be sure ⊥ is not inadvertently mixed into some expression in Bluespec seems to be calling BSC with the "-opt-undetermined-vals" option. Then, the generated Verilog will have "/* unspecified value */" annotations. Otherwise, these annotations do not seem to be generated.

Another question, is there a reason for the '?' not being converted to stuff like "8'hxx" in the Verilog backend, even when the "-opt-undetermined-vals" option is supplied?
Back to top
View user's profile Send private message
quark
Site Admin


Joined: 02 Nov 2007
Posts: 499

PostPosted: Thu Nov 14, 2013 5:31 pm    Post subject: Reply with quote

I think there are a few misunderstandings. Let me clarify:

(1)
Quote:
when you said "BSC has to keep the if-statement and, instead, moves on to elaborating the arms", it seems to imply that Bluespec uses lazy evaluation

No, that's not what I was talking about.

I was referring to the fact that operators in BSV can be either static or dynamic. For instance, if you have the expression "1 + 1", the elaboration stage can compute that addition and convert it to the value "2"; that computation doesn't get done in the execution of the hardware (you won't see "1+1" in the generated Verilog). However, if you have the expression "rg1 + rg2", which is adding the values of two registers, this cannot be computed statically by BSC because the values of the registers are dynamic values, that will only exist in the hadrware. So BSC has to "keep" the addition operator around, and represent it in the generated Verilog.

The same is true for if-statements. BSC can compute the following statement during elaboration:
Code:
if (True) val1 else v2

The result would be to replace this statement by the value "val1". However, if the condition of the if-statement is dynamic, then BSC cannot compute the statement and so it "keeps" the statement in the hardware. For instance:
Code:
 if (rg1) expr1 else expr2

In this statement, because BSC cannot decide which branch to take, it must generate hardware that can possibly take either branch. Therefore, BSC will have to evaluate both branches.

That's what I was referring to.

During the elaboration stage, if the condition of an if-statement cannot be determined (because it contains a don't-care value that has not been reduced), then the elaboration stage "keeps" the statement (to be computed later, perhaps dynamically in hardware) and moves on to elaborate both branches.

The question becomes: why would BSC not reduce a don't-care value? Let me come back to that. I first need to clarify:

(2)
Quote:
Ok, so by reading documentation about Bluespec Classic's '_' (cited below), which is equivalent to '?' in BSV, it seems to be clear that it is probably implemented internally like Haskell's "undefined" (a ⊥ value).

This is not True. The statement you quoted is not correct.

The don't-care value *is* exactly what it says. It is an expression which can legally be given any value (of the given type).

For some operators, if the argument is don't-care, then the result is also don't-care:
Code:
(not ?)  ==>  ?
(? + 1)  ==>  ?

However -- as you correctly intuited -- this is not true for all operators. The if-statement is a perfect example:
Code:
 if (?) 3 else 17

The above expression should only ever have the value 3 or the value 17. It would be an error to convert this to don't-care, because that would allow many other possible values.

This is how BSC should behave. If you are observing something different, then that is a bug to be fixed (and please report it to us!).

(3)
Quote:
The current "case" behavior is treating '?' like it was a different entity from '0' and '1'

No, BSC should not be doing this. If you observe that it is, that's a bug and I would appreciate an example, so that we can fix it.

What you may be observing is that the elaboration stage cannot decide whether a don't-care is equal to 1 or 0, and so it "keeps" the entire case-statement around -- a later stage of compilation may finally pick a value and simplify the case-statement.

I'll give an example, but first let me return to the question of why the elaboration stage doesn't pick a value. This is part of a heuristic that is based on the idea that it's best to delay picking the value until as late as possible, when the best optimization can be made.

For instance, a common optimization for the don't-care value is to eliminate a mux:
Code:
if (cond) val1 else ?  ==>  val1

The condition expression is removed entirely. In particular, for Maybe values, it elimates a mux for the invalid bits:
Code:
if (cond) {1'b0, ?} else {1'b1, val}  ==>*  {cond, val}

But if you pick the value of a don't-care too early, you may miss this opportunity. For example:
Code:
if (cond) val1 else (?+1)

If you picked the don't-value to be a number, and added 1, then you wouldn't be able to apply the optimization. But if you propagate the don't-care value, by converting "?+1" to just "?", then you can apply the optimization.

As a result, the elaboration stage never picks a value -- that is, it never converts a don't-care to 0, 1, or AAAA -- the elaboration stage only applies optimizations like the ones above. Later stages in BSC will eventually choose a value (based on the "-unspecified-to" flag). After choosing the value, some simplification may be possible, so those later stages will do some further elaboration, if possible.

This is a heuristic, so it's not perfect. There may be better design decisions that we could take in BSC, for optimizing don't-care values. I would be interested in exploring this, and welcome examples like these.

You have uncovered an interesting situation with "toHex", which is that there may be times when the elaboration stage should choose a value. It is a good question whether BSC can figure this out on its own, or whether the user needs to explicitly call a function like "removeDontCare". I would like to explore this.

I figured out what was happening in your "removeDontCares" function. You had this case-expression:
Code:
case(num[i]) matches
  1'b0: 1'b0;
  1'b1: 1'b1;
  default: 1'b0;
endcase

which is actually reduced to nested if-expressions:
Code:
if (num[i] == 1'b0)
  1'b0
else if (num[i] == 1'b1)
  1'b1
else
  1'b0

The second if-expression is optimized away by an optimization that removes unnecessary comparison operators for 1-bit conditions:
Code:
if (x == 0) 0 else 1  ==>  x
if (x == 1) 1 else 0  ==>  x

So your nested if-expression actually reduces to one if-expression:
Code:
if (num[i] == 1'b0)
  1'b0
else
  num[i]

Now, when "num[i]" is a don't-care bit, you actually have this situation:
Code:
if (...) 1'b0 else ?  ==>  1'b0

So for don't-care bits, the entire expression is reduced to just "0". If you changed the case-default to return 1 (instead of 0), though, the case-stamement reduces to "?", a don't-care (because different optimization rules will apply).

So that's why your function happened to work, to convert don't-care bits to 0.

I have not yet looked at your latest example (which returns "fx"), so I will look into that.

Quote:
Problem is: due to the case expression, a single don't-care bit contaminates the entire Bit#(4) containing it.

As I said, this should not be happening. I'll look into the "fx" example and see if there is a bug in BSC or an explanation.

Quote:
the only way to be sure ⊥ is not inadvertently mixed into some expression in Bluespec seems to be calling BSC with the "-opt-undetermined-vals" option. Then, the generated Verilog will have "/* unspecified value */" annotations. Otherwise, these annotations do not seem to be generated.

Quote:
Another question, is there a reason for the '?' not being converted to stuff like "8'hxx" in the Verilog backend, even when the "-opt-undetermined-vals" option is supplied?

These questions are making incorrect assumptions. Let me explain what the "-opt-undetermined-vals" flag does.

As I said, BSC makes the decision to delay picking a don't-care value as long as possible, in order to get the best optimization. However, BSC has two back ends: Bluesim and Verilog. At the point where BSC splits off into Bluesim or Verilog, there may still be don't-care values in the design (if optimization rules could not be applied to them). By default, BSC chooses to finally pick a value at this point (0, 1, or AAAA depending on the "-unspecified-to" flag). This is so that the Bluesim and Verilog simulations will produce the same results, even down the same don't-care bits. This equivalence is often important to users.

However, delaying the choice of don't-care value can expose more optimizations, so the generated Verilog can potentially be more optimized if BSC delays picking a value until later in the Verilog backend. And that's what the "-opt-undetermined-vals" flag does. That flag says: don't force the don't-care expressions to have a value until the very last minute, later in the back end. The side-effect of this is that Bluesim and Verilog may pick different values; but in some cases you may not care -- particularly if you don't use Bluesim, there's no need to hobble the Verilog back end.

That's all the flag does. It prevents BSC from picking the value before the bacl-end split. (This should be how the flag is documented in the BSC User Guide; please let me know if it's not clear there.)

That also explains why you see the comment "/* unspecified value */" in the generated Verilog. This comment appears when there is a don't-care value that has survived all the way to the Verilog back end and, when writing out the Verilog file, BSC has to pick a value. If the don't-care value was picked in an earlier stage, then it was replaced with a constant number (0, 1, or AAAA) and by the time we get to the Verilog file, we no longer know that it was originally a don't-care value. (And, in fact, it may not still be the same don't-care value by the same it reaches the Verilog; there may have been optimizations, where the picked value is optimized with adjacent code, such as "?+1" being picked as "0+1" and then optimized to just "1", so we could no longer write "unspecified value" next to the "1" because it's no longer the pure don't-care value.)

For your information: Note that don't-care values can be chosen to be X and Z in the Verilog back end. But Bluesim is a 2-value simulator, so X and Z are not allowed for Bluesim. So the "-unspecified-to" flag cannot be given with the arguments "X" or "Z" except when the "-opt-undetermined-vals" flag is also turned on.

Quote:
Will the beta versions (like "Bluespec-2013.05.beta2") continue to be made available here to the forum users?

I don't know what you mean by "continue", as beta releases are never announced. We will freely let you know if there's a new beta release that you should try, if you're having problems, but we only announce full-fledged releases. There will be an official release soon and then we hope to keep a schedule of making a full-fledged release every six months. So hopefully you won't need to worry about beta releases. However, if you want to track whether a feature has been fixed or added to a new beta release, you can email [email protected]. I will also post a reply here if a "removeDontCare" function is added.
Back to top
View user's profile Send private message
matias



Joined: 11 Nov 2013
Posts: 6

PostPosted: Fri Nov 15, 2013 3:54 pm    Post subject: Reply with quote

Hi quark, thank you very much for reading my long text and providing those very clarifying answers.

Quote:
I was referring to the fact that operators in BSV can be either static or dynamic. [...]


I see now, thanks. When I wrote that I was thinking the underlying implementation of this language feature (in BSC) was using lazy evaluation, but now I realize that it does not matter at all in this case.

Quote:
This is not True. The statement you quoted is not correct.
The don't-care value *is* exactly what it says. It is an expression which can legally be given any value (of the given type).


Ah, nice to know this definition has changed since Bluespec Classic. The new definition really maps much better to common EDA concepts.

Quote:
Code:
 if (?) 3 else 17

The above expression should only ever have the value 3 or the value 17. It would be an error to convert this to don't-care, because that would allow many other possible values.


Perfect, this is exactly the behavior we would expect from a don't-care.

Quote:
No, BSC should not be doing this. If you observe that it is, that's a bug and I would appreciate an example, so that we can fix it.


What made me make this assumption was the "fx" example in my last message. Please note that if you remove the default arm from the "case" expression, compilation fails with the following error:

Quote:
Error: "Prelude.bs", line 901, column 15: (S0015)
Attempt to use a raw undetermined string


Which is, perhaps, caused by the "case" expression returning don't-care because of a single bit of the Bit#(4) being originally a don't-care.

I said the don't-care appears to be treated like a different entity from '0' or '1' (at least in "case" expressions) because of the behavior presented when the code has a default arm. An arm exists in the "case" expression for every possible value of a Bit#(4) containing only '0's and '1's, but the default arm is still taken when a don't-care is present.

That situation apparently arises whenever there are Bit#(n) values containing some don't-care bits. It can also be reproduced using simpler examples:

Code:
 
        Bit#(2) value = 0;
        value[0] = ?;
        String test = (value == 0) ? "0" : ((value == 1) ? "1" : "x");
        $display(test);


So the value is {1'b0, ?}, which should only ever evaluate to 0 or to 1. But a "x" is displayed. In fact, even if you change "Bit#(2)" to "Bit#(1)", the behavior persists.

Well, if the code above worked as expected, it would be fairly easy for BSC to implement support for numeric literals containing X, which are currently not supported, e.g. "Bit#(2) value = 2'b0X;" would (perhaps) be equivalent to the code above.

Quote:
You have uncovered an interesting situation with "toHex", which is that there may be times when the elaboration stage should choose a value. It is a good question whether BSC can figure this out on its own, or whether the user needs to explicitly call a function like "removeDontCare". I would like to explore this.


That would be very nice. I realize it would not be trivial for BSC to uncover all situations where a value would need to be chosen for a don't-care during elaboration. This is a very interesting problem to explore.

Quote:
So your nested if-expression actually reduces to one if-expression:
Code:
if (num[i] == 1'b0)
  1'b0
else
  num[i]

Now, when "num[i]" is a don't-care bit, you actually have this situation:
Code:
if (...) 1'b0 else ?  ==>  1'b0



Ah, I see. Changing the case expression to "res[i] = (num[i] == 1'b0) ? 1'b0 : num[i];" appears to work. Thank you very much for the detailed analysis of what was going on.

We have another version of the code on which we tried to implement "removeDontCares" in a slightly different way (using "res[i] = ((num[i] == 1'b1) ? 1'b1 : 1'b0);", as we have mentioned in the first post).

I have attached a zip file containing two files, "Example_works.bsv" and "Example_fails.bsv", with two different usages of "removeDontCares" and "toHex" on the same Maybe value. The first compiles correctly. The second causes an internal compiler error, both when using the 2012.01.A (stable) and 2013.05.beta2 releases. I hope it can be useful for you to debug this issue.

Quote:
0, 1, or AAAA depending on the "-unspecified-to" flag


Ah, thank you! I had missed that flag. I guess I have to read "user-guide.pdf" with more attention. This was exactly what I was looking for when I made that last question.

Quote:
That also explains why you see the comment "/* unspecified value */" in the generated Verilog.


I made that question because I assumed the don't-care "contamination" was the intended behavior (because of what I had read in old Bluespec Classic documentation). If that was the case, it would be important for BSC to always alert if some don't-care was mixed into some result, to avoid the user from inadvertently creating undefined expressions. However, now I understand that it is not the intended semantics for '?'.

Quote:
I don't know what you mean by "continue", as beta releases are never announced.


I asked because we got the link for downloading "Bluespec-2013.05.beta2" from a post here in the forum. Otherwise, we would only have access to the stable releases (from the Downloads section), because we have never contacted support by email. As users of the university program, we would be very willing to test almost every beta version to help with the development of the tools, even in the cases we do not have problems with the currently released stable versions.



altsourceprobe_test.zip
 Description:
Example triggering an internal compiler error

Download
 Filename:  altsourceprobe_test.zip
 Filesize:  3.05 KB
 Downloaded:  656 Time(s)

Back to top
View user's profile Send private message
quark
Site Admin


Joined: 02 Nov 2007
Posts: 499

PostPosted: Mon Nov 18, 2013 4:06 pm    Post subject: Reply with quote

I believe I understand what is happening in your example that returns "fx". In that example, the "x" is the default arm of a case-expression that ought to be unreachable. I've reduced it to a simpler example, which will be easier to explain:
Code:
Bit#(1) x = ?;
String s;
if (x == 0)
   s = "0";
else if (x == 1)
   s = "1";
else
   s = "X";
$display(s);

The final else-arm should not be reachable, but if you compile this the result is "X". The reason is that BSC optimizes the don't-care value twice, but it does so independently even though it's the same value "x". A don't-care is allowed to be any value, but once picked it should remain that value; it should not be allowed to be multiple values.

In the above example, BSC first optimizes "? == 0" to be just "?". A don't-care value compared to a 1-bit constant can either match or not. This is fine. But then BSC also optimizes the expression "? == 1" and reduces it to "?". Independently, these optimizations are OK. But together, there is no one value of "x" that satisfies both optimizations. At the end of elaboration we have:
Code:
if (?)
   "0"
else if (?)
   "1"
else
   "X"

The elaboration stage does not pick a value for the don't-care expressions. Later stages pick AAAA (alternating 0s and 1s) for the value of the don't care, which is 0 for 1-bit values. So the else-branch is taken in both cases, resulting in "X". But the variable cannot be both not equal to "0" and not equal to "1". So this is a bug in BSC.

We need to fix BSC so that, when it inlines a don't care value into multiple places, it treats them as the same value, and not independent values.

This also explains the error when you remove the default arm. When a case-statement has no default arm, BSC inserts an implicit default that returns don't-care. So, the example would look like this:
Code:
if (?)
   "0"
else if (?)
   "1"
else
    ?  // returns don't-care

When the don't-care conditions are picked to be 0, we are left with "?" as the result for "s", but the Verilog backend does not expect to have to pick String values for dont-care.
Back to top
View user's profile Send private message
matias



Joined: 11 Nov 2013
Posts: 6

PostPosted: Mon Nov 25, 2013 1:37 pm    Post subject: Reply with quote

Hi quark,

Sorry for the late reply. I had very busy days during the last week. With your explanations I think we have now a very clear understanding on how the compiler currently works regarding don't-cares.

quark wrote:
The elaboration stage does not pick a value for the don't-care expressions. Later stages pick AAAA (alternating 0s and 1s) for the value of the don't care, which is 0 for 1-bit values. So the else-branch is taken in both cases, resulting in "X". But the variable cannot be both not equal to "0" and not equal to "1". So this is a bug in BSC.


Now it makes whole sense. In my example:

Code:
Bit#(2) value = 0;
value[0] = ?;
String test = (value == 0) ? "0" : ((value == 1) ? "1" : "x");
$display(test);


If I compile it with the options "-opt-undetermined-vals -unspecified-to 1", it indeed prints "0" instead of "x", due to the effect you explained ("value == 0" becomes "?", which in turn becomes "1" due to the "-unspecified-to" option).

quark wrote:
When a case-statement has no default arm, BSC inserts an implicit default that returns don't-care.


Also very a very enlightening explanation, thank you!

quark wrote:
We need to fix BSC so that, when it inlines a don't care value into multiple places, it treats them as the same value, and not independent values.


That would be nice. But dealing with multiple-bit values containing some don't-care bits still seems to be nontrivial, even if the issue above is fixed. At a first glance, the compiler would need to convert "value == 0" internally into something like "value[0] == 1'b0 && value[1] == 1'b0" and then treat each bit-vector index as if it was a different variable. This issue could, however, be dealt with manually using a "removeDontCares"-like function which you are planning to provide.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    bluespec.com Forum Index -> Designing with BSV's Rules, Interfaces, ... All times are GMT - 4 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum
bluespec.com topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group
Protected by Anti-Spam ACP