مترجم تحسينات الأسئلة

Question

1. ما هي بعض الطرق مترجم يلغي المتكررة subexpressions recomputations?كيف يمكنك تتبع الفرعية العبارات ؟ و كيف يمكنك التعرف المتكررة منها ؟
2. إلى جانب استخدام المعامل المشغلين ، ما هي بعض من الحد من قوة التقنيات الشائعة المجمعين استخدام ؟

Answer 1

1. أعتقد أن الكثير من المجمعين استخدام SSAPRE (واحد ثابت التنازل الجزئي التكرار القضاء) القضاء عنه مرارا.وهذا يتطلب القانون أن يكون في SSA شكل, يسمح العديد من التحسينات.

2. أنا لست متأكدة من هذا ، ولكن انظر هذه قائمة LLVM يمر. LLVM هو الأمثل IR لمعديها التي غالبا ما تكون أسرع من دول مجلس التعاون الخليجي.هناك صغير شرح كل تمريرة.إذا كنت بحاجة إلى مزيد من المعلومات ، أنظر LLVM مصدر للحصول على هذه التصاريح.هو مكتوب في C++ ولكن هو نظيفة تماما ومفهومة.

تحرير:بالمناسبة, إذا كنت في وضع مترجم, أنا أوصي LLVM, فمن السهل جدا للاستخدام يولد رمز الأمثل للغاية.

Answer 2

1, اسم الأمثل الذي تبحث عنه هو شائع subexpression القضاء (CSE).اعتمادا على التمثيل ، وهذا يمكن أن يكون من السهل إلى حد ما.عادة, مترجم بعض التمثيل الوسيط من البرنامج حيث عمليات كسر قدر الإمكان و خطي.لذلك على سبيل المثال ، التعبير c = a * b + a * b قد تكون موزعة كما يلي:

v1 = a * b
v2 = a * b
c = v1 + v2

لذلك يمكن أن تفعل CSE في مستوى منخفض جدا من خلال البحث عن العمليات مع نفس المشغل و المعاملات.عندما واجهت مكررة (v2 في هذه الحالة) ، يمكنك استبدال كافة مثيلات مع الأصل.لذا يمكننا تبسيط التعليمات البرمجية أعلاه إلى:

v1 = a * b
c = v1 + v1

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

وفي كلتا الحالتين, يمكنك الحصول على بعض تحسين الأساسية, و كل ما عليك أن تتبع أساسية في التعبير.قد تريد أن تأخذ خطوة أخرى في هذا المجال والبحث عن الحساب الهويات.فعلى سبيل المثال ، a * b هو نفس b * a.أيضا ، x * (y + z) = x * y + x * z.وهذا يجعل الأمثل الخاص بك أكثر تعقيدا ، وليس من الواضح أنها سوف تعطيك الكثير لتحسين الأداء.اغلب من الاستفادة من CSE الأمثل يأتي من معالجة العمليات الحسابية مثل مجموعة يصل و لن تحتاج معقدة الهويات مثل تلك المذكورة أعلاه.

2, ما من قوة التخفيضات هي مفيدة حقا يتوقف على العمارة ترجمة ل.هذا وعادة ما ينطوي فقط على تحويل الضرب والانقسامات في التحولات والإضافات الطرح.

Answer 3

سأكون في غاية يوصي اثنين من المراجع المطبوعة على هذه المواضيع:

1. المتقدمة مترجم تصميم و تنفيذ ستيفن س.Muchnick
2. بناء وتحسين مترجم روبرت مورغان

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

Answer 4

لإضافة أحد أكثر الكتاب إلى قائمة من التوصيات تحقق "هاكر فرحة" هنري س.وارن.إنها الخلاصة كبيرة من التقنيات لتحسين العمليات المشتركة ، مثل تحويل عدد صحيح الانقسامات في الضرب.

Answer 5

كنت تبحث عن جزئية-التكرار القضاء على (قبل).كل CSE (من إجابات أخرى) و حلقة ثابتة رمز الحركة هي تصنف من قبل.(الاختلاف من قبل كسول رمز الحركة التي أعتقد هو الأمثل).

تحقق من كيث كوبر المحاضرات, التي يبدو أنها تصف التقنيات بشكل جيد جدا.

هل لا استخدام SSAPRE.AFAIK ، وهذا يتطلب شكل معين من أفريقيا جنوب الصحراء المعروفة باسم HSSA ، والتي لديها عدد قليل من سلبيات:

• جميلة معقدة
• فإنه يتطلب القيمة العالمية الترقيم (وهكذا SSAPRE لا توفر قيمة الترقيم ، حيث من المتوقع أن توجد بالفعل).
• أنها لا تقدم أي شيء إذا كانت لغتك لا يدعم مؤشرات إلى كومة المتغيرات (و إذا لم تتوقف عن الكتابة الخاصة بك وتحليل واستخدام LLVM أو دول مجلس التعاون الخليجي).
• دول مجلس التعاون الخليجي تستخدم HSSA لفترة من الوقت, ولكنها قد انتقلت بعيدا عن ذلك.
• LLVM جربت ذلك لكن AFAIK أنها لا تستخدم بعد الآن.

تحرير:

Muchnick هذا الكتاب يحتوي على وصف مفصل لها ربط في جواب آخر.