Make a Compiler Frontend using C++ and LLVM

システムプログラミング会 at PFN

Transcript

1. LLVM ͱ C++ ͰίϯύΠϥ ϑϩϯτΤϯυͭͬͨ͘ γεςϜϓϩάϥϛϯάձ 2016/7/1 
2. • ࢓ࣄɿαʔϏεͷςετΦʔτϝʔγϣϯΤϯδ χΞʢQAʣ • झຯɿ • Vim • σεΫτοϓΞϓϦͮ͘ΓʢElectronʣ • ίϯύΠϥϑϩϯτΤϯυ ࠓ೔͸͜ΕͰ͢ʂ @Linda_pp @rhysd 
3. ໨࣍ • ϓϩάϥϛϯάݴޠ Dachs • C++ ͱ LLVM ʹΑΔ࣮૷ • Dachs ࠓޙ 
4. ϓϩάϥϛϯάݴޠ Dachs 
5. Dachs ͱ͸ https://github.com/rhysd/Dachs 2014 ೥͙Β͍͔Βগͣͭ͠࡞͍ͬͯΔ൚༻໨ తͷݴޠɽLLVM ϑϩϯτΤϯυͱ࣮ͯ͠૷ɽ 
6. Dachs ͱ͸ 
7. Dachs ͱ͸ • Ruby ͷΑ͏ʹ؇͘ॻ͖͍ͨʢॻ͖΍͍͢ߏ จɼGCʣ • ੩తͳνΣοΫ͸΍ͬͯ΄͍͠ʢڧ͍ܕ෇ ͚ɼimmutabilityʣ • ੩తϦϯΫͰόΠφϦੜ੒ʢ࠷దԽɼऔΓճ ͠΍͢͞ͳͲʣ 
8. ؇͘ॻ͖͍ͨɿؔ਺ func fib(n) case n when 0, 1 ret 1 else ret fib(n-1) + fib(n-2) end end func main() println(fib(10)) # UFCS ʹΑΔߏจ౶ҥ 10.fib.println end 
9. ؇͘ॻ͖͍ͨɿҾ਺ func fib(n) case n when 0, 1 ret 1 else ret fib(n-1) + fib(n-2) end end template<class T> auto fib(T const n) { if (n <= 1) { return 1; } else { return fib(n-1) + fib(n-1); } } Ҿ਺ͷܕΛॻ͔ͳ͍ͱؔ਺ςϯϓϨʔτʹɽ fib(n: int): int ͷΑ͏ʹܕΛॻ͘͜ͱ΋Ͱ͖Δ %BDIT $ 
10. ؇͘ॻ͖͍ͨɿdo-end ߏจ func each(array, block) var i := 0u for i < array.size block(array[i]) i += 1u end end func main [1, 2, 3].each do |i| println(i) end # ϥϜμࣜΛ൐͏ݺͼग़͠ͷߏจ౶ҥ each([1, 2, 3], -> i in println(i)) end 
11. ؇͘ॻ͖͍ͨɿdo-end ߏจ func each(array, block) var i := 0u for i < array.size block(array[i]) i += 1u end end func main [1, 2, 3].each do |i| println(i) end end • do-end ϒϩοΫ͸Ϋ ϩʔδϟʢม਺ΛΩϟ ϓνϟ͢Δಗ໊ؔ਺ʣ ʹม׵͞ΕΔɽ • ؔ਺ͷ࠷ޙͷҾ਺ͱ͠ ͯؔ਺ΦϒδΣΫτ͕ ౉ͬͯ͘Δ 
12. ؇͘ॻ͖͍ͨɿclass • init ͕ίϯετϥ Ϋλ • ϝϯόม਺ͷܕ Λਪଌ • ίϯετϥΫλͷؔ਺ς ϯϓϨʔτΛղܾ → Ϋϥ εςϯϓϨʔτΛղܾ class Random init(@seed) end func gen x := @seed high := x / 127773 low := x % 127773 var t := 16807 * low - 2836 * high t += 0x7fffffff if t <= 0 @seed = t ret t end end 
13. ؇͘ॻ͖͍ͨɿclass class Random init(@seed) end func gen x := @seed high := x / 127773 low := x % 127773 var t := 16807 * low - 2836 * high t += 0x7fffffff if t <= 0 @seed = t ret t end end template<class T> class Random { T seed; public: Random(T s) : seed(s) {} auto gen() { const auto x = this->seed, high = x / 127773, low = x % 127773; auto t = 16807 * low - 2836 * high; if (t <= 0) { this->seed = t; } return t; } }; %BDIT $ 
14. ؇͘ॻ͖͍ͨɿGC • array ܕ͸഑ྻʹऔͬ ͯ GC Ͱ؅ཧ͠ɼ৳ॖ Մೳɽ • ϥϯλΠϜ͕ libgc (Boehm GC) Λ࢖ͬͯ ͍Δ func five_elems # ഑ྻ͸ώʔϓʹऔΓɼGC Ͱ؅ཧ ret [1, 2, 3, 4, 5] end func main five_elems()[2].println end 
15. ੩తνΣοΫɿܕ • ม਺ఆٛͰ͸ӈล͔Β஋Λਪଌɼؔ਺΍ ΫϥεͰ ͸ςϯϓϨʔτʹͯ͠࢖༻࣌ʹΠϯελϯεԽ func fib(n) ret if n <= 1 then 1 else fib(n-1) + fib(n-2) end end func main() result := if special then 42 else fib(n) end end 
16. ੩తνΣοΫɿimmutability # Ҿ਺ʹ var Λ෇͚Δ͔Ͳ͏͔Ͱ੍ޚ func foo(var a, b) # a ͸ clone ͞ΕɼมߋՄೳ # OK! a.modify_something() # b ͸ࢀরʹͳΓɼมߋෆՄೳ # NOT OK! b.modify_something() end func main() kls := new SomeClass foo(kls, kls) end 
17. ͦͷଞͷαϯϓϧ https://github.com/rhysd/Dachs/tree/ master/samples ཚ਺ੜ੒ثɼBrainFxxkॲཧܥɼෆಈ఺ίϯ ϏωʔλɼϚϯσϧϒϩू߹ͳͲ 
18. C++ ͱ LLVM ʹΑΔ࣮૷ 
19. ύʔε ҙຯղੳ
    ʢ໊લɾલํࢀরղܾɼ ςϯϓϨʔτղੳʣ ҙຯղੳ
    ܕνΣοΫɼΫϩʔδϟ ͷΩϟϓνϟղܾɼ֤ छνΣοΫ --7.
    *3
    ΁ม׵ όΠφϦ ੜ੒ ύʔαδΣωϨʔλ Ͱύʔε͠
    "45
    ੜ੒ είʔϓ໦ੜ੒ɼ γϯϘϧςʔϒϧ "45
    ʹܕ৘ใ෇Ճɼ Ϋϩʔδϟ͝ͱͷΩϟ ϓνϟςʔϒϧੜ੒ MMWN*3#VJMEFS
    Ͱ
    *3
    ੜ੒ --7.
    ͕ΦϒδΣ ΫτϑΝΠϧੜ੒ɼ ME
    ͰϦϯΫ ࠷దԽ
    --7.
    1BTTFT 
