موسيقى
بسم الله الرحمن الرحيم والصلاة والسلام على أشرف
المرسلين، اليوم إن شاء الله بنكمل اللي كنا بدينا فيه
المحاضرة الماضية اللي هو section 86 a simple code
generator وكنا بصينا على عملية الـ target code
generation كيف إن في عندنا مهام مختلفة لازم لازم
تتحضر علشان تقدر اللي هو الـ Algorithm تتناول الـ
three address code instructions اللي هي الـ input
ويتحولها إلى machine instructions، وقولنا أهم شغل
من التحضيرات هذه اللي هي الـ register and address
descriptors، الـ register and address descriptors
اللي هي احنا على السريع بدي أنتقل إلى الـ slide هذه
اللي كانت مثلًا اللي بدأنا فيه من البداية وهدولة
هم الـ descriptors هدولة الـ register descriptors و
هدولة الـ address أو الـ memory descriptors، okay
فاحنا الآن أصبحت لدينا اللي هو التجهيزات اللي لازم
صارت واضحة، وإضافة إلى ذلك غير الـ descriptors في
عندنا قضية تجسيم الـ code إلى blocks، شوفنا هذا
الأمر تقسيم الـ code إلى sub blocks، فالآن الـ
algorithm لما بدى تبدأ بدى تاخد كل sub block و
تشتغل عليه لوحده، في هذا sub block بدى تاخد الـ
three address instructions وتحوض وترجم وتطلع
لكل واحدة منهم تطلع اللي هو one or more one or
more ايش machine instructions مظبوط، فالأمر
هذا المثال اللي في الآخر هذا عندي أنا هذا الـ three
others code instructions هدولة بتخيلهم كانوا sub
block واحد، والـ algorithm بده تاخدهم واحد واحد و
تطلع لكل واحدة مجموعة اللي هو الـ machine
instructions اللي بترجمها تمام، يبقى احنا الآن الـ
algorithm ايش عمليًا بدها تسوي، الـ algorithm ايش
عمليًا بدها تسوي؟ نطلع على الـ steps بننظر على الـ
steps تبعت الـ code generation algorithm اللي هو
section 862 صح 862، كل الكلام اللي قبل 862 احنا
already حكينا فيه ما في أي داعي لمراجعته مرة ثانية،
862 اللي هي لب الـ algorithm بدنا ننظر إلى عمل الـ
algorithm على أساس إن في عندنا فرق شويّة بسيطة من
بين لو هي الـ instruction اللي الـ algorithm بترجمها
هي تحتوي على operation أو لا تحتوي يعني الـ
instructions اللي تحتوي على operation أنا أخدها
على أنها حالة machine instructions for operations
والـ instructions اللي ما فيش فيها operation يعني
اللي تحتوي على بس مجرد copy statement زي machine
instruction for copy statements، أصبح
السؤال الآن ايش الـ generation algorithm الـ code
generation algorithm بده تسوي إذا كان اللي أمامها
three address association تحتوي على operation و
ايش بده تسوي إذا لا تحتوي مجرد copy، الألغوريثم هي
هي، ولكن بيتصرف بخطوات في هذه الحالة وخطوات في
الحالة الثانية، ببساطة شديدة، في حالة لما يكون في
operation في الـ instruction، الـ operation هذه ممكن
تكون plus أو minus أو أي mathematical operation
لازم يكون في عنها function اسمها get register، get
register، هذه وظيفتها إن تعطيني registers اللي
تستخدمهم الـ algorithm في التعامل مع قيم الـ
variable، إذا دول X Y و Z دول الـ variables اللي في
الـ memory لازم ايش يتاخدوا على الـ registers لكن هل
ضروري لازم إن الـ algorithm تعمل لهم load من الـ
memory وتحطهم في الـ registers؟ ضروري المفروض، ولكن
إذا كان already تم تحميله في الـ instruction سابقة
على الـ registering ملزمش زي مثلًا.. اوديكوا على
المثال هذا، هاي هنا الـ operation is minus والـ
variables a و b احتجنا إنه راح الـ a على r1 و b على
r2 قبل ما نعمل عملية الـ subtraction صح؟ بينما هنا
محتجناش، هنا minus محتاج لاش نجيب الـ A والـ C جيبنا
بس الـ C لإن الـ C مش موجود، لإنما الـ A موجود في الـ
register روح واحد صح، يبقى الـ algorithm بدها بدها
برجع رجوع أنا ثاني على وين ما كنت، بدها بدها
تستعين بـ get register هذه عشان get register تقولها
لـ X استخدمي الـ register الفلاني، و لـ Y استخدمي الـ
register الفلاني، و لـ Z استخدمي الـ register الفلاني
الآن لو روحنا على هدولة التلت registers الـ
register تبع X اللي أعطتنيها أستخدمه لـ X والـ
register تبع Y والـ register تبع Z وجيت على الـ
register تبع Y ولا جيت already يحتول على قيمة Y
يبقى مش فيش داعي إن أنا اعمل load مظبوط؟ يعني أنا
هذه الـ algorithm في الآخر لتعمل add لتعمل add من rz
و ry تجمعهم وتحقق على rx، طيب هل rz اروح حمل الـ z
عليه إذا هو already موجود هناك؟ محتاج أحمل
العربية تطلب من get register تعطيها أسامي تلات رجستر
تستخدمها أعطتها تلات رجستر يجب إن أنا اتعامل معاهم
لأنهم Rx وRy وذاك الآن بدنا نفحص إذا Y already
موجود في الـ register اللي أعطتنا إياه لـ Y يبقى
ما فيش داعي اعمله وإلا if not if not بدي اعمل load
لقيمة Y على هذا الـ register بس ليش بيقول هنا Y'؟ Y'
يقصد فيها إن الـ Y نفسها الـ descriptor تبعها
بيقول
مثلًا أي واحد من الـ variables هذين بيقول الـ A مثلًا
أو الـ B الـ descriptor تبعها بيقول إن قيمتها موجودة
في B فقط، okay، هذه الـ A بيقول إن الـ descriptor
تبعها موجود في A وفي R واحد ممكن يبقى موجود الـ
value في أكثر من مكان يقصد إنه يجيبه من أي مكان هو
موجود فيه أحطه تمام، واضح؟ يعني هنا y prime يقصد
فيها one
of the memory locations one of the memory locations
إيه قيمة Y موجودة فيها؟ غالبًا هي موجودة في Y بس
ممكن تبقى موجودة أيضًا في مكان آخر، المهم بتجيبها من
أي مكان من الأماكن هذه اللي هي موجودة فيها وبنعمل
لولة على RY هذا فقط إذا كان نتيجة RY لا يحتوي أصلا
على Y ونفس الأمر بالنسبة لـ Z بعد
هيك.. بعد ما نتأكد من الأمر هذا إذا لازم load لـ Y
لازم load لـ Z بعدين نعمل ال.. يبقى الأمر تبع الـ
add، الـ instruction add هذه حتمًا هذه لازم تنعمل هذه
100% لازم تنعمل مظبوط؟ مظبوط؟ RX RY RZ إنما
السؤال هل سوف يسبقها load ولا لأ هذا بيعتمد على
ماذا عن الـ Registers التي أعطتنا إياها جيتريتش؟ وهل
يحتوي على الـ Values أو لا؟ هذا كل ما أقوله
بالنسبة للـ operation لما يكون الـ instruction عبارة عن
operation بالضبط يبقى احنا عمليًا رحلنا معظم
التعقيدات تبع الـ algorithm على جيتريتش، جيتريتش هي
الآن مسئولة عن إنها تختار الـ registers صح ولا لأ؟
إذا ذكر إنه مسئولية الـ algorithm لما احنا كنا
حكينا قبل هيكة مسئولية الـ algorithm إن ت decide هل
بنعمل load ولا لأ هذا أول مسئولية صح ولا لأ؟
المسئولية الثانية generator operation هي هتعمل هذا
وهتعمل هذا الأولى إنها تقرر هل تعمل load ولا لأ؟
هتقرر بناء على إنها تبحث عن الـ register اللي أتى
من get rich، والمسئولية الثالثة اللي هي إنه إذا
محتاجين نعمل store، بنعمل store، هذه لسه قدام كمان
شوية بتبين معانا، بس تلت مسئوليتها دولة هي الآن
منطلقة بالاثنين هذولة لكن هذي decide إنه نعمل load
ولا لأ، بيعتمد على مين؟ بيعتمد على الـ registers
اللي هتيجينا منهم هتيجينا من get rich صح، get rich الآن عليها
مسئولية استخدام الـ registers بحكمة بمعنى اللي هو
الـ register allocation يبقى ما تعطينيش register
أستخدمه ويبقى فيه قيمة والقيمة هذه ضرورية بقرار
أهمية الـ register من عدمه أو كل إلى أو روح إلى
get rich هنا
الهيكل الأساسي تبع الـ algorithm بيقرر إذا كان يعمل
load ولا لا، بيقرر بيعمل الـ algorithm الـ operation
إذا هي زائد وروح بيجيب add إذا هي ناقص بيجيب
subtract وفي الآخر بيقرر إذا كان يعمل store ولا لا
إدارة استخدام الـ registers بشكل حكيم ومحكم هذا عند
الـ get rich، طيب
يبقى احنا دلوقت شوفنا فيما يتعلق بإذا كانت الـ
instruction تحتوي على الـ operation، إذا لا تحتوي
على الـ operation وهذا الأمر أيضًا شوفناه قبل ذلك في
المثال إن عند مثلًا X بيساوي و Y copy statement X
بيساوى و Y ايش عملت ال.. طلع على المثال اللي
كنا شوفناه اللي هو هياده وقال دي A بيساوي دي؟ ايش
اللي عملته؟ عملت إنه load الـ D على R2 يبقى هنا
السؤال هل بحتاج أعمل load ولا لأ؟ يعتمد برضه على
نفس القضية لما احنا بنستدعي get register لهذا ال
instruction هتعطينا register واحد، مش هتعطيني ال
register ل دي، يختلف عن ال register ليه هتعطيني ال
register واحد أستخدمه للاتنين لأن هذا assignment
statement ماشي الحال لأن ال register هي ده قططني
R2 بدي أسأل السؤال هل أنا محتاج أجيب D من ال
memory و أخزنها في R2 برضه بيرجع إلى نفس الـ .. ال
.. الكلام السابق، هل ال D already موجود في R2، إذا
موجود في R2 يبقى مش load هنا لأن ال D هي R2 لا
يحتوي على ال D، يحتوي على حاجة تانية اللي هي T
فاحنا روحنا حملنا أنه لا يحتوي على ال D، طب إيش ال
T هذه؟ ال T هذه أنا ماليش دخل، ال get register هي
أعطتني R2، إيش في جوات ال R2 هذا؟ هو فاضي في حاجة
جواته، أنا ماليش دخل، أنا بتكتب فوقه هي المسؤولة عن
إنه إذا في حاجة تكون، هذا الحاجة مالهاش أهمية إيه
إذا بتبقى استخدامها قدامك؟ هي اللي بتحدد إذا كانت
ال T هادئلة أهمية ولا مالهاش، هل بقدر أكتر فيها ولا
لا، أنا ماليش دخل، هي أعطتنيها، أنا بتستخدم أعطتني R2
بتستخدم R2 بغض النظر إيش اللي فيه، وهذا الكلام احنا
هنحكي عنه الآن كما شوية أنه التقرير يعني كيف يتم
اختيار ال registers، واضح؟
افترض أنه أعطتني R2، ولما راحت على غطولة وجدت أنه
دي قاعدة جوه يبقى مش محتاج أعمل load، يبقى هذا ال
statement كلها مش هتلزم، يبقى هذا ال a نغساو دي، لا
يستدعي أي ترجمة إلى machine instruction مش هيلزم
ليه load machine instruction بس هيك خلاص ما فيش إش
بدين أعمل لأ، بدين أعمل، احنا هنا لازم نغير ال
descriptors، حطينا إيه، قلنا إن إيه أنت الآن صرت في
R2 وإن ال D صارت في R2، صح أو لأ؟ صح، مش هعمل
instruction لكن لازم أروح أحط، أعمل setting لل
descriptors، ال setting لل descriptors هي في عملية
اللي بترجم عملية الاصطناع، الآن أصبحت ال code
generation algorithm في هذه الحالتين اللي هم أنا
برجع و ارجع في هذه الحالة لما تكون ال instruction
فيها operation و حالة لما تكون ال instruction
مافيش أي أغلب عن copy statement، if y is not
already in ال register اللي أخذته من get register، إذا
هي مش موجودة ال y، بروح بعمل load، then generate the
machine instruction load لوضع I على RY، إذا كنا
بالفعل في Y، فلنفعل أي شيء، فلنفعل أي شيء إلا أنه
يجب أن نقوم بالتحسين في ال register descriptors و
ال address descriptors، صح؟ حسنًا، الآن هؤلاء اللي
هو القليتين تبعات ال generation algorithm، في قضية
تالتة وهي أنه ending ال basic block ending، شو تعمل
ال algorithm في نهاية ال basic block، شو هو ال
basic block؟ شو هو ال basic block؟ لما احنا جسمنا
ال instruction set، ال instruction كلها ال
instruction sequence، إيه ال blocks هدول هم ال basic
blocks، صح؟ هذا basic blocks، كل واحد منهم basic ال
algorithm عمليا ال generation algorithm بتاخد
basic block اه
of three others code و بتعطي إيش machine
instructions
بتاخد basic block بتفر على كل ال instructions اللي
فيه، بترجمهم واحدة بعد واحدة، قد يكون فيه خمسة ستة
سبعة، قد يكون في واحدة فقط، قد يكون في اتنين تلاتة
صح، المهم أنا لازم أجزلها ال instructions ال
blocks، ليش؟ علشان حكاية ال memory أو ال register
allocation و ال variable، مين منهم اللي هحتاجه و
اللي .. لو أنا بتطلع عليهم كلهم القضية بتتشعب لكن
لما أنا بتطلع على أجزاء، بصيب أقدر أعمل management
لكل جزء لوحده، طيب يبقى احنا الآن، طيب إيش اللي بدي
يصير بالنسبة لـ .. اللي هو النقطة هذه؟ اللي هي
ending ال basic block، احنا طلعنا على المثال هذا
وشوفنا إن المثال هذا عمليا الترجمة انتهت إلى هنا
هي آخر instruction، صح؟ أيوة، لما خلصنا، مخلصناش، لما
خلصنا ال instruction مخلصناش الشغل، صار لازم أعمل
ترتيب لـ .. أو cleanup أو ending، حيث إن أي شيء
variable القيمة تبعته موجودة فقط في ال register
هذا ال register ما عوش أي حاجة تانية، هذا تمام اللي
موجود في ال register و راح أستخدمه لاحقا فهذا يجب
أن أرحله على ال memory، هنا إيش المراحل، مراحل A و D
يعني هذا و هذا هي A و D، بس ما رحل V، V موجودة فقط في
R ثلاثة، بس قال لأ، ما بديش أرحل على ال memory، ليش لأ؟
أنا temporary، لو أنت لاحظت على ال instructions أنا
عندي هنا T، وظيفتها بس تتواخد ناتج الطرح، و ال U
ناتج الطرح هذا، و ال V ناتج الجمع هذا، و في الآخر
القيمة
اه و دي .. و دي بتتحط في A، يعني دي بتاخد قيمة
جديدة، فقبل بأخر هياخد قيمة جديدة، اتخذت قيمة السوق
تبعته في A، بعدين أخدت قيمة جديدة تبعتها من مين؟
من V زائد U، فبالتالي ال V زائد U هدول اللي وصفوا
وظيفتهم كانت إنهم temporary، هم و ال T، okay، فال U
و ال T و ال V هدول هي temporaries، فال V مع أنه
قيمتها موجودة في R3 فقط، إلا إنه محتاج ناشن لأنها
temporary لأنها محتاجة لإن أعمل store لمن؟ لـ A
والـ D هذا القمر كيف ال algorithm بدها تستشعره؟ في
عندنا جزئية
ال policy هذه إنه إذا if the variable is a
temporary used فقط بداخل ال block، ما فيش أي مشكلة
إنه لما ننتهي ال block، we can forget about the
value of ال temporary، صح؟ we can forget about ال
value of ال temporary، ولكن إذا ال variable is Live
on Exit، Live on Exit، ماهي معناته؟ مع نهاية ال block
نحن
نعلم أنه سيكون له استخدام لاحق، يبقى ماقدرش أتركه
في ال register و ييجي بعد ذلك ال block اللي جاي
يكتب فوقه و يضيئ قيمته، رحّل قيمته من ال register
إلى ال memory، however if life on exit or if we don't
know، أو إذا ما كناش عارفين إذا هو هستخدم أو لا
احتياطا بنروحش نسوي، then we need to assume إن هو
ربما يكون احتياطا، إذا ما احنا مانعرفش، لأن أنا نفسي
أقول إنه ربما يكون هستخدم later، وفي هذه الحالة كل
variable، كل ال memory variable ال location تبعه ال
location descriptor تبعه بيقول إنه موجود بس في ال
register، إنه
مش موجود في ال memory، فبدنا نحطه في ال memory، صح؟
هنعمل store لهذا ال variable على ال memory
location، كيف هذا الكلام بنعرفه؟ لازم يكون في عندي
أنا معلومات عن اللي هو استخدام ال registers، استخدام
ال variables، ففي نقطة احنا كنا مررنا عنها، أفلتناها،
أجلناها بدنا نرجعلها الآن، في نقطة ورا أنا قاعد بقى
أرجع رجوع على لما كنا بنحكي عن ال blocks، اه في أدي
حاجة اسمها اللي هو next use information، next use
information يقصد بيها إنه لكل variable من ال
variable سبب ال instructions، عندي مثلا X يساوي Y
زائد Z، هذي three address code instruction بتحتوي
على variables، ال variables هذولة بدنا نعرف قدام
هذه ال instruction، وقم مثلا واحد، هل قدام في اتنين
أو في تلاتة أو في أربعة، هنستخدم ال X أو ال Y أو ال
Z، إذا راح نستخدمهم يبقى بنا ن keep بنا نخليهم، إذا
مش راح نستخدمهم يبقى بنقدر نكتب فوقهم أو ننسى أمرهم
لما نخرج من ال blog، فال next use information هذه
فيه قايمة لتسجيلها
تسجيل ال next use، إيش هي ال next use؟ متى هيكون
الاستخدام اللاحق؟ تمام، ديجي نطلع على القايمة هذه
أنا عندي instructions، وال instructions هدولة خليني
أكتف، خليني أكتب نفس المثال اللي هو مستخدم هنا في
هاي
T بساوي A ناقص B، U بساوي A ناقص C، V بساوي T زائد U
A بيساوي D، و D بيساوي V زائدي، تمام، ال instructions
هدول بيبدأ أرقمهم، بيبدأ أرقمهم، هي واحد، اتنين، تلاتة
اربعة، خمسة، هذا التقييم بيبدأ أسميه I، الآن لكل واحد
من هذه ال instructions بدي أولًا برضه كمان ال
variables كلهم من ال A لل B لل C لل D بعدين ال T و
ال U و ال V هدول ال variables، في بعض منهم احنا
اتفقنا عليه إنهم temporary، مين هما ال
T و ال U و ال V هدوله temporary، ال A و ال V و ال C
و ال D هدوله مش temporary، ماشي، لكل واحد بدنا نسجل
هل هو live ولا لأ وبدنا نسجل الـ next use تبعه هذا
الكلام يجب أن نعمل
عملية
تسجيل الـ next use information ايش بنفعله هدول
الـ variables موجودين في الـ symbol table الـ A
موجودة كـ identifier في الـ symbol table فالبيانات
هذه ممكن تبقى انخزنها في الـ symbol table ليش ضروري
اعمل data structure خاصة بسجل احكيها تلقاه ان هو
live ولا لأ احكيها تلقاه ايش الـ next use تمام قدام
هناك ايش بيسوي بيقوللي انه بكل
instruction
بدأ أجي من الآخر بدا أبدأ من الآخر في بي بي اللي
هي الـ block ال هيكة كله هو الـ block بدأ
أبدأ من الآخر at each statement I نسوي الـ table أه
بس قبل أنسيت أقولك أنه we assume that الـ symbol
table هذه البيانات الموجودة في الـ symbol table
initially shows all non-temporary مين الـ non
-temporary؟ هدوله الـ non-temporary وهدوله
إيه إيش؟ تفرجنا علي إنهم temporary كل الـ non
-temporary live on exit live .. live .. live ..
live ماشي؟ لأن بيقولي خد هذا .. هذا .. هذا
البيانات مسجلة وهدوله مش live هدوله مش live الـ
next use مش عارفين لسه البيانات هذه مسجلة في الـ
symbol table انا الآن بتقول للـ algorithm هذه انه
امشي على الـ instruction سبعات الـ block من الاخر من
خمسة يعني I بالساوية خمسة بعدين I بالساوية أربعة
بعدين I بالساوية تلاتة I اتنين I واحد صح؟ ايش أسوي
اطلع على الـ instruction الـ D هذه الـ D هذه اللي على
شمال الـ assignment هو الـ X و اللي على جميعها هم الـ
Y و الـ Z اول اشي خد البيانات اللي تخص هلولا خدها
من هنا يعني كيف هذا الـ instruction ايش فيها
variables الـ D و الـ U و الـ V و الـ U ايش وضع الـ D
الحالي وضع الـ D انه liveو وضع الـ V الحالي انه ليس
live و وضعه ان اليوم كذلك ليس live تمام احنا نسخنا
هذا يقولي اول حاجة attach to الـ statement جيب الـ
information اللي currently موجودة في الـ symbol
table جبناها regarding الـ تلاتة variables صح
جبناها بعد ذلك يقول لي ايش سوي في الـ symbol table
اللي الآن غير خلّي الـ X not live الـ X مين هدي الـ X
هنا الـ D not live okay
بينما اللي على يمين اليساوي خلّيهم live مين هم الـ
V و الـ U صح خلّيهم live و
سجل انهم live to خمسة next use كامسة؟ مشي الـ
instruction حطم خمسة؟ تمام؟ ارجع
على اللي جابها اللي جابها دي a و d انسخ ما يتعلق
بال a و ال d ايش
الرقم a و d ال a إيش مضحكة live و ال d إيش مضحكة
not live الان بقوللي غير خلّي ال a اللي هي قبل
يساوي not live و ال d live ال D live لعند I احنا
في Iاش اربعة اه
sorry okay صح
طيب، الآن ممكن تقولي شو معنى الكلام هذا؟ أنا الآن
ال generation algorithm ال code generation
algorithm جرت جرت ووصلت لهنا لما نتطلع على هذا إيش
معناته؟ معناته إن ال a live و أنا هنا ال a live
يعني لو ال algorithm بدت تنهي الترجمة هنا ده تعتبر
إن ال a live live يعني أصحى كتجربة على الـ variable
تبعها إذا القيمة تبعتها إذا القيمة تبعتها موجودة
في الـ register لازم الـ register .. لازم قيمة اللي
تطرحها المجلد live يعني keep إيش يعني keep؟ يعني
حافظ عليها حافظ عليها مضايحاش إيش يعني مضايحاش؟
يعني إذا ال address descriptor تبع إيه بيقول إنها
موجودة في register كذا و فقط في هذا ال register
يبقى لازم أعمل store عشان أحافظ عليها صح ولا لأ؟
أما إذا قال لي not live يبقى خلاص هذا الـ variable
dead not live يعني dead يعني ليش dead يعني القيمة
تبعته اللي dead يعني القيمة تبعته مش هتلزم مش
هتلزم يبقى ما بيلزم أعمل store أه إذا انتهى
الترجمة عند هذا الـ block إذا انتهى الـ block عند
هذا الـ statement صح أو لا؟ okay الـ D كذلك لو افترض
أن الـ algorithm ماشي و الآن خلصنا هنا إيش بتقول؟
عشان كل الدوش يعني كلها عشان نعطيك دي قيمة نروح
تكون القيمة دي قاعدة فى الـ register و بس فى الـ
register و نطلع و نسيبها فى الـ register بدون ما
نخزنها على الـ memory مش منطق صح؟ okay بينما الـ V و
الـ X الـ V و الـ U not live شاهد كيف؟ not live يبقى
مش مهمين لو موجودين فقط في الـ registers مش مهم
يخلّيهم في الـ registers و يخلّي الـ block اللي بعد
يجي يكتب فوقهم مش قضية نرجع نكمل للكل الان انا في
I بساوي تلاتة تلاتة ايش أسوي؟ بدي أنجل القيم الـ V
و الـ T و الـ U الـ V ليش وضحها؟ Live Live لعند خمسة
صح؟ هنا Live لعند خمسة يعني هيستخدم القيمة تبعتها
و الـ next استخدام هيكون الـ instruction رقم خمسة
Live لعند خمسة يعني خلي دي حافظ عليها ماضيحاش لأنه
راح تستخدم في خمسة صح ولا لأ؟ أنا و لا أعرف أنا الـ
code generation و لا أعرف وصلت لهنابقول لي هي في V
هتاخد قيمة، القيمة هذه أفضل لها، ماضيحاش، ليش؟
لأنه في خمسة لها استخدام، صح ولا؟ تمام، ونفس الأشي
T؟ لأ، T لأ، T القيمة تبعتها، القيمة تبعت T، هتدخل
في عملية الجمع، و بعد هيك مش هتستخدم بعد هيك، شايف
كده؟ هذه الـ T طالعش مولي X not live يعني أنا و أنا
هنا و أنا هنا قيمة ال T dead انتهينا منها انتهينا
قضينا حاجتنا من الـ variable هذه ال T صح استخدمنا
قيمته فعملتين جامعة و بعدها لم يكن حد رجع نستخدمها
تاني طب بالنسبالي الـ U ايش الـ U هنا live لحد خمسة
الان انا نجلت الكلام هنا نجلته بس الان بدى اغيره
بقول لي غيره مين اللي انا اغيره الـ V الان بدى اصير
ايش؟ not live طبعا not live بتبتدى مساحة ان الـ T و
الـ U بيبدوا يصيروا live الـ T و الـ U بيبدوا يصيروا
live و لها تلاتة حلو؟ okay ارجعتي الآن ل I
بالساوية اتنين اول حاجة بتدهسك
أنسخ الـ U بيانات الـ U و بيانات الـ A و بيانات الـ C
و يعني الـ A ليس Live الـ U Live لعند تلاتة Live
لعند تلاتة و الـ C Live تمام؟
مظبوط
الـ C Live بس الـ life اللي عنده اين؟ الـ life من
الأصل الـ life من الأصل لما نجينا عملنا الـ
initialization تمام؟ كل اللي عملناه اللي هو الـ
initialization المفروض .. اللي هم هدولة المفروض
قاعد أقول الـ next use فبحهم B plus ايش ع الـ B
plus؟ يعني الـ block القادر بالظبط فانا الآن الـ C
بدي احط هيك انها B plus أنا الـ c صح هنا مش هستخدمها
صح هنا مش هستخدمها لإنها مش temporary من الـ
temporaries ال t و ال u و ال v لإن ال c مش
temporary فانا بتوقع تستخدم لربما مش هقولها لربما
تستخدم يعني اللي أعلم أنه راح يستخدم بحافظ عليه
اللي راح يستخدم لاحقا بحافظ عليه بعمل live عشان to
keep it اللي لا أعلم برضه بحافظ عليه لربما انه قد
يستخدم وين في الـ block القادم بي بلس هاد من عندي
انا استخدمت رمز ل next block هدول هم فيينات الـ
block الحالي هدول just الـ instructions لبعد الـ
block الحالي طيب احنا ايش قلنا اول شي بينتسخ الـ
information هذه بتنتسخ على الـ instruction بعد هيك
باجي بغير الـ U باخديها مش live
بشكوب التلاتة ال a و ال c بخليهم live بس لعند مين
اتنين صح اللي
هي رقم الـ instruction اللي أنا فيها تمام نرجع نوصل
للمدام اه لان بسوي واحد اللي هي اخد instruction
بنرحل الـ information هذه و خاصة بي الـ T و الـ A و
الـ B الـ T ليش مضحكة Live لعند تلاتة والـ A Live
لعند اتنين والـ B Live لعند الـ block القادم الأن
نغيّر هذا الكلام الـ
T بتصبح Not Live الـ
A و الـ B بصبح live لعند واحد بيبقى من الـ
instruction الـ B
هي الاستخدام
الوحيد لها فهي live محتاجين قيمتها هنا و هذا
اخر استخدام لها لكن و مع ذلك لا أريد أن أحضرها أريد
أن أجعلها live لماذا؟ لأنها ليست موقعية احتمال أن
تستخدمها لاحقا هذا الان الـ information اللي هنا و
اللي هنا تلزمني هذا بتلزمني في إيه؟ هذا بتلزمني
أثناء الشغل أثناء ال code generation algorithm
التي تعمل وتتطلع عليك ال variables هذولة تعرف أن
ال Tهل بعد هذه ال instruction راح يستخدم و لا لأ؟
أه راح يستخدم وين؟ في instruction رقم تلاتة ال A
أه وين؟ في instruction رقم اتنين مظبوط؟ على طول هي
تجاه البعد ال B أه وين؟ لربما في ال block القادم
صح ولا لأ؟ هذا الكلام في إيش بفيدني؟ بفيدني في ال
register allocation صح؟ يوم أنا بدي استخدم
registers لهذه ال variables بحرص أنه ال registers
هذه ماخدش register تبع متغير متغير هي ده موجود في
ال register و مالوش مكان آخر تاني همروحش اخده
همروحش اخده و اكتب فوقه فالآن هذه ال information
بناء عليها الألغوريثم ال code generation algorithm
يعني هذه الآن عبارة عن algorithm algorithm بس لإيش
لتسجيل بيانات next use information اسمها next use
information البيانات هذه next use information
بتستند إليها مين بتستند إليها مين اللي هو ال code
generation algorithm
code generation algorithm في القرارات الخاصة بها
طيب
وبالتحديد في ال end of block end ده basic block
عشان نشوف هل ال مثلا خلصنا ال block هذا الآن أنا
خلصت تعالي على تعالي على هذا هي خلصنا ال block هي
نايت ال block الآن نعمل عند ال exit نعمل اسطورة
لمين؟ لمين؟ أولا ال temporary variables كلهم معنى
مش معنى ابنهم بتطلع بس على المش temporal مين المش
temporal؟ هدولة A و B و C طيب ال A و ال B و ال C و ال
D هدولة مين منهم live
on exit عند
هذه اللحظة ال D live صح كلهم live كلهم live مظبوط
كلهم live هدولة حتى لو مش .. حتى لو live مش
محتاجهم لأنه temporary صح هدولة الآن مين منهم
هدولة ال .. ال .. ال live live on exit مين منهم
اللي live on exit القيمة تبعته موجودة في ال
register و في ال register فقط طلع هذا ال a موجودة
في مين؟ هذه الخطوة في النهاية عندما ننتهي هذه هي ال
Descriptors لنا ال A وين موجودة؟ في R2 صح؟
Value
تبعها at end of block قيمة هذا وين؟ R2 قيمة ال B
في نهاية ال block وين موجودة؟ طلع على ال descriptor
تبع ال B لأ هي في B في B يعني قاعدة في ال memory
تبعها ال C في ال C ال D في R1 و R1 فقط يعني لو
مثلا ال A1 و D مافيش أي مشكلة لكن لأنها في R1 فقط
و لأنها live on exit يبقي الله إذا ماعملها Stuart
ليش عملت اسطورة لبس الاتنين هدولة؟ لأن هم اللي
بنطبق عليهم وشغلهم الاتنين أولا هم مش temporary
تمام؟ الاتنين live on exit والاتنين موجودين فقط في
ال registers مش قاعدين في ال memory تبعتهم فلازم
احطهم في ال memory اعمل اسطورة هي كقالية عمل ال
algorithm يفترض أصبح مكتملة يعني بمعنى آخر أن ال
algorithm بتيجي
على ال
instructions one instruction و بتطلع على الـ
variables و تطلب من الـ function هذه get register
تعطيها registers لل variables اللي موجودين في ال
instruction عندي ثلاثة، عندي اتنين، عندي واحد
تخططيني الآن و بتقرر هل بلزم اعمل load ل Y ولا Z
إذا بلزم بتعمل، بلزمش بتعملش ثم بعد هيك بتروح
بترجم ال operation إذا هي plus بتعمل add إذا هي
minus بتعمل subtract هذه الحالة في استثناء لها وهي
أن لما تكون ال operation لما تكون ال instruction
مش operation عبارة عن copy اذا copy statement x
سوى y ال get reg تعطيني register واحد لل two
variables لل x و لل y معا تعطيني لهم register واحد
الآن هذا ال register أنا بده اجيب قيمة ال y و
احطها في x يعني لازم احطها في ال register في الأول
و لا أسلمها ال x الآن برضه السؤال هل بلزم أجيبها و
احطها في ال register لربما تكون هي موجودة في نفس
ال register هو هو اللي أعطانيها get rich إذا هذا
الحال بلزمش طيب ماجبت .. مالزمش load هل بلزم أترجم
ال assignment لأ بلزمش برضه أترجم ال assignment بس
مجرد بغير ال descriptors صح ولا لا بقول إن ال X
صارت الآن في R كذا و ال Y في R كذا هو نفسه ال R
كيف؟ بأعطيهم نفس ال register ال gate register هذي
قططني R R Y تمام؟ R Y يحتوى على Y لأنه لم يعمل
load وفي نفس الوقت لم يعمل أي حاجة ثانية بس مجرد
ذلك بيجب أقول أن ال X الآن موجودة في R Y هذا و ال
Y كذلك موجودة في R Y اللي هو هذا الكلام اللي شفناه
احنا عمليا تم هنا صح؟ بس هنا اياتهلأن دي مش موجودة
في R2 عمللها load عمللها load عمللها
load عمللها load عمللها load عمللها load عمللها
load عمللها load عمللها load عمللها load عمل
الآن instruction هذي ال subtraction و ال subtraction
هذي ليش هنا لازمني two loads و هنا لازمني واحدة و
هنا كذلك لازمني ليش مالزمنيش loads بالمرة و هنا
ليش لازمني load واحدة و هنا ليش مالزمنيش loads و
بس ال operation و هنا في ال exit ليش لازمني هدول
اتنين
الـ GetRegisterFunction هذه سكشن تمانية ستة تلاتة
بيوضح آلية عمل الـ GetRegisterFunction الـ
GetRegisterFunction هذه بس بدنا نذكر فكرتها
باختصار شديد على السريع
شو قولنا هي الغرب منها؟ إيش الغرض منها اللي جيت ال
register يعني؟ بتحجز عندك ال variable بتحجز القيمة
بتحجز ال register بتحجزلي ال registers أو بتقول لي
إيش استخدم ال registers لل instruction هذه لدي
instruction و ال instruction فيها captured
variables واحد اتنين أو تلاتة بدي لكل variable
هدولة memory ادرس بدي اجيب القيم تبعد من ال
registers بدي أقول لمين ال registers اللي
استخدمها أه هي عند ال machine فيها عدد محدود من ال
registers ال get register هي اللي بتعطينا ال
allocation صح فاخدها
عندك على سبيل المثال اللي هو ال instruction زي هذه
X بساوة Y زائد 6
و Y و Z هتجب ان تضبط ال register جيت ال register
هذي أنا بعطيها ال instruction و هي بتروح و بتبص
على ال instruction بتشوف إيش فيها ال variables و
بتقول لي لكل variable إيش استخدم يعني هتقول لي ل X
استخدم ال register كده و ل Y استخدم ال register
كده و ل Z استخدم ال register كده فهي هتستخدم
register ل Y و register ل Z فما
يتعلق بهذا و هذا نفس الشيء سواء نحن نحكي عن Y ولا
Z اللي يخص ال Y يخص ال Z أيضا فتستخدم تطلع على ال
variable نفسه هو نفسه Y إذا كنت تبحث عن الـ
Descriptor تبعه إذا كان بالفعل قاعد في الـ
Register خلاص إذا كان الـ Y موجود في الـ Register
فبناخد هذا الـ Register لأن نروح على الـ
Descriptor تبع الـ Y بشوف
هل هو قاعد في الـ Register قد يكون قاعد في الـ
Register و أيضا قاعد في الـ Y و أيضا قاعد في الـ
Other المهم هل في Register كواحد من الـ Locations
خلاص بناخد هذا ال register على أن هو ال register
اللي بيستخدم ال Y تمام؟ اختار مستخدم ال register
اللي بيحتوي على Y كريه RY و لا أشهر مachine في هذا
الحالة بنوفر على حالنا issuing a load يوم ما أنا
اعطي هذا لل algorithm ال algorithm بيحطه و بيحطه
فحص هتلاقي ال Y هو نفسه جاهد في ال register يبقى
مش هتعمل load فا إذا لم يكن موجود في عدة موقعات لكن
لم يكن موجود في أي موقع يمكننا أن نختار واحد من ما
يكون متوفر أي موقع متوفر إذا لم يكن موجود في أي
موقع لكن هناك موقع متوفر ممتاز متوفر يعني ممتاز
فبناخد أي واحد من الممتاز لم يكن موجود في موقع
يبقى لازم نعمله load نعمله load في مين؟ نريد أن
نشوف واحد فاضي ونضعه فيه، الآن الوضع الصعب يحدث
عندما Y ليس في مكان فاضي وما في مكان فاضي نحتاج أن
نختار واحدًا من المستخدمين اللي نستطيع استخدامه و
نحتاج أن نجعله بأمان لاستخدامه يعني بدنا نستخدم
واحد مستخدم ولكن بنستخدمه بحذر بحيث أنه ما نؤثرش
على أي information، أبسط حالة إنه إذا والله في واحد
.. يعني كلهم مستخدمين لكن واحدًا من هؤلاء ال
registers المستخدمين مستخدم لـ variable، الـ variable
هذا dead يعني ليس live يعني لن نحتاجه، وهذه تبقى
حالة ممتازة، مستمرة هي مُرَنٍّ، مخرج مريح جدا من القضية
من الوضع هذا، يعني هو صح مشغول لكن مشغول لـ variable
الـ variable هذا مش محتاجينه، فبالتالي Okay if the
address disk ..
آه تمام تمام بس في الآخر هم الثلاث حالات دولة
الحالة هذه هي اللي بتتشعب، تتفرّع لنا، نتفرّج فيها نتفرج
فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها
نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج
فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها
نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج
فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها
نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج
نتفرّج فيها نتفرّج فيها نتفرّج فيها نتفرّج فيها
على الـ registers كلها R1, R2, R3 وجدت كلهم مليانين
كلهم مليانين ماشي، الآن بنطلع
عليهم ونشوف أي واحد منهم اللي ممكن آخده، فكلهم الآن
candidate مرشحين، إذا الـ register
يحتوي على variable و
الـ variable هذا، روحت على الـ descriptor تبعه ووجدت
أنه موجود في أكثر من مكان، موجود في .. يعني موجود
في R3 وأيضًا .. مش هو موجود في R3، يبقى أكيد في ال
descriptor تبعه وقاعد هنا في R ثلاثة بتظهر، بس إذا
لجيت أيضًا في حاجة ثانية يبقى هذا الفرق الموجود في
مكانين، يبقى أنا بقدر آخذ واحدًا منهم اللي هو هذا
فإذا الـ address descriptor for V says that V is
somewhere besides إلى جانب R، يعني إضافة إلى R then
we are okay، بنقدر نأخذ الـ register هذا وخلاص، بس
بغيّر في الـ descriptor تبع V، بقول أنه خلاص أنت الآن
موجود بس في المكان الثاني اللي هو عادة الـ memory
location تبعيك، وآخذ هذا وأستخدمه لمين؟ الـ
variable اللي هي if V is X، اللي هو the value is
being computed by the instruction I، إذا
أنا بنتي ريجستر I، ولو أنا دولت ووجدت كل الـ registers
مشغولين، لكن وجدت واحدًا منهم
خلاص يبقى مقدر أستخدمه، يبقى مقدر أستخدم الـ VSX
اللي هو الـ value that is being computed by the
instruction I and X is not also one of the other
operators of the instruction، ممكن تكون X موجودة جوة
في الـ instruction يعني آه مثلًا X بالساوي Y زائد X
آه في هذه الحالة لأ مقدرش، لأن لسه كيف اروح اكتف وأجهّز
الـ V is not used later، زي الحالة اللي قلتها، إذا V
.. إذا الـ value هي ده مش موجود يعني .. يعني موجود
هنا مثلًا R3، لحالة لا هو X ولا هو موجود في أكثر من
مكان، موجود بس في R3، ولكنه is not used later is
dead، خلاص، then we are okay، كيف أعرف إنه dead ولا
لأ؟ من الـ Descriptor، من الـ Next Use Information،
إذا
لم نحن بخير بأي واحدة من هذه الثلاث، إذا ولا واحد
من هذه الثلاث تبقى قاطع، فأنا بدي أعمل Shuffling،
Shuffling يعني، بدي أشيل واحد، يعني V جاءت في R
ثلاثة وR ثلاثة لا هي .. مش موجود غيرها مالوش غيرها
وما هيش X، ما هيش
.. إيش قلنا هنا؟ الـ V هذه ما هيش X بالظبط، هذا V مش
X وزي بعينه كمان أن V راح يستخدم، راح يستخدم لاحقًا
ما أقدرش أتخلص منه، يبقى بدي أروح أعمل استبدال لأي
واحد من الـ registers وآخده وأرجعه على الـ memory
آخذ .. أي واحد .. مش أي واحد .. لازم هنا .. هذا
عاملش هنخش في بفاصيلة فيها اللي اسمها زي ما تقول
أنه عملية voting أو عملية تقييم، عملية التقييم هذه
اللي هي الـ spill، تمام؟ بقيم الـ registers كلها على
أساسها، واللي بآخذ تقييمه أعلى هو اللي بستبدله، زي نفس
النظام الحياة في الـ slide اللي بعده، مثلًا أنا مش
عاوز أدخل فيها الـ .. القضية ده أنه أنا عندي أربع
حالات، أو هن ثلاث حالات بالأساس، ثلاث حالات، إذا .. إذا
.. إذا فشلوا الاحتمالات هذه، إذا لما .. لما درايا
قع بيظل الـ .. بيظل الخيار الوحيد أمامنا هو الـ
Spill؟ الـ Spill بمعنى أن أنا بدي أكلمه بالظبط
بالظبط
هذه هي الـ conditions تبعتها، نقيم كل واحد من الـ
registers على أساس المعايير هذه، واللي تبقى الـ Spill
تبعته أعلى هو اللي أنا بآخذه وبعمله shift
اللي أقل الـ score هو اللي بعمله استبدال، يعني أقل
الأولوية، آه أقل الأولوية بالظبط، خلاص
فالآن
هيك صار أنه أنا في عندي بالأساس الـ algorithm ال
algorithm بدأ
بتستعين بالـ get ridge عشان تعطيك الـ register
فإحنا لما بدنا نرجع على الـ slide اللي بتوضح ال
code
generation algorithm أمامها ثلاث عمليات أساسية
whether loads are necessary ولا لأ قبل هذا الكلام
to select أو allocate register
for variables select
or allocate register for variables، أيوة هذا أوكل
الـ get rich، بعد ذلك الـ algorithm يجب أن يقرر إذا
كنت تعمل load أو لا load، ثانيًا تعمل الـ operation
المقابلة للـ operation، تعمل الـ instruction المقابلة لل
operation زي plus ولا minus، ثالثًا تنظف أو تتحقق من
أنه يلزم store أو لا، هذه أصبح ببساطة يوم ما إحنا
بدنا نأخذ أي مثال زي هذا المثال و
بدنا نحله أو نترجمه، بدك تاخده
على هذا تعمل أربع tasks عند كل instruction
بتكرر الثلاث tasks الأولانية، وفي الآخر بتعمل
الـ task الأخيرة اللي هي تبع الـ on exit، أي نعم، فإيش
تركت لكل instruction؟ أولًا جت reg عشان تعطيك
registers، تفحص الـ registers هدول بينزل نعمل load
ولا لأ ثم بعمل الـ instruction، هذا كلام بتكرر في
كلمة، عشان يتم هذا القمر بلزمنا descriptors وبلزمنا
البيانات الـ on exit هذه أو الـ next use information
تمام، فإحنا الآن يعني القمر هذا هو خلاصة الـ code
generation، بضل بعد ذلك أن هذا الـ code اللي طلع
معايا
بنعمل optimization فبينعمل machine dependent
optimization لأن هذا الآن machine code ف
optimization حسب الـ machine وحسب الـ resources تبع
الـ machine، عمليًا إحنا هيك بنكون أجمَلنا اللي بدناه
من الـ chapter ثمانية
الأساسيات يعني ما أقدرش أقول أنه إحنا غطينا كافة ..
كافة الـ chapter، طبعًا آه هي مثلًا الـ optimization
كلها لسه ضايلة أمامنا في هذا الـ chapter بس إحنا
عمليًا بقدر أقول إحنا غطينا المصطلح الأول من ال
chapter أو جزء الأساسي من النص الأول، هذا ال
chapter هو نهاية عملية الـ code generation، بعد هي
كان بيبقى فيه أي شيء عبارة عن optimization أو شيء
إضافي بس الكويس جدا في مساق زي هذا المساق اللي
هنكون وصلنا لهذا المرحلة، هذا طبعًا آخر محاضرة في ال
semester، وإن شاء الله يعني إحنا طبعًا يعني مبسوطين
بحضوركم معنا وإن شاء الله بنشوف محاضرات ثانية
سواء .. بس أنتم ماشي خلصتوا أنتم لأن ولا لأ؟
ضايل كويس في بعد حصر هذا؟ خير إن شاء الله أول
بيجي زمايل ثانيين لكم ونسجل معاهم وإن شاء الله
بتعمل فايدة على الجميع، يعطيكم العافية