يستخدم المترجم gc لغة خاصة موجهة للكائنات مثل DSL لوصف قواعد تحسين التخصيص الأحادي الثابت (SSA).

أقترح تحليل العناصر الرئيسية لهذه اللغة ، وميزاتها وحدودها.
كتمرين ، دعنا نضيف إلى مترجم Go إنشاء تعليمات لم يتم إنشاؤها مسبقًا ، وتحسين التعبير a*b+c .

هذه هي المقالة الأولى في سلسلة حول الأجزاء الداخلية لخلفية مترجم Go SSA ، لذلك بالإضافة إلى مراجعة وصف قواعد DSL نفسها ، سننظر في المكونات ذات الصلة لإنشاء القاعدة اللازمة لجلستنا التالية.

مقدمة

ينتهي برنامج التحويل البرمجي للواجهة الأمامية في وقت إنشاء عرض SSA من AST المشروح. يمكن العثور على الوظائف المسؤولة عن التحويل في cmd / compile / internal / gc / ssa.go. نقطة الدخول إلى الواجهة الخلفية لـ SSA هي دالة ssa.Compile ، المحددة في cmd / compile / internal / ssa / compile.go .

يتكون محسن SSA Go من عدة مراحل ، يمر كل منها من خلال الوظيفة المترجمة. تستخدم بعض المراحل ما يسمى "قواعد إعادة الكتابة" ، وهي قواعد تحويل تسلسل SSA إلى آخر ، ومن المحتمل أن تكون أكثر مثالية.

يتم وصف قواعد التحول باستخدام تعبيرات S. عناصر هذه التعبيرات هي ssa.Value . في أبسط الحالات ، تسمح لك هذه القواعد باستبدال ssa.Value بأخرى.

على سبيل المثال ، الكود أدناه يزيل ضرب الثوابت 8 بت:

 (Mul8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c*d))]) 

هناك فئتان رئيسيتان لقيم SSA: عالية المستوى ، ومستقلة تقريبًا عن الجهاز المستهدف ، وتلك الخاصة بالهندسة المعمارية (عادةً ما يتم تعيينها لتعليمات الجهاز 1 في 1).

يتم وصف التحسينات من حيث هاتين الفئتين. أولاً ، مستوى عالٍ ومشترك لجميع الهياكل ، ثم موجه نحو النظام الأساسي.

كل الكود المرتبط بالقواعد يكمن في cmd / compile / internal / ssa / gen . سننظر في مجموعتين:

1. genericOps.go - عمليات مستقلة عن الآلة.
2. AMD64Ops.go - عمليات خاصة بـ GOARCH=AMD64 (64 بت x86).

بعد المراحل القليلة الأولى التي تعمل على الآلة المجردة ، يتم تنفيذ ما يسمى genericOps ، مما يؤدي إلى الانتقال من genericOps إلى مجموعة من البنى المحددة. في مثالنا ، سيكون هذا AMD64Ops . بعد هذه النقطة ، تعمل جميع المراحل اللاحقة على العرض التقديمي من الفئة الثانية.

بعد المُحسِّن ، يبدأ تشغيل مولد الشفرة. بالنسبة إلى AMD64 ، يمكن العثور على تنفيذ إنشاء الكود في الحزمة cmd / compile / internal / amd64 . مهمة مُنشئ الشفرة هي استبدال ssa.Block و ssa.Value بالتسلسل obj.Prog الذي تم تمريره إلى المجمع . سيجمع المُجمّع رمز الجهاز ، والذي سيكون جاهزًا للتنفيذ بعد الربط .

قواعد التحسين

إذا كانت الملفات ذات تعريفات التشغيل تسمى " ${ARCH}Ops.go " ، يتم وضع قواعد التحسين في " ${ARCH}.Rules ".

تقوم القواعد عالية المستوى بإجراء تحويلات بسيطة ، ومعظم طي التعبيرات الثابتة ، بالإضافة إلى بعض التحويلات التي تبسط المعالجة اللاحقة.

يتكون كل ملف بقواعد منخفضة المستوى من جزأين:

1. خفض - استبدال العمليات المجردة بمكافئات الماكينة.
2. التحسينات نفسها.

مثال على اختزال العملية إلى جهاز:

 (Const32 [val]) -> (MOVLconst [val]) // L - long, 32- (Const64 [val]) -> (MOVQconst [val]) // Q - quad, 64- | | generic op | AMD64 op 

في التحسينات ذات المستوى المنخفض يتم تنفيذ العدد الرئيسي من التحسينات المهمة ، مثل تقليل تكلفة العمليات ، والتضمين الجزئي واستخدام إمكانيات أوضاع معالجة الذاكرة المتوفرة في المعالج.

