رفيع المستوى / الأمثل الدلالي

Question

وأنا أكتب مترجم، وأنا أبحث عن الموارد لتحسين. أنا تجميع لآلة القانون، لذلك أي شيء في وقت التشغيل غير وارد.

وما كنت أبحث عنه في الآونة الأخيرة هو أقل الأمثل رمز وأكثر الدلالي / رفيع المستوى الأمثل. على سبيل المثال:

free(malloc(400)); // should be completely optimized away

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

ومثال آخر:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

في هذه الحالة أنا أحب أن تكون قادرة على تهيئة قدرة b لstr.Length + 2 (ما يكفي لعقد بالضبط النتيجة، دون إضاعة الذاكرة).

لنكون صادقين تماما، ليس لدي أي فكرة من أين نبدأ في معالجة هذه المشكلة، لذلك كنت آمل عن مكان للبدء. لم يكن هناك أي عمل في مجالات مماثلة؟ هل هناك أي المجمعين التي نفذت أي شيء من هذا القبيل في الشعور العام؟

Answer 1

لقيام والتحسين في 2 أو أكثر من العمليات، عليك أن تفهم العلاقة الجبرية من هاتين العمليتين. إذا قمت بعرض العمليات في مجال مشكلتهم، وغالبا ما يكون مثل هذه العلاقات.

ولديك مجانا (malloc (400)) غير ممكن لأن حرة وmalloc هي العكوس في مجال تخصيص التخزين. الكثير من العمليات والعكوس وتعليم مترجم أنهم العكوس، ومما يدل على أن نتائج واحدة تدفق البيانات دون قيد أو شرط إلى الآخر، ما هو مطلوب. لديك للتأكد من أن العكوس الخاصة بك حقا العكوس وليس هناك في مكان ما مفاجأة. و/ س س * يبدو وكأنه مجرد قيمة لذلك، ولكن إذا كان x هو صفر تحصل على الفخ. إذا كنت لا تبالي في فخ، وهو معكوس. إذا كنت لا يهتمون فخ ثم الأمثل هو أكثر تعقيدا:       (إذا كان (خ == 0) ثم فخ () آخر أ) الذي لا يزال الأمثل جيد إذا كنت تعتقد الفجوة مكلفة.

والعلاقات "الجبرية" أخرى ممكنة. على سبيل المثال، هناك قد idempotent العمليات: التصفير على أي شيء متغير (وضع لنفسه قيمة مرارا وتكرارا)، وما إلى ذلك هناك عمليات حيث أعمال المعامل واحد مثل عنصر الهوية. X + 0 ==> X لأي 0. إذا X و 0 هي المصفوفات، هذا لا يزال صحيحا والادخار وقتا كبيرا.

ويمكن أن تحدث تحسينات أخرى عندما يمكنك التفكير المجرد حول ما رمز هو فعل. "تفسير الملخص" هو عبارة عن مجموعة من التقنيات لالمنطق حول القيم من خلال تصنيف النتائج في مختلف صناديق مثيرة للاهتمام (على سبيل المثال، وهذا صحيح هو غير معروف، صفر، سلبية أو إيجابية). للقيام بذلك عليك أن تقرر ما صناديق مفيدة، ومن ثم حساب قيمة مجردة في كل نقطة. وهذا مفيد عندما تكون هناك اختبارات على فئات (على سبيل المثال، "اذا كان (س <0) {..." وأنتم تعلمون تجريدي أن x هو أقل من الصفر. يمكنك لهم تحسين بعيدا مشروط.

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

ما هو الصعب هو أن تقرر أي تحسينات تستحق به، لأنك يمكن أن ينتهي لمتابعة كميات هائلة من الاشياء التي قد لا تؤتي ثمارها. دورات الكمبيوتر يتم الحصول على أرخص، وهكذا فمن المنطقي أن تتبع المزيد من العقارات من التعليمات البرمجية في المجمع.

Answer 2

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