Hacker News Reader

Comment by dooglius | Hacker News Reader

Not really, assembly language is extremely close to microcode, much much closer than it is to C. C has a whole bunch of baggage like pointer provenance, inability to read uninitialized memory, doesn't understand cache aliasing, etc that don't fit hardware well.

View on HN

No, it really isn't on anything modern, like ARM SoCs or x86 CPUs. The number of times I've hit my head to wall trying to understand what the heck the CPU is doing for a given sequence of instructions, like why the number of cycles or memory bandwidth required is way different from my expectation.

A modern CPU willy nilly reorders instructions, stores, and creates new "virtual" registers out of thin air to dissolve stall inducing dependency chains. It can also split instructions, fuse them together and even entirely remove some instructions -- as long as it doesn't affect the end result.

Generally (within limits of CPU memory model) the only thing you're guaranteed is that eventually the result is what you'd expect from sequential execution. That of course applies on the core you're running on, otherwise you naturally need to synchronize with other cores.

Luckily there are tools to find out, which work to some extent, IF you can run it on same CPU model (and really, whole system, incl. memory subsystem!) as what you're interested in.

Can you give an example? The most complicated assembly->microcode examples I can think of are floating-point instructions like FSIN that run CORDIC loops under the hood, and those are still pretty easy to reason about.

Pseudo-code:

  a = 10;
  b = 20;
  c = b + 30;
  bar = a + b;

  x = 1;
  y = 2;
  z = y + 3;
  foo = x + y;

... in order to remove dependency stalls might be executed as:

  b = 20;
  y = 2;
  a = 10;
  x = 1;
  c = b + 30;
  z = y + 3;
  bar = a + b;
  foo = x + y;

This would still be true, even if 'x' and 'a', 'y' and 'b' etc. variables (well, registers) had same name. In that case CPU would just make up new "variables" as required and do the same transformation!

Okay, you're talking about OoO execution here, and you're right that this can be hard to reason about (in terms of stalls/latencies), however that's orthogonal to microcode translation.

OoO and the fact that CPUs really are free to do whatever transformations they deem fit, as long as the end result within limits of memory model is same.

The CPU must conform to the strictures of the ISA, which is a much more stringent specification than the abstract machines of most language specifications. In particular, the state of registers and flags at any given time need to be preserved, even in the presence of external interrupts.

Note that several decades ago, there were processors that weren't capable of actually keeping the state correct after a processor exception, so if you got a division-by-0 error, your program counter had advanced by 30 or so. (This is, I believe, part of the reason why traps are undefined behavior in C: if your processor can't guarantee any state after a machine trap, it's impossible to implement a programming language that has even the loosest guarantees).

> The CPU must conform to the strictures of the ISA, which is a much more stringent specification than the abstract machines of most language specifications. In particular, the state of registers and flags at any given time need to be preserved, even in the presence of external interrupts.

https://en.wikipedia.org/wiki/Tomasulo_algorithm.

So no, the consistent serialized ISA-conforming state might be reconstructed by replaying after the exception (interrupt) arrives.

Alternatively, interrupt might be served only after execution reaches the next checkpoint.

I don't understand how you can acknowledge the cpu is literally rewriting your code on the fly by changing the order of operations and making things massively parallel and rewriting things in a proprietary language, while holding the belief that "microcode is really not that different from assembly". At least you can inspect what a C compiler emits to assembly.

This has nothing to do with microcode. It doesn't even have anything to do with microops. Reordering instructions (likely register renaming or load-store forwarding here, though the pseudo C code doesn't let me determine) is just part of how the processor retires instructions.

The example I gave, yes. No assembler code can have anything to do with micro-ops; they're implementation specific.

On x86, a lot of instructions are close matches, yet some are removed entirely (say "xor eax, eax") or fused into one micro-op, (like "cmp #123, eax / je <address>").

Future CPUs might even do some data flow analysis to optimize code even further.

Say speculative "constant" folding based on runtime profile to remove chunks of code from hot inner loops.

