تحويل CFG إلى IL

Question

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

وهذا على ما يرام ولكن overcomplicates بعض الاشياء. تخيل:

Jump 'B'
'C': Return
'B': Jump 'C'

وهذا من شأنه أن يؤدي إلى الرسم البياني تدفق مثل هذا: (اذهب B) -> (السريع C) -> (العودة) وهذا بالطبع مثال مبسط لكنه يظهر المشكلة عند التحويل من CFG.

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

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

Answer 1

وتحويل CFG إلى IL: كنت ترغب في السير على الرسم البياني، تنبعث منها كل قمة بالضبط مرة واحدة (باستثناء تلك التي هي غير قابلة للوصول). لذلك تحتاج إلى سجل والتي تم تنبعث القمم: فإن العلم على قمة الرأس به، أو تجزئة من قمة الرأس إلى صواب / خطأ

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

وهذا هو أكثر أو أقل ما كنت تستخدم.

def needs_label(cfg, v, last):
    if cfg.predecessors(v) > 1:
        # There's more than one way of entering this vertex
        return True
    elif cfg.predecessors(v) == 1 and last != cfg.predecessors(v)[0]:
        # There's only one way, but the last vertex emitted was not that way
        # so it will be entered using a jump.
        return True
    else:
        return False

def emit_label(v):
    print 'label%d' % (v.id)

def emit_vertex(v):
    if v.type == 'branch':
        # Branch to second successor
        print 'br label%d' % cfg.successors(v)[1].id
    else:
        ...

def emit_jump(v):
    print 'jmp label%d' % v.id

def emit_cfg(cfg):
    q = Queue()   # Queue for saving vertices that we want to emit later
    done = {}    # Hash recording which vertices have already been emitted
    q.push(cfg.start())
    while not q.empty():
        v = q.pop()
        last = None
        while v is not None and not done[v]:
            # Emit the vertex, with a prefixed label if necessary
            if needs_label(cfg, v, last):
                emit_label(v)
            emit_vertex(v)
            done[v] = True
            last = v
            # Get the vertex's successors
            succs = cfg.successors(v)
            # If there aren't any, then this path is finished, so go back to
            # the outer loop to pop another saved vertex
            if len(succs) == 0:
                v = None   # Setting this will terminate the inner loop
                continue
            # Stick all the vertices on the stack for later, in case we can't
            # process them all here
            for s in succs:
                q.push(s)
            # Pick a new vertex from the list of successors.  Always pick the first
            # because if it's a branch then the second will have been branched on
            v = succs[0]
            # If it was emitted earlier we need to jump to it
            if done[v]:
                emit_jump(v)
                v = None
            # Otherwise continue the inner loop, walking from the new vertex

ومعاملة فروع (القمم مع خليفة أكثر من واحد) هي ساذجة جدا: عادة تريد معرفة التي هي أكثر عرضة وتابع أن أحد مباشرة، إذا كان ذلك ممكنا

Answer 2

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