سلسلة تعريف الاستخدام

في مجال علوم الحاسوب ، تُعرف سلسلة الاستخدام والتعريف (أو سلسلة UD ) بأنها بنية بيانات تتكون من استخدام U لمتغير ، وجميع تعريفات D لهذا المتغير التي يمكن أن تصل إلى هذا الاستخدام دون أي تعريفات وسيطة أخرى. ^{[ 1 ] [ 2 ]} وتعني سلسلة الاستخدام والتعريف عمومًا إسناد قيمة ما إلى متغير.

يُعدّ نظير سلسلة التعريف والاستخدام (أو سلسلة التعريف والاستخدام ) سلسلة تعريف-استخدام ، والتي تتكون من تعريف D لمتغير ما وجميع الاستخدامات U التي يمكن الوصول إليها من ذلك التعريف دون أي تعريفات وسيطة أخرى. ^{[ 3 ]}

يتم إنشاء سلاسل UD وDU باستخدام شكل من أشكال تحليل الكود الثابت يُعرف بتحليل تدفق البيانات . يُعدّ معرفة سلاسل use-def وdef-use لبرنامج أو برنامج فرعي شرطًا أساسيًا للعديد من تحسينات المُصرّف ، بما في ذلك نشر الثوابت وإزالة التعبيرات الفرعية المشتركة .

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

انظر إلى مقتطف الشفرة التالي:

int x = 0 ; /* أ */ x = x + y ; /* ب */ /* 1، بعض استخدامات x */ x = 35 ; /* ج */ /* 2، المزيد من استخدامات x */

لاحظ أن xالمتغير يُسند إليه قيمة في ثلاث نقاط (مُشار إليها بـ A وB وC). مع ذلك، عند النقطة المُشار إليها بـ "1"، xيجب أن تُشير سلسلة تعريفات الاستخدام إلى أن قيمته الحالية يجب أن تكون مُستمدة من السطر B (وقيمته عند السطر B يجب أن تكون مُستمدة من السطر A). على النقيض من ذلك، عند النقطة المُشار إليها بـ "2"، xتُشير سلسلة تعريفات الاستخدام إلى أن قيمته الحالية يجب أن تكون مُستمدة من السطر C. بما أن قيمة المتغير xفي الكتلة 2 لا تعتمد على أي تعريفات في الكتلة 1 أو ما قبلها، xفمن المُمكن اعتباره متغيرًا مُختلفًا هناك؛ عمليًا، هو مُتغير مُختلف - فلنُسمِّه x2.

int x = 0 ; /* أ */ x = x + y ; /* ب */ /* 1، بعض استخدامات x */ int x2 = 35 ; /* ج */ /* 2، بعض استخدامات x2 */

xتُسمى عملية تقسيم المتغير إلى متغيرين منفصلين بتقسيم النطاق الحي . انظر أيضًا نموذج التعيين الفردي الثابت .

تحدد قائمة العبارات ترتيبًا قويًا بين العبارات.

• تُصنّف البيانات وفقًا للاصطلاحات التالية :${\displaystyle s(i)}$، حيث i عدد صحيح في${\displaystyle [1,n]}$و nهو عدد العبارات في الكتلة الأساسية
• يتم تحديد المتغيرات بخط مائل (مثل v و u و t )
• يُفترض أن لكل متغير تعريفًا في السياق أو النطاق. (في شكل التعيين الفردي الثابت ، تكون سلاسل الاستخدام والتعريف صريحة لأن كل سلسلة تحتوي على عنصر واحد.)

بالنسبة لمتغير مثل v ، يتم تعريفه بالحرف V (حرف كبير مائل)، وباختصار، يتم تعريفه بالحرف ⁠${\displaystyle s(0)}$. بشكل عام، يمكن أن يكون تعريف المتغير في نطاق خارجي (على سبيل المثال، متغير عام ).

ضع في اعتبارك التنفيذ التسلسلي لقائمة العبارات ،${\displaystyle s(i)}$⁠ , وما يمكن ملاحظته الآن على أنه الحساب في العبارة j :

• تعريف في البيان${\displaystyle s(i)}$⁠ مع i < j يكون موجودًا عند j ، إذا كان له استخدام في عبارة ⁠${\displaystyle s(k)}$حيث k ≥ j . يُرمز إلىمجموعةالتعريفات الحية عند العبارة i بـ${\displaystyle A(i)}$وعدد التعريفات الحية كـ${\displaystyle |A(i)|}$. ( ⁠${\displaystyle A(i)}$⁠ هو مفهوم بسيط ولكنه قوي:تستند النتائج النظرية والعملية في نظرية تعقيد المساحة ، وتعقيد الوصول (تعقيد الإدخال/الإخراج)، وتخصيص السجلات ، واستغلال موضع الذاكرة المؤقتة إلى ⁠${\displaystyle A(i)}$. )
• تعريف في البيان${\displaystyle s(i)}$يلغي جميع التعريفات السابقة (${\displaystyle s(k)}$مع k < i ) لنفس المتغيرات.

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

