The Wolfram Compiler

Abdul Dakkak
Kernel Developer
Wolfram Research

Join the Conversation #WolframTechConf

Disclaimer

Most of what you are about to see is internal detail and is not exposed to users. We will have a mechanism to opt-in and see the details.

The Objective

Write code in Wolfram language

Avoid writing C/C++/Assembly

Give similar speed to C/C++ code

Predictable performance guarantees

Explainable semantics and design decisions

The Hardware

More multicore processors 10,16,...,200 core systems

More memory / disk space

More distributed and decentralized

More specialized hardware for certain tasks

The Hardware

from https://www.codeproject.com/Articles/1151592/Modernize-Your-Code-for-Intel-Xeon-Phi-Processors

The Hardware

from http://sean-parent.stlab.cc/presentations/2017-01-18-concurrency/2017-01-18-concurrency.pdf

The Strategy

Provide tools for program analysis, code generation, and type inferencing

Generate performant code

Reduce magic, and instead have sensible rules that are clearly explainable

Generated code can be used outside the Wolfram language

Target modern and future hardware

Can opt-in/out of optimizations

Allow advanced users to define their own EDSL within the Wolfram language

Allow advanced users to intermix Mathematica with C/Assembly/LLVM/...

The Compiler

The Compiler

The Compiler

The Compiler

The AST

Needs["Compile`AST`"]
Needs["CompileAST`Create`"]
Needs["CompileAST`Class`"]
Needs["Compile`AST`Export`"]
Needs["CompileAST`PatternMatching`"]

mexpr=CreateMExpr[Module[{x},x+Module[{x},x+y]]];
ShowMExpr[mexpr]

Can perform transformations on the expression

RunPass[MExprBindingRewritePass,mexpr];
ShowMExpr[mexpr]

Can perform analysis on the expression

mexpr=CreateMExpr[Module[{x},x+y]];
MExprFreeVariables[mexpr]

Can perform transformations on the expression

mexpr=CreateMExpr[Function[{y},Module[{x},x+y]]];
MExprBetaReduce[mexpr,{CreateMExpr[z]}]

The Macro System

mexpr=CreateMExpr[Take[lst,UpTo[8]]];
RunPasses[{MExprBindingRewritePass},mexpr];
ShowMExpr[mexpr]

Declare what UpTo really means for Take

RegisterBuiltinMacro[Take,
Take[lst_,UpTo[n_]]->Take[lst,Min[Length[lst],n]]
];

Can now use UpTo in the rest of the code

mexpr=MacroExpand[mexpr];
ShowMExpr[mexpr]

Can be used to perform program transformation / optimization

RegisterBuiltinMacro[Composition,
Composition[a_,Composition[b_,c_]]->Composition[a,b,c],
Composition[Composition[a_,b_],c_]->Composition[a,b,c]
];
RegisterBuiltinMacro[Length,
Length[Map[_,lst_]]->Length[lst]
];
RegisterBuiltinMacro[Map,
Map[f_,Map[g_,lst_]]->Map[Composition[f,g],lst],
Map[f_,Take[Map[g_,lst_],n_]]->Map[Composition[f,g],Take[lst,n]]
];

mexpr=MacroExpand[CreateMExpr[Map[myFun1,Map[myFun2,Take[Map[myFun3,lst],UpTo[8]]]]]];
ShowMExpr[mexpr]

The Intermediate Representation

pm=CompileExpr[Function[{Typed[x,"Integer64"]},Module[{counter=x,p=0},While[counter-->0,p++];p]]];
pm["toDot"]

pm["getElement",1]["toString"]

Have prototype to translate the SSA to CPS (lambda calculus).

The Type System

Independent of the compiler: no types are hard coded

Uses unification to infer missing types

Support of abstract types: type classes (in haskell), interfaces (in type script), prototypes (in swift), traits (in rust)

Allows for type overlaps, sequences, and recursion

Limited support for dependent types and type evaluation

The Type System

from http://blog.coldflake.com/posts/choosing-the-Type-of-your-Types/

The Type System

$TypeEnvironment["abstracttypes"]["graphForm"]

Example 1: Compile Time Generation

Scenario

A program needs a computation that can be known at compile time (ahead of time). Can be done in Mathematica using the With statement:

fib10=With[{
f=Fibonacci[10]
},
compute=Function[{},
f
]
]

Evaluating Fibonacci at Compile time Using Macros

