0
$\begingroup$

I have this rather weird CPU architecture for which currently only an assembler exists. I won't go into too much details about this architecture as it is not publicly available. However, some quirks of it are:

  • It can only address full 32 bit words in memory
  • No shift operations
  • No internal registers. It fully operates on the system memory for each access.
  • No multiplication / division in hardware
  • No indirect jumps
  • No calls (subroutines with returns to the jumped of address) at all.

The question of writing a C compiler for this thing came up.

As far as I see, the first point of only being able to access full 32 bit words shouldn't be a problem because I could simply define a 'char' as 32 bits wide, which should be valid, weird but valid.

Missing multiplication / division / shift operations can be constructed from additions and subtractions. So this seems possible as well.

So this actually got me thinking: "What are the requirements to an architecture so that it is actually possible to write a C compiler for it?"

I'm an electrical engineer with a strong background on CPU architectures and C programming. However, I'm not too much into theoretical CS. So an easy formulated answer is highly appreciated (if possible).

$\endgroup$
9
  • $\begingroup$ Welcome to Computer Science! Your question can be interpreted in multiple ways. The boring computer science answer is that any ISA which is Turing-complete can implement any language, but I feel like that's not the answer that you want. If your question is about what requirements the C standard specifically imposes, your question might be on-topic on Stack Overflow. Alternatively, if your question is how you might practically implement a C compiler for such an architecture, you could ask that on Programming Language Design and Implementation. $\endgroup$
    – Pseudonym
    Jul 5, 2023 at 0:54
  • $\begingroup$ So I guess an "easy" way of determining, if a c compile can be built, is to map the architecture to another simple existing architecture for which turing completeness is proven / a compiler exists. My question was indeed more leaned towards the actual implementability of a standard conform c compiler instead of proving turing completeness. $\endgroup$
    – GNA
    Jul 5, 2023 at 8:15
  • $\begingroup$ No calls will compel you to inline all functions ! This seems terrible ! $\endgroup$
    – user16034
    Jul 5, 2023 at 8:21
  • $\begingroup$ I mean... I'm not an expert in compiler building. But I know how typical ISAs look like. I'm just curious, what the minumum is. Because, actually, there is a company that said "Sure. We can build a compiler for that" And I was holding back laughter in that meeting. I know that the ISA of this core will not allow any efficient output. But it should be possible in theory, right? $\endgroup$
    – GNA
    Jul 5, 2023 at 8:23
  • $\begingroup$ Without calls, you can forget recursion to arbitrary depth. This is a severe limitation. $\endgroup$
    – user16034
    Jul 5, 2023 at 8:31

1 Answer 1

2
$\begingroup$

I cannot provide an authoritative answer, but, besides key arithmetic support missing, this machine is lacking a stack mechanism, which precludes the implementation of function calls. These can be emulated by inlining, to a very limited extent, but that cannot decently be called C anymore.


Update:

The missing arithmetic operations can be implemented with decent efficiency using addition, subtraction and bitwise masking. Even floating-point can be implemented.

As said in the comments below, indirect addressing can be used to implement a stack, and indirect jumps to labels can be emulated efficiently.

So the set of missing features is vanishing...

$\endgroup$
5
  • $\begingroup$ I suppose we could emulate a stack manually, and since we lack indirect jumps, put a big "dispatcher" somewhere that has thousands of cases of "if target == labelX: jmp labelX" (to emulate return, pop a value and then jump into the dispatcher) $\endgroup$
    – harold
    Jul 5, 2023 at 9:51
  • $\begingroup$ @harold: you are right, indirect addressing allows to manage a stack, which can hold the return addresses. The dispatcher can be made efficient by structuring the tests as a binary search tree. $\endgroup$
    – user16034
    Jul 5, 2023 at 10:01
  • $\begingroup$ This hypothetical dispatcher would presumably have to be generated at link-time. (There are precedents for this, e.g. MIPS link-time optimisation.) Fair warning, though, a binary search tree implemented in code can play havoc with CPU branch prediction. $\endgroup$
    – Pseudonym
    Jul 6, 2023 at 0:30
  • $\begingroup$ @Pseudonym: I don't mind trading 1000 well-predicted branches for 10 mis-predicted ones. $\endgroup$
    – user16034
    Jul 6, 2023 at 6:52
  • 1
    $\begingroup$ @YvesDaoust I think efficiency of implementation kind of went out the window some time ago, but yes. $\endgroup$
    – Pseudonym
    Jul 6, 2023 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.