العمليات لها اسم ذا ذاكرة ، والذي يسمى عادة كود التشغيل. تعكس عمليات opcodes للعمليات المعتمدة على الهندسة عادة أسماء التعليمات الفعلية.

قاعدة الوصف لغة بناء الجملة

يتم وصف القواعد الأساسية في rulegen.go :

 // rule syntax: // sexpr [&& extra conditions] -> [@block] sexpr // // sexpr are s-expressions (lisp-like parenthesized groupings) // sexpr ::= [variable:](opcode sexpr*) // | variable // | <type> // | [auxint] // | {aux} // // aux ::= variable | {code} // type ::= variable | {code} // variable ::= some token // opcode ::= one of the opcodes from the *Ops.go files 

 //  : // sexpr [&&  ] -> [@block] sexpr // // sexpr -  S- (   ) // sexpr ::= [variable:](opcode sexpr*) // | variable // | <type> // | [auxint] // | {aux} // // aux ::= variable | {code} // type ::= variable | {code} // variable ::= Go  ( ) // opcode ::=   *Ops.go  

ومن الجدير بالذكر أن التعليقات " // " مسموح بها داخل ملفات .Rules .

دعونا نلقي نظرة على مثال بسيط يحتوي على كل هذه العناصر:

  Opcode=ADDLconst -    32-  : AuxInt=c - ,    `x` : : (ADDLconst [c] x) && int32(c)==0 -> x | / | / | | / | / | | / | /    | /   ( `&&`    ) ,     

كل هذه التوقيعات التفسيرية ليست جزءًا من سجل قاعدة صالح.

تحول هذه القاعدة x+0 إلى x . كل شيء داخل قسم الشروط هو رمز Go عادي ،
ما لم تقتصر على التعبيرات التي يجب أن تكون النتيجة bool .
يمكنك استدعاء المسندات المعرفة في rewrite.go .

بالإضافة إلى رموز opcodes المعتادة ، يمكن استخدام مجموعات تؤدي إلى عدة قواعد:

 (ADD(Q|L)const [off] x:(SP)) -> (LEA(Q|L) [off] x) //  Q|L alternation: (ADDQconst [off] x:(SP)) -> (LEAQ [off] x) (ADDLconst [off] x:(SP)) -> (LEAL [off] x) //    `x`: (ADDQconst [off] (SP)) -> (LEAQ [off] (SP)) (ADDLconst [off] (SP)) -> (LEAL [off] (SP)) 

(SP) هي إحدى العمليات في genericOps.go وتعبر عن تحميل مؤشر إلى مكدس الأجهزة. بالنسبة للهندسة المعمارية التي لا توجد بها أجهزة SP ، يتم محاكاتها.

ميزات المتغيرات في القوالب (تعبيرات S على يسار -> ):

• المتغيرات ، مثل x ، بدون تعبير من خلال : تلتقط أي شيء
• مثل المتغير العادي ، يلتقط _ أي قيمة ، ولكن يمكن تجاهل النتيجة

 //       :    ADDQconst, //          : (ADDQconst _) -> v (ADDQconst x) -> (ADDQconst x) 

إذا لم AuxInt تحديد AuxInt (التعبير بين قوسين معقوفين) ، فسيتم AuxInt القاعدة على أي قيمة AuxInt . وبالمثل مع {} -المعلمات (حولهم أدناه).

الاسم v يعني الشكل الخارجي الملتقط.
على سبيل المثال ، بالنسبة للتعبير (ADDQconst (SUBQconst x)) النموذج الخارجي هو ADDQconst .

يمكن استخدام المتغيرات عدة مرات ، وهذا يسمح لك بطلب أن تتطابق أجزاء عديدة من تعبير S مع بعضها البعض:

 (ADDQconst [v] (ADDQconst [v] x)) // , ,  "x+2+2" (x+v+v). 

أنواع القواعد

في بعض الحالات ، يلزم الإشارة بوضوح إلى نوع النموذج الذي تم إنشاؤه و / أو النموذج المطابق.
يشار إلى النوع في "الأقواس المثلثة" ، كوسيطة نوع في قوالب C ++:

 // typ.UInt32 -   BTSLconst. // BSFL    typ.UInt32,    //    . (Ctz16 x) -> (BSFL (BTSLconst <typ.UInt32> [16] x)) 

بالإضافة إلى الأنواع ، هناك "أحرف" (أو ، بشكل عام - خصائص Aux ).

 (StaticCall [argsWidth] {target} mem) -> (CALLstatic [argsWidth] {target} mem) 

