تحليل تدفق البيانات

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

ينبغي أن يكون نطاق القيمة ترتيبًا جزئيًا بارتفاع محدود (أي، لا توجد سلاسل تصاعدية لانهائية).${\displaystyle x_{1}}$<${\displaystyle x_{2}}$...). يجب أن يكون الجمع بين دالة التحويل وعملية الربط رتيبًا بالنسبة لهذا الترتيب الجزئي. يضمن الرتابة أن تظل القيمة ثابتة أو تزداد في كل تكرار، بينما يضمن الارتفاع المحدود عدم إمكانية نموها إلى ما لا نهاية. وبالتالي، سنصل في النهاية إلى حالة يكون فيها T(x) = x لجميع قيم x، وهي النقطة الثابتة.

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

تبدأ الخوارزمية بوضع كتل توليد المعلومات في قائمة العمل. وتنتهي عندما تصبح قائمة العمل فارغة.

تتأثر كفاءة حل معادلات تدفق البيانات بالتكرار بترتيب زيارة العقد المحلية. ^{[ 9 ]} كما تعتمد على ما إذا كانت معادلات تدفق البيانات تُستخدم لتحليل تدفق البيانات الأمامي أو العكسي على مخطط تدفق التحكم. وبشكل بديهي، في مسألة التدفق الأمامي، يكون الحل أسرع إذا تمت معالجة جميع العقد السابقة للكتلة قبل الكتلة نفسها، لأن التكرار سيستخدم حينها أحدث المعلومات. في حال عدم وجود حلقات تكرار، يمكن ترتيب الكتل بحيث تُحسب حالات الخروج الصحيحة بمعالجة كل كتلة مرة واحدة فقط.

فيما يلي، نناقش بعض ترتيبات التكرار لحل معادلات تدفق البيانات (مفهوم ذو صلة بترتيب تكرار CFG هو اجتياز الشجرة ) .

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

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

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

 إذا كان b يساوي 4،  أ = 5؛  آخر  أ = 3؛  endif  إذا كانت قيمة a أقل من 4،  ... 

إن تعريف الوصول للمتغير aفي السطر 7 هو مجموعة التعيينات a = 5في السطر 2 a = 3وفي السطر 4.

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

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

الكود الأولي:

ب1: أ = 3؛ ب = 5؛ د = 4؛ x = 100؛ إذا كان أ > ب، ب2: ج = أ + ب؛ د = 2؛ ب3: نهاية الشرط ج = 4؛ أعد b * d + c؛

التحليل العكسي:

// في: {} ب1: أ = 3؛ ب = 5؛ د = 4؛ x = 100; // لن يتم استخدام x لاحقًا، وبالتالي لن يكون ضمن مجموعة الإخراج {a,b,d} إذا كان أ > ب، // الناتج: {أ، ب، د} // اتحاد جميع (الداخل) خلفاء b1 => b2: {أ، ب}، و b3: {ب، د} // في: {أ، ب} ب2: ج = أ + ب؛ د = 2؛ // الناتج: {ب، د} // في: {ب، د} ب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 سيسمح بإكمال العملية في وقت أبكر.

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

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

على سبيل المثال، في تحليل المتغيرات الحية، تُسمى عملية الربط "الاتحاد". مجموعة الحذف هي مجموعة المتغيرات التي تُكتب في كتلة، بينما مجموعة التوليد هي مجموعة المتغيرات التي تُقرأ دون كتابتها أولاً. تصبح معادلات تدفق البيانات كما يلي:

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

في العمليات المنطقية، يُقرأ هذا على النحو التالي

out( b ) = 0 for s in succ( b ) out( b ) = out( b ) or in( s ) in( b ) = (out( b ) and not kill( b )) or gen( b )

تُسمى مسائل تدفق البيانات التي تحتوي على مجموعات من قيم تدفق البيانات التي يمكن تمثيلها كمتجهات ثنائية بمسائل المتجهات الثنائية ، أو مسائل التوليد والحذف ، أو المسائل القابلة للفصل محليًا . ^{[ 13 ]} لهذه المسائل حلول عامة في زمن متعدد الحدود. ^{[ 14 ]}

بالإضافة إلى مشاكل تعريفات الوصول والمتغيرات الحية المذكورة أعلاه، فإن المشاكل التالية هي أمثلة على مشاكل المتجهات الثنائية: ^{[ 14 ]}

• التعبيرات المتاحة
• تعابير وجه شديدة الانشغال
• سلاسل تعريف الاستخدام

تُعدّ مسائل المجموعات الجزئية، أو مسائل المجموعات الجزئية المحدودة، أو مسائل IFDS، فئة أخرى من المسائل ذات حلول عامة متعددة الحدود. ^{[ 13 ] [ 15 ]} توفر حلول هذه المسائل تحليلات لتدفق البيانات حساسة للسياق وحساسة لتدفق البيانات.

هناك العديد من تطبيقات تحليلات تدفق البيانات القائمة على IFDS للغات البرمجة الشائعة، على سبيل المثال في إطار عمل Soot ^{[ 16 ]} و WALA ^{[ 17 ]} لتحليل Java.

كل مشكلة تتعلق بالمتجهات الثنائية هي أيضًا مشكلة IFDS، ولكن هناك العديد من مشاكل IFDS المهمة التي لا تعتبر مشاكل متجهات ثنائية، بما في ذلك المتغيرات الحية حقًا والمتغيرات التي ربما تكون غير مهيأة.