V4 JIT: add some documentation and literature references.

Change-Id: I67667b74672b94b951361bf2a446476edf44b826
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

3 files changed, 33 insertions, 0 deletions

diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 64f0cde9fe..b3240b987f 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -1326,6 +1326,8 @@ protected:
     }
 };
 
+// This function converts the IR to semi-pruned SSA form. For details about SSA and the algorightm,
+// see [Appel]. For the changes needed for semi-pruned SSA form, and for its advantages, see [Briggs].
 void convertToSSA(IR::Function *function, const DominatorTree &df, DefUses &defUses)
 {
 #if defined(SHOW_SSA)
diff --git a/src/qml/jit/qv4regalloc.cpp b/src/qml/jit/qv4regalloc.cpp
index 2a3a1cd1bc..cb24db36b9 100644
--- a/src/qml/jit/qv4regalloc.cpp
+++ b/src/qml/jit/qv4regalloc.cpp
@@ -1272,6 +1272,8 @@ LifeTimeInterval *RegisterAllocator::cloneFixedInterval(int reg, bool isFP, cons
     return lti;
 }
 
+// Creates the intervals with fixed ranges. See [Wimmer2]. Note that this only applies to callee-
+// saved registers.
 void RegisterAllocator::prepareRanges()
 {
     LifeTimeInterval ltiWithCalls = createFixedInterval(_info->calls().size());
@@ -1779,3 +1781,13 @@ void RegisterAllocator::dump(IR::Function *function) const
 
     printer.print(function);
 }
+
+// References:
+//  [Wimmer1] C. Wimmer and M. Franz. Linear Scan Register Allocation on SSA Form. In Proceedings of
+//            CGO’10, ACM Press, 2010
+//  [Wimmer2] C. Wimmer and H. Mossenbock. Optimized Interval Splitting in a Linear Scan Register
+//            Allocator. In Proceedings of the ACM/USENIX International Conference on Virtual
+//            Execution Environments, pages 132–141. ACM Press, 2005.
+//  [Traub]   Omri Traub, Glenn Holloway, and Michael D. Smith. Quality and Speed in Linear-scan
+//            Register Allocation. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming
+//            Language Design and Implementation, pages 142–151, June 1998.
diff --git a/src/qml/jit/qv4regalloc_p.h b/src/qml/jit/qv4regalloc_p.h
index 9172b5dfd8..34ae19dfec 100644
--- a/src/qml/jit/qv4regalloc_p.h
+++ b/src/qml/jit/qv4regalloc_p.h
@@ -55,6 +55,25 @@ namespace JIT {
 
 class RegAllocInfo;
 
+// This class implements a linear-scan register allocator, with a couple of tweaks:
+//  - Second-chance allocation is used when an interval becomes active after a spill, which results
+//    in fewer differences between edges, and hence fewer moves before jumps.
+//  - Use positions are flagged with either "must have" register or "could have" register. This is
+//    used to decide whether a register is really needed when a temporary is used after a spill
+//    occurred.
+//  - Fixed intervals are used to denotate IR positions where certain registers are needed in order
+//    to implement the operation, and cannot be used by a temporary on that position. An example is
+//    caller saved registers, where the call will use/clobber those registers.
+//  - Hints are used to indicate which registers could be used to generate more compact code. An
+//    example is an addition, where one (or both) operands' life-time ends at that instruction. In
+//    this case, re-using an operand register for the result will result in an in-place add.
+//  - SSA form properties are used:
+//      - to simplify life-times (two temporaries will never interfere as long as their intervals
+//        are not split), resulting in a slightly faster algorithm;
+//      - when a temporary needs to be spilled, it is done directly after calculating it, so that
+//        1 store is generated even if multiple spills/splits happen.
+//      - phi-node elimination (SSA form deconstruction) is done when resolving differences between
+//        CFG edges
 class RegisterAllocator
 {
     typedef IR::LifeTimeInterval LifeTimeInterval;