20. ASTʢ࣮૷Πϝʔδʣ struct ͱ boost::variant ʢ҆શͳڞ༻ମΫϥεʣ ͷΠϯελϯεΛϊʔ υʹ࢖ͬͯදݱ struct string_literal { /*...*/ }; struct binary_expr { /*.. */ }; struct if_expr { /*.. */ }; using expr = boost::variant< string_literal, if_expr, binary_expr >; struct return_statement { /*...*/ }; struct for_statement { /*...*/ }; using statement = boost::variant< return_statement, for_statement, expr >; 
21. ύʔα Boost.Spirit ͱ͍͏ύʔαδΣωϨʔλϥΠ ϒϥϦΛ࢖༻͠ɼจࣈྻͷιʔείʔυΛ AST ʹม׵͢Δɽ EDSL ͰએݴతʹύʔεϧʔϧΛ௚઀ C++ ͷ ίʔυͱͯ͠ఆٛ͢Δɽ 
22. Boost.Spirit • Boost.Spirit ͱ͍͏ύʔαδΣωϨʔλϥΠϒϥϦΛ࢖༻ • ԋࢉࢠΦʔόʔϩʔυͰ EDSL ͬΆ͘ύʔε͢ΔϧʔϧΛॻ͚Δ • C++ ςϯϓϨʔτΛѱ༻ར༻ͯ͠ίϯύΠϧ࣌ʹϧʔϧͷ੔߹ੑ ΛνΣοΫ • ίϯύΠϧ࣌ؒ΋ Boost ͢Δʢੜ੒͞ΕΔύʔαͷੑೳ͸ྑ͍ʣ • kinaba ͞Μͷ Let’s Boost ͕ࢀߟʹͳΓ·͢ɿhttp:// www.kmonos.net/alang/boost/classes/spirit.html 
23. ύʔαͷงғؾ // variable_decl ::= ['var'] variable_name [':' type] // Λύʔε͢ΔϧʔϧΛఆٛ variable_decl = ( -qi::matches[qi::lit("var")] // ୯߲ - ͸ 0 or 1ճϚον >> variable_name // ม਺໊Λύʔε͢Δϧʔϧ >> -( ':' >> type // ': type' Λ෇͚ͯܕΛ໌ࣔͯ͠΋ྑ͍ ) ) [ // ηϚϯςΟοΫΞΫγϣϯ // ରԠ͢Δύʔε͕੒ޭͨ࣌͠ʹݺ͹ΕΔ _val = make_node_ptr<ast::node::variable_decl>( _1, // "var" ͕͔͋ͬͨͲ͏͔ͷ bool ஋ _2, // ม਺໊ _3, // boost::optional<ܕϊʔυ> ͳ஋ ) ];
24. ҙຯղੳɼLLVM IR ੜ੒ • visitor ύλʔϯͰͻͨ͢Β AST ΛᢞΊ·͘Δ • AST ΛҰ८ͯ͠είʔϓ໦΍γϯϘϧςʔϒϧੜ੒ • AST ΛҰ८ͯ͠ܕ৘ใΛऩूɾνΣοΫ • AST ΛҰ८֤ͯ͠ϊʔυʹରԠ͢Δ LLVM IR Λ llvm::IRBuilder Ͱੜ੒ • llvm::IRBuilder ͸ϏϧμʔύλʔϯͰ IR ίʔυΛੜ੒͢ΔͨΊͷϔϧύʔɽLLVM ެ ࣜͷνϡʔτϦΞϧ͕෼͔Γ΍͍͢ http://llvm.org/docs/tutorial/LangImpl3.html 
25. ࢀߟɿ visitor // return จ͔Β໭Γ஋ܕΛूΊΔ visitor // Ͳ͏ visit ͢Δ͔Λఆٛͨ͠ߏ଄ମ struct return_types_gatherer { std::vector<type::type> result_types; // return จͷ node ͷ࣌ template<class Walker> void visit(ast::node::return_stmt const& ret, Walker const& w) { // Ҿ਺Ͱ౉ͬͯ͘Δؔ਺ΦϒδΣΫτΛݺͼग़͢ͱࢠϊʔυ // Λ࠶ؼతʹ visit ͯ͘͠ΕΔ w(); result_types.push_back(ret->ret_type); } // ͦΕҎ֎ͷϊʔυͷͱ͖ template<class T, class W> void visit(T const&, W const& w) { w(); } }; // ࢖͍ํ return_types_gatherer gatherer; ast::make_walker(gatherer).walk(some_ast_node); 
26. ࠷దԽͱΦϒδΣΫτੜ੒ ΄΅ LLVM ʹ͓ΜͿʹͩͬ͜ঢ়ଶɽ LLVM ͸͍͍ͧɽ 
27. UBSHFU
    USJQMF
    Λऔಘ EBUB
    MBZPVU
    Λऔಘ όοΫΤϯυ ͷॳظԽ UBSHFU
    NBDIJOF
    Λ औಘ *3#VJMEFS
    Ͱ
    *3
    ੜ੒ ؔ਺͝ͱͷ
    *3
    ࠷దԽ Ϟδϡʔϧ͝ͱ ͷ
    *3
    ࠷దԽɾ *3
    ݕূ ΦϒδΣΫτϑΝ Πϧͷੜ੒ ME
    ͰϥϯλΠϜΛ ϦϯΫ FH
    
    Y@BQQMFEBSXJO $16
    ৘ใ
    FH
    ""SDI *3
    ͷ֤ܕ͕Կ
    CJU
    ͔
    FH
    ුಈখ਺఺਺
    G
    
    
    CJU MMWN'VODUJPO1BTT.BOBHFS MMWN.PEVMF1BTT.BOBHFS ΦϒδΣΫτϑΝΠϧΛੜ੒͢Δ NPEVMF
    QBTT
    Λ࢖ͬͯੜ੒ ੨͍෦෼͸΄΅
    --7.
    ͷ
    "1*
    Λ
    ࢖͏͚ͩͰ͍͚Δ  ҙຯղੳ
    ׬ྃ