<<Compile`

computeFib[x_]:=With[{res=Factorial[x["data"]]},CreateMExprLiteral[res]]
RegisterBuiltinMacro[Fib,
Fib[0]->1,
Fib[1]->1,
Fib[a_Integer]->Compile`Internal`MacroEvaluate[computeFib[a]]
];

mexpr=MacroExpand[CreateMExpr[Fib[30]]];
ShowMExpr[mexpr]

Evaluating Fibonacci at Compile time Using Type System

ClearTypeEnvironment[];
InitializeTypes[];

$TypeEnvironment["reopen"];

$TypeEnvironment["declareType",TypeAlias["Fib"[TypeLiteral[0,"Integer"]],TypeLiteral[1,"Integer"]]];
$TypeEnvironment["declareType",TypeAlias["Fib"[TypeLiteral[1,"Integer"]],TypeLiteral[1,"Integer"]]];
$TypeEnvironment["declareType",TypeAlias["Fib"[TypeLiteral[2,"Integer"]],TypeLiteral[2,"Integer"]]];
$TypeEnvironment["declareFunction","Fib",Type[TypeForAll[{"a"},{"a"}->TypeEvaluate[Times,{"a","Fib"[TypeEvaluate[Subtract,{"a",TypeLiteral[1,"Integer"]}]]}]]]];

$TypeEnvironment["finalize"]

generateConstant[st_,Constant[e_Integer]]:=st["resolveType",Type[TypeLiteral[e,"Integer"]]];
st=CreateTypeInferenceState[GenerateLambda,"LanguageExtensions"-><|Constant->generateConstant|>];
ty=st["infer",App[Variable["Fib"],{3}]];
ty["unresolve"]

Example 2: Low Level Code Generation

Scenario

Implementing architecture independent vector operations

Using Type System

Defining rgb to grayscale

ClearAll[Compile`$ThrowStackException];
ir=CompileToLLVMIR[
Function[{Typed[a,"SIMDVector"["Real32",4]]},Total[a*Compile`Intrinsics`Pack[Typed[0.299,"Real32"],Typed[0.587,"Real32"],Typed[0.114,"Real32"],Typed[0,"Real32"]]]],
"OptimizationLevel"->0,"LLVMOptimization"->"ClangOptimization"[0],"CreateWrapper"->"Legacy"
]

Defining more generic simd operations

ClearAll[Compile`$ThrowStackException];
ir=CompileToLLVMIR[
Function[{},
Function[{Typed[a,"SIMDVector"["Real32",4]]},Dot[a,a]];
Function[{Typed[a,"SIMDVector"["Real32",4]]},Min[a,a]];
Function[{Typed[a,"SIMDVector"["Real32",4]]},Max[a,a]];
Function[{Typed[a,"SIMDVector"["Real32",4]]},a+a];
Function[{Typed[a,"SIMDVector"["Real32",4]]},a-a];
Function[{Typed[a,"SIMDVector"["Integer64",4]]},a];
Function[{Typed[a,"SIMDVector"["Integer64",4]]},Length[a]];
Function[{Typed[a,"SIMDVector"["Integer64",4]]},a+1];
Function[{Typed[a,"SIMDVector"["Real32",4]]},a*Typed[3,"Real32"]];
Function[{},Module[{k=Typed[3.0,"Real32"]},Compile`Intrinsics`Pack[k,k,k,k]]];
Function[{Typed[a,"SIMDVector"["Real32",4]]},Compile`Intrinsics`Fill[a,Typed[3.0,"Real32"]]];
Function[{Typed[a,"SIMDVector"["Real32",4]]},Length[a]];
0
],
"OptimizationLevel"->0,"LLVMOptimization"->"ClangOptimization"[3],"CreateWrapper"->False]

Optimizations

ClearAll[Compile`$ThrowStackException];
ir=CompileToLLVMIR[
Function[{Typed[a,"NumberArray"["Real32",1]]},Length@Compile`Internal`PartitionedArrayView[a,0,Typed[4,TypeLiteral[4,"Integer64"]]]],
"OptimizationLevel"->2,"LLVMOptimization"->"ClangOptimization"[1],"CreateWrapper"->False
]

Example 3: Defining Derivative

Problem

Implementing derivative

D[Sin[x]+Cos[x],x]

Using Macros

RegisterBuiltinMacro[D,
D[_Integer,x_]->0,
D[Sin[x_],x_]->Cos[x],
D[Cos[x_],x_]->-Sin[x],
D[Plus[a_,b_],x_]->D[a,x]+D[b,x]
];

mexpr=MacroExpand[CreateMExpr[D[Sin[x]+Cos[x],x]]];
ShowMExpr[mexpr]

Using Type System

ClearTypeEnvironment[];
InitializeTypes[];

$TypeEnvironment["reopen"];
$TypeEnvironment["declareType",TypeConstructor["Sin",{"*"}->"*"]];
$TypeEnvironment["declareType",TypeConstructor["Cos",{"*"}->"*"]];
$TypeEnvironment["declareType",TypeConstructor["Times",{"*","*"}->"*"]];
$TypeEnvironment["declareType",TypeConstructor["Plus",{"*","*"}->"*"]];
$TypeEnvironment["declareType",TypeConstructor["Minus",{"*"}->"*"]];

$TypeEnvironment["declareFunction","Sin",Type[TypeForAll[{"a"},{"a"}->"Cos"["a"]]]];
$TypeEnvironment["declareFunction","Cos",Type[TypeForAll[{"a"},{"a"}->"Minus"["Sin"["a"]]]]];
$TypeEnvironment["declareFunction","Plus",Type[TypeForAll[{"a","b"},{"a","b"}->"Plus"["a","b"]]]];

$TypeEnvironment["finalize"]

st=CreateTypeInferenceState[GenerateLambda];
ty=st["infer",Lambda[{Variable["x"]},App[Variable["Plus"],{App[Variable["Sin"],{Variable["x"]}],App[Variable["Sin"],{Variable["x"]}]}]]];
ty["unresolve"]

Questions

Thank You