تحليل المتغيرات الحية

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

ضع في اعتبارك البرنامج التالي:

ب = 3 ج = 5 أ = د(ب * ج)

مجموعة المتغيرات النشطة بين السطرين 2 و3 هي { b, c} لأن كليهما يُستخدم في عملية الضرب في السطر 3. أما مجموعة المتغيرات النشطة بعد السطر 1 فهي { b} فقط، لأن المتغير cيتم تحديثه لاحقًا في السطر 2. قيمة المتغير aغير مستخدمة في هذا الكود.

aلاحظ أنه يمكن حذف التعيين إلى حيث aلا يتم استخدامه لاحقًا، ولكن لا توجد معلومات كافية لتبرير إزالة السطر 3 بالكامل حيث fقد يكون له آثار جانبية (طباعة b * c، ربما).

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

معادلات تدفق البيانات المستخدمة لكتلة أساسية معينة${\displaystyle s}$والخروج من المبنى${\displaystyle {\mathit {final}}}$تتضمن تحليلات المتغيرات الحية ما يلي:

${\displaystyle {\mbox{GEN}}[s]}$: مجموعة المتغيرات التي يتم استخدامها في s قبل أي عملية إسناد في نفس الكتلة الأساسية.

${\displaystyle {\mbox{اقتل}}[s]}$: مجموعة المتغيرات التي يتم تعيين قيمة لها في s (في العديد من الكتب التي تناقش تصميم المترجمات، يتم تعريف KILL (s) أيضًا على أنها مجموعة المتغيرات التي يتم تعيين قيمة لها في s قبل أي استخدام ، ولكن هذا لا يغير حل معادلة تدفق البيانات):

${\displaystyle {\mbox{LIVE}}_{\mathrm {in} }[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{\mathrm {out} }[s]-{\mbox{KILL}}[s])}$

${\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[{\mathit {final}}]={\emptyset }}$

${\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[s]=\bigcup _{p\in \mathrm {succ} [s]}{\mbox{LIVE}}_{\mathrm {in} }[p]}$

${\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}$

${\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}$

حالة الدخول للكتلة هي مجموعة المتغيرات النشطة في بداية الكتلة. أما حالة الخروج فهي مجموعة المتغيرات النشطة في نهايتها. حالة الخروج هي اتحاد حالات الدخول للكتلات اللاحقة. يتم تطبيق دالة النقل للعبارة بجعل المتغيرات التي تُكتب غير نشطة، ثم جعل المتغيرات التي تُقرأ نشطة.

// في: {}; الكتل السابقة: لا شيء ب1: أ = 3؛ ب = 5؛ د = 4؛ x = 100; // لن يتم استخدام x لاحقًا، وبالتالي لن يكون ضمن مجموعة الإخراج {a,b,d} إذا كان أ > ب، // الناتج: {أ، ب، د} // اتحاد جميع (الداخل) خلفاء b1 => b2: {أ، ب}، و b3: {ب، د} // المدخلات: {أ، ب}؛ الكتل السابقة: ب1 ب2: ج = أ + ب؛ د = 2؛ // الناتج: {ب، د} // المدخلات: {b,d}؛ الكتل السابقة: b1 و b2 ب3: نهاية الشرط ج = 4؛ أعد b * d + c؛ // خارج:{}

تحتوي الحالة الداخلية لـ b3 على b و d فقط ، نظرًا لكتابة c . أما الحالة الخارجية لـ b1 فهي اتحاد الحالتين الداخليتين لـ b2 و b3. يمكن حذف تعريف c في b2، لأن c لا يكون نشطًا مباشرةً بعد العبارة.

يبدأ حل معادلات تدفق البيانات بتهيئة جميع حالات الدخول والخروج إلى مجموعة فارغة. تُهيأ قائمة العمل بإضافة نقطة الخروج (b3) إليها (وهو أمر شائع في التدفق العكسي). تختلف حالة الدخول المحسوبة لهذه النقطة عن سابقتها، لذا تُضاف حالتا الدخول السابقتان b1 وb2، وتستمر العملية. يُلخص الجدول أدناه التقدم المُحرز.

لاحظ أن b1 أُدخل في القائمة قبل b2، مما أجبر على معالجة b1 مرتين (أُعيد إدخال b1 باعتباره العنصر السابق لـ b2). كان إدخال b2 قبل b1 سيسمح بإكمال العملية في وقت أبكر.

تُعدّ التهيئة بالمجموعة الفارغة تهيئةً متفائلة، حيث تبدأ جميع المتغيرات كحالات فارغة. تجدر الإشارة إلى أن حالات الخروج لا يمكن أن تتقلص من تكرار إلى آخر، على الرغم من إمكانية أن تكون حالة الخروج أصغر من حالة الدخول. ويتضح ذلك من حقيقة أنه بعد التكرار الأول، لا يمكن أن تتغير حالة الخروج إلا بتغير حالة الدخول. وبما أن حالة الدخول تبدأ كمجموعة فارغة، فلا يمكنها إلا أن تكبر في التكرارات اللاحقة.

أهو، ألفريد؛ لام، مونيكا؛ سيثي، رافي؛ أولمان، جيفري (2007). المترجمات: المبادئ والتقنيات والأدوات (  الطبعة الثانية). ص  608.