28. Dachs ࠓޙ 
29. ࠓޙ • ύʔα͕ͭΒ͍ͷΛͲ͏ʹ͔͍ͨ͠ • ίϯύΠϧ͕஗͗͢ΔʢMacBook Air ͩͱ4෼͙Β͍ʣ • γϯϘϧ͕େ͖͗ͯ͢ OS X Ͱ gdb ͕Ϋϥογϡ͢Δ • ಠࣗͷ LLVM Pass Λ௥Ճͯ͠ stack promotion ͳͲࣗલͷ࠷దԽΛ࣮૷͍ͨ͠ • ௿Ϩϕϧͳ APIʢstack ʹऔΔ഑ྻɼϙΠϯλʣͷ࠶ઃܭ • ඪ४ϥΠϒϥϦΛࣗ਎ͷݴޠͰ࣮૷͢Δʹ͸ඞཁ • LLVM ͷ C++ όΠϯσΟϯά͸มߋ͕ܹ͍͠ͷͰ llvm-c Λ࢖͏ʁˠ ͍ͬͦผݴ ޠʹ͢Δʁ • ਖ਼֬ͳ GC Λࡌ͍ͤͨ 
30. ݴ͍͔ͨͬͨ͜ͱ • ͍͖͞ΐ͏ͷߏจ΍ݴޠػೳΛߟ͑Δͷ͸ָ ͍͠ • ߟ͑ͯΈͨߏจ΍ηϚϯςΟΫε͕࣮ࡍʹಈ ͘ͱ͞Βʹָ͍͠ • LLVM ͸͍͍ͧ 
31. LLVM ͱ C++ ͰίϯύΠϥ ϑϩϯτΤϯυͭͬͨͯ͘Δ SPձ 2016/7/1  @Linda_pp @rhysd