commit 9326c8029b527effbfd05314cb2976b9213c6176
parent de1256d40ded07f3806bf5cb9019669be78752d2
Author: Brian Swetland <swetland@frotz.net>
Date: Sun, 19 Dec 2021 18:38:40 -0800
docs: save some jottings
- random notes
- a llvm mailing list post about physical register live ranges
Diffstat:
2 files changed, 181 insertions(+), 0 deletions(-)
diff --git a/docs/llvm-live-ranges-of-physical-registers--lattner-2006.txt b/docs/llvm-live-ranges-of-physical-registers--lattner-2006.txt
@@ -0,0 +1,85 @@
+
+LLVM has 3 register types:
+- virtual (normal ssa regs)
+- physical (short live span, only w/in basic blocks)
+- physical untracked (SP, FP, etc, special purpose)
+
+
+https://lists.llvm.org/pipermail/llvm-dev/2006-June/006084.html
+
+[LLVMdev] Live ranges of physical registers
+Chris Lattner sabre at nondot.org
+Fri Jun 2 10:26:09 PDT 2006
+
+On Thu, 1 Jun 2006, Fernando Magno Quintao Pereira wrote:
+> I am coding a liveness analysis algorithm, and I found this comment
+> on LiveVariables.cpp:
+>
+> Line 00195 - http://llvm.org/doxygen/LiveVariables_8cpp-source.html :
+>
+> // PhysRegInfo - Keep track of which instruction was the last use of a
+> // physical register. This is a purely local property, because all
+> physical
+> // register references as presumed dead across basic blocks.
+>
+> Indeed, I am using the X86 architecture, and I could not find
+> general purpose registers such as EAX, EBX, etc, alive in between basic
+> blocks in the control flow graphs generated by LLVM.
+
+Yup!
+
+> (some specific registers, such as the stack pointer, will be, of
+> course, alive). Could someone tell me a little bit about this?
+> Is this property true due to the way LLVM generates code?
+> Can I assume that registers available for register allocation will not
+> be alive in between basic blocks?
+
+Before register allocation, there are three types of registers:
+
+1. Virtual registers. These are in SSA form, and follow all the normal
+ SSA properties. These can be live across blocks.
+2. Unallocatable physical registers (e.g. ESP). These can be live
+ anywhere and can be used/modified in ways the register allocator is not
+ required to understand.
+3. Allocatable physregs (e.g. EAX). These are *required* to only be live
+ within a machine basic block. This restriction is primarily to
+ simplify/speed up the compiler (at no loss of generality because vregs
+ can always be used). The live ranges of allocatable physregs should be
+ short, e.g. an instruction selector may emit:
+
+ EAX = vreg1234
+ EDX = vreg4567
+ div vreg1928
+ vreg8910 = EAX
+
+The set of allocatable physregs can be obtained with
+MRegisterInfo::getAllocatableSet.
+
+Also, I'd suggest reading through the CodeGen/LiveVariables.cpp file. It
+is pretty short and describes some of these issues. Here's the file
+header comment:
+
+// This file implements the LiveVariable analysis pass. For each machine
+// instruction in the function, this pass calculates the set of registers that
+// are immediately dead after the instruction (i.e., the instruction calculates
+// the value, but it is never used) and the set of registers that are used by
+// the instruction, but are never used after the instruction (i.e., they are
+// killed).
+//
+// This class computes live variables using are sparse implementation based on
+// the machine code SSA form. This class computes live variable information for
+// each virtual and _register allocatable_ physical register in a function. It
+// uses the dominance properties of SSA form to efficiently compute live
+// variables for virtual registers, and assumes that physical registers are only
+// live within a single basic block (allowing it to do a single local analysis
+// to resolve physical register lifetimes in each basic block). If a physical
+// register is not register allocatable, it is not tracked. This is useful for
+// things like the stack pointer and condition codes.
+
+
+-Chris
+
+--
+http://nondot.org/sabre/
+http://llvm.org/
+
diff --git a/docs/notes.txt b/docs/notes.txt
@@ -0,0 +1,96 @@
+
+Tracking Source Location
+------------------------
+LLVM Source Location is u32
+- "sourcemanager" assigns files into global offset space
+- high bit == macro expansion (separate space)
+- 0 = invalid (errors not related to source like command line options)
+
+
+Register Allocation
+-------------------
+aho 2e pdf p565 8.5 -- a simple code generator
+mogensen 2017 p130 -- simple IR
+
+Register Spilling and Live-Range Splitting for SSA-Form Programs
+Braun / Hack 2009
+- adapts furtherst-first algo to ssa use, no coloring needed
+
+Phys vs Virt Registers
+----------------------
+mogensen 2017 / 8.6.2 (p198pdf)
+- phys regs can be used "pre-colored" for instructions with
+ limitations, func call params, etc
+- "live range splitting" by inserting moves from colorless to pre-colored regs
+
+cmu compilers class 2018 / register selection lecture
+- similar comments re: special instructions, func calls, etc
+
+
+Live Analysis
+-------------
+torczon 2012 8.6.1 finding uninit vars w/ live info (p470pdf)
+LiveOut / UEVar / VarKill iterative method
+
+mogenson 2017 8.2 liveness analysis (p188pdf)
+
+cmu compilers 2018 - 05-liveness-analysis.pdf
+
+
+Constant Folding
+----------------
+simple constant folding
+
+ * -> C(C1*C2)
+ / \
+C1 C2
+
+more complex const folding (various algebraic transforms, etc)
+
+ * -> *
+ / \ / \
+C1 * V1 C(C1*C2)
+ / \
+ V1 C2
+
+
+Assorted Resources
+------------------
+https://groups.seas.harvard.edu/courses/cs153/2019fa/schedule.html
+https://blog.yossarian.net/2020/10/23/Understanding-static-single-assignment-forms
+https://lowlevelbits.org/how-to-learn-compilers-llvm-edition/
+
+Tiny Scheme / 5k repl
+---------------------
+http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf
+https://github.com/udem-dlteam/ribbit
+
+
+Code Snippets
+-------------
+
+int fib(int n) {
+ int a = 0;
+ int b = 1;
+ int z = 0;
+ while (n != z) {
+ int t = a + b;
+ a = b;
+ b = t;
+ n = n - 1;
+ z = 0;
+ }
+ return a;
+}
+
+int gcd(int x1, int x2) {
+ while (x2 != 0) {
+ int q = x1 / x2;
+ int t = q * x2;
+ int r = x1 - t;
+ x1 = x2;
+ x2 = r;
+ }
+ return x1;
+}
+
