📚 Notes

• This blog content is for learning reference only
• It is recommended to understand the concepts and implement them independently
• Welcome to exchange and discussion

task: Conditional Branches and Loops & Avoiding Undefined BehaviorConditional Branches and Loops

if-else

int f(int x) {
  int y = 0;
  if (x > 500) y = 150;
  else if (x > 300) y = 100;
  else if (x > 100) y = 75;
  return y;
}

Conditional jump instructions determine whether to enter a code block.

beq, bne, blt, bge, bltu, bgeuThere are four pseudo-instructions: bgt, ble, bgtu, bleu, which achieve their purpose by swapping operands. For example, bgt r1, r2, offset is equivalent to blt r2, r1, offset. These instructions cover all comparison operations for signed and unsigned numbers.

Tip: A single unsigned comparison instruction can be used to check a range for signed numbers.

When comparing unsigned, negative numbers are greater than all non-negative numbers.

void f(int x) { if (x >= 300 && x <= 550) printf("A"); }

switch-case

int f(int x) {
  int y = 0;
  switch (x) {
    case 1: y = 2; break;
    case 2: case 3: y = 5; break;
    case 4: case 5: case 6: case 7: y = 8; break;
    case 8: case 9: case 10: case 11: y = 10; break;
    case 12: y = 15; break;
    default: y = -1; break;
  }
  return y;
}

With -O0 or -O1 compilation, gcc generates a jump table (x -> branch entry offset). It uses lw to read the offset from the jump table, calculates the branch address, and then jumps with jr.

If compiled with -O2, gcc directly generates a result lookup table (x -> y). It reads the y value directly, skipping the jump entirely.

If cases are sparse like case 1, case 10, case 100, gcc generates if-else style code. The space cosst of building a jump table becomes too high.

while, do-while & for

int f(int n) {
  int y = 0;
  for (int i = 0; i < n; i ++) {
    y += i;
  }
  return y;
}

The machine-level representation of a loop is a conditional jump instruction that branches back.

Jumping means continuing the loop. Not jumping means exiting the loop.

Avoiding Undefined Behavior

Integer Overflow

#include <stdio.h>
#include <limits.h>
int foo(int x) { return (x + 1) > x; }
int main() {
  printf("INT_MAX=%d, cmp: %d%d\n", INT_MAX, (INT_MAX + 1) > INT_MAX, foo(INT_MAX));
  return 0;
}

gcc -w a.c && ./a.out
gcc -w -O2 a.c && ./a.out
clang -w a.c && ./a.out
clang -w -O2 a.c && ./a.out

Code that appears semantically equivalent may produce different results.

Reason: Signed integer overflow is undefined behavior.

Different machines may use different representations for signed integers (original code, inverse code, two's complement...)

The C standard cannot unify the exact behavior of signed integer overflow. For example, 32-bit original code and inverse code cannot represent -2147483648.

This leads to undefined behavior, allowing the compiler to handle it arbitrarily.

Overflow semantics of addition instructions

An ISA will use a specific encoding method to represent signed integers (most commonly two's complement).

Therefore, for an ISA, the overflow result of addition enstructions is well-defined.

RISC-V: wraps around, i.e., maximum positive number + 1 = minimum negative number.

x86: wraps around and sets the overflow flag OF (overflow flag).

MIPS: addu/addiu - wraps around, add/addi - throws an exception.

The 'u' here is misleading. Most instructors assume that the presence or absence of 'u' corresponds to signed or unsigned addition in C language. Even if not misled, it's likely unclear why 😂.

Fact: Most programming languages don't require exceptions on signed overflow.

Thus, MIPS's add/addi seems very redundant. Compilers do not use it. To save valuable opcode space, MIPSr6 finally removed the exception-throwing addi.

Shifts

#include <stdio.h>
int main() {
  int i = 30;
  printf("1 << %d = 0x%08x\n", i, 1 << i); i ++;
  printf("1 << %d = 0x%08x\n", i, 1 << i); i ++;
  printf("1 << %d = 0x%08x\n", i, 1 << i); i ++;
  printf("1 << %d = 0x%08x\n", i, 1 << i); i ++;
  return 0;
}

Whether using -O2 compilation yields different results.

The behavior of shift instructions is well-defined. However, C standards state that shifting beyond the representable range is undefined behavior.

Division by Zero

#include <stdio.h>
int f(int a, int b) { return a / b; }
__attribute__((noinline)) int g() { return 1 / 0; }
__attribute__((noinline)) int h(int a, int b) { return a / b; }
int main() {
  printf("1 / 0 = %d\n", 1 / 0);
  printf("f(1, 0) = %d\n", f(1, 0));
  printf("g(1, 0) = %d\n", g());
  printf("h(1, 0) = %d\n", h(1, 0));
  return 0;
}

clang -O2 a.c && ./a.out

C language defines division by zero as undefined behavior, so the compiler can handle it arbitrarily.

0000000000401140 <g>:
  401140: c3                    retq

clang simply removes the entire division calculation 😂.

The function's return value depends on the value in the eax register at the time of the call.

Semantics of division by zero

x86: throws an exception RISC-V: the result is defined as -1

rv64gcc a.c && ./a.out

MIPS: does not throw an exception, but the result is unpredictable. In QEMU, it might directly return the dividend as the result.

mips-linux-gnu-gcc -mno-check-zero-division -static a.c && ./a.out

But since it is undefined behavior at the language level, adding -O2 allows gcc to ignore it.

It generates a self-trap instruction for the runtime enviroment to handle. x86 - ud2RISC-V - ebreakMIPS - teq

Undefined Behavior and Mitigation

Assuming int is represented in two's complement with 32 bits:

Expression	Result	Expression	Result
UINT_MAX+1	0	1<<-1	undefined
LONG_MAX+1	undefined	1<<0	1
INT_MAX+1	undefined	1<<31	undefined
SHRT_MAX+1	INT_MAX == SHRT_MAX then undefined	1<<32	undefined
char c=CHAR_MAX; c++	???	1/0	undefined
-INT_MIN	undefined	INT_MIN/-1	undefined

Reference reading: Understanding integer overflow in C/C++, ICSE 2012

Scientific approach: sanitizer - compiler automatically inserts assert()

gcc -fsanitize=undefined a.c && ./a.out man gcc # Learn more about the -fsanitize option

Scientific approach: sanitizer - compiler automatically inserts assert()

gcc -fsanitize=undefined a.c && ./a.out
man gcc  # Learn more about the -fsanitize option

Summary

C is a high-level assembly language

The result of converting C code to binary is more understandable than expected Constants, variables, operations, conditional branches, loops Looking at C code, you can basically "manually compile" into machine instructions

Undefined behavior: the dark side of the program Can be addressed using sanitizer

Significance: writing C code allows predicting how it will run on the computer

Eliminate fear of software-hardware collaboration, and achieve precise control over machine-level behavior through software