كيفية تنفيذ المكالمات الخلفية في جهاز افتراضي مخصص

Question

كيف يمكنني تنفيذ المكالمات الخلفية في جهاز افتراضي مخصص؟

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

Answer 1

أعتبر أنه من المسلم به أننا نناقش هنا جهازًا افتراضيًا تقليديًا "قائمًا على المكدس".

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

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

والتي بدون تحسين قد تنتج رمز بايت رمزيًا مثل:

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

يعني CALL_FUN2 "استدعاء دالة ذات وسيطتين".مع التحسين، يمكن أن يصبح في وقت ما مثل:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

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

Answer 2

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

لهذا الرمز:

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

سيكون

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

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

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

بالنظر مرة أخرى ، يعكس هذا "التجميع" بشكل أفضل هذا C ++ ، والذي تجنب بوضوح مكالمات العودية

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}