Or to replace longer instruction patterns with HW optimized implementation, if that's what it takes to get some extra performance for the next year's model.

https://en.wikichip.org/wiki/macro-operation_fusion

Registers are allocated (and renamed) after instruction decode (e.g. what creates micro-ops), in a separate unit. Micro ops themselves do not have renamed registers.

See the diagram here https://software.intel.com/sites/default/files/managed/9e/bc...

True. I simplified implementation details for clarity.

You are mixing up how branch prediction works with how processing unit works.

One of those only worth of time to learn as hardware engineers, but understanding both of them will give you an introduction to Spectre vulnerability.

No, branch prediction is not involved with what I was talking about.

> pointer provenance, inability to read uninitialized memory

what do you mean by these two? not sure about the former. as for the latter, of course you can read uninitialized memory, unless you mean something else?

No, reading uninitialized memory in C is UB.

As far as I know (and I could be wrong), reading uninitialized memory in C is not UB, but gives an indeterminate value, which may be either an unspecified value or a trap representation. If it is a trap representation, accessing it is indeed UB, but if all possible values of your memory are valid, e.g. if you have an unpadded integer where every bit representation means something valid, then it is not UB, though it is still an unspecified value which does not even have to be consistent: you could get different values when reading the same uninitialized location twice.

Edit: Some excerpts from the C standard:

6.7.8 Initialization

10 If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate.

3.17.2 indeterminate value

either an unspecified value or a trap representation

3.17.3 unspecified value

valid value of the relevant type where this International Standard imposes no requirements on which value is chosen in any instance

6.2.6 Representation of types

6.2.6.1 General

5 Certain object representations need not represent a value of the object type. … Such a representation is called a trap representation.

Not a C expert, just reading what I can find online:

This page says value is indeterminate, which is either unspecified or a trap, as you say: https://wiki.sei.cmu.edu/confluence/display/c/EXP33-C.+Do+no...

But.

This part says that reading an indeterminate value is, in fact, undefined behavior (line 11 in the table): https://wiki.sei.cmu.edu/confluence/display/c/CC.+Undefined+...

That says used, not read. And indeterminate, not unspecified. My point was on reading a value, not on acting on the value. I know it looks like nit-picking, and you should just not read uninitialized memory, but I don't think it's consistent with the standard to say that reading uninitialized memory is always UB.

What kind of read would not constitute "using" a value? And per your previous post an object that was not initialised is indeterminate, not just unspecified. So yes, reading uninitialized memory is always UB.

A read into a character type.

From 6.2.6.1¶5:

>Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. ... Such a representation is called a trap representation.

A read from uninitialized memory is not always UB.

What you quoted doesn't actually say anything about what happens when a trap representation is read into a character type. Such a read is still "using" the value at least in the everyday sense of the word, so in the absence of something explicitly to the contrary, as far as I can see the part of the standard that states that using an uninitialised value is UB stil applies.

Per http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_451.htm , the current standard is unclear in some respects, but the latest committee view is that that under the current standard any library function (including memcpy) may exhibit undefined behaviour when called with uninitialized memory, even when the uninitialized memory is of character type or is propagated through values of character type.

That's the way I think it _should_ work, but sadly does not. For instance, see https://godbolt.org/z/ent-xp

Your code is

    int x;
    if(x == 0) foo();
    if(x != 0) foo();

That is reading the uninitialized value twice. Since it is unspecified, it does not have to be consistent, so you could get the same behavior as non-zero for the first reading, and zero for the second reading. Changing your code to:

    int x;
    if(x == 0) foo();
    else foo();

will give different output (same if you use !=).

A good optimizing compiler will just elide the whole code block.

Only if there was UB, and the point is that there probably isn't. (I'm not really knowledgeable on the C standard, so I might have misinterpreted something.)

Making an "if" statement depend on the value of the uninitialized memory is an example of what is meant by using the value, and thus UB.