• [argsWidth] - Value.AuxInt . بالنسبة لـ StaticCall - الحجم الكلي للوسيطات التي تم تمريرها
• {target} - Value.Aux . ل StaticCall - وظيفة تسمى
• <typ.UInt32> - Value.Type . نوع القيمة

تختلف دلالات Aux و AuxInt اختلافًا كبيرًا من عملية إلى أخرى. أفضل مصدر للتوثيق في هذه الحالة هو ملفات *Ops.go يحتوي كل opData opData opcode على حقل aux يصف كيفية تفسير هذه الحقول.

لوصف الأنواع يتم استخدام الحزمة cmd / compile / internal / types . بعض الأنواع خاصة types.TypeFlags الخلفية لـ SSA ، على سبيل المثال types.TypeFlags . types.TypeFlags ، والباقي شائعة بين cmd/compile/internal/gc و cmd/compile/internal/ssa .

أنواع خاصة

هناك نوع خاص من types.TypeMem . types.TypeMem ، الذي يؤدي عدة وظائف في وقت واحد:

1. يسمح لك بفرز ssa.Value حسب أنماط الوصول إلى الذاكرة. على وجه الخصوص ، هذا يضمن ترتيب التنفيذ الصحيح في إطار الكتل الأساسية (حولها أدناه).
2. يحدد حالة دفق الذاكرة في البرنامج. إذا قامت التعليمات بتعديل الذاكرة ، فسيتم إنشاء قيمة SSA جديدة types.TypeMem سيتم إنشاء types.TypeMem كنتيجة لهذه العملية.

مثل المعنى الخاص لـ OpPhi ، يتم تفسير الذاكرة بشكل استثنائي في العديد من مراحل المحسن.

نوع خاص آخر هو types.TypeFlags . types.TypeFlags المذكورة أعلاه. يصف هذا النوع التعليمات التي تولد إشارات وحدة المعالجة المركزية .

في هذه الحالة ، فإن التعليمات مثل ADDQ ، على الرغم من أنها تولد إشارات ، ليست من أنواع types.Flags ، ولكن يتم تمييزها clobberFlags .

types.Flags تستخدم لتمييز نتيجة التعليمات مثل CMPQ ، التي لا تكتب النتيجة لأي من معاملاتها الواضحة ، ولكن فقط تحديث الحالة الداخلية للمعالج ، والتي يمكن استخدامها من خلال التعليمات التالية.

تتيح لك تعليمات مثل SETL "قراءة" الإشارات وإعادتها على أنها ssa.Value ، والتي يمكن وضعها في السجل.

  L-less than G-greater than | | (SETL (InvertFlags x)) -> (SETG x) | ,   

برنامج التفتيش SSA

لنفترض أن لدينا برنامج مثل هذا ( example.go ):

 package example func fusedMulAdd(a, b, c float64) float64 { return a*c + b } 

يمكننا إلقاء نظرة على رمز SSA الذي تم إنشاؤه لوظيفة fusedMulAdd :

 $ GOSSAFUNC=fusedMulAdd go tool compile example.go > ssa.txt 

تحقق الآن من دليل العمل (الحالي):

• يحتوي ملف ssa.txt على ملف تفريغ tekt.
• ssa.html ، الذي يتم إنشاؤه تلقائيًا ، على نفس المعلومات ، ولكن بتنسيق أكثر تفاعلية ssa.html قراءته. حاول فتح في متصفح.

 v7 (4) MOVSD a(SP), X0 v11 (4) MOVSD c+16(SP), X1 v12 (4) MULSD X1, X0 v6 (4) MOVSD b+8(SP), X1 v13 (4) ADDSD X1, X0 v15 (4) MOVSD X0, ret+24(SP) b1 (4) RET 

هذا ما يبدو عليه برنامج SSA لـ fusedMulAdd بعد المرحلة lower (ssa.html):

 lower [77667 ns] b1: v1 (?) = InitMem <mem> v2 (?) = SP <uintptr> v7 (?) = LEAQ <*float64> {~r3} v2 v8 (3) = Arg <float64> {a} v9 (3) = Arg <float64> {b} v10 (3) = Arg <float64> {c} v12 (+4) = MULSD <float64> v8 v10 v13 (4) = ADDSD <float64> v12 v9 v14 (4) = VarDef <mem> {~r3} v1 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4) 

