Swift Intermediate Language - LLVM

1 Swift Intermediate LanguageA high level IR to complement LLVM Joe Groff and Chris LattnerWhy SIL?ClangParseSemaCodeGenLLVM*.cASTAST'I R*.oClangParseSemaCodeGenLLVM*.cASTAST'I R*.oClangParseSemaCodeGenLLVM*.cASTAST'I R*.oClangCodeGenCodeGen ParseSemaLLVM*.cASTAST'IR*.oClangCodeGen CodeGen ParseSemaLLVM*.cASTAST'IR*.oClang-Wunrea chable-code-WuninitializedStatic AnalyzerCodeGenCodeGen ParseSemaLLVM*.cASTAST'IR*.oClangAnalysi sCFG-Wunreachable-code-WuninitializedSta tic AnalyzerCodeGenCodeGen ParseSemaLLVM*.cASTAST'IR*.oClangWide abstraction gap between source and LLVM IR IR isn't suitable for source-level analysis CFG lacks fidelity CFG is off the hot path Duplicated effort in CFG and IR loweringSwiftSwiftHigher-level languageSwiftHigher-level Language Move more of the Language into codeSwiftHigher-level Language Move more of the Language into code Protocol-based genericsSwiftHigher-level Language Move more of the Language into code Protocol-based genericsSafe languageSwiftHigher-level Language Move more of the Language into code Protocol-based genericsSafe Language Uninitialized vars, unreachable code should be compiler errorsSwiftHigher-level Language Move more of the Language into code Protocol-based genericsSafe Language Uninitialized vars.

2 Unreachable code should be compiler errors Bounds and overflow checksParseSemaASTIRGenIRLLVM*.oSwiftSIL SILGenParseSemaASTIRGenIRLLVM*.oSwiftSIL SILGenParseSemaASTIRGenIRSwiftAnalysisSI LF ully represents program semantics Designed for both code generation and analysis Sits on the hot path of the compiler pipeline Bridges the abstraction gap between source and LLVMD esign of SILF ibonaccifunc fibonacci(lim: Int) { var a = 0, b = 1 while b < lim { print(b) (a, b) = (b, a + b) } }Fibonaccisil @fibonacci: $( ) -> () { entry(%limi: $ ): Fibonaccisil @fibonacci: $( ) -> () { entry(%limi: $ ): Fibonaccisil @fibonacci: $( ) -> () { entry(%limi: $ ): High-Level Type Systemsil @fibonacci: $( ) -> () { entry(%limi: $ ): High-Level Type Systemsil @fibonacci: $( ) -> () { entry(%limi: $ ): High-Level Type Systemsil @fibonacci: $( ) -> () { entry(%limi: $ ).}}}}}}

3 High-Level Type SystemHigh-Level Type SystemKeeps machine-level type layout abstractHigh-Level Type SystemKeeps machine-level type layout abstractType-related information is implicitHigh-Level Type SystemKeeps machine-level type layout abstractType-related information is implicit TBAAHigh-Level Type SystemKeeps machine-level type layout abstractType-related information is implicit TBAA Type parameters for generic specializationHigh-Level Type SystemKeeps machine-level type layout abstractType-related information is implicit TBAA Type parameters for generic specialization Classes and protocol conformances for devirtualizationHigh-Level Type SystemKeeps machine-level type layout abstractType-related information is implicit TBAA Type parameters for generic specialization Classes and protocol conformances for devirtualizationStrongly-typed IR helps validate compiler correctnessBuiltinssil @fibonacci: $( ) -> () { entry(%limi: $ ): Builtinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 Builtinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitBuiltinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print.}}}}

4 $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitBuiltinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitBuiltinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitBuiltinssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitBuiltinsBuiltinsBuiltins opaquely represent types and operations of the layer below SILB uiltinsBuiltins opaquely represent types and operations of the layer below SILS wift's standard library implements user-level interfaces on top of builtinsBuiltinsBuiltins opaquely represent types and operations of the layer below SILS wift's standard library implements user-level interfaces on top of builtinsstruct Int { var value: } struct Bool { var value: } func ==(lhs: Int, rhs: Int) -> Bool { return Bool(value.)}}}}

5 ( , )) }BuiltinsBuiltins opaquely represent types and operations of the layer below SILS wift's standard library implements user-level interfaces on top of builtinsstruct Int { var value: } struct Bool { var value: } func ==(lhs: Int, rhs: Int) -> Bool { return Bool(value: ( , )) }SIL is intentionally ignorant of: Machine-level type layout Arithmetic, comparison, etc. machine-level operationsLiteral Instructionssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Word"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit Literal Instructionssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Word"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit Literal Instructionssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print.}}