In the compiler discovers UB, the Standard places no requirements of any kind on the program or compiler. It is free to launch missiles, or (more likely) assume this code cannot be reached, and omit it from the program, along with any code that reaches it unconditionally, and any check that would send control that way. Such elision is the basis for many important optimizations.

Implementations are free to define things left undefined by Standards. For example, "#include <unistd.h>" is UB by the ISO Standard, but defined by Posix, which implementations also adhere to.

Indeed, but in fact there is UB:

https://stackoverflow.com/questions/11962457/why-is-using-an...

Unspecified values are constant (since they are values), just unspecified. This behaviour is only permitted because reading uninitialised memory is UB; you won't see the same thing if x is an unspecified value.

Thanks, it seems you are right. Sorry that you got downvoted whereas my wrong statement got upvoted; such is the nature of HN.

No. It is not "undefined behavior". The "behavior" here is assignment (reading memory). It always will behave precisely and consistently: it _will_ assign the "indeterminite" value of the un-initialized memory. Using such an "indeterminite value" in other operations (e.g comparison per the link Steve B. posted above: https://www.ralfj.de/blog/2019/07/14/uninit.html) is the UB bit.

> [reading memory} always will behave precisely and consistently

What is the point of not making it UB? You can't AFAICS possibly rely on any useful way on it behaving 'precisely and consistently' so just make it UB anyway?

I think this lets you copy it around, e.g. when you have a struct that you have partially initialized.

That makes sense, finally. Thanks.

Can you write a well-defined C program that reads uninitialised memory?

Not portably, you could of course use inline assembly in practice, but the normal way of doing it is UB.

Wouldn't this do it?

int a; printf("%d", (&a + sizeof(int)));

...but that isn't a well-defined program, is it?

Reads? I think so; I believe the bad part is when you try to use it.

No, it is undefined behaviour. Check the spec.

I couldn't find the verbiage for that. The standard seems to have this under undefined behavior:

> The value of an object with automatic storage duration is used while it is indeterminate.

But reading the value without using it seems fine?

The 'object' in this context is the storage location, not the value you read from it. You're 'using' the 'object' when you read from it.

Oh, not that kind of read. I meant "read" in the context of "without actually using its value in a way that affects your program execution"–not, in what I believe the C++ term is–an ODR use. As in here: https://news.ycombinator.com/item?id=22740582

For the first, https://blog.regehr.org/archives/1621

For the second, https://www.ralfj.de/blog/2019/07/14/uninit.html

(the second one is a bit more Rust focused but the core idea is the same)

Another major way in which assembly language is closer to the hardware than C is the presence of explicit SIMD instructions.

I'm intrigued that you make that claim when as far as I know most microcode is proprietary and not necessarily documented. Also that claim is highly dependent on which cpu and manufacturer you're talking about, if the cpu needed to be updated, etc.

The micro-architectures are reasonably documented enough (e.g. we know what each the execution ports do, that register renaming is a thing) and if you look at e.g. Agner Fog's instruction tables [0] that map macro-instructions onto latencies and port counts, that gives a pretty reasonable picture of what's going on.

[0] https://www.agner.org/optimize/instruction_tables.pdf

In other words, the assembly code itself isn't really a good picture of what is happening.

Let me up the ante a bit. You also have to consider out-of-order execution, and instructions being executed in parallel, and speculative execution.

Let me quote wikipedia here:

> The Pentium 4 can have 126 micro-operations in flight at the same time. Micro-operations are decoded and stored in an Execution Trace Cache with 12,000 entries, to avoid repeated decoding of the same x86 instructions. Groups of six micro-operations are packed into a trace line. Complex instructions, such as exception handling, result in jumping to the microcode ROM. During development of the Pentium 4, microcode accounted for 14% of processor bugs versus 30% of processor bugs during development of the Pentium Pro.

Like, that's one paragraph, there are others I can cherry pick to show just how complicated the execution of microcode is. Unless you're an actual engineer on processor development and have insider info, I find it highly suspect that you could look at a decently sized chunk of assembly code and really know what happens with the microcode.

Sure you can have a table that says, it takes ballpark about this long. Ok fine, but that's not the same thing as assembly mapping cleanly to what the processor is actually doing.

Microcode is not used for the majority of operations. Are you confusing it with micro-ops?

Maybe you have a different definition in mind than I do? I'm using microcode to mean sequences of micro-ops. Wikipedia [0] seems to agree, "the microcode is a layer of hardware-level instructions that implement higher-level machine code instructions or internal state machine sequencing in many digital processing elements". My understanding is that with a couple exceptions (IIRC mov and zeroing xor are treated specially as part of register renaming) all assembly instructions get translated into microcode (i.e. a sequence of micro-ops).

[0] https://en.wikipedia.org/wiki/Microcode

I don't have the patience to go fix Wikipedia, but microcode is a patching system (it's what "processor microcode updates" means). Most of the time, that's adjusting chicken bits and other flags. Instructions can be implemented in microcode, but they are really, really slow so it's typically done for security reasons or to emulate some new features that don't require fast performance.

