Article at version 1
If ready() returns zero, ready() && consume() leaves consume() uncalled. A compiler emitting code for that expression needs a path around the second call. Computing both values up front can change what the program does even when the final Boolean result stays the same.
In C, && and || evaluate the left operand first. If the result already determines the expression's value, evaluation skips the right operand. Both operators yield an int equal to 0 or 1. WG14 C11 draft, §§6.5.13–14
This example starts with a small expression tree for A && (B || !C). Each letter represents a call that reports an integer and can have side effects. The emitter writes C11 with explicit if and goto statements so you can inspect and run the result with an ordinary compiler.
Give the expression two destinations
The emitter accepts a label for the true result and another for the false result. After evaluating the required calls, the generated code transfers control to one of those labels.
| Expression node | Where its left operand sends control | What happens next |
|---|---|---|
A && B |
True goes to a new label for B. False goes to the caller's false label. |
At the new label, B uses the caller's true and false labels. |
A || B |
True goes to the caller's true label. False goes to a new label for B. |
At the new label, B uses the caller's true and false labels. |
!A |
A receives the original destinations in reverse order. |
No separate arithmetic operation is needed. |
A |
The probe runs once. Its nonzero result selects the true label. | A zero result selects the false label. |
The dedicated label for the right operand is the point where execution continues when the left operand requires another test. Clang uses the same idea in EmitBranchOnBoolExpr, where the destinations are basic blocks. Clang branch emission source
Emit a function from the tree
Save this as emit_bool.c. The example builds a fixed, well-formed tree in memory. Each probe identifier is a hard-coded letter from A to C. The label counter starts at 2 because the generator reserves labels 0 and 1 for the function's final true and false returns.
#include <stdio.h>
enum Kind { TEST, AND, OR, NOT };
struct Expr {
enum Kind kind;
char test;
const struct Expr *left;
const struct Expr *right;
};
static void emit_cond(FILE *out, const struct Expr *expr,
unsigned yes, unsigned no, unsigned *next_label)
{
switch (expr->kind) {
case TEST:
fprintf(out, " if (probe('%c')) goto L%u;\n"
" goto L%u;\n", expr->test, yes, no);
break;
case AND: {
const unsigned rhs = (*next_label)++;
emit_cond(out, expr->left, rhs, no, next_label);
fprintf(out, "L%u:\n", rhs);
emit_cond(out, expr->right, yes, no, next_label);
break;
}
case OR: {
const unsigned rhs = (*next_label)++;
emit_cond(out, expr->left, yes, rhs, next_label);
fprintf(out, "L%u:\n", rhs);
emit_cond(out, expr->right, yes, no, next_label);
break;
}
case NOT:
emit_cond(out, expr->left, no, yes, next_label);
break;
}
}
int main(void)
{
const struct Expr a = {TEST, 'A', NULL, NULL};
const struct Expr b = {TEST, 'B', NULL, NULL};
const struct Expr c = {TEST, 'C', NULL, NULL};
const struct Expr not_c = {NOT, 0, &c, NULL};
const struct Expr either = {OR, 0, &b, ¬_c};
const struct Expr root = {AND, 0, &a, &either};
FILE *out = fopen("lowered.c", "w");
if (out == NULL) {
perror("lowered.c");
return 1;
}
unsigned next_label = 2; /* L0 and L1 are the final exits. */
fputs("int probe(char id);\n\nint lowered(void)\n{\n", out);
emit_cond(out, &root, 0, 1, &next_label);
fputs("L0:\n return 1;\nL1:\n return 0;\n}\n", out);
const int write_failed = ferror(out);
if (fclose(out) == EOF || write_failed) {
fputs("Could not finish writing lowered.c.\n", stderr);
return 1;
}
return 0;
}
The generated lowered.c contains the following function.
int probe(char id);
int lowered(void)
{
if (probe('A')) goto L2;
goto L1;
L2:
if (probe('B')) goto L0;
goto L3;
L3:
if (probe('C')) goto L1;
goto L0;
L0:
return 1;
L1:
return 0;
}
Trace a few paths through it:
- If
Ais zero, execution goes straight toL1. OnlyAruns. - If
AandBare nonzero, execution reachesL0afterB. OnlyAandBrun. - If
Ais nonzero andBis zero, execution reachesL3and callsC. Because the expression uses!C, a nonzeroCgoes to the false exit.
Each probe uses a conditional jump for the true outcome and an unconditional jump for the false outcome. Keeping both destinations explicit makes it easy to inspect which probe each path can reach.
Compare both the value and the call trace
Save this as check_bool.c. The probe appends its letter to a log. The checker runs native C and the generated function on all eight combinations, resetting the log between runs.
#include <stdio.h>
#include <string.h>
int lowered(void);
static int values[3];
static char trace[4];
static size_t length;
int probe(char id)
{
if (length < sizeof trace - 1) {
trace[length++] = id;
trace[length] = '\0';
} else {
trace[0] = '!'; /* Make an unexpected fourth call visible. */
}
switch (id) {
case 'A': return values[0];
case 'B': return values[1];
case 'C': return values[2];
default: return 0;
}
}
int main(void)
{
for (unsigned mask = 0; mask < 8; ++mask) {
values[0] = (mask & 4) != 0;
values[1] = (mask & 2) != 0;
values[2] = (mask & 1) != 0;
length = 0;
trace[0] = '\0';
const int expected = probe('A') && (probe('B') || !probe('C'));
char expected_trace[sizeof trace];
strcpy(expected_trace, trace);
length = 0;
trace[0] = '\0';
const int actual = lowered();
if (actual != expected || strcmp(trace, expected_trace) != 0) {
fprintf(stderr, "Mismatch for case %u.\n", mask);
return 1;
}
printf("%d%d%d -> %d (%s)\n",
values[0], values[1], values[2], actual, trace);
}
return 0;
}
I tested these commands with GCC targeting Windows x64 through MinGW-w64. Run them in a working directory where the emitter can create or replace lowered.c.
gcc -std=c11 -Wall -Wextra -Werror -pedantic emit_bool.c -o emit_bool.exe
.\emit_bool.exe
gcc -std=c11 -O2 -Wall -Wextra -Werror -pedantic lowered.c check_bool.c -o check_bool.exe
.\check_bool.exe
The three input digits stand for A, B, and C. The last column shows which calls ran.
000 -> 0 (A)
001 -> 0 (A)
010 -> 0 (A)
011 -> 0 (A)
100 -> 1 (ABC)
101 -> 0 (ABC)
110 -> 1 (AB)
111 -> 1 (AB)
Check the traces for 100 and 110. Both return 1, but the first needs to call C and the second stops after B. A test that compares only the return value misses that distinction. Both the results and the call traces matched at -O0 and -O2.
When the expression controls an if, a compiler can pass the destinations for the two arms directly. When it needs a Boolean value, the two paths can produce 1 and 0 and return or merge them. The language rule governs which calls occur and in what order. The backend chooses the instructions that preserve that behavior. LLVM conditional branch reference
My compiler course puts these techniques in a larger project, with lessons on logical operators, generating if statements, and creating labels. Creating a C Compiler From Scratch Video Course!
Originally published by @nibblebits