← Back
Home › Systems › Compilers and language tooling

shader-compiler

shader compiler

DXC, naga

SystemTechniques · 10Primitives · 17 shader-compiler Dataflow analysiscompilers · medium: Compute a fact per program point (live variables, reaching definitions, available expressions) by iterating transfer functions over the CFG to a fixed point.›Function inliningcompilers · medium: Inline call sites by cost model and call-graph order; enables downstream optimizationsInstruction schedulingcompilers · medium: List scheduling over dependence DAGs with latency models; software pipelining of loopsInstruction selectioncompilers · medium: Cover the IR with target instruction patterns at least cost; greedy maximal munch is simple, dynamic programming over a tree or DAG is optimal.›Register allocationcompilers · medium: Map unlimited virtual registers onto a few machine registers, spilling the rest to the stack; linear scan is fast, graph coloring and splitting allocators give better code.›Sparse conditional constant propaga…compilers · medium: SCCP: constant propagation plus unreachable-code detection on SSAStructured control flowcompilers · medium: Turn a jump graph into nested block, loop and if constructs with numbered breaks; reducible graphs need no duplication.›SSA formcompilers · low: Give every variable exactly one definition, merging at joins with phi functions; def-use becomes explicit and optimizations turn sparse and cheap.›Dominator treecompilers · low: Dominators via Lengauer-Tarjan or Cooper-Harvey-Kennedy; dominance frontiers for SSAPeephole optimizationcompilers · low: Local pattern rewrites on short instruction windows or IRRecursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›Spirv binary formatcompilers · low: SPIR-V module structure: SSA instructions, decorations, structured control flow rulesPipeline state cachinggraphics · low: Cache compiled shader pipelines across runs, precompile permutations, avoid hitchesControl-flow graphcompilers · low: Split a linear instruction list into basic blocks and connect them by jumps; the graph every optimizer, SSA builder and dataflow pass walks.›Topological sortgraphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Strongly connected componentsgraphs · low: Tarjan/Kosaraju SCCs for cycle detection in dependency graphsd-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Instruction pipelininghardware-os · low: Pipeline stages, hazards, forwarding and stalls in CPU coresMachine code emissioncompilers · low: Encode instructions to bytes for x86-64 and AArch64, branch relaxation, constant poolsTree pattern matchingcompilers · low: Matching AST patterns with metavariablesInterval treedata-structures · low: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.›Name resolutioncompilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›+ 3 more techniques+ 1 more primitives

Similar systems

Share the most building blocks with this one.

compiler 42 %cuda-platform 28 %wasm-toolchain 27 %gpu-driver 20 %decompiler 20 %