Generally speaking the compiler used also needs to be certified to the same safety critical standard, or else you will need to spend a nontrivial effort in showing equivalence of the source code and the machine code. As you can probably imagine, optimizing compilers are not used a lot :) The same goes for other parts of the toolchain that can affect the final output.
And the same goes for the microcontroller used. The hardware needs to be certified. You obviously also cannot use libraries that are not certified to the same standard. Though we're mostly talking about small microcontrollers anyway; generally everything is always linked in statically.
There are ways to incorporate complexity without doing it in safety critical code, though. Generally you develop as little safety-critical code as possible, and specify a simple interface over which it interfaces to non-critical code. Then you certify it with the argument that it will behave safely regardless of what input it gets from the non-trusted source (often you still don't need to consider adversarial situations). How this is accomplished really depends on the application: The simplest case is the one where you can ensure safety simply by shutting down the system in case of invalid input. For example, a nuclear reactor can be shut down, or some other heavy machine may be simply stopped (power cut). As you can imagine, this is not such a good solution for, say, aeroplanes. There the usual safe mode means falling back to manual operation.
Usually this separation also means separate hardware for the critical and noncritical parts. However, if you have a kernel certified to a certain level, where the certification is for noninterference of non-critical processes with critical processes, you might be able to run critical and noncritical tasks on the same microcontroller. In practice this is hard to do, as the kernel is a complex piece of software to develop.
I hear there all kinds of crazy hardware solutions for this, especially in the automotive industry, as profit margins drive developers towards single-chip solutions. Like microcontrollers where every other instruction has access to some privileged memory areas and operations, and the others do not. Thus you can get a very simple kind of separation of trusted and untrusted code without a full-blown MMU (or even without a full MPU) and without a page table.