kerncraft/iaca.py
def find_asm_blocks(asm_lines):
    """Find blocks probably corresponding to loops in assembly."""
    blocks = []

    last_labels = OrderedDict()
    packed_ctr = 0
    avx_ctr = 0
    xmm_references = []
    ymm_references = []
    zmm_references = []
    gp_references = []
    mem_references = []
    increments = {}
    for i, line in enumerate(asm_lines):
        # Register access counts
        zmm_references += re.findall('%zmm[0-9]+', line)
        ymm_references += re.findall('%ymm[0-9]+', line)
        xmm_references += re.findall('%xmm[0-9]+', line)
        gp_references += re.findall('%r[a-z0-9]+', line)
        if re.search(r'\d*\(%\w+(,%\w+)?(,\d)?\)', line):
            m = re.search(r'(?P<off>[-]?\d*)\(%(?P<basep>\w+)(,%(?P<idx>\w+))?(?:,(?P<scale>\d))?\)'
                          r'(?P<eol>$)?',
                          line)
            mem_references.append((
                int(m.group('off')) if m.group('off') else 0,
                m.group('basep'),
                m.group('idx'),
                int(m.group('scale')) if m.group('scale') else 1,
                'load' if m.group('eol') is None else 'store'))

        if re.match(r"^[v]?(mul|add|sub|div|fmadd(132|213|231)?)[h]?p[ds]", line):
            if line.startswith('v'):
                avx_ctr += 1
            packed_ctr += 1
        elif re.match(r'^\S+:', line):
            # last_labels[label_name] = line_number
            last_labels[line[0:line.find(':')]] =i

            # Reset counters
            packed_ctr = 0
            avx_ctr = 0
            xmm_references = []
            ymm_references = []
            zmm_references = []
            gp_references = []
            mem_references = []
            increments = {}
        elif re.match(r'^inc[bwlq]?\s+%[a-z0-9]+', line):
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = 1
        elif re.match(r'^add[bwlq]?\s+\$[0-9]+,\s*%[a-z0-9]+', line):
            const_start = line.find('$') + 1
            const_end = line[const_start + 1:].find(',') + const_start + 1
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = int(line[const_start:const_end])
        elif re.match(r'^dec[bwlq]?', line):
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = -1
        elif re.match(r'^sub[bwlq]?\s+\$[0-9]+,', line):
            const_start = line.find('$') + 1
            const_end = line[const_start + 1:].find(',') + const_start + 1
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = -int(line[const_start:const_end])
        elif last_labels and re.match(r'^j[a-z]+\s+\S+\s*', line):
            # End of block(s) due to jump

            # Check if jump target matches any previously recoded label
            last_label = None
            last_label_line = -1
            for label_name, label_line in last_labels.items():
                if re.match(r'^j[a-z]+\s+' + re.escape(label_name) + r'\s*', line):
                    # matched
                    last_label = label_name
                    last_label_line = label_line

            labels = list(last_labels.keys())

            if last_label:
                # deduce loop increment from memory index register
                pointer_increment = None  # default -> can not decide, let user choose
                possible_idx_regs = None
                if mem_references:
                    # we found memory references to work with

                    # If store accesses exist, consider only those
                    store_references = [mref for mref in mem_references
                                        if mref[4] == 'store']
                    refs = store_references or mem_references

                    possible_idx_regs = list(set(increments.keys()).intersection(
                        set([r[1] for r in refs if r[1] is not None] +
                            [r[2] for r in refs if r[2] is not None])))
                    for mref in refs:
                        for reg in list(possible_idx_regs):
                            # Only consider references with two registers, where one could be an index
                            if None not in mref[1:3]:
                                # One needs to mach, other registers will be excluded
                                if not (reg == mref[1] or reg == mref[2]):
                                    # reg can not be it
                                    possible_idx_regs.remove(reg)

                    idx_reg = None
                    if len(possible_idx_regs) == 1:
                        # good, exactly one register was found
                        idx_reg = possible_idx_regs[0]
                    elif possible_idx_regs and itemsEqual([increments[pidxreg]
                                                           for pidxreg in possible_idx_regs]):
                        # multiple were option found, but all have the same increment
                        # use first match:
                        idx_reg = possible_idx_regs[0]

                    if idx_reg:
                        mem_scales = [mref[3] for mref in refs
                                      if idx_reg == mref[2] or idx_reg == mref[1]]

                        if itemsEqual(mem_scales):
                            # good, all scales are equal
                            try:
                                pointer_increment = mem_scales[0] * increments[idx_reg]
                            except:
                                print("labels", pformat(labels[labels.index(last_label):]))
                                print("lines", pformat(asm_lines[last_label_line:i + 1]))
                                print("increments", increments)
                                print("mem_references", pformat(mem_references))
                                print("idx_reg", idx_reg)
                                print("mem_scales", mem_scales)
                                raise

                blocks.append({'first_line': last_label_line,
                               'last_line': i,
                               'ops': i - last_label_line,
                               'labels': labels[labels.index(last_label):],
                               'packed_instr': packed_ctr,
                               'avx_instr': avx_ctr,
                               'XMM': (len(xmm_references), len(set(xmm_references))),
                               'YMM': (len(ymm_references), len(set(ymm_references))),
                               'ZMM': (len(zmm_references), len(set(zmm_references))),
                               'GP': (len(gp_references), len(set(gp_references))),
                               'regs': (len(xmm_references) + len(ymm_references) +
                                        len(zmm_references) + len(gp_references),
                                        len(set(xmm_references)) + len(set(ymm_references)) +
                                        len(set(zmm_references)) +
                                        len(set(gp_references))),
                               'pointer_increment': pointer_increment,
                               'lines': asm_lines[last_label_line:i + 1],
                               'possible_idx_regs': possible_idx_regs,
                               'mem_references': mem_references,
                               'increments': increments, })
            # Reset counters
            packed_ctr = 0
            avx_ctr = 0
            xmm_references = []
            ymm_references = []
            zmm_references = []
            gp_references = []
            mem_references = []
            increments = {}
            last_labels = OrderedDict()
    return list(enumerate(blocks))
