Language Change Specification for Long Integers Proposal

Voting Results: Cast your votes here

Yes:

1. Kevin Jennings - 2016-11-07
2. Morten Zilmer - 2016-12-11

No:

1. Thomas Preusser - 2016-11-21
2. Ernst Christen - 2016-12-12
3. Lieven Lemiengre - 2017-01-09
4. Yann Guidon - 2017-01-09
5. Martin Zabel - 2017-01-23 - I prefer LCS-2016-026a.
6. Rob Gaddi - 2017-01-26 ver 1 - I think that, while it would be technically possible to implement this in a way that was gentle on execution time, the amount of work necessary to do so would be huge and not forthcoming from the vendors.
7. Lieven Lemiengre - 2017-01-27
8. Farrell Ostler - 2017-01-31

Abstain:

Details_of_Language_Change

LRM 5.2.3.1 Integer Types -- General

Page 39 second paragraph

Changes are shown in red font.

However, an implementation shall allow the declaration of any integer type whose range is wholly contained within the bounds -(2**511)–2147483647 and +(2**511-1)+2147483647 inclusive.

LRM 5.2.3.2 Predefined Integer Types

Page 39 middle of page

Changes are shown in red font.

The range of INTEGER is implementation dependent, but it is guaranteed to include the range -(2**511)–2147483647 and +(2**511-1)+2147483647.

LRM 5.2.4.1 Physical Types -- General

Page 40 below middle of page

Changes are shown in red font.

However, an implementation shall allow the declaration of any physical type whose range is wholly contained within the bounds -(2**511)–2147483647 and +(2**511-1)+2147483647 inclusive.

LRM 5.2.4.2 Predefined Physical Types

Page 41 below middle of page

Changes are shown in red font.

The range of TIME is implementation dependent, but it is guaranteed to include the range -(2**511)–2147483647 and +(2**511-1)+2147483647

-- Kevin Jennings - 2016-10-26

Comments

This would make simulation much less efficient. Not sure this is a good idea.

-- Tristan Gingold - 2016-11-06

Where is the subtype definition for normal integers. This would reduce the impact for almost all designs and testbenches. It also allows optimizations in the simulator. E.g. in the currently proposed LCS, integer'low defaults to -(2**512) and the simulator needs to use 512 bit integers to represent this value. If integer is a subtype of "implementation_defined_integer" and uses it's old range, the simulator can infer a range bound of 32 bit and use other register sizes in the CPU.

-- Patrick Lehmann - 2016-11-19

There will be no subtype definition for 'normal integers'. The defined range of an integer object (i.e. variable xyz: integer range 0 to 65535) gives the compiler all the information that it needs to figure out how many bits are needed. I suspect that to be the large majority of use cases for synthesizable code, but probably less so for testbenches. The most likely affected cases are where the range is not declared (again, likely only in testbench code) or loops that are run for "integer'range" and now one will be getting a much larger integer than they had in the past. Those people might be affected in which case they can modify their code or continue to compile with old tools. Their is nothing in the LRM going back to VHDL '87 that prevents a tool from implementing this larger range so anyone that is depending or benefiting from the current 31 bit implementation is depending or benefiting from something that is not guaranteed in the specification anyway. Moving the language forward for those that need it while only affecting those taking advantage of something that was not guaranteed in the first place is the right way to go.

-- Kevin Jennings - 2016-11-21

I believe it would be less controversial to allow arbitrary user-defined ranges as direct subtype of universal_integer that are not constrained by integer. This would both (a) allow tools to normally work with an efficient standard-compliant integer size, e.g. 32 bit, and (b) enable designers to open up arbitrary wide ranges whenever necessary.

-- Thomas Preusser - 2016-11-21

There are a number of proposals on the Twiki for how to get larger ranges for integers but virtually no agreement or, most importantly, anyone willing to push one forward. Not wanting to see absolutely no changes to the language for this next revision, I took it upon myself to simply write up the most straightforward proposal and wrote the changes for this LCS. I did extend the proposal from 64 bits since the general consensus seemed to be that 64 bits, while probably good enough for now, is probably not good enough going forward. (Note, I did not write any of these 'big integer' proposals). You are free to pick up a different big integer proposal and turn it into an LCS or write up your own big integer proposal and LCS. According to the chair, there is roughly one month to get that completed since the plan is to have voting completed by the end of the year (give or take).

-- Kevin Jennings - 2016-11-21

I could not find anything in the LRM that specified the precision required for 'intermediate' calculations (if there is something, please post reference). What I have found with simulator 'M' is that one can exceed the range of integer by a little bit (100) and be OK, but you can't go to the point of doubling the number of bits required.