Micro-ops are part of the micro-architecture of the processor, and are in hardware. They are not patchable and are not software.

Microcode on x86? Don't forget to also greet our friends such as RDTSCP, CPUID, RDMSR, POPCNT (on some models) etc. Also remember to check ENTER, BOUND, etc. out in the museum vitrine.

But yeah, microcoded instructions are relatively rarely executed.

I can't find any evidence that RDTSCP is microcoded. That would defeat the whole purpose of a high-performance counter. Any source?

I can't find any primary source, but I'm pretty sure about it.

Agner Fog's instruction tables list it as issuing ~23 fused uops (a bit more or fewer depending on generation) and a throughput of 1 per ~32 cycles. That seems like it could be microcoded.

I don't think wikipedia is broken, so plz don't fix. The definition of microcode matches my understanding. I've never heard it used as a patching system per se, ever.

What do you think those "processor microcode updates" are, then? They don't have anything to do with micro-ops, or really have any influence over the core micro-architecture. It would be way too slow to make that programmable.

People have this common misconception that the programmable micro-code is what your CPU is actually executing, and x86 somehow translates into instructions for it, and this was really just because of a conflation of the terms "micro-code" and "micro-op".

Admittedly, Intel isn't the best at this term either. They have several places in the Architecture Manuals where they refer to the "micro-code synthesizer" when they mean "micro-op synthesizer"; this really has nothing to do with the micro-code ROM.

They're for updating the microcode. That is tangential to their use AIUI, but useful.

Also AIUI the microcode controls the issuing of the micro-ops.

> It would be way too slow to make that programmable

Then what is the "processor microcode updates" updating? I think this may just be a terminology mixup.

Dunno if this helps, FYI from https://stackoverflow.com/questions/17395557/observing-stale...

...and I can't copy/paste it. In the above link, look for 'embarrassing' by Krazy Glew.

An example of Instructions being implemented in Microcode is AMD's implementation of PDEP and PEXT on the Zen and Zen2 chips, leading to shockingly bad performance of 289 cycles vs 1 on Intel:

https://twitter.com/uops_info/status/1202950247900684290 https://github.com/llvm-project/llvm/blob/master/lib/Target/...

Back in the days of VAX practically everything was done via microcode instructions, perhaps that's what they're thinking of?

>inability to read uninitialized memory

    printf("%x", *(int*)0x12345678);

This is not a well-defined C program though.

At some point, the question of "well-defined C program" is philosophical. Let's get down to brass tacks: If someone sat down and wrote this, would it happily compile? Would it compile under some compilers and configurations but not others? Would it throw warnings instead of errors under some configurations? Which of these configurations are the default configurations? Which non-default configurations are considered best practices? How complex are the best practices, and how widespread is knowledge about them?

In short, how much does the concept of a "well-defined C program" differ from the concept of a "C program" as implemented in practice? Can we say that most C programs, or even a medium-sized percentage of C programs, are well-defined?