ترجمة هذا إلى تعبيرات S:

 (MOVQstore {~r3} (SP) (ADDSD (MULSD (Arg {a}) (Arg {c})) (Arg {b}))) 

 regalloc [87237 ns] b1: v1 (?) = InitMem <mem> v14 (4) = VarDef <mem> {~r3} v1 v2 (?) = SP <uintptr> : SP v8 (3) = Arg <float64> {a} : a[float64] v9 (3) = Arg <float64> {b} : b[float64] v10 (3) = Arg <float64> {c} : c[float64] v7 (4) = LoadReg <float64> v8 : X0 v11 (4) = LoadReg <float64> v10 : X1 v12 (+4) = MULSD <float64> v7 v11 : X0 v6 (4) = LoadReg <float64> v9 : X1 v13 (4) = ADDSD <float64> v12 v6 : X0 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4) 

إضافة قواعد تحسين جديدة

في المعالجات ذات FMA ، يمكننا حساب a*c + b في تعليمة واحدة بدلاً من اثنين.

خذ CL117295 كأساس لتأليف إيليا توكار .

لراحتك ، لقد أعددت رقعة diff .

1. إضافة عملية جديدة - FMASD

في ملف compile/internal/ssa/gen/AMD64Ops.go ابحث عن AMD64ops شريحة AMD64ops وأضف عنصرًا جديدًا (في أي مكان):

 { // fp64 fma name: "FMASD", //   SSA argLength: 3, reg: fp31, //   regalloc,   resultInArg0: true, //     source,  destination asm: "VFMADD231SD", //   }, 

نظرًا لعدم وجود عمليات (fp,fp,fp -> fp) قبل ، تحتاج إلى تحديد مؤهل جديد:

  fp01 = regInfo{inputs: nil, outputs: fponly} fp21 = regInfo{inputs: []regMask{fp, fp}, outputs: fponly} + fp31 = regInfo{inputs: []regMask{fp, fp, fp}, outputs: fponly} 

2. إضافة قاعدة التحسين

 (ADDSD (MULSD xy) z) -> (FMASD zxy) 

لن يكون التنفيذ الأكثر صحة غير مشروط وسيتحقق من توافر FMA. سنفترض أن هناك بالتأكيد FMA على الجهاز المستهدف.

يستخدم المحول البرمجي config لهذه الاختبارات:

 //  config.useFMA=false,    . (ADDSD (MULSD xy) z) && config.useFMA-> (FMASD zxy) 

 $ lscpu | grep fma 

3. تنفيذ توليد التعليمات البرمجية

الآن ، في دالة ssaGenValue ، المحددة في ملف compile/internal/amd64/ssa.go ، تحتاج إلى إضافة رمز لإنشاء FMASD :

 func ssaGenValue(s *gc.SSAGenState, v *ssa.Value) { switch v.Op { case ssa.OpAMD64FMASD: p := s.Prog(v.Op.Asm()) //   obj.Prog    // From:  source . p.From = obj.Addr{Type: obj.TYPE_REG, Reg: v.Args[2].Reg()} // To: destination . // v.Reg()  ,      FMASD. p.To = obj.Addr{Type: obj.TYPE_REG, Reg: v.Reg()} // From3:  source . //  From3 .     //  RestArgs,    source ,  . p.SetFrom3(obj.Addr{ Type: obj.TYPE_REG, Reg: v.Args[1].Reg(), }) if v.Reg() != v.Args[0].Reg() { //   resultInArg0 s := v.LongString() v.Fatalf("input[0] and output not in same register %s", s) } //    ,     case. } } 

الآن كل شيء جاهز لاختبار عمل التحسين الجديد. من النادر جدًا إضافة تعليمات جديدة ، وعادة ما يتم إجراء تحسينات جديدة بناءً على عمليات SSA المحددة بالفعل.

فحص النتائج

الخطوة الأولى هي إنشاء كود Go من gen/AMD64Ops.go و gen/AMD64.Rules .

 #  GOROOT  ,   ,   `go env GOROOT`. cd $GOROOT/src/cmd/compile/internal/ssa/gen && go run *.go 

بعد ذلك ، نحتاج إلى إنشاء مترجم جديد:

 go install cmd/compile 

الآن ، عند تجميع نفس المثال ، نحصل على رمز جهاز مختلف:

 - v7 (4) MOVSD a(SP), X0 - v11 (4) MOVSD c+16(SP), X1 - v12 (4) MULSD X1, X0 - v6 (4) MOVSD b+8(SP), X1 - v13 (4) ADDSD X1, X0 - v15 (4) MOVSD X0, ret+24(SP) - b1 (4) RET + v12 (4) MOVSD b+8(SP), X0 + v7 (4) MOVSD a(SP), X1 + v11 (4) MOVSD c+16(SP), X2 + v13 (4) VFMADD231SD X2, X1, X0 + v15 (4) MOVSD X0, ret+24(SP) + b1 (4) RET 

الكتل الأساسية

الآن بعد أن تم إنجاز أصعب العمل ، دعنا نتحدث عن الكتل الأساسية .

القيم التي قمنا بتحسينها أعلاه موجودة في كتل ، وتعمل الكتل.

الكتل ، مثل ssa.Value ، مجردة وتعتمد على الآلة. جميع الكتل لها نقطة دخول واحدة بالضبط ومن 0 إلى 2 كتل وجهة (اعتمادًا على نوع الكتلة).

أبسط الكتل هي If و Exit و Plain :

• تحتوي كتلة Exit على 0 كتل تخصيص. هذه كتل أوراق تصنع قفزة غير محلية ، على سبيل المثال ، باستخدام panic .
• تحتوي الكتلة Plain على كتل تعيين واحدة. يمكن اعتباره قفزة غير مشروطة بعد الانتهاء من جميع تعليمات الكتلة إلى كتلة أخرى.
• If الكتلة تحتوي على كتلتي وجهة. يتم إجراء الانتقال اعتمادًا على الحالة ( Block.Control ).

فيما يلي أمثلة بسيطة لإعادة كتابة الكتل المجردة إلى كتل AMD64 :

   "then" ( ) |  "else" ( ) | | (If (SETL cmp) yes no) -> (LT cmp yes no) (If (SETLE cmp) yes no) -> (LE cmp yes no) 

سيتم النظر في موضوع الكتل بمزيد من التفصيل في سياق مراحل التحسين الأخرى في جزء SSA من المترجم.

حدود قواعد التحسين

خلفية SSA لها مزاياها. بعض التحسينات ممكنة في O(1) . ومع ذلك ، هناك أيضًا عيوب بسبب عدم كفاية SSA للمحسن وحده ، على الأقل حتى تتغير بعض جوانب تنفيذه.

افترض أنك تريد append :

 xs = append(xs, 'a') xs = append(xs, 'b') // => xs = append(xs, 'a', 'b') 

في الوقت الذي يتم فيه إنشاء SSA ، يتم فقدان البنية عالية المستوى للرمز ويتم append ، كونها ليست وظيفة عادية ، بالفعل في نص الكتلة المحتوية عليها. سيكون عليك كتابة قاعدة مرهقة تلتقط التسلسل الكامل للعمليات التي تم إنشاؤها append .

بالحديث بشكل خاص عن .Rules ، فإن DSL لديه عمل ضعيف إلى حد ما مع الكتل ( ssa.Block ). أي تحسين غير بديهي مرتبط بالكتل من المستحيل التعبير عنه بهذه اللغة. تحديث الكتلة الجزئي غير ممكن. من المستحيل أيضًا التخلص من الكتل (ولكن هناك اختراق في شكل الكتلة First ، والذي يستخدم لحذف الرمز الميت).

حتى إذا كانت بعض أوجه القصور قابلة للإصلاح ، يتفق معظم المترجمين على أنه لا يوجد نموذج وسيط واحد وأفضل لتمثيل الشفرة.

انطلق بسرعة أكبر

إذا توصلت إلى بعض قواعد التحسين الرائعة ، فلا تتردد في إرسالها إلى go-review.googlesource.com . يسعدني أن iskander.sharipov@intel.com (أضف إلى iskander.sharipov@intel.com في CC).

مترجم القرصنة سعيد!

المواد الإضافية

أمثلة على التصحيحات الجيدة في Go التي أضافت أو غيرت قواعد SSA:

• CL99656: cmd / compile / internal / ssa: ينبعث منها IMUL3 {L / Q} لـ MUL {L / Q} const على x86
• CL102277: cmd / compile / internal / ssa: تحسين NEG المزدوج على AMD64
• CL54410: cmd / compile / داخلي / ssa: استخدم sse إلى صفر على amd64
• CL58090: cmd / compile / داخلي / ssa: إزالة الإضافات الصفرية الزائدة على amd64
• CL95475: cmd / compile / داخلي / ssa: دمج مخازن البايت على amd64
• CL97175: cmd / compile / داخلي / ssa: دمج متاجر LittleEndian المتتالية على arm64
• CL115617: cmd / compile / internal / ssa: إزالة امتداد صفر عديم الفائدة
• CL101275: cmd / compile: أضف عمليات AMD64 LEAL {1،2،4،8}

منذ وقت ليس ببعيد ، ظهر مستند README لوصف جزء SSA من المترجم.
القراءة الموصى بها.