I also could not find anything in the LRM that required operations on constrained integers to be performed at full 'universal_integer' precision (again, if there is something, please post reference) so calculations performed on constrained integers do not need to be performed with the full 512 bit precision listed in this LCS. While one would not want to perform calculations with only 'n' bit precision when operating on 'n' bit numbers, it might be acceptable to perform them on '2n' bits down to some minimum size such as 32 or 64 as is done today.

To reiterate, nothing in this LCS breaks backwards compatibility to the standard going all the way back to VHDL-87 since implementations were only required to implement a minimum range but have always been free to implement a larger range. That coupled with the fact that choosing simply to redefine this minimum range is pretty much the least amount of specification change that is required for any of the larger integer proposals (and therefore more likely to be done correctly) is the reason why I chose the LongInteger proposal to write up this LCS. At present, there are no other change specifications written for any of the other integer proposals so, without this LCS, there will be no VHDL integers larger than 32 bits for at least the next however many years if this one is not approved.

Example program that demonstrates how intermediate calculations can overflow the integer range by a little bit (+100), but not by a lot (double the number of bits required to represent).

entity Foo is
end Foo;

architecture RTL of Foo is
begin
    process
        variable a, b, c:   integer;
        constant BigInt:    integer := integer'high;
    begin
        wait for 1 ns;
        -- a, b and c should all mathematically end up as 'BigInt'.
        a := BigInt;                    report "a=" & integer'image(a);
        b := (a+100) - 100;             report "b=" & integer'image(b);
        c := (((a+1)*(a+1))/(a+1))-1;   report "c=" & integer'image(c);
        report "Done" severity ERROR;
        wait;
    end process;
end RTL;

Output:
# ** Note: a=2147483647
# ** Note: b=2147483647
# ** Note: c=-1

-- Kevin Jennings - 2016-12-09

As an additional note, while I haven't found anything in the LRM that states any precision requirements (again, if there is, someone please reference), I will point out what actually is there which is the following from page 39: It is an error if the execution of such an operation (in particular, an implicit conversion) cannot deliver the correct result (that is, if the value corresponding to the mathematical result is not a value of the integer type). As can be seen with my previously posted results at least one simulator is not able to meet this requirement. Furthermore, any implementation that uses a fixed number of bits for calculations, since I don't think the LRM allows for performing mathematical simplifications, it will always be possible to come up with a value of n for which ((x+1)**(n+1)/(x+1)**n) - 1 does not return x where x=integer'high which means that implementation will also fail the above mentioned LRM requirement (unless there is something elsewhere in the LRM that discusses ranges of intermediate values of calculations).

I’m reading that LRM paragraph with emphasis on "cannot deliver the correct result" which would mean that the correct mathematical result is the only acceptable output. However, the text in parentheses says "...the value corresponding to the mathematical result is not a value of the integer type" which I suppose could be interpreted as meaning that the result is OK as long as it is an integer, not whether it is mathematically correct. By that measure, the 'M' simulator did not fail since it returned the value -1 which is an integer. I don’t see how that could really be an accepted interpretation, but maybe it is to someone bent on going down odd tangents.

It has been suggested by some that this LCS would be acceptable if type 'integer' was redefined to be a subtype of the new bigger 512 bit integer. I disagree. There would be several more edits to the LRM and potential ramifications to those edits if integer was redefined. This LCS, as written, is completely backwards compatible with all previous LRM releases and there is (or at least should be) tremendous value right there. Making integer a subtype of 'big integer' might not meet that goal.

It has also been suggested that performing 512 bit calculations would possibly be a performance drag. I disagree that it will have a major impact, but I do agree that if the actual implementation in the simulator is the brain dead approach of simply doing all integer calculations as 512 bits then yes it will probably be a major performance hit. But that is not the only approach and let me reiterate that the LRM says nothing today about performing 32 bit integer operations, what it says is that it is an error if "an operation cannot deliver the correct result". All of us today can easily perform integer math operations (+, -, *, /) on a pair of 8 bit integers without needing more than 16 bits and get the correct mathematical result. You don't need 512 bits, you don't even need 32. There are certainly other integer functions, but you get the point.

I would suggest a better approach than the brain dead one would be to add up the number of bits on the integer inputs to an operation, maybe double that number and use that for the effective number of bits to use during the operation. For example, if a and b are all 0 to 1023 range, then they obviously require 10 bits. The function f(a, b) can be assumed to produce at most 2*(10+10)= 40 bits. Similarly f(a, b, c) produces at most 60 bits. Maybe limit that at 512 bits on the high end if the simulator people need a hard limit, but once they can handle big numbers there might not be a need for an actual hard limit other than available memory. I don't know what current 'big num' libraries do but maybe there is some guidance there as well that can help implement something that is not brain dead. Note that no knowledge of what the function f() does is needed, only that it works with integers and how many integers are in play.

