تسجيل تخصيص وتسرب ، الطريقة السهلة؟

Question

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

1. الصواب - خوارزمية ستولد رمزًا صحيحًا بغض النظر عن عدد المتغيرات المحلية الموجودة.
2. البساطة - شيء يمكنني فهمه دون الحاجة إلى قراءة الكثير من الأدب.
3. الكفاءة - يجب أن تكون أفضل من الطريقة الحالية ، وهي:

ترجمة عملية x = y # z ل:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

بينما أستهدف Intel 386 ، بعض القيود ذات الصلة هي:

• تأخذ العمليات الثنائية حجتين ، أحدهما مصدر ووجهة. عمليات أحادية تأخذ حجة واحدة.
• يمكن للعمليات الوصول إلى موقع ذاكرة واحد فقط ؛ وبالتالي فإن العمليات الثنائية تحتاج إلى حجة واحدة على الأقل في السجل.
• هناك ما لا يقل عن ستة سجلات متوفرة: %eax %ebx %ecx %edx %esi %edi. (%ebp يمكن أيضًا إدراجها كملاذ أخير.)
• هناك حالات خاصة مثل تقسيم عدد صحيح وسجلات الإرجاع ، لكن يمكنني تجاهلها في الوقت الحالي.

هناك ثلاث خطوات يحصل عليها المترجم في الوقت الحالي:

• i386ification: يتم تحويل جميع العمليات إلى نموذج a = a # b (أو a = #a لعمليات أحادية).
• تحليل LEVING: يتم تحديد مجموعات المتغيرات الحية قبل وبعد كل عملية.
• تخصيص التسجيل: تم تصميم رسم بياني للتداخل وتلوينه.

ثم يرمي المترجم الطباشير الملون في الهواء ولا يعرف ماذا تفعل بعد ذلك.

مثال

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

إليك الرسم البياني للتداخل إلى حد ما للوظيفة ، و CFG مع معلومات li -livid. تتطلب صورة CFG بعض التمرير الرأسي ، للأسف.

• رسم بياني للتداخل لوظيفة على 14 متغير
• الرسم البياني لتدفق التحكم لوظيفة ، مع معلومات lifies

تم استخدام سبعة ألوان. أرغب في تسرب أحدهم (أو مجموعة المتغيرات المعينة لهذا اللون). طريقة الاختيار التي ليست مهمة للغاية. ما يصبح صعبًا هو كيفية التعامل مع المتغيرات المنسكبة.

دعنا نقول أنني أسكب "الوردي" ، وهي مجموعة المتغيرات t, $t4, $t7. هذا يعني أن تلك العمليات التي تشير إلى أحد هذه المتغيرات ستصل إليها من موضعها على إطار المكدس ، بدلاً من السجل. هذا يجب أن يعمل لهذا المثال.

ولكن ماذا لو كان البرنامج:

...
a = a + b
...

وكلاهما a و b كان يجب أن تسرب؟ لا أستطيع أن أستند إلى تعليمات addl b, a مع اثنين من عناوين الذاكرة. سأحتاج إلى سجل احتياطي آخر لعقد أحد المعاملات مؤقتًا ، وهذا يعني تسرب لون آخر. هذا يشير إلى طريقة عامة لـ:

1. إذا كان يمكن تلوين جميع المتغيرات r ألوان رائعة!
2. خلاف ذلك ، انسكب بعض الألوان والمتغيرات المرتبطة بها.
3. في حالة وجود عملية تصل إلى متغيرين منسكرين ، قم بتسكع لون آخر واستخدم سجل الاحتياط للتخزين المؤقت لجميع هذه العمليات.

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

مشاكل محددة

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

المشاكل الثانوية هي:

• كيف يمكنني تحديد مكان إدراج تعليمات الحمل/التخزين ، من أجل الصواب (والأهم من ذلك ، الكفاءة)؟
• هل يمكنني تسرب متغير لهذا الجزء فقط من حياته عندما لا يكون مستفيدًا فوريًا ، وأصلحه لاحقًا؟ بحيث تعمل جميع التعليمات على السجلات غير المسلحة. قد يعيش المتغير في سجلات مختلفة في أوقات مختلفة.
• هل يمكنني أن أكون أكثر كفاءة مع الحالات الخاصة. علي سبيل المثال، %eax يستخدم لقيمة الإرجاع ، لذلك سيكون من الرائع أن يتم تخصيص المتغير الذي تم إرجاعه لهذا السجل بحلول الوقت الذي تمت فيه مواجهة العائد. وبالمثل ، فإن بعض السجلات هي "Callee-Save" ، لذلك إذا حدث عدد أقل من المتغيرات في وقت مكالمة وظيفية ، فإن تخصيصها لتخصيصها لسجلات غير محددة ، فهذا يعني أنه يمكنني تجنب تخزين تلك السجلات.
• هل سيساعد نموذج SSA كثيرًا (إن وجد)؟ قد تكون القدرة على القضاء على التعبيرات الفرعية المشتركة وتقييم الثوابت قد تقلل من الضغط (؟) ، ولكن هل سيكون لها أي تأثير؟