/*** @param(a, b) القيم المستخدمة لحساب المقسوم عليه.* @return القاسم المشترك الأكبر لـ a و b.*/دالة القاسم المشترك الأكبر ( عدد صحيح أ ، عدد صحيح ب ) {int c = a ;int d = b ;إذا ( ج == 0 )أعد د ؛بينما ( د ≠ 0 ) {إذا ( ج > د )ج = ج - د ؛آخرد = د - ج ؛}أعد c ;}

للعثور على جميع سلاسل استخدام التعريفات للمتغير d، اتبع الخطوات التالية:

1. ابحث عن أول مرة يتم فيها تعريف المتغير (الوصول للكتابة).

   في هذه الحالة يكون " d=b" (السطر 7)

2. ابحث عن أول مرة يتم فيها قراءة المتغير.

   في هذه الحالة يكون " return d"

3. اكتب هذه المعلومات بالأسلوب التالي: [اسم المتغير الذي تقوم بإنشاء سلسلة استخدام له، وإمكانية الوصول للكتابة، وإمكانية الوصول للقراءة]

   في هذه الحالة يكون الأمر كالتالي:[d, d=b, return d]

كرر هذه الخطوات بالأسلوب التالي: اجمع كل عملية كتابة مع كل عملية قراءة (ولكن ليس العكس).

ينبغي أن تكون النتيجة كالتالي:

[ د ، د = ب ، إرجاع د ][ d , d = b , while ( d != 0 )][ د ، د = ب ، إذا ( ج > د )][ د ، د = ب ، ج = ج - د ][ د ، د = ب ، د = د - ج ][ d , d = d - c , while ( d != 0 )][ د ، د = د - ج ، إذا ( ج > د )][ د ، د = د - ج ، ج = ج - د ][ د ، د = د - ج ، د = د - ج ]

يجب عليك توخي الحذر إذا تغير المتغير بمرور الوقت.

على سبيل المثال: من السطر 7 إلى السطر 13 في الكود المصدري، لا يُعاد تعريف المتغير d أو تغييره. في السطر 14، يمكن إعادة تعريف d . لهذا السبب، يجب دمج عملية الكتابة هذه على d مع جميع عمليات القراءة الممكنة. في هذه الحالة، يكون الكود الذي يلي السطر 10 فقط هو المهم. السطر 7، على سبيل المثال، لا يمكن الوصول إليه مرة أخرى. لفهم ذلك، يمكنك تخيل متغيرين مختلفين d :

[ d1 , d1 = b , return d1 ][ d1 , d1 = b , while ( d1 != 0 )][ d1 , d1 = b , if ( c > d1 )][ d1 , d1 = b , c = c - d1 ][ d1 , d1 = b , d1 = d1 - c ][ d2 , d2 = d2 - c , while ( d2 != 0 )][ d2 , d2 = d2 - c , if ( c > d2 )][ d2 , d2 = d2 - c , c = c - d2 ][ d2 , d2 = d2 - c , d2 = d2 - c ]

ونتيجة لذلك، قد تحصل على شيء كهذا. سيتم استبدال المتغير d1 بالمتغير b.

/*** @param(a, b) القيم المستخدمة لحساب المقسوم عليه.* @return القاسم المشترك الأكبر لـ a و b.**/دالة القاسم المشترك الأكبر ( عدد صحيح أ ، عدد صحيح ب ) {int c = a ;int d ;إذا ( ج == 0 )أعد b ؛إذا كان ( ب != 0 ) {إذا كان ( ج > ب ) {ج = ج - ب ؛د = ب ؛}آخرد = ب - ج ؛بينما ( د ≠ 0 ) {إذا ( ج > د )ج = ج - د ؛آخرد = د - ج ؛}}أعد c ;}

1. حدد التعريفات في البيان${\displaystyle s(0)}$⁠
2. لكل i في​${\displaystyle [1,n]}$ابحث عن تعريفات حية لها فائدة في البيان${\displaystyle s(i)}$⁠
3. قم بربط التعريفات والاستخدامات
4. حدد العبارة${\displaystyle s(i)}$، كبيان تعريفي
5. حذف التعريفات السابقة

باستخدام هذه الخوارزمية، يتم تحقيق أمرين:

1. يتم إنشاء رسم بياني موجه غير دوري (DAG) على المتغيرات uses و definitions. يحدد الرسم البياني الموجه غير الدوري تبعية البيانات بين عبارات التعيين، بالإضافة إلى ترتيب جزئي (وبالتالي توازي بين العبارات).
2. بيان متى${\displaystyle s(i)}$عند الوصول إلى هذه النقطة، توجد قائمة بتخصيصات المتغيرات النشطة . إذا كان هناك تخصيص واحد فقط نشط، على سبيل المثال،فقد يتم استخدام نشر الثوابت .