I put forth this suggestion not to imply that it should be in the LRM (it shouldn't) but to point out an alternative implementation to the brain dead approach that would be at least as effective as what we have today and shows a way that integer operations can be performed without having to do full 512 bit math on every integer.

Where there will be a performance impact is that each integer operation may have to branch to code that handles specific integer sizes. But the determination of which code to branch to can be statically determined since it depends only on the statically defined integer ranges so potentially the branch doesn't even show up in the run time code. In any case, I would expect the impact of the branch to be minimal, perhaps even hard to measure, but will leave it to folks who actually implement this stuff to weigh in.

-- Kevin Jennings - 2016-12-11

One clinker function that would violate the above mentioned suggestion on the number of bits would be raising to an integer power when used for anything other than to calculate a constant. Rather than an a priori estimate of how many bits are needed to hold the output of a function, there might need to have some feedback from compiling the code of the function body back to the code that calls the function to indicate how many bits will be needed for the result. Should still be able to be a static feedback rather than runtime. Seems like that could be feasible...but I don't have to implement it either.

-- Kevin Jennings - 2016-12-13

This proposal forces all integer calculations to be done with 512 bits, thereby causing a significant performance loss. Consider this example:

package a is
   function f(x: integer) return integer;
end package;

When compiling this package by itself, there is no knowledge of what actuals this function will be called with.

process
    subtype int32 is integer range -2^31 to (2^31-1);
    subtype int64 is integer range -2^63 to (2^63-1);
 variable a: integer;
    variable b: int32;
    constant c32 : int32 := 457;
    constant c64 : int64 := 754;
    constant c512 : integer := 45578;
begin
    a := f(c32);
    a := f(c64);
    a := f(c512);
    a := c32 * c32;
    b := c32 * c512;
    wait;
end process;

Since overloading is defined based on types (not subtypes), there is only one function f() for all these function calls, the one for (full width) integer. All calculations have therefore to be done with the full 512 bits. In fact, the LRM requires all calculations to be done with full precision, since the subtype check is only performed as part of the assignment. To change this, a lot more is needed than what this proposal suggests.

-- Ernst Christen - 2016-12-12

I agree with your statement about overloading, but that is not relevant here, here's why.

- Looking at is the function declaration and body does not provide the information to any tool to know what size is needed for an integer. In fact, it would be expected to have different sizes being used for different calls to a subprogram.

- Every instance where a function is called, the input parameter has a defined range (even if that is the current default of 32 bit integers.

- Tools already have access to the ranges of the actuals as well as the ranges of called subprogram parameters because they have to check that things are within the bounds.

- The integer operations are limited and are already defined in the LRM which implies that, given the ranges of the input operands, the range of the output can be computed.

- All of these ranges are static. They need to be computed once for each instance (and each instance can have different ranges), but those ranges do not change during runtime.

Given that, what I'm suggesting is that the tools have everything they need in order to:

- Determine how many bits of precision are needed to perform an operation to obtain the correct mathematical result.

- Pass information regarding parameter size and subprogram output sizes between the subprogram (which computes the output sizes once and then uses the sizes that are subsequently passed in) and the caller of the subprogram (which stores the function computed output size as well as the input parameter sizes and passes them to the subprogram instances).

I do not agree that "All calculations have therefore to be done with the full 512 bits. In fact, the LRM requires all calculations to be done with full precision". If you have a specific LRM reference then please state exactly which section/page/paragraph or something. What the LRM does state on page 39 at the top is that the correct "mathematical result" be obtained. The correct result can be obtained without necessarily having to perform 512 or even 32 bit math.

Just because there is only one function and that one function must be able to operate on any size integer, does not imply that all calculations must be done with 512 bits. The tool that implements the function also has access to the ranges of the parameters and can branch to appropriate math routines based on those ranges.

-- Kevin Jennings - 2016-12-13

My statement that all calculations have to done with full precision is a conclusion, not an LRM definition, and it is based on practicality. The alternative, as Tristan said somewhere, would be to create several copies of the code for the function, one for each integer size deemed relevant. In essence, this amounts to overloading even though it may be hidden. It would add a considerable amount of complexity to code generation and also incur a run time overhead because for practical reasons an integer object will have the maximum number of bits regardless of its subtype (memory is cheap).

You make a remark above that at the point of the function call the ranges of the actuals are known. According to the current LRM definitions, this is true if the actual is a primary, but not if it is an expression. LRM 9.1: "The type of an expression depends only upon the types of its operands and on the operators applied; …" Only the type is known, there is no subtype. As I said before, it's only at the point of assignment (or the copy in case of a function call) where subtype constraints are enforced, based on the subtype of the target or formal. In the case of an integer (or its subtypes) expression this type is INTEGER. As you suggest, it may be possible to determine the maximum number of bits the expression might produce, but it doesn't give you a subtype. Add to this the fact that there are thousands of functions out there in existing designs that have return types/subtypes of integer, positive or natural. If any of these are involved in an expression we are back to square one.

I have no problems with a minimum range for integer longer than 32 bits, but in my opinion such a range must be supported by native instructions on modern 64-bit computer hardware. Also, an analysis should be done about the practical impact of making such a change because it is likely that there are places where the code silently depends on 32-bit size.

-- Ernst Christen - 2016-12-13

I do not see any LRM support for a "full precision" interpretation. My interpretation of the statement at the top of page 39 is that the model is in error if the operation cannot deliver the correct result. Check out the other statements in the LRM that begin "It is an error if..." e.g. section 5.3.1.

I am working on an integers round-up that will hopefully help us progress on these proposals.

-- Ryan Hinton - 2016-12-13

@Ernst EC: My statement that all calculations have to done with full precision is a conclusion, not an LRM definition, and it is based on practicality

KJ: Your statement is contradicted by the LRM. I've pointed this out multiple times on this page.

EC: The alternative, as Tristan said somewhere, would be to create several copies of the code for the function, one for each integer size deemed relevant.

KJ: My previous reply to you outlined an alternative that uses one copy of the function. You've ignored that alternative for some reason.

EC: According to the current LRM definitions, this is true if the actual is a primary, but not if it is an expression

KJ: This is not relevant because expressions will, I believe, always have a deterministic size that a tool can calculate based solely on the parameters and the expression or function. A simple example is the expression x*x. If it takes n bits to represent x, then the expression will take 2n bits. An expression could also be an arbitrary function call. I suggested that the tool's code for the function compute the size of the function output independent of the values of the input parameters and return that to the caller. (for each instance as part of initialization at t=0). But maybe that's not actually the case, maybe there is some form of function that can output a non-deterministic output size. If one wants to shoot down my suggestion, then find that type of function and show the analysis to say why the output size is non-deterministic. Hopefully that function is also relevant to a hardware model since that is what VHDL models. Shooting down the suggestion however is not the same as shooting down the LCS. The LCS states the requirement, the tool vendors implement it and can be creative and innovative in that implementation. Insisting that only what I earlier called the 'brain dead' approach, or Tristan's first crack at it are the only ways to implement simply is not correct. As a final additional suggestion, if a function really is too hard for the tool to analyze in order to figure out the output size, then why would it not be acceptable for the tool to error out and say "Function 'Bizarro' is too difficult to analyze, please simplify a bit so I can figure out the size of the integer output of this function please". This determination would be done at t=0 along with all the other stuff that happens at that time just getting setup to simulate. Tools exit all the time in ways not specified by the LRM.

EC: but in my opinion such a range must be supported by native instructions on modern 64-bit computer hardware

KJ: My suggested outline of how this LCS could be implemented allows for that. However, it doesn't limit the range to only that which can be supported by today's instruction set.

EC: an analysis should be done about the practical impact of making such a change because it is likely that there are places where the code silently depends on 32-bit size

KJ: This LCS, as written, is fully backwards compatible with every revision of the LRM, delivers something that has been asked for by multiple people and, I believe, can be implemented without undue performance impact or asking the software tool folks to do something extraordinary. If those aren't the characteristics that a good LCS should have, I don't know what is.

@Ryan RH: I am working on an integers round-up that will hopefully help us progress on these proposals.

KJ: I don't think that any 'integers round-up' will help make progress. Writing up an actual LCS for any of the other large integer proposals would help those proposals make progress. Coming up with even more ways to implement the requirement of 512 bit integers for this LCS without severely impacting performance would be useful as well.

-- Kevin Jennings - 2016-12-14

You're right: shooting down your suggested approach for optimizing integer calculations doesn't shoot down the LCS. However, this proposal has been flagged by many implementors as having a significant impact on speed and implementation complexity. Any LCS that cannot adequately address these concerns is unlikely to pass a vote.

It sounds like your scheme is asking for tools to statically analyze ranges of each function for actual input ranges. Short of calling a function for every single allowed input, this static analysis sounds equivalent to the halting problem in general. Since I see my simulation stop at the time+delta when I actually try to call the function, I assume the subtype constraints in my simulator aren't checked until the call is actually made. So your scheme retains a significant impact on speed and/or implementation complexity.

KJ: "... too difficult to analyze ..." Tools exit all the time in ways not specified in the LRM.

It sounds like you're endorsing an LRM change that might require implementations to fail for valid code in a way not specified in the LRM.

-- Ryan Hinton - 2016-12-14