الجوانب التي لست مهتمًا بها (الآن) هي:

• تخصيص المكدس وتحسينه: يتم تنفيذه بسذاجة بالفعل ، ويمكن تحسينه باستخدام الرسم البياني للتداخل إذا لزم الأمر.
• كفاءة وقت الترجمة ، طالما أنها تنتهي. (لا يعني اكتمال NP خوارزمية معينة.

تحديث

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

لقد وجدت العرض التقديمي الجميل (PPT ، للأسف):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/register٪20allocation.ppt

الذي يجيب على السؤال حول كيفية التعامل مع احتياجات التشغيل المحددة (مثل استخدام نفس السجل للمصدر والوجهة ؛ أو تحتاج إلى سجل معين لبعض العمليات). ما لست متأكدًا منه هو ما إذا كانت دورة التخصيص ذات اللون الثقيل تنتهي.

سأحاول القيام ببعض الأعمال الفعلية قريبًا ونأمل أن أغلق السؤال.

Answer 1

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

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

يوضح هذا المخطط تمامًا أين تذهب جميع الأحمال/المتاجر ، فأنت تنشئها كما تذهب. يمكن تكييفه بسهولة مع الإرشادات التي تأخذ قيمة في الذاكرة ، أو والتي يمكن أن تأخذ أي من وسيطتين في الذاكرة ، ولكن ليس كلاهما.

إذا كنت موافقًا على وجود جميع البيانات على المكدس في كل حدود كتلة أساسية ، فإن هذا المخطط يعمل بشكل جيد. يجب أن يعطي نتائج مشابهة للمسح الخطي داخل كتلة أساسية ، كما يفعل بشكل أساسي أشياء مشابهة للغاية.

يمكنك التعقيد بشكل تعسفي حول كيفية تحديد القيم التي يجب تسربها والتي تسجل لتخصيصها. يمكن أن يكون بعض Lookahead مفيدًا ، على سبيل المثال من خلال وضع علامة على كل قيمة مع سجل محدد ، يجب أن يكون في مرحلة ما في الكتلة الأساسية (على سبيل المثال ، مقابل قيمة الإرجاع ، أو ECX لمبلغ التحول) ويفضل ذلك التسجيل عند القيمة يتم تخصيصه لأول مرة (وتجنب هذا السجل لتخصيصات أخرى). ولكن من السهل فصل صحة الخوارزمية عن الاستدلال التحسن.

لقد استخدمت هذا المخصص في برنامج التحويل البرمجي SSA ، YMMV.

Answer 2

أولاً: لا توجد طريقة ذكية للقيام بذلك. المشكلة هي NP-Complete ؛-)

كيف يتم الانسكاب:

يمكنك تشغيل خوارزمية تخصيص التسجيل الخاصة بك والحصول على قائمة بالمتغيرات التي يجب أن تسكبها. يمكنك الآن تخصيص بعض المساحة على المكدس في بداية وظيفتك. اربط كل متغير مسكوب أيضًا مكان على المكدس. إذا كنت تريد أن تكون ذاكرة SMART COALESCE مع نطاقات حية غير متداخلة. كلما احتجت إلى تسرب سجل ، احفظه للذاكرة وتحميله ، عندما تكون هناك حاجة مرة أخرى.

كيفية التعامل مع EAX:

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

طرق سهلة وصحيحة للتعامل مع الانسكاب:

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

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

إجابات محددة

1. ماذا يعني الصواب بالنسبة لك؟ حتى خوارزميات التخصيصات البسيطة صحيحة إذا لم ترتكب خطأ في البرمجة. التدقيق (الرياضي) صحة أكثر صعوبة بكثير. يجب إدراج كل من الأحمال والمتاجر قبل الحاجة إلى القيمة/التسجيل مرة أخرى. كلاهما يجب إدراجه بعد تخزين/إنشاء القيمة.

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

3. الأمر متروك لك مرة أخرى لتنفيذ بعض التحسينات. يتمثل أحد الاحتمالات في منع EAX فقط عند الحاجة ، وليس للبرنامج بأكمله.

4. في ظل ظروف معينة ، يساعد SSA. الرسوم البيانية الاستدلال لرمز SSA هي دائما وتر, ، وهذا يعني أنه لا توجد دورة مع أكثر من 3 عقد. هذه حالة خاصة من تلوين الرسم البياني ، حيث يمكن العثور على الحد الأدنى من التلوين في وقت متعدد الحدود. التحويل إلى SSA لا يعني بالضرورة أكثر أو أقل تسجيل الضغط. في حين أن نموذج SSA يحتوي عادةً على المزيد من المتغيرات ، فإن هذه المتغيرات تميل إلى أن يكون لها أعيام أصغر.