Skip to content

Instantly share code, notes, and snippets.

View pre_cps.md

Partial redundancy elimination (PRE) is an optimization where you eliminate computations that are redundant on some but not all control flow paths.

Example:

if (...) {
    // ...
    int a = x + y;
    // ...
} else {
    // ...
View hejlsberg_fp.asm
; Math48 Floating Point Package
; Version 1.1 Revision 1
; by Anders Hejlsberg
; 2532 Bytes
;HOPTABEL
JP FPADD
JP FPSUB
JP FPMUL
View tp3.asm
; https://web.archive.org/web/20190701203222/https://www.pcengines.ch/tp3.htm
; The disassembler was applied to a copy of TP 3.01A downloaded from WinWorld.
; I postprocessed the disassembly with a script to clean up spacing and column alignment.
; *** TURBO PASCAL version 3.01 A source code
; ***
; *** commented by Pascal Dornier
; *** all rights reserved
; "***
cseg $100 ; "COM file...
View vec.c
// A sketch of persistent vectors with the in-place v2 trick.
typedef struct Leaf Leaf;
typedef struct Node Node;
typedef struct Vec Vec;
typedef uint32_t Ver;
typedef uint64_t Val;
typedef int32_t RelPtr;
View branch_math.md

Let's say you have to perform a 4-way case analysis and are given a choice between cascaded 2-way branches or a single 4-way branch.

What's the difference in branch misprediction penalties, assuming the 4 cases are random?

Denote the branch penalty by x (which is 15-20 cycles on Sky Lake according to Agner Fog).

With the 4-way branch, the worst-case branch penalty is x. The expected branch penalty is 3/4 x: there's a 3/4 chance of x penalty.

View lex_parse.c
// Lexer
#define TOK_CHAR(ch1, tok1) \
case ch1: \
next_ch(); \
tok = TOK_##tok1; \
tok_prec = 0; \
break;
#define TOK_EXPR(ch1, tok1, prec1, lexpr1, rexpr1) \
View gen_mul.c
void gen_mul(Value *dest, Value *src) {
if (isconst(dest)) {
gen_swap(dest, src); // this doesn't generate instructions and just swaps descriptors ("value renaming")
}
val_to_reg(dest); // the post-condition is that dest is allocated to a register
if (isconst(src) && isimm32(src->ival)) {
if (src->ival == 0) {
int_to_val(dest, 0);
} else if (src->ival == 1) {
// do nothing
View do_mul.c
// semantic analysis, called by parser
void do_mul(Value *dest, Value *src) {
promote_arith(dest, src);
if (isint(dest)) {
if (isconst2(dest, src)) {
dest->ival *= src->ival;
} else {
gen_mul(dest, src);
}
View expr.c
void parse_expr(Value *dest);
Sym *parse_ident(void) {
if (tok != TOK_IDENT) {
error("Expected identifier");
}
Sym *ident = tok_sym;
next();
return ident;
}
View asm_x64.c
// x64 encoding
enum Reg {
RAX, RCX, RDX, RBX, RSP, RBP, RSI, RDI,
R8, R9, R10, R11, R12, R13, R14, R15,
};
enum XmmReg {
XMM0, XMM1, XMM2, XMM3, XMM4, XMM5, XMM6, XMM7,
XMM8, XMM9, XMM10, XMM11, XMM12, XMM13, XMM14, XMM15,
You can’t perform that action at this time.