4 ms·

How does a program work when its disallow "backward branches". Same thing with "subroutine calls" how do you structure a program without them?

kragen 2y ago
Well, you have one backward branch at the end of the program, and you inline your subroutines. I'm pretty sure you've written shaders for ancient GPUs that had similar limitations? And anything you can do in hardware you can do without subroutine calls, and in hardware the loop starts again on every clock cycle.
bdowling 2y ago
You can do a lot with a program that looks like: while(1) { if (condition1) ... if (condition2) ... // etc } Subroutine calls can be eliminated by inlining everything, using macros to make the code more manageable. Loops can be simulated using macros that expand to multiple copies of the code, one for each step. One advantage is that the program will never get into an unbounded loop because the program counter will always advance towards the end of the main loop.
Jtsummers 2y ago
It allows one backward branch. Think of it like hand-rolling your OS scheduler for processes/threads. You also have to track your "program counter" yourself. As a silly example: typedef enum state {EVEN, ODD} state_t; state_t task1 = EVEN; state_t task2 = EVEN; while (1) { switch(task1) { case EVEN: // do even things task1 = ODD; break; case ODD: // do odd things task1 = EVEN; break; default: fprintf(stderr, "WTF?\n"); exit(1); } switch(task2) { case EVEN: // do even things task2 = ODD; break; case ODD: // do odd things task2 = EVEN; break; default: fprintf(stderr, "WTF?\n"); exit(1); } } For every "process" you've unrolled like this, you have to place it into its own switch/case or call out to a function which has similar logic (when subroutines aren't disallowed). If the process is short enough you let it execute all the way through, bigger processes would need to be broken apart like above to avoid consuming an entire cycle's time (especially important in real-time systems).

kragen 2y ago

Well, you have one backward branch at the end of the program, and you inline your subroutines. I'm pretty sure you've written shaders for ancient GPUs that had similar limitations? And anything you can do in hardware you can do without subroutine calls, and in hardware the loop starts again on every clock cycle.

bdowling 2y ago

You can do a lot with a program that looks like: while(1) { if (condition1) ... if (condition2) ... // etc } Subroutine calls can be eliminated by inlining everything, using macros to make the code more manageable. Loops can be simulated using macros that expand to multiple copies of the code, one for each step. One advantage is that the program will never get into an unbounded loop because the program counter will always advance towards the end of the main loop.

Jtsummers 2y ago

It allows one backward branch. Think of it like hand-rolling your OS scheduler for processes/threads. You also have to track your "program counter" yourself. As a silly example: typedef enum state {EVEN, ODD} state_t; state_t task1 = EVEN; state_t task2 = EVEN; while (1) { switch(task1) { case EVEN: // do even things task1 = ODD; break; case ODD: // do odd things task1 = EVEN; break; default: fprintf(stderr, "WTF?\n"); exit(1); } switch(task2) { case EVEN: // do even things task2 = ODD; break; case ODD: // do odd things task2 = EVEN; break; default: fprintf(stderr, "WTF?\n"); exit(1); } } For every "process" you've unrolled like this, you have to place it into its own switch/case or call out to a function which has similar logic (when subroutines aren't disallowed). If the process is short enough you let it execute all the way through, bigger processes would need to be broken apart like above to avoid consuming an entire cycle's time (especially important in real-time systems).