6 $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Word"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit Literal InstructionsLiteral InstructionsMore uniform IR representationLiteral InstructionsMore uniform IR representation No Value/Constant divideLiteral InstructionsMore uniform IR representation No Value/Constant divideAll instructions carry source location information for diagnosticsLiteral InstructionsMore uniform IR representation No Value/Constant divideAll instructions carry source location information for diagnosticsEspecially important for numbers, which need to be statically checked for overflowPhi Nodes?sil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exitPhi Nodes?}

7 Sil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit br loop(%a0: $ , %b0: $ )loop(%a: $ , %b: $ ):body: %b1 = struct $ (%b: $ ) apply %print(%b1) : $( ) -> () %c = builtin "add_Int64"(%a: $ , %b: $ ): $ br loop(%b: $ , %c: $ )exit: %unit = tuple () return %unit: $()}Phi Nodes?sil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit br loop(%a0: $ , %b0: $ )loop(%a: $ , %b: $ ):body: %b1 = struct $ (%b: $ ) apply %print(%b1) : $( ) -> () %c = builtin "add_Int64"(%a: $ , %b: $ ): $ br loop(%b: $ , %c: $ )exit: %unit = tuple () return %unit: $()}Basic Block Argumentssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt.}

8 $ , body, exit br loop(%a0: $ , %b0: $ )loop(%a: $ , %b: $ ):body: %b1 = struct $ (%b: $ ) apply %print(%b1) : $( ) -> () %c = builtin "add_Int64"(%a: $ , %b: $ ): $ br loop(%b: $ , %c: $ )exit: %unit = tuple () return %unit: $()}Basic Block Argumentssil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit br loop(%a0: $ , %b0: $ )loop(%a: $ , %b: $ ):body: %b1 = struct $ (%b: $ ) apply %print(%b1) : $( ) -> () %c = builtin "add_Int64"(%a: $ , %b: $ ): $ br loop(%b: $ , %c: $ )exit: %unit = tuple () return %unit: $()}Basic Block ArgumentsBasic Block ArgumentsMore uniform IR representationBasic Block ArgumentsMore uniform IR representation Entry block is no longer a special caseBasic Block ArgumentsMore uniform IR representation Entry block is no longer a special case No special case code for managing phisBasic Block ArgumentsMore uniform IR representation Entry block is no longer a special case No special case code for managing phisProvides natural notation for conditional defsentry: success failure Basic Block ArgumentsMore uniform IR representation Entry block is no longer a special case No special case code for managing phisProvides natural notation for conditional defs%s = /* can only use %s here */%e = landingpad.

9 Invoke @mayThrowException(), label %success, label %failureentry: success failure Basic Block ArgumentsMore uniform IR representation Entry block is no longer a special case No special case code for managing phisProvides natural notation for conditional defs /* can only use %s here */(%s):(%e):invoke @mayThrowException(), label %success, label %failureFibonaccisil @fibonacci: $( ) -> () { entry(%limi: $ ): %lim = struct_extract %limi: $ , # %print = function_ref @print: $( ) -> () %a0 = integer_literal $ , 0 %b0 = integer_literal $ , 1 br loop(%a0: $ , %b0: $ ) loop(%a: $ , %b: $ ): %lt = builtin "icmp_lt_Int64"(%b: $ , %lim: $ ): $ cond_br %lt: $ , body, exit body: %b1 = struct $ (%b: $ ) apply %print(%b1) : $( ) -> () %c = builtin "add_Int64"(%a: $ , %b: $ ): $ br loop(%b: $ , %c: $ ) exit: %unit = tuple () return %unit: $() }Method Lookupentry(%c: $SomeClass): %foo = class_method %c: $SomeClass, # : $(SomeClass) -> () apply %foo(%c) : $(SomeClass) -> ()Method Lookupentry(%c: $SomeClass): %foo = class_method %c: $SomeClass, # : $(SomeClass) -> () apply %foo(%c) : $(SomeClass) -> ()Method Lookupentry(%c: $SomeClass): %foo = class_method %c: $SomeClass, # : $(SomeClass) -> () apply %foo(%c) : $(SomeClass) -> ()sil_vtable SomeClass { # : @SomeClass_foo }Method Lookupentry(%c: $SomeClass): %foo = class_method %c: $SomeClass, # : $(SomeClass) -> () apply %foo(%c) : $(SomeClass) -> ()sil_vtable SomeClass { #.}

10 @SomeClass_foo }sil @SomeClass_foo : $(SomeClass) -> ()Method Lookupentry(%c: $SomeClass): %foo = function_ref @SomeClass_foo : $(SomeClass) -> () apply %