jvm-summit-talk/jvm-summit-talk.factor

   1 ! Copyright (C) 2009 Slava Pestov.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: slides help.markup math math.private kernel sequences
   4 slots.private ;
   5 IN: jvm-summit-talk
   6
   7 CONSTANT: jvm-summit-slides
   8 {
   9     { $slide "Factor language implementation"
  10         "Goals: expressiveness, metaprogramming, performance"
  11         "We want a language for anything from scripting DSLs to high-performance numerics"
  12         "I assume you know a bit about compiler implementation: parser -> frontend -> optimizer -> codegen"
  13         { "This is " { $strong "not" } " a talk about the Factor language" }
  14         { "Go to " { $url "https://factorcode.org" } " to learn the language" }
  15     }
  16     { $slide "Why are dynamic languages slow?"
  17         "Branching and indirection!"
  18         "Runtime type checks and dispatch"
  19         "Integer overflow checks"
  20         "Boxed integers and floats"
  21         "Lots of allocation of temporary objects"
  22     }
  23     { $slide "Interactive development"
  24         "Code can be reloaded at any time"
  25         "Class hierarchy might change"
  26         "Slots may be added and removed"
  27         "Functions might be redefined"
  28     }
  29     { $slide "Factor's solution"
  30         "Factor implements most of the library in Factor"
  31         "Library contains very generic, high-level code"
  32         "Always compiles to native code"
  33         "Compiler removes unused generality from high-level code"
  34         "Inlining, specialization, partial evaluation"
  35         "And deoptimize when assumptions change"
  36     }
  37     { $slide "Introduction: SSA form"
  38         "Every identifier only has one global definition"
  39         {
  40             "Not SSA:"
  41             { $code
  42                 "x = 1"
  43                 "y = 2"
  44                 "x = x + y"
  45                 "if(z < 0)"
  46                 "    t = x + y"
  47                 "else"
  48                 "    t = x - y"
  49                 "print(t)"
  50             }
  51         }
  52     }
  53     { $slide "Introduction: SSA form"
  54         "Rename re-definitions and subsequent usages"
  55         {
  56             "Still not SSA:"
  57             { $code
  58                 "x = 1"
  59                 "y = 2"
  60                 "x1 = x + y"
  61                 "if(z < 0)"
  62                 "    t = x1 + y"
  63                 "else"
  64                 "    t = x1 - y"
  65                 "print(t)"
  66             }
  67         }
  68     }
  69     { $slide "Introduction: SSA form"
  70         "Introduce “φ functions” at control-flow merge points"
  71         {
  72             "This is SSA:"
  73             { $code
  74                 "x = 1"
  75                 "y = 2"
  76                 "x1 = x + y"
  77                 "if(z < 0)"
  78                 "    t1 = x1 + y"
  79                 "else"
  80                 "    t2 = x1 - y"
  81                 "t3 = φ(t1,t2)"
  82                 "print(t3)"
  83             }
  84         }
  85     }
  86     { $slide "Why SSA form?"
  87         {
  88             "Def-use chains:"
  89             { $list
  90                 "Defs-of: instructions that define a value"
  91                 "Uses-of: instructions that use a value"
  92             }
  93             "With SSA, defs-of has exactly one element"
  94         }
  95     }
  96     { $slide "Def-use chains"
  97         "Simpler def-use makes analysis more accurate."
  98         {
  99             "Non-SSA example:"
 100             { $code
 101                 "if(x < 0)"
 102                 "    s = new Circle"
 103                 "    a = area(s1)"
 104                 "else"
 105                 "    s = new Rectangle"
 106                 "    a = area(s2)"
 107             }
 108         }
 109     }
 110     { $slide "Def-use chains"
 111         {
 112             "SSA example:"
 113             { $code
 114                 "if(x < 0)"
 115                 "    s1 = new Circle"
 116                 "    a1 = area(s1)"
 117                 "else"
 118                 "    s2 = new Rectangle"
 119                 "    a2 = area(s2)"
 120                 "a = φ(a1,a2)"
 121             }
 122
 123         }
 124     }
 125     { $slide "Factor compiler overview"
 126         "High-level SSA IR constructed from stack code"
 127         "High level optimizer transforms high-level IR"
 128         "Low-level SSA IR is constructed from high-level IR"
 129         "Low level optimizer transforms low-level IR"
 130         "Register allocator runs on low-level IR"
 131         "Machine IR is constructed from low-level IR"
 132         "Code generation"
 133     }
 134     { $slide "High-level optimizer"
 135         "Frontend: expands macros, inline higher order functions"
 136         "Propagation: inline methods, constant folding"
 137         "Escape analysis: unbox tuples"
 138         "Dead code elimination: clean up"
 139     }
 140     { $slide "Higher-order functions"
 141         "Almost all control flow is done with higher-order functions"
 142         { { $link if } ", " { $link times } ", " { $link each } }
 143         "Calling a block is an indirect jump"
 144         "Solution: inline higher order functions at the call site"
 145         "Inline the block body at the higher order call site in the function"
 146         "Record inlining in deoptimization database"
 147     }
 148     { $slide "Generic functions"
 149         "A generic function contains multiple method bodies"
 150         "Dispatches on the class of argument(s)"
 151         "In Factor, generic functions are single dispatch"
 152         "Almost equivalent to message passing"
 153     }
 154     { $slide "Tuple slot access"
 155         "Slot readers and writers are generic functions"
 156         "Generated automatically when you define a tuple class"
 157         { "The generated methods call " { $link slot } ", " { $link set-slot } " primitives" }
 158         "These primitives are not type safe; the generic dispatch performs the type checking for us"
 159         "If class of dispatch value known statically, inline method"
 160         "This may result in more methods inlining from additional specialization"
 161     }
 162     { $slide "Generic arithmetic"
 163         { { $link + } ", " { $link * } ", etc perform a double dispatch on arguments" }
 164         { "Fixed-precision integers (" { $link fixnum } "s) upgrade to " { $link bignum } "s automatically" }
 165         "Floats and complex numbers are boxed, heap-allocated"
 166         "Propagation of classes helps for floats"
 167         "But not for fixnums, because of overflow checks"
 168         "So we also propagate integer intervals"
 169         "Interval arithmetic: etc, [a,b] + [c,d] = [a+c,b+d]"
 170     }
 171     { $slide "Slot value propagation"
 172         "Complex numbers are even trickier"
 173         "We can have a complex number with integer components, float components"
 174         "Even if we inline complex arithmetic methods, still dispatching on components"
 175         "Solution: propagate slot info"
 176     }
 177     { $slide "Constraint propagation"
 178         "Contrieved example:"
 179         { $code
 180             "x = •"
 181             "b = isa(x,array)"
 182             "if(b)"
 183             "    a = length(x)"
 184             "else"
 185             "    b = length(x)"
 186             "c = φ(a,b)"
 187         }
 188         { "We should be able to inline the call to " { $snippet "length" } " in the true branch" }
 189     }
 190     { $slide "Constraint propagation"
 191         "We build a table:"
 192         { $code
 193             "b true => x is array"
 194             "b false => x is ~array"
 195         }
 196         { "In true branch, apply all " { $snippet "b true" } " constraints" }
 197         { "In false branch, apply all " { $snippet "b false" } " constraints" }
 198     }
 199     { $slide "Going further"
 200         "High-level optimizer eliminates some dispatch overhead and allocation"
 201         {
 202             { "Let's take a look at the " { $link float+ } " primitive" }
 203             { $list
 204                 "No type checking anymore... but"
 205                 "Loads two tagged pointers from operand stack"
 206                 "Unboxes floats"
 207                 "Adds two floats"
 208                 "Boxes float result and perform a GC check"
 209             }
 210         }
 211     }
 212     { $slide "Low-level optimizer"
 213         "Frontend: construct LL SSA IR from HL SSA IR"
 214         "Alias analysis: remove redundant slot loads/stores"
 215         "Value numbering: simplify arithmetic"
 216         "Representation selection: eliminate boxing"
 217         "Dead code elimination: clean up"
 218         "Register allocation"
 219     }
 220     { $slide "Constructing low-level IR"
 221         { "Low-level IR is a " { $emphasis "control flow graph" } " of " { $emphasis "basic blocks" } }
 222         "A basic block is a list of instructions"
 223         "Register-based IR; infinite, uniform register file"
 224         { "Instructions:"
 225             { $list
 226                 "Subroutine calls"
 227                 "Machine arithmetic"
 228                 "Load/store values on operand stack"
 229                 "Box/unbox values"
 230             }
 231         }
 232     }
 233     { $slide "Inline allocation and GC checks"
 234         {
 235             "Allocation of small objects can be done in a few instructions:"
 236             { $list
 237                 "Bump allocation pointer"
 238                 "Write object header"
 239                 "Fill in payload"
 240             }
 241         }
 242         "Multiple allocations in the same basic block only need a single GC check; saves on a conditional branch"
 243     }
 244     { $slide "Alias analysis"
 245         "Factor constructors are just ordinary functions"
 246         { "They call a primitive constructor: " { $link new } }
 247         "When a new object is constructed, it has to be initialized"
 248         "... but the user's constructor probably fills in all the slots again with actual values"
 249         "Local alias analysis eliminates redundant slot loads and stores"
 250     }
 251     { $slide "Value numbering"
 252         { "A form of " { $emphasis "redundancy elimination" } }
 253         "Requires use of SSA form in order to work"
 254         "Define an equivalence relation over SSA values"
 255         "Assign a “value number” to each SSA value"
 256         "If two values have the same number, they will always be equal at runtime"
 257     }
 258     { $slide "Types of value numbering"
 259         "Many variations: algebraic simplifications, various rewrite rules can be tacked on"
 260         "Local value numbering: in basic blocks"
 261         "Global value numbering: entire procedure"
 262         "Factor only does local value numbering"
 263     }
 264     { $slide "Value graph and expressions"
 265         { $table
 266             {
 267                 {
 268                     "Basic block:"
 269                     { $code
 270                         "x = •"
 271                         "y = •"
 272                         "a = x + 1"
 273                         "b = a + 1"
 274                         "c = x + 2"
 275                         "d = b - c"
 276                         "e = y + d"
 277                     }
 278                 }
 279                 {
 280                     "Value numbers:"
 281                     { $code
 282                         "V1: •"
 283                         "V2: •"
 284                         "V3: 1"
 285                         "V4: 2"
 286                         "V5: (V1 + V3)"
 287                         "V6: (V5 + V3)"
 288                         "V7: (V3 + V4)"
 289                         "V8: (V6 - V7)"
 290                         "V9: (V2 + V8)"
 291                     }
 292                 }
 293             }
 294         }
 295     }
 296     { $slide "Expression simplification"
 297         {
 298             "Constant folding: if V1 and V2 are constants "
 299             { $snippet "(V1 op V2)" }
 300             " can be evaluated at compile-time"
 301         }
 302         {
 303             "Reassociation: if V2 and V3 are constants "
 304             { $code "((V1 op V2) op V3) => (V1 op (V2 op V3))" }
 305         }
 306         {
 307             "Algebraic identities: if V2 is constant 0, "
 308             { $code "(V1 + V2) => V1" }
 309         }
 310         {
 311             "Strength reduction: if V2 is a constant power of two, "
 312             { $code "(V1 * V2) => (V1 << log2(V2))" }
 313         }
 314         "etc, etc, etc"
 315     }
 316     { $slide "Representation selection overview"
 317         "Floats and SIMD vectors need to be boxed"
 318         "Representation: tagged pointer, unboxed float, unboxed SIMD value..."
 319         "When IR is built, no boxing or unboxing instructions inserted"
 320         "Representation selection pass makes IR consistent"
 321     }
 322     { $slide "Representation selection algorithm"
 323         {
 324             "For each SSA value:"
 325             { $list
 326                 "Compute possible representations"
 327                 "Compute cost of each representation"
 328                 "Pick representation with minimum cost"
 329             }
 330         }
 331         {
 332             "For each instruction:"
 333             { $list
 334                 "If it expects a value to be in a different representation, insert box or unbox code"
 335             }
 336         }
 337     }
 338     { $slide "Register allocation"
 339         "Linear scan algorithm used in Java HotSpot Client"
 340         "Described in Christian Wimmer's masters thesis"
 341         "Works fine on x86-64, not too great on x86-32"
 342         "Good enough since basic blocks tend to be short, with lots of procedure calls"
 343         "Might switch to graph coloring eventually"
 344     }
 345     { $slide "Compiler tools"
 346         "Printing high level IR"
 347         "Printing low level IR"
 348         "Disassembly"
 349         "Display call tree"
 350         "Display control flow graph"
 351         "Display dominator tree"
 352     }
 353 }
 354
 355 : jvm-summit-talk ( -- )
 356     jvm-summit-slides "JVM Summit talk" slides-window ;
 357
 358 MAIN: jvm-summit-talk