Julia SSA-form IR

تستخدم جوليا تمثيلًا وسيطًا لتعيين ثابت واحد (SSA IR) لأداء التحسين. هذا التمثيل الوسيط مختلف عن تمثيل LLVM، ومميز لجوليا. يسمح بإجراء تحسينات خاصة بجوليا.

1. تُعَلم الكتل الأساسية (المناطق التي لا تحتوي على تدفق تحكم) بشكل صريح.
2. إذا/إلا والحلقات تتحول إلى عبارات goto.
3. يتم تقسيم الأسطر التي تحتوي على عمليات متعددة إلى أسطر متعددة من خلال إدخال متغيرات.

على سبيل المثال، الكود التالي بلغة جوليا:

function foo(x)
    y = sin(x)
    if x > 5.0
        y = y + cos(x)
    end
    return exp(2) + y
end

عند استدعائه مع وسيط من نوع Float64 يتم ترجمته إلى:

using InteractiveUtils
@code_typed foo(1.0)

CodeInfo(
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
2 ─ %4 = invoke Main.cos(x::Float64)::Float64
└── %5 = Base.add_float(%1, %4)::Float64
3 ┄ %6 = φ (#2 => %5, #1 => %1)::Float64
│   %7 = Base.add_float(7.38905609893065, %6)::Float64
└──      return %7
) => Float64

في هذا المثال، يمكننا رؤية كل هذه التغييرات.

1. الكتلة الأساسية الأولى هي كل شيء في

1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2

1. يتم ترجمة جملة if إلى goto #3 if not %2 والتي تنتقل إلى الكتلة الأساسية الثالثة إذا لم يتم استيفاء الشرط x>5 وإلا تنتقل إلى الكتلة الأساسية الثانية.
2. %2 هو قيمة SSA تم تقديمها لتمثيل x > 5.

Background

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

Categories of IR nodes

تمثل تمثيل SSA IR أربع فئات من عقد IR: عقد Phi و Pi و PhiC و Upsilon (تستخدم الأخيرتان فقط لمعالجة الاستثناءات).

Phi nodes and Pi nodes

تعتبر عقد Phi جزءًا من تجريد SSA العام (راجع الرابط أعلاه إذا لم تكن على دراية بالمفهوم). في IR الخاص بـ Julia، يتم تمثيل هذه العقد على النحو التالي:

struct PhiNode
    edges::Vector{Int32}
    values::Vector{Any}
end

حيث نضمن أن كلا المتجهين لهما نفس الطول دائمًا. في التمثيل القياسي (الذي يتم التعامل معه بواسطة codegen والمفسر)، تشير قيم الحافة إلى أرقام بيانات "come-from" (أي إذا كانت الحافة تحتوي على إدخال 15، يجب أن يكون هناك goto أو gotoifnot أو سقوط ضمني من البيان 15 الذي يستهدف هذه العقدة phi). القيم إما أن تكون قيم SSA أو ثوابت. من الممكن أيضًا أن تكون القيمة غير معينة إذا لم يتم تعريف المتغير في هذا المسار. ومع ذلك، يتم إدراج فحوصات عدم التعريف بشكل صريح وتمثيلها كقيم منطقية بعد تحسينات منتصف النهاية، لذا يمكن لمولدات الشيفرة أن تفترض أن أي استخدام لعقدة Phi سيكون له قيمة معينة في الفتحة المقابلة. من القانوني أيضًا أن يكون التعيين غير مكتمل، أي أن تكون لعقدة Phi حواف واردة مفقودة. في هذه الحالة، يجب ضمان ديناميكيًا أن القيمة المقابلة لن يتم استخدامها.

لاحظ أن SSA يستخدم الدلالات التي تحدث بعد المنهي الخاص بالسابقة المقابلة ("على الحافة"). وبالتالي، إذا ظهرت عدة عقد Phi في بداية كتلة أساسية، فإنها تعمل في وقت واحد. هذا يعني أنه في مقتطف IR التالي، إذا جئنا من الكتلة 23، فإن %46 ستأخذ القيمة المرتبطة بـ %45 قبل أن ندخل هذه الكتلة.

%45 = φ (#18 => %23, #23 => %50)
%46 = φ (#18 => 1.0, #23 => %45)

PiNodes ترمز المعلومات المثبتة بشكل ثابت التي يمكن أن تُفترض ضمنيًا في الكتل الأساسية التي تهيمن عليها عقدة pi معينة. إنهم متساوون من الناحية المفاهيمية مع التقنية التي تم تقديمها في الورقة ABCD: Eliminating Array Bounds Checks on Demand أو عقد معلومات الشرط في LLVM. لرؤية كيفية عملها، اعتبر، على سبيل المثال.

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    # use x
else
    # use x
end

يمكننا إجراء إدراج العبارات وتحويل ذلك إلى:

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # use %x_int
else
    %x_float = PiNode(x, Float64)
    # use %x_float
end

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

PhiC nodes and Upsilon nodes

تُعقِّد معالجة الاستثناءات قصة SSA بشكل معتدل، لأن معالجة الاستثناءات تُدخل حواف تدفق تحكم إضافية إلى IR يجب تتبع القيم عبرها. إحدى الطرق للقيام بذلك، والتي تتبعها LLVM، هي جعل الاستدعاءات التي قد تُثير استثناءات في محددات الكتل الأساسية وإضافة حافة تدفق تحكم صريحة إلى معالج الالتقاط:

invoke @function_that_may_throw() to label %regular unwind to %catch

regular:
# Control flow continues here

catch:
# Exceptions go here

ومع ذلك، فإن هذا يمثل مشكلة في لغة مثل جوليا، حيث في بداية خط أنابيب التحسين، لا نعرف أي الاستدعاءات قد تتسبب في حدوث استثناء. سيتعين علينا أن نفترض بحذر أن كل استدعاء (الذي في جوليا هو كل عبارة) قد يتسبب في حدوث استثناء. سيكون لذلك عدة آثار سلبية. من ناحية، سيؤدي ذلك بشكل أساسي إلى تقليل نطاق كل كتلة أساسية إلى استدعاء واحد، مما يقوض الغرض من إجراء العمليات على مستوى الكتلة الأساسية. من ناحية أخرى، سيكون لكل كتلة أساسية للتقاط استثناءات n*m من وسائط عقد phi (n، عدد العبارات في المنطقة الحرجة، m عدد القيم الحية عبر كتلة التقاط الاستثناء).

للتغلب على ذلك، نستخدم مجموعة من عقد Upsilon و PhiC (حيث تشير C إلى catch، مكتوبة φᶜ في طابعة IR الجميلة، لأن الرمز الفرعي unicode c غير متاح). هناك عدة طرق للتفكير في هذه العقد، ولكن ربما أسهلها هو التفكير في كل PhiC كتحميل من مخزن فريد للعديد من القيم، يتم قراءته مرة واحدة، مع كون Upsilon هو عملية التخزين المقابلة. تحتوي PhiC على قائمة عمليات لجميع عقد upsilon التي تخزن في فتحتها الضمنية. ومع ذلك، لا تسجل عقد Upsilon أي عقدة PhiC تخزن فيها. يتم ذلك من أجل تكامل أكثر طبيعية مع بقية SSA IR. على سبيل المثال، إذا لم يكن هناك المزيد من الاستخدامات لعقدة PhiC، فمن الآمن حذفها، وينطبق الشيء نفسه على عقدة Upsilon. في معظم تمريرات IR، يمكن التعامل مع عقد PhiC مثل عقد Phi. يمكن للمرء اتباع سلاسل الاستخدام-التعريف من خلالها، ويمكن رفعها إلى عقد PhiC جديدة وعقد Upsilon جديدة (في نفس الأماكن مثل عقد Upsilon الأصلية). نتيجة هذه الخطة هي أن عدد عقد Upsilon (ووسائط PhiC) يتناسب مع عدد القيم المعينة لمتغير معين (قبل تحويل SSA)، بدلاً من عدد العبارات في المنطقة الحرجة.

لرؤية هذا المخطط قيد التنفيذ، اعتبر الدالة

@noinline opaque() = invokelatest(identity, nothing) # Something opaque
function foo()
    local y
    x = 1
    try
        y = 2
        opaque()
        y = 3
        error()
    catch
    end
    (x, y)
end

الـ IR المقابل (مع إزالة الأنواع غير ذات الصلة) هو:

1 ─       nothing::Nothing
2 ─ %2  = $(Expr(:enter, #4))
3 ─ %3  = ϒ (false)
│   %4  = ϒ (#undef)
│   %5  = ϒ (1)
│   %6  = ϒ (true)
│   %7  = ϒ (2)
│         invoke Main.opaque()::Any
│   %9  = ϒ (true)
│   %10 = ϒ (3)
│         invoke Main.error()::Union{}
└──       $(Expr(:unreachable))::Union{}
4 ┄ %13 = φᶜ (%3, %6, %9)::Bool
│   %14 = φᶜ (%4, %7, %10)::Core.Compiler.MaybeUndef(Int64)
│   %15 = φᶜ (%5)::Core.Const(1)
└──       $(Expr(:leave, Core.SSAValue(2)))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

لاحظ بشكل خاص أن كل قيمة تعيش في المنطقة الحرجة تحصل على عقدة upsilon في أعلى المنطقة الحرجة. وذلك لأن كتل catch تعتبر أن لديها حافة تدفق تحكم غير مرئية من خارج الدالة. ونتيجة لذلك، لا تهيمن أي قيمة SSA على كتل catch، ويجب أن تأتي جميع القيم الواردة من خلال عقدة φᶜ.

Main SSA data structure

هيكل بيانات SSAIR الرئيسي يستحق المناقشة. إنه يستلهم من LLVM و B3 IR الخاص بـ Webkit. جوهر هيكل البيانات هو متجه مسطح من العبارات. يتم تعيين كل عبارة بشكل ضمني قيمة SSA بناءً على موقعها في المتجه (أي أن نتيجة العبارة في الفهرس 1 يمكن الوصول إليها باستخدام SSAValue(1) إلخ). بالنسبة لكل قيمة SSA، نقوم أيضًا بالحفاظ على نوعها. نظرًا لأن قيم SSA يتم تعيينها تعريفياً مرة واحدة فقط، فإن هذا النوع هو أيضًا نوع نتيجة التعبير في الفهرس المقابل. ومع ذلك، بينما يكون هذا التمثيل فعالًا إلى حد ما (نظرًا لأن التعيينات لا تحتاج إلى ترميز صريح)، فإنه بالطبع يحمل العيب المتمثل في أن الترتيب له دلالة دلالية، لذا فإن إعادة الترتيب والإدراجات تغير أرقام العبارات. بالإضافة إلى ذلك، نحن لا نحتفظ بقوائم الاستخدام (أي أنه من المستحيل السير من تعريف إلى جميع استخداماته دون حساب هذه الخريطة بشكل صريح - قوائم التعريفات ومع ذلك تكون تافهة حيث يمكنك البحث عن العبارة المقابلة من الفهرس)، لذا فإن عملية RAUW (استبدال جميع الاستخدامات بـ) على نمط LLVM غير متاحة.

بدلاً من ذلك، نقوم بما يلي:

• نحتفظ بذاكرة مؤقتة منفصلة من العقد للإدراج (بما في ذلك الموضع الذي سيتم إدراجها فيه، نوع القيمة المقابلة والعقدة نفسها). يتم ترقيم هذه العقد حسب حدوثها في ذاكرة الإدراج، مما يسمح باستخدام قيمها على الفور في أماكن أخرى في IR (أي إذا كان هناك 12 بيانًا في قائمة البيانات الأصلية، فسيكون البيان الجديد الأول متاحًا كـ SSAValue(13)).
• تتم عمليات نمط RAUW عن طريق تعيين فهرس العبارة المقابل إلى قيمة الاستبدال.
• يتم مسح العبارات عن طريق تعيين العبارة المقابلة إلى nothing (هذه في الأساس مجرد قاعدة خاصة للحالة المذكورة أعلاه).
• إذا كان هناك أي استخدامات للعبارة التي تم مسحها، فسيتم تعيينها إلى nothing.

هناك دالة compact! التي تقوم بتقليص هيكل البيانات أعلاه من خلال إجراء إدخال العقد في المكان المناسب، ونقل النسخ التافهة، وإعادة تسمية الاستخدامات لأي قيم SSA تم تغييرها. ومع ذلك، فإن الجزء الذكي من هذه الخطة هو أنه يمكن إجراء هذا التقليص بشكل كسول كجزء من المرور اللاحق. تحتاج معظم تمريرات التحسين إلى السير على قائمة البيانات بأكملها، وإجراء التحليل أو التعديلات على طول الطريق. نحن نقدم مكرر IncrementalCompact يمكن استخدامه للتكرار على قائمة البيانات. سيقوم بإجراء أي تقليص ضروري وإرجاع الفهرس الجديد للعقدة، بالإضافة إلى العقدة نفسها. من القانوني في هذه المرحلة السير على سلاسل الاستخدام-التعريف، بالإضافة إلى إجراء أي تعديلات أو حذف على IR (ومع ذلك، فإن الإدخالات غير مسموح بها).

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