Share
Embed
Transcript
91 slides
-
Θ͍Θ͍swi$c ൪֎ฤϫʔΫγϣοϓ #3 - Ԭ • ͝ࢀՃ͋Γ͕ͱ͏͍͟͝·ͨ͠ • ΈΜͳҰੜݒ໋ղ͍͍ͯͯخ͍͠Ͱ͢ •
C++ ͷ෦͕͔ͬͨ͠ͷͰղ͚ͳͯ͘વͰ͢ 3 -
Θ͍Θ͍swi$c ൪֎ฤϫʔΫγϣοϓ #3 - Ԭ • ࢿྉશͯઌिެ։͠·ͨ͠ • ͨͩ͠ϫʔΫγϣοϓͷϨϙδτϦফ͍ͯ͠·͢ •
h#ps:/ /qiita.com/freddi_/items/aa604dd68697f823a41d 4 -
ͪΐͬͱ෮श ~ SILͱ • Swi%ͷதؒදݱݴޠ (Swi% Intermediate Language) • Swi%ͷίʔυΛίϯύΠϧ͍ͯ͠Δ్தͰݱΕΔ
• ࠷దԽSILͷίʔυͰߦΘΕΔ • ࠷దԽલͷSIL͕raw SILɺޙ͕canonical SIL 5 -
ͪΐͬͱ෮श ~ SILʢྫʣ SILʹมޙ sil_stage canonical import Builtin import Swift
import SwiftShims @_hasStorage @_hasInitialValue var a: Int { get set } // a sil_global hidden @$s5swift1aSivp : $Int // main sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 { bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>): alloc_global @$s5swift1aSivp // id: %2 %3 = global_addr @$s5swift1aSivp : $*Int // user: %6 %4 = integer_literal $Builtin.Int64, 10 // user: %5 %5 = struct $Int (%4 : $Builtin.Int64) // user: %6 store %5 to %3 : $*Int // id: %6 %7 = integer_literal $Builtin.Int32, 0 // user: %8 %8 = struct $Int32 (%7 : $Builtin.Int32) // user: %9 return %8 : $Int32 // id: %9 } // end sil function 'main' // Int.init(_builtinIntegerLiteral:) sil public_external [transparent] [serialized] @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int { // %0 // user: %2 bb0(%0 : $Builtin.IntLiteral, %1 : $@thin Int.Type): %2 = builtin "s_to_s_checked_trunc_IntLiteral_Int64"(%0 : $Builtin.IntLiteral) : $(Builtin.Int64, Builtin.Int1) // user: %3 %3 = tuple_extract %2 : $(Builtin.Int64, Builtin.Int1), 0 // user: %4 %4 = struct $Int (%3 : $Builtin.Int64) // user: %5 return %4 : $Int // id: %5 } // end sil function '$sSi22_builtinIntegerLiteralSiBI_tcfC' 7 -
ͪΐͬͱ෮श ~ SILίʔυͷߏ • SILͷߏҎԼͷͬ͟ͱҎԼͷ௨Γʢςʔϒϧͱ͔Ұ෦লུʣ • SIL Module (ιʔεϑΝΠϧશମ) •
ͷதʹɺSIL Func.on (Swi*Ͱ࡞͔ͬͨؔΒੜ) • ͷதʹɺSIL Basic Block (݅ذͷείʔϓͱ͔) • ͷதʹɺSIL Instruc.on (ίʔυͷҰߦҰߦ) 8 -
ͪΐͬͱ෮श ~ SILίʔυͷߏʢྫʣ // ϑΝΠϧશମ͕SIL Module sil_stage canonical import Builtin
... // SIL Function // main sil @main : $@convention(c) (Int32, ...) -> Int32 { // bb ͔Β࢝·Δ SIL Basic Block bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional .. // ͜͜Β͔Β SIL Instruction alloc_global @$s5valueAASivp // id: %2 ... return %8 : $Int32 // id: %9 } // end sil function 'main' Ҏ߱ɺ֤୯ޠͷ಄ͷSILলུͰ͖ͦ͏ͳͱ͖লུ 9 -
ͪΐͬͱ෮श ~ SILOp(mizer • SIL Λ࠷దԽ͢ΔίϯύΠϥͷϞδϡʔϧ • ͦΕͧΕͷ࠷దԽͷׂΛ࣋ͭ Pass ͱ͍͏Ϟδϡʔϧ͔ΒͳΔ
• Module શମΛݟΔ Pass ͱ Func2on ΛݟΔ Pass ͕͋Δ 10 -
Dead Code Elimina-on • ΘΕ͍ͯͳ͍ίʔυΛআ͢Δ࠷దԽPass • ΘΕ͍ͯͳ͍ίʔυ == "ࢮΜͰΔίʔυ" ==
Dead Code • େମͷ໘Ͱ DCE ͱུ͞Ε͍ͯΔ • ίϯύΠϥͷίʔυͱ͔ • ϫʔΫγϣοϓͷ՝Ͱ࡞Β͞Εͨ Pass • ϫʔΫγϣοϓͷআͷ͕݅ݫ͘͠ͳ͍minDCE 11 -
Dead Code Elimina-onͷΈ 1. আ͠ͳ͍݅ʹͯ·Δ Instruc+on Λ Live Insturc-on ͱ
ͯ͠Mark 2. Mark͞Ε͍ͯͳ͍ Insturc+on Λ Func+on ͔ΒऔΓআ͘ 3. Func+on ͔Β͍Βͳ͍ίʔυ͕ফ͍͑ͯΔ 4. (ƅдƅ)řŵŖ 12 -
Dead Code Elimina-onͷΈ • ຊՈͰͷ Live Insturc.on ͷ͍͍ͩͨͷ݅ • ⭕
return noreturn ͱ͍ͬͨ Insturc.onɻ • ϫʔΫγϣοϓͰ return ͷΈ • ❌ ෭࡞༻ͷ͋ΔՄೳੑ͕͋Δ Insturc.on • ⭕ Live Instruc.on ʹґଘ͍ͯ͠Δ Instruc.on • ❌ Live Insturc.on ͕ ੍ޚґଘ ͍ͯ͠Δ݅ذ • ෳͷ Basic Block ͷؒͷࠪ • ϫʔΫγϣοϓͰ࣮ͨ͠ minDCE ⭕ ͕͍͚ͭͨ݅ͩΛར༻ 13 -
Dead Code Elimina-onͷΈ ༨ஊ • ❌ Live Insturc.on ੍͕ޚґଘ͍ͯ͠Δ݅ذ •
ෳͷ Basic Block ͷؒͷࠪ • h5ps:/ /blog.wa=.me/2018/02/19/swi=-sil-5/ ΛಡΜͰͶ 14 -
return noreturn ͱ͍ͬͨ Insturc+on • Basic Block ͷϧʔϧ •
Terminator ͱݺΕΔ Instruc*on ͰऴΘΒͳ͍ͱ͍͚ͳ͍ • return • noreturn • unreachable (FatalErrorͷ͋ͱʹ͍ͨΓ͢Δ) • throw ... 15 -
ϫʔΫγϣοϓͰreturn͞ΕͨΛusefulͱͯ͠ѻͬͨ ཧ༝ • ྫ͑ԼͷSILίʔυ store %5 to %3 : $*Int
// id: %6 %7 = integer_literal $Builtin.Int32, 0 // user: %8 %8 = struct $Int32 (%7 : $Builtin.Int32) // user: %9 return %8 : $Int32 // id: %9 16 -
ϫʔΫγϣοϓͰreturn͞ΕͨΛusefulͱͯ͠ѻͬͨ ཧ༝ • ͜ͷίʔυ ࠷ޙʹ return %8 ͯ͠Δʢid: %9ʣ •
id: %9 return (Terminator) => Live • %8 ͷΛੜ͍ͯ͠Δ Instruc,on ґଘ ͍ͯ͠Δ => Live • %8 Λฦ͍ͯ͠Δ Instruc,on id: %8 ͷ Inscruc,onͱݺͿ • id: %8 ͕ར༻͍ͯ͠Δ %7ʢid: %7ʣґଘ => Live • %7 ͔ΒɹґଘΛҶͮΔࣜʹࠪͯ͠ɹLive ͱͯ͠Markͱ͍͚ͳ͍ 17 -
ϫʔΫγϣοϓͰreturn͞ΕͨΛusefulͱͯ͠ѻͬͨ ཧ༝ • ྫ͑ԼͷSILίʔυ id: %6 ͕ফ͑Δ͔͠Εͳ͍ • return ʹґଘ͍ͯ͠ͳ͍Instruc,on
• %7, %8, %9 ʹґଘ͍ͯ͠ͳ͍͔Β store %5 to %3 : $*Int // id: %6 %7 = integer_literal $Builtin.Int32, 0 // user: %8 %8 = struct $Int32 (%7 : $Builtin.Int32) // user: %9 return %8 : $Int32 // id: %9 18 -
ϫʔΫγϣοϓͰreturn͞ΕͨΛusefulͱͯ͠ѻͬͨ ཧ༝ • minDCE ʹ • noreturn ͷ࣌ͱ͔ແ݅Ͱͯ͢ͷίʔυΛফ͢ͷͰ • ͦͷ࣌
Instruc/onʹ ෭࡞༻͕͋Δ͔Ͳ͏͔ ΛௐΔ • ϫʔΫγϣοϓͰ͕࣌ؒΓΜͷͰলུ • ࠓͷίϨ • ʮInstruc/onʹ ෭࡞༻͕͋Δ͔Ͳ͏͔ ΛௐΔʯؔͷ 19 -
seemsUseful • ҎԼɺຊՈ DCE ʹ͋Δ seemsUseful ͱ͍͏ؔͷҰ෦ • ໊લͷ௨ΓʮUsefulͳInstruc1onʯ͔Λ true/false
Ͱฦ͢ • Live ͱ Useful ಉ͡ҙຯͱࢥͬͯྑ͍ • ઌ΄Ͳհͨ͠ Terminator ͷνΣοΫ͜͜Ͱஅͯ͠Δ • Instruc1on ͷґଘͷࠪ·ͨผͷॴ static bool seemsUseful(SILInstruction *I) { if (I->mayHaveSideEffects()) return true; ... 20 -
seemsUseful • Func&on தͷ Instruc&on Λ Mark ͢Δ markLive ؔͰར༻
• seemUseful ͷ݁Ռ͕ trueͳΒ • Instruction Λ markValueLive͢Δ • ݫີʹ Insctruction தͷ SIL Value ΛMark 21 -
mayHaveSideEffects ͷ෦࣮ • ͜Μͳ͔Μ͡ bool SILInstruction::mayHaveSideEffects() const { // If
this instruction traps then it must have side effects. if (mayTrap()) return true; MemoryBehavior B = getMemoryBehavior(); return B == MemoryBehavior::MayWrite || B == MemoryBehavior::MayReadWrite || B == MemoryBehavior::MayHaveSideEffects; } 24 -
mayTrapʁ • / / If this instruc.on traps then it
must have side effects. • ༁: ͜ͷ໋ྩ͕τϥοϓ͢Δ߹ɺ෭࡞༻͕͋Δͣ • trap == ϓϩάϥϜͷҟৗऴྃ 26 -
mayTrap ͷ෦࣮ΛͱΓ͋͑ͣ͘ • ׂͱγϯϓϧͰ͍͞͠ bool SILInstruction::mayTrap() const { switch(getKind()) {
case SILInstructionKind::CondFailInst: case SILInstructionKind::UnconditionalCheckedCastInst: case SILInstructionKind::UnconditionalCheckedCastAddrInst: return true; default: return false; } } 27 -
dyn_cast<I> isa<T> αϯϓϧίʔυ • ࠓݟ͍ͯΔInstruc)on͕Interger Literal Instruc)on͔ݟ͍ͯΔ // Inst͕
Interger Literal Instruction͔͠ΒΔ // $0 = integer_literal $Builtin.Int64, 100 if (auto *BI = dyn_cast<IntegerLiteralInst>(Inst)) { 29 -
dyn_cast<I> isa<T> • ͦΕͧΕͷInstruc)onɺSILInstruction ܕΛܧঝͨ͠ܕͰ ද͞ΕΔ • SILInstruction ܕɺίϯύΠϥ্Ͱ
SIL Instruc)on Λද ݱ͍ͯ͠Δ • తͷInstruc)onܕͷμϯΩϟετ͕ޭ͢Εྑ͍ 30 -
getKind • getKind ΩϟετΛΘͳ͍ํ๏ • enumΛฦ͍ͯͯ͠ɺswitchͱ͔͑ͯྑ͍ • SILInstructionKind ɺenumͷͰInstruction͕Ͳͷछ ྨͷͷ͔Λද͢
switch(I->getKind()) { case SILInstructionKind::IntegerLiteralInst: ... case SILInstructionKind:: ReturnLiteralInst: ... 31 -
mayTrap ͷ෦࣮ΛͱΓ͋͑ͣ͘ (࠶ܝ) bool SILInstruction::mayTrap() const { switch(getKind()) { case
SILInstructionKind::CondFailInst: case SILInstructionKind::UnconditionalCheckedCastInst: case SILInstructionKind::UnconditionalCheckedCastAddrInst: return true; default: return false; } } 32 -
cond_fail // BNF sil-instruction ::= 'cond_fail' sil-operand, string-literal • ͠Φϖϥϯυ͕
1 ͷͱ͖Run'me Failure • Φϖϥϯυ == Ҿͱߟ͑ΔͱΘ͔Γ͍͢ • sil-operand ͕Φϖϥϯυ cond_fail %0 : $Builtin.Int1, "failure reason" // %0 must be of type $Builtin.Int1 • h#ps:/ /github.com/apple/swi5/blob/master/docs/SIL.rst#cond_fail 36 -
unconditional_checked_cast // BNF sil-instruction ::= 'unconditional_checked_cast' sil-operand 'to' sil-type •
ΩϟετͰ͖Δ͔Λ͔֬ΊΔ • ΦϖϥϯυͷΦϒδΣΫτ͕ΩϟετෆՄͷ߹Run%me Failure • as! ͷΑ͏ͳͷ %1 = unconditional_checked_cast %0 : $A to $B %1 = unconditional_checked_cast %0 : $*A to $*B // $A and $B must be both objects or both addresses // %1 will be of type $B or $*B • h#ps:/ /github.com/apple/swi5/blob/master/docs/SIL.rst#uncondi=onal_checked_cast 37 -
unconditional_checked_cast_addr // BNF sil-instruction ::= 'unconditional_checked_cast_addr' sil-type 'in' sil-operand 'to'
sil-type 'in' sil-operand • Ωϟετ • ࠷ॳͷΦϖϥϯυ͕ɺ࠷ޙͷΦϖϥϯυͷܕʹ͕ΩϟετෆՄ ͷ߹Run%me Failure 38 -
unconditional_checked_cast_addr • unconditional_checked_cast ͱಉ͡Α͏ʹݟ͑Δ͚Ͳ • Ͳ͏ΒΩϟετݩͷΦϒδΣΫτഁغ͞ΕΔΒ͍͠ unconditional_checked_cast_addr $A in %0
: $*@thick A to $B in $*@thick B // $A and $B must be both addresses // %1 will be of type $*B // $A is destroyed during the conversion. There is no implicit copy. • h#ps:/ /github.com/apple/swi5/blob/master/docs/ SIL.rst#uncondi=onal_checked_cast • h#ps:/ /it1.jp/?p=1231 ͕Θ͔Γ͍͔͢ 39 -
unconditional_checked_cast_value Ͳ͏ͳ ͷʁ • mayTrap ʹೖͬͯͳ͍ unconditional_checked ܥ౷ͷ Instruc*on •
ೖΕΕ͔ɺͦ͏Ͱͳ͍͔ෆ໌ • Run*me Failure ͢Δͷʹ .... 40 -
mayHaveSideEffects ͷ෦࣮ʢ࠶ܝʣ bool SILInstruction::mayHaveSideEffects() const { // If this instruction
traps then it must have side effects. if (mayTrap()) return true; MemoryBehavior B = getMemoryBehavior(); return B == MemoryBehavior::MayWrite || B == MemoryBehavior::MayReadWrite || B == MemoryBehavior::MayHaveSideEffects; } • ͭ·ΓɺϓϩάϥϜ͕݅ʹΑͬͯҟৗऴྃ͢ΔͳΒʮ෭࡞༻͋Γʯͱଊ͑Δ • ͭ͗ Memory Behavior! 41 -
getMemoryBehavior ͷ࣮ SILInstruction::MemoryBehavior SILInstruction::getMemoryBehavior() const { if (auto *BI =
dyn_cast<BuiltinInst>(this)) { // Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); if (BInfo.ID != BuiltinValueKind::None) return BInfo.isReadNone() ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; // Handle LLVM intrinsic functions. const IntrinsicInfo &IInfo = BI->getIntrinsicInfo(); if (IInfo.ID != llvm::Intrinsic::not_intrinsic) { // Read-only. if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) && IInfo.hasAttribute(llvm::Attribute::NoUnwind)) return MemoryBehavior::MayRead; // Read-none? return IInfo.hasAttribute(llvm::Attribute::ReadNone) && IInfo.hasAttribute(llvm::Attribute::NoUnwind) ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } } // Handle full apply sites that have a resolvable callee function with an // effects attribute. if (isa<FullApplySite>(this)) { FullApplySite Site(const_cast<SILInstruction *>(this)); if (auto *F = Site.getCalleeFunction()) { return F->getEffectsKind() == EffectsKind::ReadNone ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } } switch (getKind()) { #define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR) \ case SILInstructionKind::CLASS: \ return MemoryBehavior::MEMBEHAVIOR; #include "swift/SIL/SILNodes.def" } llvm_unreachable("We've just exhausted the switch."); } 43 -
SILInstruction::MemoryBehavior • ϝϞϦ্ͷৼΔ͍Λఆٛ͢Δ enum • ҎԼͷ5͕ͭఆٛ͞Ε͍ͯΔ • None • MayRead
• MayWrite • MayReadWrite • MayHaveSideEffects 45 -
...::MemoryBehavior::MayReadWrite • The instruc-on may read or write memory. •
༁) ಡΉ͔ॻ͖ࠐΉ͔͠Εͳ͍ʢ·ͨͦͷ྆ํʁʣ 49 -
...::MemoryBehavior::MayHaveSideEffects • The instruc-on may have side effects not captured
solely by its users. Specifically, it can return, release memory, or store. Note, alloc is not considered to have side effects because its result/users represent its effect. • ༁) Instruc-onɺͦͷར༻ऀ͚ͩͰଊ͑ΒΕͳ͍෭࡞༻Λ࣋ͭ͜ͱ͕ ͋Γ·͢ɻ۩ମతʹɺϦλʔϯɺϝϞϦղ์ɺετΞͳͲͰ͢ɻҙɿ allocɺͦͷ݁Ռ/ར༻ऀ͕ͦͷ࡞༻Λද͢ͷͰɺ෭࡞༻͕͋Δͱߟ͑ ΒΕ·ͤΜɻ • ҙ༁ʣͳʹ͔͠Βɺͷͪͷͪ෭࡞༻͕͋Δ 50 -
MemoryBehavior ? • ͭ·ΓɺͦͷInstruc(on͕ɺͲͷΑ͏ʹϝϞϦ্ͰৼΔ͏͔ Λද͢ • ݟͨײͩ͡ͱɺ࣍ͷϝϞϦ্ͷৼΔ͍͕ʮ෭࡞༻ʯͱͯ֘͢͠ΔΑ͏ʹ͍ͯ͠Δ • MayWrite (ॻ͖)
• MayReadWrite (ಡΈॻ͖) • MayHaveSideEffects (෭࡞༻͋Γ) • seemUseful ɺࠓݟ͍ͯΔInscruc+onʹ෭࡞༻͕͋Δ͔ௐ͍ͯΔ 51 -
getMemoryBehaviorͷ࣮ΛݟΔ ࠷ॳͷ if ʹϑΥʔΧεΛͯΔ if (auto *BI = dyn_cast<BuiltinInst>(this)) {
// Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); if (BInfo.ID != BuiltinValueKind::None) return BInfo.isReadNone() ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; // Handle LLVM intrinsic functions. const IntrinsicInfo &IInfo = BI->getIntrinsicInfo(); if (IInfo.ID != llvm::Intrinsic::not_intrinsic) { // Read-only. if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) && IInfo.hasAttribute(llvm::Attribute::NoUnwind)) return MemoryBehavior::MayRead; // Read-none? return IInfo.hasAttribute(llvm::Attribute::ReadNone) && IInfo.hasAttribute(llvm::Attribute::NoUnwind) ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } } 52 -
BuiltinInst ͱʁ • Represents an invoca/on of buil/n func/onality provided
by the code generator. • ༁) ίʔυɾδΣωϨʔλ͕ఏڙ͢ΔΈࠐΈػೳͷݺͼग़ ͠Λද͠·͢ɻ • ! ! ! ! ! 54 -
BuiltinInst ͱʁ • SIL.rst ʹ͋ͬͨ • h+ps:/ /github.com/apple/swi:/blob/master/docs/SIL.rst#buil=n • Invokes
func=onality built into the backend code generator, such as LLVM- level instruc=ons and intrinsics. • SIL Instruc=on ͷ಄ʹ builtin ͱ͍͍ͭͯΔͷ͕ϙΠϯτ • ༁) LLVMϨϕϧͷ໋ྩΈࠐΈؔͳͲɺόοΫΤϯυίʔυδΣωϨʔλʔʹΈࠐ·ΕͨػೳΛ ݺͼग़͠·͢ɻ swift // Example %1 = builtin "foo"(%1 : $T, %2 : $U) : $V 55 -
Buil%nInst ͱʁ • BuiltinInst ʹҎԼͷ̎ͭͷछྨ͕͋Δ • Swi$ buil)n func)on •
LLVM intrinsic func)on 56 -
BuiltinInst ͱʁ Swi% buil)n func)on • Swi$(SIL)ͷίʔυϨϕϧͰදݱͰ͖ͳ͍ॲཧ ͷݺͼग़͠ • LLVMͷॲཧʹॻ͖ΘΔ͖ॴ
• ྫ) Int(64)ಉ࢜ͷൺֱԋࢉ // SIL %5 = builtin "cmp_eq_Int64"(%3 : $Builtin.Int64, %4 : $Builtin.Int64) ... ↓ LLVM IRͩͱ͜͏ͳΔ // LLVM IR %10 = icmp eq i64 %8, 10 57 -
BuiltinInst ͱʁ Swi% buil)n func)on • Buil&ns.def ʹbuil&n func&onͷҰཡ͋Γ •
ͪͳΈʹઌఔͷ cmp_eq_Int64 ɺBuil&ns.def Ͱ cmp_eq ͱͯ͠Ϧετ͞Ε͍ͯΔ 58 -
getMemoryBehaviorͷ࣮ΛݟΔ Swi$ buil)n func)ons • ݟͨײ͡ɺͦͷ̎ͭͰ݅Λ͚͍ͯΔ • Swi% buil*n func*ons
ͷΞϓϩʔνΛ·ͣݟͯΈΔ if (auto *BI = dyn_cast<BuiltinInst>(this)) { // Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); ... // Handle LLVM intrinsic functions. const IntrinsicInfo &IInfo = BI->getIntrinsicInfo(); ... } 60 -
getMemoryBehaviorͷ࣮ΛݟΔ Swi$ buil)n func)ons if (auto *BI = dyn_cast<BuiltinInst>(this)) {
// Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); if (BInfo.ID != BuiltinValueKind::None) return BInfo.isReadNone() ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; • Ͳ͏Β͜ͷbuil&nͷfunc&onͷใΛͱͬͯɺҎԼͷใΛͱʹMemory BehaviorΛஅ • BInfo.ID • BInfo.isReadNone() 61 -
BInfo.ID • ݟͨײ͡ BuiltinValueKind enum /// BuiltinValueKind - The
set of (possibly overloaded) builtin functions. enum class BuiltinValueKind { None = 0, #define BUILTIN(Id, Name, Attrs) Id, #include "swift/AST/Builtins.def" }; • Ͳ͏Βઌఔݴٴͨ͠ Buil'ns.def ͔ΒɺͳΜ͔औ͍ͬͯΔʁ 63 -
BInfo.ID • Buil&ns.def Λ͘ • ͖ͬ͞ݴٴͨ͠ cmp_eq_Int64 पลͷ෦ΛݟͯΈΔ ... #ifndef
BUILTIN_BINARY_PREDICATE #define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs, Overload) \ BUILTIN(Id, Name, Attrs) #endif BUILTIN_BINARY_PREDICATE(ICMP_EQ, "cmp_eq", "n", IntegerOrRawPointerOrVector) BUILTIN_BINARY_PREDICATE(ICMP_NE, "cmp_ne", "n", IntegerOrRawPointerOrVector) BUILTIN_BINARY_PREDICATE(ICMP_SLE, "cmp_sle", "n", IntegerOrVector) ... 64 -
BInfo.ID BUILTIN_BINARY_PREDICATEͱ͍͏ͷ͕ఆٛ͞Ε͍ͯΔ // ϚΫϩ BUILTIN_BINARY_PREDICATE(ICMP_EQ, "cmp_eq", "n", IntegerOrRawPointerOrVector) ICMP_EQ͕͖ͬ͞ྫͰࡌ͍ͬͯͨ cmp_eq
ͷId ҎԼͰBUILTINʹมͰ͖ΔΑ͏ʹͳ͍ͬͯΔ // ϚΫϩ #define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs, Overload) \ BUILTIN(Id, Name, Attrs) 65 -
BInfo.ID /// BuiltinValueKind - The set of (possibly overloaded) builtin
functions. enum class BuiltinValueKind { None = 0, #define BUILTIN(Id, Name, Attrs) Id, #include "swift/AST/Builtins.def" }; • ͭ·ΓɺBInfo.ID Builtns.defͰఆٛ͞Εͨɺbuil/n func/onͷID • Buil/ns.defͷ෦ͷϚΫϩͰ BUILTIN(Id, Name, Attrs) ʹ͔͑ͯɺ • ͦͷBUILTIN - Id Λenumͷʹ͍ͯ͠Δ 66 -
getMemoryBehaviorͷ࣮ΛݟΔ Swi$ buil)n func)ons • if (BInfo.ID != BuiltinValueKind::None) •
false ͳΒLLVM intrinsic func.on ͱͯ࣍͠ͷύʔτͰϋϯυϦϯά if (auto *BI = dyn_cast<BuiltinInst>(this)) { // Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); if (BInfo.ID != BuiltinValueKind::None) return BInfo.isReadNone() ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; • ࣍ isReadNoneɻ͚ͩͲ͍͍ͩͨಉ͡ϝΧχζϜͳͷͰαοͱհ 67 -
isReadNone • buil&n func&on͕ ϝϞϦΞΫηεΛڐՄ͞Ε͍ͯΔ͔ΛௐΔ • LLVM IRͰؔʹ ଐੑ(A#ribute) ͕͚ͭΒΕΔ
• Ͳ͏͍͏ৼΔ͍Λߦ͏͔ʁ͕ଐੑ͔ΒಡΈऔΕΔ • readnone ଐੑ͕͍͍ͭͯΔͱɺϝϞϦΞΫηε͕ڐՄ͞Εͳ͍ • ٯʹݴ͑ɺreadnone͕͍ͭͯͳ͚Εɺͳʹ͔ϝϞϦͰΔ͔ ͠Εͳ͍ͱ͍͏͜ͱʹͳΔ 68 -
isReadNone // Builtins.def ͔Β·ͨൈਮ #ifndef BUILTIN_BINARY_PREDICATE #define BUILTIN_BINARY_PREDICATE(Id, Name, Attrs,
Overload) \ BUILTIN(Id, Name, Attrs) #endif BUILTIN_BINARY_PREDICATE(ICMP_EQ, "cmp_eq", "n", IntegerOrRawPointerOrVector) • BUILTIN(Id, Name, Attrs) ͷͳ͔Ͱ Attrs="n" ͩͬͨΒ readnone • ϝϞϦΞΫηε͕Ͱ͖ͳ͍ॲཧʹม͞ΕΔͱ͍͏͜ͱ • bul&n func&ons Bul&ns.def Ͱ ଐੑΛҰͭҰͭ ϥϕϦϯάͯ͠Δ • มઌɺଐੑ͕͚ͭΕͳ͍ Instruc&on ୯ମ͔ͩΒʁ 69 -
getMemoryBehavior ͷ࣮ΛݟΔ Swi$ buil)n func)ons if (auto *BI = dyn_cast<BuiltinInst>(this))
{ // Handle Swift builtin functions. const BuiltinInfo &BInfo = BI->getBuiltinInfo(); if (BInfo.ID != BuiltinValueKind::None) return BInfo.isReadNone() ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; • ͭ·Γ↑ ҎԼͷΑ͏ʹಡΈऔΕΔ • Insruc*onͷใ͔Βɺbuil*n func*on ͷଐੑΛݟΔ • ͠ɺreadnone (ϝϞϦΞΫηε͕ڐՄ͞Εͯͳ͍ʣͳΒ෭࡞༻વͳ͠ • ͦ͏Ͱͳ͍ͳΒɺ෭࡞༻ԿΒ͔ͷܗͰ͋Δ͔͠Εͳ͍ 70 -
getMemoryBehaviorͷ࣮ΛݟΔ Swi$ buil)n func)ons • ͜ͷ·ͰͷϊϦ͕Θ͔ΔͱޙΘ͔Δ • ࣍ɺLLVM intrinsic func.onsͷϋϯυϦϯά
• ͬͪ͜ଐੑΛݟͯΔͷ͕ϊϦͰΘ͔Δ // Handle LLVM intrinsic functions. const IntrinsicInfo &IInfo = BI->getIntrinsicInfo(); if (IInfo.ID != llvm::Intrinsic::not_intrinsic) { // Read-only. if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) && IInfo.hasAttribute(llvm::Attribute::NoUnwind)) return MemoryBehavior::MayRead; // Read-none? return IInfo.hasAttribute(llvm::Attribute::ReadNone) && IInfo.hasAttribute(llvm::Attribute::NoUnwind) ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } 71 -
getMemoryBehaviorͷ࣮ΛݟΔ Swi$ buil)n func)ons if (IInfo.hasAttribute(llvm::Attribute::ReadOnly) && IInfo.hasAttribute(llvm::Attribute::NoUnwind)) return MemoryBehavior::MayRead;
// Read-none? return IInfo.hasAttribute(llvm::Attribute::ReadNone) && IInfo.hasAttribute(llvm::Attribute::NoUnwind) ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; • ͭ·Γ↑ͷίʔυ • ྫ֎Λ֎ʹ͛ͳ͍Ͱɺ͔ͭಡΈࠐΈΦϯϦʔͷؔ MayRead • ྫ֎Λ֎ʹ͛Δɺ·ͨɺϝϞϦΞΫηεͰ͖Δؔ MayHaveSideEffects • ͦΕҎ֎ None 73 -
getMemoryBehaviorͷ࣮ΛݟΔ • bul%n instruc%on Ͱͳ͍߹Ͳ͏͔ • ࣍ͷύʔτΛݟͯΈΔ // Handle full
apply sites that have a resolvable callee function with an // effects attribute. if (isa<FullApplySite>(this)) { FullApplySite Site(const_cast<SILInstruction *>(this)); if (auto *F = Site.getCalleeFunction()) { return F->getEffectsKind() == EffectsKind::ReadNone ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } } 75 -
FullApplySite • apply, begin_apply ͱ͍ͬͨؔݺͼग़͠ͷͨΊͷInsruc*on͕ ͋Δ • apply • begin_apply
• try_apply • PassͷίʔυͰɺFullApplySite ͱ͍͏ܕͰ·ͱΊΒΕ͍ͯΔ 76 -
SIL Func)onͷA,ribute • SIL Func)on ʹଐੑ͋Δ • h#ps:/ /github.com/apple/swi5/blob/master/docs/SIL.rst#func>ons //
BNF sil-function-attribute ::= '[' sil-function-effects ']' sil-function-effects ::= 'readonly' sil-function-effects ::= 'readnone' sil-function-effects ::= 'readwrite' sil-function-effects ::= 'releasenone' 77 -
SIL Func)onͷA,ribute • sil-function-attribute SIL Func)onͷએݴ࣌ʹඞਢ // BNF sil-function ::=
'sil' sil-linkage? sil-function-attribute+ sil-function-name ':' sil-type '{' sil-basic-block+ '}' 78 -
getMemoryBehaviorͷ࣮ΛݟΔ • Έ͔ͨΜ͡ • ؔݺͼग़͠ͷInstruc)on͔Ͳ͏͔ௐ͍ͯΔ • ؔݺͼग़ͩͬͨ͠Β callee(ݺͼͨؔ͢)ͷଐੑΛௐΔ • ReadNone
͡Όͳ͍ͳΒ MayHaveSideEffects if (isa<FullApplySite>(this)) { FullApplySite Site(const_cast<SILInstruction *>(this)); if (auto *F = Site.getCalleeFunction()) { return F->getEffectsKind() == EffectsKind::ReadNone ? MemoryBehavior::None : MemoryBehavior::MayHaveSideEffects; } } 79 -
getMemoryBehaviorͷ࣮ΛݟΔ • ࠷ޙͷύʔτ • Ͳ͏ݟͯBuil&n.def(Swi/ buil&n funcion)ͷͱ͖ͱಉ͡ύλʔϯ switch (getKind()) {
#define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR) \ case SILInstructionKind::CLASS: \ return MemoryBehavior::MEMBEHAVIOR; #include "swift/SIL/SILNodes.def" } llvm_unreachable("We've just exhausted the switch."); 81 -
SILNodes.def ͷMEMBEHAVIORʹ͍ͭͯ • SILNodes.defʹ֤Instruc1on͕ͲͷΑ͏ʹϝϞϦ্ͷৼΔ͏͔ॻ͍ͯ͋Δ • FULL_INST ͱ͍͏ใͰ·ͱΊΒΕ͍ͯΔ • CLASS ʹɺ͖ͬ͞ͷ
SILInstructionKind ͱಉׂ͕͡ΓৼΒΕ͍ͯ Δ ( getKind ͷΓͷenumܕ) • MEMBEHAVIOR ʹɺMemoryBehavior ͱಉׂ͕͡ΓৼΒΕ͍ͯΔ ʢenumܕ) • ઌఔͷ Buil1ns.def ͷͱ͖ͱಉ͡ɹ 82 -
getMemoryBehavior ͷ࣮ΛݟΔ • ͱ͍͏͜ͱɺ • SILNodes.def ʹ͋ΔɺʮInscrutc2on͕ϝϞϦ্ͰͲͷΑ͏ʹৼΔ͏͔ ʢMEMBEHAVIORʣʯͷఆٛΛϚΫϩͰ switch-case ʹల։͍ͯ͠Δ
switch (getKind()) { #define FULL_INST(CLASS, TEXTUALNAME, PARENT, MEMBEHAVIOR, RELEASINGBEHAVIOR) \ case SILInstructionKind::CLASS: \ return MemoryBehavior::MEMBEHAVIOR; #include "swift/SIL/SILNodes.def" } llvm_unreachable("We've just exhausted the switch."); 83 -
getMemoryBehaviorͷ࣮ΛݟΔ ·ͱΊ • getMemoryBehavior ҎԼͷ؍ͰInstruc*onͷϝϞϦͷৼΔ͍Λݟ͍ͯΔ • มઌͷ LLVM IR ͷ
Instrucion ɺͲΜͳଐੑʹͳΔ͔ʁ • Attrs in Buil*ns.def • ݺͼग़͢ LLVM IR ͷ Func0on ɺͲΜͳଐੑ͔ʁ • ݺͼग़͍ͯ͠Δ SIL Function ɺͲΜͳଐੑ͔ʁ • ↑ ͰΘ͔Μͳ͍ͳΒɺطʹ Instruc0on ʹఆٛ͞Ε͍ͯΔଐੑΛݟʹߦ͘ • MEMBEHAVIOR in SILNode.def 84 -
mayHaveSideEffects ·ͱΊ • ࣍ͷ߹ɺSIL Instruc,on ʹ෭࡞༻͕͋ΔͱίϯύΠϥஅ͢Δ • ݅ʹΑͬͯɺRun,me Failure ͢Δ͔ʁ
• ݅ʹΑͬͯɺϝϞϦ্Ͱॻ͖ࠐΈͳͲͱ͍ͬͨ͜ͱΛߦ͏͔ʁ bool SILInstruction::mayHaveSideEffects() const { // If this instruction traps then it must have side effects. if (mayTrap()) return true; MemoryBehavior B = getMemoryBehavior(); return B == MemoryBehavior::MayWrite || B == MemoryBehavior::MayReadWrite || B == MemoryBehavior::MayHaveSideEffects; } 86 -
ίϯύΠϥʹͱͬͯʮ෭࡞༻͕͋Γͦ͏ʯͷผͷํ • LLVM ͷଐੑͳͲΛར༻ͯ͠அ͍ͯ͠Δ • Buil*ns.def LLVM ͷ͔ؔΒಡΈऔͬͯஅ •
SILNodes.def Ͱ SIL Instruc*on ͷϝϞϦͷৼΔ͍ఆٛ͞Ε ͍ͯΔ 89 -
ࠓษڧͨ͜͠ͱ • LLVMɺSIL ͷ ଐੑ(A*ribute) • SILNodes.def • Buil:ns.def •
mayHaveSideEffects • getMemoryBehavior 90 -
ࢀߟจݙ • Θ͍Θ͍swi%c ϫʔΫγϣοϓ Vol.3 Ԭ • Swi%ͷதؒݴޠSILΛಡΉ ͦͷ5 -
Dead Code Elimina:on • SILOp:mizerʹܰ͘ೖ͢Δ • SIL.rst • LLVM/Clang࣮ફ׆༻ϋϯυϒοΫ 91