التحكم في التبعية

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

التبعية التحكمية هي حالة يتم فيها تنفيذ تعليمات البرنامج إذا تم تقييم التعليمات السابقة بطريقة تسمح بتنفيذها.

تعتمد التعليمات B على التعليمات السابقة A إذا كانت نتيجة A تحدد ما إذا كان ينبغي تنفيذ B أم لا. في المثال التالي، التعليماتS2{\displaystyle S_{2}}يعتمد التحكم على التعليماتS1{\displaystyle S_{1}}. لكن،S3{\displaystyle S_{3}}لا يعتمد علىS1{\displaystyle S_{1}}لأنS3{\displaystyle S_{3}}يتم تنفيذه دائماً بغض النظر عن نتيجةS1{\displaystyle S_{1}}.

S1. إذا كان (أ == ب) S2. a = a + b S3. b = a + b

بشكل بديهي، توجد علاقة تحكم بين عبارتين A و B إذا

  • من المحتمل أن يتم تنفيذ حكم الإعدام على (ب) بعد (أ)
  • ستحدد نتيجة تنفيذ الأمر (أ) ما إذا كان سيتم تنفيذ الأمر (ب) أم لا.

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

يمكن تقديم تعريف رسمي لاعتماد التحكم على النحو التالي:

بيانS2{\displaystyle S_{2}}يقال إن التحكم يعتمد على بيان آخرS1{\displaystyle S_{1}}إذا

  • يوجد مسارP{\displaystyle P}منS1{\displaystyle S_{1}}لS2{\displaystyle S_{2}}بحيث يكون كل بيانSأنا{\displaystyle S_{i}}≠S1{\displaystyle S_{1}}داخلP{\displaystyle P}وسيتبع ذلكS2{\displaystyle S_{2}}في كل مسار ممكن لنهاية البرنامج و
  • S1{\displaystyle S_{1}}لن يتبع ذلك بالضرورةS2{\displaystyle S_{2}}أي أن هناك مسار تنفيذ منS1{\displaystyle S_{1}}إلى نهاية البرنامج الذي لا يمرS2{\displaystyle S_{2}}.

وباستخدام مفهوم (ما بعد) الهيمنة، يصبح الشرطان متكافئين.

  • S2{\displaystyle S_{2}}يهيمن المنشور على كل شيءSأنا{\displaystyle S_{i}}
  • S2{\displaystyle S_{2}}لا يهيمن بعدS1{\displaystyle S_{1}}

بناء تبعيات التحكم

تُمثل تبعيات التحكم أساسًا حدود الهيمنة في الرسم البياني العكسي لرسم بياني تدفق التحكم (CFG). [ 1 ] وبالتالي، تتمثل إحدى طرق إنشائها في إنشاء حدود ما بعد الهيمنة لرسم بياني تدفق التحكم، ثم عكسها للحصول على رسم بياني لتبعيات التحكم.

فيما يلي رمز زائف لإنشاء حدود ما بعد الهيمنة:

لكل X في عملية اجتياز تصاعدية لشجرة ما بعد الهيمنة، قم بما يلي : PostDominanceFrontier(X) ← ∅ لكل Y ∈ Predecessors(X) نفّذ ما يلي : إذا كان immediatePostDominator(Y) ≠ X: فإن PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} انتهى. لكل Z ∈ Children(X) نفّذ ما يلي : لكل Y ∈ PostDominanceFrontier(Z) نفّذ ما يلي : إذا كان immediatePostDominator(Y) ≠ X: فإن PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} انتهى. انتهى . انتهى .

هنا، تمثل Children(X) مجموعة العقد في مخطط التدفق الحر (CFG) التي تهيمن عليها X مباشرةً ، بينما تمثل Predecessors(X) مجموعة العقد في مخطط التدفق الحر التي تسبق X مباشرةً . تجدر الإشارة إلى أنه لا تتم معالجة العقدة X إلا ​​بعد معالجة جميع عقدها الفرعية. بمجرد حساب خريطة حدود ما بعد الهيمنة، سيؤدي عكسها إلى إنشاء خريطة من العقد في مخطط التدفق الحر إلى العقد التي تعتمد عليها في التحكم.

انظر أيضاً

مراجع

  1. ↑ سيترون، ر.؛ فيرانتي، ج.؛ روزن، ب.ك.؛ ويغمان، م.ن.؛ زاديك، ف.ك. (1989-01-01). "طريقة فعالة لحساب شكل التعيين الفردي الثابت". وقائع الندوة السادسة عشرة لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة - POPL '89 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 25-35 . doi : 10.1145/75277.75280 . ISBN  0897912942. S2CID 8301431 .