def find_asm_blocks(asm_lines):
    """Find blocks probably corresponding to loops in assembly."""
    blocks = []

    last_labels = OrderedDict()
    packed_ctr = 0
    avx_ctr = 0
    xmm_references = []
    ymm_references = []
    zmm_references = []
    gp_references = []
    mem_references = []
    increments = {}
    for i, line in enumerate(asm_lines):
        # Register access counts
        zmm_references += re.findall('%zmm[0-9]+', line)
        ymm_references += re.findall('%ymm[0-9]+', line)
        xmm_references += re.findall('%xmm[0-9]+', line)
        gp_references += re.findall('%r[a-z0-9]+', line)
        if re.search(r'\d*\(%\w+(,%\w+)?(,\d)?\)', line):
            m = re.search(r'(?P<off>[-]?\d*)\(%(?P<basep>\w+)(,%(?P<idx>\w+))?(?:,(?P<scale>\d))?\)'
                          r'(?P<eol>$)?',
                          line)
            mem_references.append((
                int(m.group('off')) if m.group('off') else 0,
                m.group('basep'),
                m.group('idx'),
                int(m.group('scale')) if m.group('scale') else 1,
                'load' if m.group('eol') is None else 'store'))

        if re.match(r"^[v]?(mul|add|sub|div|fmadd(132|213|231)?)[h]?p[ds]", line):
            if line.startswith('v'):
                avx_ctr += 1
            packed_ctr += 1
        elif re.match(r'^\S+:', line):
            # last_labels[label_name] = line_number
            last_labels[line[0:line.find(':')]] =i

            # Reset counters
            packed_ctr = 0
            avx_ctr = 0
            xmm_references = []
            ymm_references = []
            zmm_references = []
            gp_references = []
            mem_references = []
            increments = {}
        elif re.match(r'^inc[bwlq]?\s+%[a-z0-9]+', line):
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = 1
        elif re.match(r'^add[bwlq]?\s+\$[0-9]+,\s*%[a-z0-9]+', line):
            const_start = line.find('$') + 1
            const_end = line[const_start + 1:].find(',') + const_start + 1
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = int(line[const_start:const_end])
        elif re.match(r'^dec[bwlq]?', line):
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = -1
        elif re.match(r'^sub[bwlq]?\s+\$[0-9]+,', line):
            const_start = line.find('$') + 1
            const_end = line[const_start + 1:].find(',') + const_start + 1
            reg_start = line.find('%') + 1
            increments[line[reg_start:]] = -int(line[const_start:const_end])
        elif last_labels and re.match(r'^j[a-z]+\s+\S+\s*', line):
            # End of block(s) due to jump

            # Check if jump target matches any previously recoded label
            last_label = None
            last_label_line = -1
            for label_name, label_line in last_labels.items():
                if re.match(r'^j[a-z]+\s+' + re.escape(label_name) + r'\s*', line):
                    # matched
                    last_label = label_name
                    last_label_line = label_line

            labels = list(last_labels.keys())

            if last_label:
                # deduce loop increment from memory index register
                pointer_increment = None  # default -> can not decide, let user choose
                possible_idx_regs = None
                if mem_references:
                    # we found memory references to work with

                    # If store accesses exist, consider only those
                    store_references = [mref for mref in mem_references
                                        if mref[4] == 'store']
                    refs = store_references or mem_references

                    possible_idx_regs = list(set(increments.keys()).intersection(
                        set([r[1] for r in refs if r[1] is not None] +
                            [r[2] for r in refs if r[2] is not None])))
                    for mref in refs:
                        for reg in list(possible_idx_regs):
                            # Only consider references with two registers, where one could be an index
                            if None not in mref[1:3]:
                                # One needs to mach, other registers will be excluded
                                if not (reg == mref[1] or reg == mref[2]):
                                    # reg can not be it
                                    possible_idx_regs.remove(reg)

                    idx_reg = None
                    if len(possible_idx_regs) == 1:
                        # good, exactly one register was found
                        idx_reg = possible_idx_regs[0]
                    elif possible_idx_regs and itemsEqual([increments[pidxreg]
                                                           for pidxreg in possible_idx_regs]):
                        # multiple were option found, but all have the same increment
                        # use first match:
                        idx_reg = possible_idx_regs[0]

                    if idx_reg:
                        mem_scales = [mref[3] for mref in refs
                                      if idx_reg == mref[2] or idx_reg == mref[1]]

                        if itemsEqual(mem_scales):
                            # good, all scales are equal
                            try:
                                pointer_increment = mem_scales[0] * increments[idx_reg]
                            except:
                                print("labels", pformat(labels[labels.index(last_label):]))
                                print("lines", pformat(asm_lines[last_label_line:i + 1]))
                                print("increments", increments)
                                print("mem_references", pformat(mem_references))
                                print("idx_reg", idx_reg)
                                print("mem_scales", mem_scales)
                                raise

                blocks.append({'first_line': last_label_line,
                               'last_line': i,
                               'ops': i - last_label_line,
                               'labels': labels[labels.index(last_label):],
                               'packed_instr': packed_ctr,
                               'avx_instr': avx_ctr,
                               'XMM': (len(xmm_references), len(set(xmm_references))),
                               'YMM': (len(ymm_references), len(set(ymm_references))),
                               'ZMM': (len(zmm_references), len(set(zmm_references))),
                               'GP': (len(gp_references), len(set(gp_references))),
                               'regs': (len(xmm_references) + len(ymm_references) +
                                        len(zmm_references) + len(gp_references),
                                        len(set(xmm_references)) + len(set(ymm_references)) +
                                        len(set(zmm_references)) +
                                        len(set(gp_references))),
                               'pointer_increment': pointer_increment,
                               'lines': asm_lines[last_label_line:i + 1],
                               'possible_idx_regs': possible_idx_regs,
                               'mem_references': mem_references,
                               'increments': increments, })
            # Reset counters
            packed_ctr = 0
            avx_ctr = 0
            xmm_references = []
            ymm_references = []
            zmm_references = []
            gp_references = []
            mem_references = []
            increments = {}
            last_labels = OrderedDict()
    return list(enumerate(blocks))
Find blocks probably corresponding to loops in assembly.