Most C programs are indeed not well-defined. Probably most of them.

Even casting 0x12345678 to int* is undefined behavior

This happens all the time on embedded systems, when you're writing a device driver, etc. Practically speaking, it's well defined what will happen.

It's implementation-defined, not undefined (see [0]). That means the behavior is well-defined by your implementation rather than by the C standard, so the code may work on one implementation but not on others.

[0]: https://stackoverflow.com/q/2397984/3476191

What makes you sure of this? I'm reasonably familiar with modern C, but I don't feel confident of the answer here. A search of Stackoverflow doesn't bring up anything that seems authoritative for C. The most relevant quotation I can find is in the Rational for C99, where Section 6.3.2.3 has:

Implicit in the Standard is the notion of invalid pointers. In discussing pointers, the Standard typically refers to “a pointer to an object” or “a pointer to a function” or “a null pointer.” A special case in address arithmetic allows for a pointer to just past the end of an array. Any other pointer is invalid.

An invalid pointer might be created in several ways. An arbitrary value can be assigned (via a cast) to a pointer variable. (This could even create a valid pointer, depending on the value.) A pointer to an object becomes invalid if the memory containing the object is deallocated or moved by realloc. Pointer arithmetic can produce pointers outside the range of an array.

Regardless how an invalid pointer is created, any use of it yields undefined behavior. Even assignment, comparison with a null pointer constant, or comparison with itself, might on some systems result in an exception.

I'm not a language lawyer, but I suspect this means that even initialization to the wrong literal might well be undefined behavior. What makes you confident that it's not, and instead is merely implementation defined?

I found this: https://stackoverflow.com/questions/51083356/does-the-c-stan...

What if it's not an "invalid pointer", but a pointer to a memory-mapped IO address, ROM, etc? I grew up learning C on 16-bit machines in the early 90's. Hard coded pointer values were very, very common.

Good find! I don't think there is anything "authoritative" there, but the discussion seems high quality. My take is that a lot of smart people disagree on which parts of that example are implementation-defined, implementation-undefined(!), or undefined-behavior. Most (but not all) think that the initial assignment is implementation defined, but 'davislor' suggests in his answer that "the line void * ptr = (char * )0x01; is already potentially undefined behavior, on an implementation where (char* )0x01 or (void* )(char* )0x01 is a trap representation".

> What if it's not an "invalid pointer", but a pointer to a memory-mapped IO address, ROM, etc?

Yes, this is central to the question. And how is the compiler to know? Is it safe to presume that the compiler can't know, and thus can't presume undefined behavior? I think the answer is in the comments you linked where 'supercat' replies to 'Peter Cordes':

The Standard makes no attempt to mandate that all implementations be suitable for low-level systems programming, nor does it in any way imply that it's possible to have a quality implementation that is suitable for low-level or systems programming without it supporting behaviors beyond those mandated by the Standard (and which might not be processed predictably by implementations that aren't suitable for systems programming).

Which is to say, yes, for a compiler implementation to actually be useful for low-level programming, it must behave in a predictable manner when given literal addresses. Unfortunately, it may be possible for a C compiler to be "standards conforming" without actually being useful for this purpose. One can only hope that at least some compilers will continue to "do the right thing" despite that lack of explicit requirements.

> Unfortunately, it may be possible for a C compiler to be "standards conforming" without actually being useful for this purpose.

It is possible for a C implementation to be conforming witout supporting low-level programming. Sometimes it even makes sense, like if you're running C code on GraalVM's LLVM bitcode interpreter. But there is no trend of "standard" C implementations following this route. While modern C compilers like to aggressively exploit undefined behavior, they generally make reasonable decisions for implementation-defined behavior. In this case, all major compilers will compile

    *(int*)0x12345678

to the obvious assembly, and what happens then depends on what your memory map looks like.

(Caveat: the compiler will still perform normal optimizations like removing unused loads or redundant stores. If the address actually points to memory-mapped I/O, you need `volatile` to prevent that.)

Reply on news.ycombinator.com