VirtualBox

Changeset 108861 in vbox for trunk/src/VBox/VMM


Ignore:
Timestamp:
Apr 5, 2025 1:15:03 AM (5 weeks ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
168311
Message:

VMM/IEM: Working on the ARM bsd/opensource spec reader & decoder generator. Work in progress. jiraref:VBP-1598

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/VMM/VMMAll/target-armv8/bsd-spec-analyze.py

    r108853 r108861  
    22# -*- coding: utf-8 -*-
    33# $Id$
     4# pylint: disable=invalid-name
    45
    56"""
    … …  
    3536# Standard python imports.
    3637import argparse;
    37 import ast;
    3838import collections;
    3939import datetime;
    … …  
    4545import tarfile;
    4646import traceback;
     47import cProfile;
    4748
    4849
    … …  
    5657    """
    5758
    58     kTypeBinaryOp   = 'AST.BinaryOp';
    59     kTypeBool       = 'AST.Bool';
    60     kTypeConcat     = 'AST.Concat';
    61     kTypeFunction   = 'AST.Function';
    62     kTypeIdentifier = 'AST.Identifier';
    63     kTypeInteger    = 'AST.Integer';
    64     kTypeSet        = 'AST.Set';
    65     kTypeSquareOp   = 'AST.SquareOp';
    66     kTypeUnaryOp    = 'AST.UnaryOp';
    67     kTypeValue      = 'Values.Value';
     59    ksTypeBinaryOp   = 'AST.BinaryOp';
     60    ksTypeBool       = 'AST.Bool';
     61    ksTypeConcat     = 'AST.Concat';
     62    ksTypeFunction   = 'AST.Function';
     63    ksTypeIdentifier = 'AST.Identifier';
     64    ksTypeInteger    = 'AST.Integer';
     65    ksTypeSet        = 'AST.Set';
     66    ksTypeSquareOp   = 'AST.SquareOp';
     67    ksTypeUnaryOp    = 'AST.UnaryOp';
     68    ksTypeValue      = 'Values.Value';
    6869
    6970    def __init__(self, sType):
    7071        self.sType = sType;
    7172
     73    @staticmethod
    7274    def assertAttribsInSet(oJson, oAttribSet):
    7375        """ Checks that the JSON element has all the attributes in the set and nothing else. """
    … …  
    135137
    136138    kfnTypeMap = {
    137         kTypeBinaryOp:      fromJsonBinaryOp,
    138         kTypeUnaryOp:       fromJsonUnaryOp,
    139         kTypeSquareOp:      fromJsonSquareOp,
    140         kTypeConcat:        fromJsonConcat,
    141         kTypeFunction:      fromJsonFunction,
    142         kTypeIdentifier:    fromJsonIdentifier,
    143         kTypeBool:          fromJsonBool,
    144         kTypeInteger:       fromJsonInteger,
    145         kTypeSet:           fromJsonSet,
    146         kTypeValue:         fromJsonValue,
     139        ksTypeBinaryOp:     fromJsonBinaryOp,
     140        ksTypeUnaryOp:      fromJsonUnaryOp,
     141        ksTypeSquareOp:     fromJsonSquareOp,
     142        ksTypeConcat:       fromJsonConcat,
     143        ksTypeFunction:     fromJsonFunction,
     144        ksTypeIdentifier:   fromJsonIdentifier,
     145        ksTypeBool:         fromJsonBool,
     146        ksTypeInteger:      fromJsonInteger,
     147        ksTypeSet:          fromJsonSet,
     148        ksTypeValue:        fromJsonValue,
    147149    };
    148150
    … …  
    152154        #print('debug ast: %s' % oJson['_type'])
    153155        return ArmAstBase.kfnTypeMap[oJson['_type']](oJson);
     156
     157    def isBoolAndTrue(self):
     158        """ Check if this is a boolean with the value True. """
     159        #return isinstance(self, ArmAstBool) and self.fValue is True;
     160        if isinstance(self, ArmAstBool):
     161            return self.fValue is True;
     162        return False;
    154163
    155164
    … …  
    172181
    173182    def __init__(self, oLeft, sOp, oRight):
    174         ArmAstBase.__init__(self, ArmAstBase.kTypeBinaryOp);
     183        ArmAstBase.__init__(self, ArmAstBase.ksTypeBinaryOp);
    175184        assert sOp in ArmAstBinaryOp.kdOps, 'sOp="%s"' % (sOp,);
    176185        self.oLeft  = oLeft;
    … …  
    180189        # Switch value == field non-sense (simplifies transferConditionsToEncoding and such):
    181190        if (    isinstance(oRight, ArmAstIdentifier)
    182             and isinstance(oLeft, [ArmAstValue, ArmAstInteger])
     191            and isinstance(oLeft, (ArmAstValue, ArmAstInteger))
    183192            and sOp in ['==', '!=']):
    184193            self.oLeft  = oRight;
    … …  
    210219
    211220    def __init__(self, sOp, oExpr):
    212         ArmAstBase.__init__(self, ArmAstBase.kTypeUnaryOp);
     221        ArmAstBase.__init__(self, ArmAstBase.ksTypeUnaryOp);
    213222        assert sOp in ArmAstUnaryOp.kdOps, 'sOp=%s' % (sOp,);
    214223        self.sOp   = sOp;
    … …  
    221230
    222231class ArmAstSquareOp(ArmAstBase):
    223     def __init__(self, aoValues):
    224         ArmAstBase.__init__(self, ArmAstBase.kTypeSquareOp);
     232    def __init__(self, oVar, aoValues):
     233        ArmAstBase.__init__(self, ArmAstBase.ksTypeSquareOp);
     234        self.oVar     = oVar;
    225235        self.aoValues = aoValues;
    226236
    227237    def toString(self):
    228         return '<%s>' % (','.join([oValue.toString() for oValue in self.aoValues]),);
     238        return '%s<%s>' % (self.oVar.toString(), ','.join([oValue.toString() for oValue in self.aoValues]),);
    229239
    230240
    231241class ArmAstConcat(ArmAstBase):
    232242    def __init__(self, aoValues):
    233         ArmAstBase.__init__(self, ArmAstBase.kTypeConcat);
     243        ArmAstBase.__init__(self, ArmAstBase.ksTypeConcat);
    234244        self.aoValues = aoValues;
    235245
    … …  
    249259
    250260    def __init__(self, sName, aoArgs):
    251         ArmAstBase.__init__(self, ArmAstBase.kTypeFunction);
     261        ArmAstBase.__init__(self, ArmAstBase.ksTypeFunction);
    252262        assert self.s_oReValidName.match(sName), 'sName=%s' % (sName);
    253263        self.sName  = sName;
    … …  
    261271
    262272    def __init__(self, sName):
    263         ArmAstBase.__init__(self, ArmAstBase.kTypeIdentifier);
     273        ArmAstBase.__init__(self, ArmAstBase.ksTypeIdentifier);
    264274        assert self.s_oReValidName.match(sName), 'sName=%s' % (sName);
    265275        self.sName = sName;
    … …  
    270280class ArmAstBool(ArmAstBase):
    271281    def __init__(self, fValue):
    272         ArmAstBase.__init__(self, ArmAstBase.kTypeBool);
     282        ArmAstBase.__init__(self, ArmAstBase.ksTypeBool);
    273283        assert fValue is True or fValue is False, '%s' % (fValue,);
    274284        self.fValue = fValue;
    … …  
    280290class ArmAstInteger(ArmAstBase):
    281291    def __init__(self, iValue):
    282         ArmAstBase.__init__(self, ArmAstBase.kTypeInteger);
     292        ArmAstBase.__init__(self, ArmAstBase.ksTypeInteger);
    283293        self.iValue = int(iValue);
    284294
    … …  
    286296        return '%#x' % (self.iValue,);
    287297
     298
    288299class ArmAstSet(ArmAstBase):
    289300    def __init__(self, aoValues):
    290         ArmAstBase.__init__(self, ArmAstBase.kTypeSet);
     301        ArmAstBase.__init__(self, ArmAstBase.ksTypeSet);
    291302        self.aoValues = aoValues;
    292303
    … …  
    294305        return '(%s)' % (', '.join([oValue.toString() for oValue in self.aoValues]),);
    295306
     307
    296308class ArmAstValue(ArmAstBase):
    297309    def __init__(self, sValue):
    298         ArmAstBase.__init__(self, ArmAstBase.kTypeValue);
     310        ArmAstBase.__init__(self, ArmAstBase.ksTypeValue);
    299311        self.sValue = sValue;
    300312
    … …  
    360372    @staticmethod
    361373    def fromJson(oJson):
    362         """ """
    363374        assert oJson['_type'] in ('Instruction.Encodeset.Field', 'Instruction.Encodeset.Bits'), oJson['_type'];
    364375
    … …  
    373384    @staticmethod
    374385    def fromJsonEncodeset(oJson, aoSet, fCovered):
    375         """ """
    376386        assert oJson['_type'] == 'Instruction.Encodeset.Encodeset', oJson['_type'];
    377387        for oJsonValue in oJson['values']:
    … …  
    452462
    453463            oCondition = ArmAstBase.fromJson(oJson['condition']);
    454             print('debug transfer in:  %s' % (oCondition.toString()));
     464            #sCondBefore = oCondition.toString();
     465            #print('debug transfer: %s: org:  %s' % (sInstrNm, sCondBefore));
    455466            (oCondition, fMod) = transferConditionsToEncoding(oCondition, aoEncodesets, collections.defaultdict(list), sInstrNm);
    456             if fMod:
    457                 print('debug transfer out: %s' % (oCondition.toString()));
     467            #if fMod:
     468            #    print('debug transfer: %s: %s  ---->  %s' % (sInstrNm, sCondBefore, oCondition.toString()));
     469            _ = fMod;
    458470
    459471            oInstr = ArmInstruction(oJson, sInstrNm, sInstrNm, aoEncodesets, oCondition);
    … …  
    478490    The checks can be morphed into the 'size' field encoding criteria as '0b0x'.
    479491    """
    480     def isBoolTrue(oNode):
    481         return isinstance(oNode, ArmAstBool) and oNode.fValue is True;
    482 
    483492    if isinstance(oCondition, ArmAstBinaryOp):
    484493        if oCondition.sOp == '&&':
    485             print('debug transfer: %s: recursion...' % (sInstrNm,));
    486494            # Recurse into each side of an AND expression.
     495            #print('debug transfer: %s: recursion...' % (sInstrNm,));
    487496            (oCondition.oLeft, fMod)  = transferConditionsToEncoding(oCondition.oLeft,  aoEncodesets, dPendingNotEq,
    488497                                                                     sInstrNm, uDepth + 1, fMod);
    489498            (oCondition.oRight, fMod) = transferConditionsToEncoding(oCondition.oRight, aoEncodesets, dPendingNotEq,
    490499                                                                     sInstrNm, uDepth + 1, fMod);
    491             if isBoolTrue(oCondition.oLeft):
     500            if oCondition.oLeft.isBoolAndTrue():
    492501                return (oCondition.oRight, fMod);
    493             if isBoolTrue(oCondition.oRight):
     502            if oCondition.oRight.isBoolAndTrue():
    494503                return (oCondition.oLeft, fMod);
    495504
    496505        elif oCondition.sOp in ('==', '!='):
    497506            # The pattern we're looking for is identifier (field) == fixed value.
    498             print('debug transfer: %s: binaryop %s vs %s ...' % (sInstrNm, oCondition.oLeft.sType, oCondition.oRight.sType));
     507            #print('debug transfer: %s: binaryop %s vs %s ...' % (sInstrNm, oCondition.oLeft.sType, oCondition.oRight.sType));
    499508            if (    isinstance(oCondition.oLeft, ArmAstIdentifier)
    500509                and isinstance(oCondition.oRight, (ArmAstValue, ArmAstInteger))):
    501510                sFieldName = oCondition.oLeft.sName;
    502511                oValue     = oCondition.oRight;
    503                 print('debug transfer: %s: binaryop step 2...' % (sInstrNm,));
     512                #print('debug transfer: %s: binaryop step 2...' % (sInstrNm,));
    504513                for oField in aoEncodesets: # ArmEncodesetField
    505514                    if oField.sName and oField.sName == sFieldName:
    … …  
    512521                            assert oField.fValue == 0;
    513522                            if oValue.iValue.bit_length() > oField.cBitsWidth:
    514                                 raise Exception('%s: Condition field value check too wide: %s is %u bits, test value is %s (%u bits)'
     523                                raise Exception('%s: Condition field value check too wide: %s is %u bits, test value %s (%u bits)'
    515524                                                % (sInstrNm, oField.sName, oField.cBitsWidth, oValue.iValue,
    516525                                                   oValue.iValue.bit_count(),));
    … …  
    523532                                break;
    524533
    525                             print('debug transfer: %s: integer binaryop -> encoding!' % (sInstrNm,));
     534                            #print('debug transfer: %s: integer binaryop -> encoding: %s %s %#x/%#x'
     535                            #      % (sInstrNm, oField.sName, oCondition.sOp, oValue.iValue, fFixed));
    526536                            if oCondition.sOp == '==':
    527537                                oField.fValue = oValue.iValue;
    … …  
    542552                                            % (sInstrNm, oField.sName, oField.fValue, oField.fFixed, oCondition.sOp,
    543553                                               oValue.sValue, fValue, fFixed));
    544                         print('debug transfer: %s: value binaryop -> encoding! %s %s %#x (fFixed=%#x)'
    545                               % (sInstrNm, oField.sName, oCondition.sOp, fValue, fFixed,));
     554                        #print('debug transfer: %s: value binaryop -> encoding: %s %s %#x (fFixed=%#x)'
     555                        #      % (sInstrNm, oField.sName, oCondition.sOp, fValue, fFixed,));
    546556                        if oCondition.sOp == '==':
    547557                            oField.fValue |= fValue;
    … …  
    556566    #
    557567    if uDepth == 0 and dPendingNotEq:
     568        def recursiveRemove(oCondition, aoToRemove):
     569            if isinstance(oCondition, ArmAstBinaryOp):
     570                if oCondition.sOp == '&&':
     571                    oCondition.oLeft  = recursiveRemove(oCondition.oLeft, aoToRemove);
     572                    oCondition.oRight = recursiveRemove(oCondition.oLeft, aoToRemove);
     573                    if oCondition.oLeft.isBoolAndTrue():    return oCondition.oRight;
     574                    if oCondition.oRight.isBoolAndTrue():   return oCondition.oLeft;
     575                elif oCondition in aoToRemove:
     576                    assert isinstance(oCondition.oLeft, ArmAstIdentifier);
     577                    assert isinstance(oCondition.oRight, (ArmAstValue, ArmAstInteger));
     578                    assert oCondition.sOp == '!=';
     579                    return ArmAstBool(True);
     580            return oCondition;
     581
    558582        for sFieldNm, atOccurences in dPendingNotEq.items():
    559583            # For a two bit field, we need at least two occurences to get any kind of fixed value.
    … …  
    573597                        fFixed = 3;                                           # Both bits are fixed.
    574598                    fValue = afValues[0] & fFixed;
    575                     print('debug transfer: %s: %u binaryops -> encoding! %s != %#x/%#x'
    576                           % (sInstrNm, len(atOccurences), oField.sName, fValue, fFixed,));
     599                    print('debug transfer: %s: %u binaryops -> encoding: %s == %#x/%#x'
     600                          % (sInstrNm, len(atOccurences), sFieldNm, ~fValue & fFixed, fFixed,));
     601                    oField.fValue |= ~fValue & fFixed;
     602                    oField.fFixed |= fFixed;
     603
    577604
    578605                    # Remove the associated conditions (they'll be leaves).
    579                     aoToRemove = [oCondition for _, _, _, oCondition in atOccurences];
    580                     def recursiveRemove(oCondition):
    581                         if isinstance(oCondition, ArmAstBinaryOp):
    582                             if oCondition.sOp == '&&':
    583                                 oCondition.oLeft  = recursiveRemove(oCondition.oLeft);
    584                                 oCondition.oRight = recursiveRemove(oCondition.oLeft);
    585                                 if isBoolTrue(oCondition.oLeft):    return oCondition.oRight;
    586                                 if isBoolTrue(oCondition.oRight):   return oCondition.oLeft;
    587                             elif oCondition in aoToRemove:
    588                                 assert isinstance(oCondition.oLeft, ArmAstIdentifier);
    589                                 assert isinstance(oCondition.oRight, (ArmAstValue, ArmAstInteger));
    590                                 assert oCondition.sOp == '!=';
    591                                 return ArmAstBool(True);
    592                         return oCondition;
    593                     oCondition = recursiveRemove(oCondition);
     606                    oCondition = recursiveRemove(oCondition, [oCondition for _, _, _, oCondition in atOccurences]);
    594607                    fMod = True;
    595608                else:
    596609                    print('info: %s: transfer cond to enc failed for: %s dValues=%s dFixed=%s'
    597                           % (sInstrNm, oField.sName, dValues, dFixed));
     610                          % (sInstrNm, sFieldNm, dValues, dFixed));
    598611            elif oField.cBitsWidth == 3 and len(atOccurences) >= 7:
    599                 print('info: %s: TODO: transfer cond to enc for 3 bit field: %s (%s)' % (sInstrNm, oField.sName, atOccurences,));
     612                print('info: %s: TODO: transfer cond to enc for 3 bit field: %s (%s)' % (sInstrNm, sFieldNm, atOccurences,));
    600613
    601614    return (oCondition, fMod);
    … …  
    729742    #print("oBrk=%s" % (oBrk,))
    730743
    731     if True:
     744    if oOptions.fPrintInstructions:
    732745        for oInstr in g_aoAllArmInstructions:
    733746            print('%08x/%08x %s %s' % (oInstr.fFixedMask, oInstr.fFixedValue, oInstr.getCName(), oInstr.sAsmDisplay));
    734747
    735748    # Gather stats on fixed bits:
    736     if True:
     749    if oOptions.fPrintFixedMaskStats:
    737750        dCounts = collections.Counter();
    738751        for oInstr in g_aoAllArmInstructions:
    … …  
    747760
    748761    # Top 10 fixed masks.
    749     if True:
     762    if oOptions.fPrintFixedMaskTop10:
    750763        dCounts = collections.Counter();
    751764        for oInstr in g_aoAllArmInstructions:
    … …  
    764777#
    765778
    766 class MaskIterator(object):
     779class MaskIterator1(object):
    767780    """ Helper class for DecoderNode.constructNextLevel(). """
    768781
    … …  
    790803        elif len(dBits) > 0:
    791804            aaiMaskAlgo = DecoderNode.compactMaskAsList(list(dBits));
    792             if len(aaiMaskAlgo) <= MaskIterator.kcMaxMaskParts:
     805            if len(aaiMaskAlgo) <= MaskIterator1.kcMaxMaskParts:
    793806                dDictDoneAlready[fMask] = 1;
    794807                aiRet = [(fMask, list(dBits), aaiMaskAlgo)];
    … …  
    802815                if len(dBits) <= cMaxTableSizeInBits:
    803816                    aaiMaskAlgo = DecoderNode.compactMaskAsList(list(dBits));
    804                     if len(aaiMaskAlgo) <= MaskIterator.kcMaxMaskParts:
     817                    if len(aaiMaskAlgo) <= MaskIterator1.kcMaxMaskParts:
    805818                        dDictDoneAlready[fMask] = 1;
    806819                        aiRet.append((fMask, list(dBits), aaiMaskAlgo));
    … …  
    817830                recursive(fMask & ~(1 << iBit), dChildBits)
    818831
    819         print("debug: fMask=%#x len(aiRet)=%d" % (fMask, len(aiRet),));
     832        print("debug: fMask=%#x len(aiRet)=%d dDictDoneAlready=%d" % (fMask, len(aiRet), len(dDictDoneAlready)));
    820833        return aiRet;
     834
     835class MaskIterator2(object):
     836    """ Helper class for DecoderNode.constructNextLevel(). """
     837
     838    ## Maximum number of mask sub-parts.
     839    # Lower number means fewer instructions required to convert it into an index.
     840    kcMaxMaskParts = 3
     841
     842    class StackEntry(object):
     843        def __init__(self, fMask, aiBits):
     844            self.fMask  = fMask;
     845            self.aiBits = aiBits;
     846            self.iCur   = -1;
     847            #fTmp = 0;
     848            #for iBit in aiBits:
     849            #    fTmp |= 1 << iBit;
     850            #assert fTmp == fMask, 'fTmp=%#x fMask=%#x aiBits=%s' % (fTmp, fMask, aiBits);
     851
     852    def __init__(self, fMask, cMaxTableSizeInBits, dDictDoneAlready):
     853        self.fMask               = fMask;
     854        self.cMaxTableSizeInBits = cMaxTableSizeInBits;
     855        self.dDictDoneAlready    = dDictDoneAlready;
     856        self.cReturned           = 0;
     857        self.cLoops              = 0;
     858
     859        dBits = collections.OrderedDict();
     860        for iBit in range(32):
     861            if fMask & (1 << iBit):
     862                dBits[iBit] = 1;
     863        self.oTop                = self.StackEntry(fMask, list(dBits));
     864        self.aoStack             = [];
     865
     866    def __iter__(self):
     867        return self;
     868
     869    def __next__(self):
     870        oTop = self.oTop;
     871        while oTop:
     872            self.cLoops += 1
     873            iCur     = oTop.iCur;
     874            cCurBits = len(oTop.aiBits);
     875            if iCur < 0:
     876                # Return self if appropriate
     877                if (    0 < cCurBits < self.cMaxTableSizeInBits
     878                    and oTop.fMask not in self.dDictDoneAlready):
     879                    aaiMaskAlgo = []#DecoderNode.compactMaskAsList(oTop.aiBits);
     880                    if len(aaiMaskAlgo) <= MaskIterator2.kcMaxMaskParts:
     881                        oTop.iCur = 0;
     882                        self.dDictDoneAlready[oTop.fMask] = 1;
     883                        self.cReturned += 1;
     884                        #return (oTop.fMask, oTop.aiBits, aaiMaskAlgo);
     885                iCur = 0;
     886
     887            if iCur < cCurBits and cCurBits > 1:
     888                # push
     889                oTop.iCur = iCur + 1;
     890                self.aoStack.append(oTop);
     891                oTop = self.StackEntry(oTop.fMask & ~(1 << oTop.aiBits[iCur]), oTop.aiBits[:iCur] + oTop.aiBits[iCur + 1:]);
     892                self.oTop = oTop;
     893            else:
     894                # pop.
     895                oTop.iCur = 0xff;
     896                oTop = self.aoStack.pop() if self.aoStack else None;
     897                self.oTop = oTop;
     898        # Done;
     899        print('MaskIterator2: fMask=%#x -> %u items returned; %u loops' % (self.fMask, self.cReturned, self.cLoops));
     900        raise StopIteration;
     901
     902class MaskIterator(object):
     903    """ Helper class for DecoderNode.constructNextLevel(). """
     904
     905    ## Maximum number of mask sub-parts.
     906    # Lower number means fewer instructions required to convert it into an index.
     907    # This is implied by the code in compileMaskCompactorLimited.
     908    kcMaxMaskParts = 3
     909
     910    def __init__(self, fMask, cMaxTableSizeInBits, dDictDoneAlready):
     911        self.fMask               = fMask;
     912        self.aaiAlgo             = MaskIterator.compileMaskCompactor(fMask);
     913        self.fCompactMask        = DecoderNode.toIndexByMask(fMask, self.aaiAlgo);
     914        #print('debug: fMask=%#x -> fCompactMask=%#x aaiAlgo=%s' % (fMask, self.fCompactMask, self.aaiAlgo));
     915        self.fnExpandMask        = DecoderNode.compactDictAlgoToLambdaRev(self.aaiAlgo);
     916        self.cMaxTableSizeInBits = cMaxTableSizeInBits;
     917        self.dDictDoneAlready    = dDictDoneAlready;
     918        self.cReturned           = 0;
     919
     920    @staticmethod
     921    def compileMaskCompactor(fMask):
     922        """
     923        Returns an with instructions for extracting the bits from the mask into
     924        a compacted form. Each array entry is an array/tuple of source bit [0],
     925        destination bit [1], and bit counts [2].
     926        """
     927        aaiAlgo   = [];
     928        iSrcBit   = 0;
     929        iDstBit   = 0;
     930        while fMask > 0:
     931            # Skip leading zeros.
     932            cSkip    = (fMask & -fMask).bit_length() - 1;
     933            #assert (fMask & ((1 << cSkip) - 1)) == 0 and ((fMask >> cSkip) & 1), 'fMask=%#x cSkip=%d' % (fMask, cSkip)
     934            iSrcBit += cSkip;
     935            fMask  >>= cSkip;
     936
     937            # Calculate leading ones the same way.
     938            cCount = (~fMask & -~fMask).bit_length() - 1;
     939            #assert (fMask & ((1 << cCount) - 1)) == ((1 << cCount) - 1) and (fMask & (1 << cCount)) == 0
     940
     941            # Append to algo list.
     942            aaiAlgo.append((iSrcBit, iDstBit, (1 << cCount) - 1));
     943
     944            # Advance.
     945            iDstBit += cCount;
     946            iSrcBit += cCount;
     947            fMask  >>= cCount;
     948        return aaiAlgo;
     949
     950    @staticmethod
     951    def compileMaskCompactorLimited(fMask):
     952        """
     953        Version of compileMaskCompactor that returns an empty list if there are
     954        more than three sections.
     955        """
     956        assert fMask;
     957
     958        #
     959        # Chunk 0:
     960        #
     961
     962        # Skip leading zeros.
     963        iSrcBit0 = (fMask & -fMask).bit_length() - 1;
     964        fMask  >>= iSrcBit0;
     965        # Calculate leading ones the same way.
     966        cCount0  = (~fMask & -~fMask).bit_length() - 1;
     967        fMask  >>= cCount0;
     968        if not fMask:
     969            return [(iSrcBit0, 0, (1 << cCount0) - 1)];
     970
     971        #
     972        # Chunk 1:
     973        #
     974
     975        # Skip leading zeros.
     976        cSrcGap1 = (fMask & -fMask).bit_length() - 1;
     977        fMask  >>= cSrcGap1;
     978        # Calculate leading ones the same way.
     979        cCount1  = (~fMask & -~fMask).bit_length() - 1;
     980        fMask  >>= cCount1;
     981        if not fMask:
     982            return [ (iSrcBit0, 0, (1 << cCount0) - 1),
     983                     (iSrcBit0 + cCount0 + cSrcGap1, cCount0, (1 << cCount1) - 1)];
     984
     985        #
     986        # Chunk 2:
     987        #
     988
     989        # Skip leading zeros.
     990        cSrcGap2 = (fMask & -fMask).bit_length() - 1;
     991        fMask  >>= cSrcGap2;
     992        # Calculate leading ones the same way.
     993        cCount2  = (~fMask & -~fMask).bit_length() - 1;
     994        fMask  >>= cCount2;
     995        if not fMask:
     996            iSrcBit1 = iSrcBit0 + cCount0 + cSrcGap1;
     997            return [ (iSrcBit0, 0, (1 << cCount0) - 1),
     998                     (iSrcBit1, cCount0, (1 << cCount1) - 1),
     999                     (iSrcBit1 + cCount1 + cSrcGap2, cCount0 + cCount1, (1 << cCount2) - 1), ];
     1000
     1001        # Too many fragments.
     1002        return [];
     1003
     1004    @staticmethod
     1005    def maskCompactorAlgoToBitList(aaiAlgo):
     1006        aiRet = [];
     1007        for iSrcBit, _, fMask in aaiAlgo:
     1008            cCount = fMask.bit_count();
     1009            aiRet += [iSrcBit + i for i in range(cCount)];
     1010        return aiRet;
     1011
     1012    def __iter__(self):
     1013        return self;
     1014
     1015    def __next__(self):
     1016        fCompactMask = self.fCompactMask;
     1017        while fCompactMask != 0:
     1018            cCurBits = fCompactMask.bit_count();
     1019            if cCurBits <= self.cMaxTableSizeInBits:
     1020                fMask = self.fnExpandMask(fCompactMask);
     1021                if fMask not in self.dDictDoneAlready:
     1022                    aaiMaskAlgo = MaskIterator.compileMaskCompactorLimited(fMask);
     1023                    if aaiMaskAlgo:
     1024                        #assert aaiMaskAlgo == MaskIterator.compileMaskCompactor(fMask), \
     1025                        #    '%s vs %s' % (aaiMaskAlgo, MaskIterator.compileMaskCompactor(fMask));
     1026                        self.dDictDoneAlready[fMask] = 1;
     1027                        self.fCompactMask = fCompactMask - 1;
     1028                        self.cReturned += 1;
     1029                        return (fMask, MaskIterator.maskCompactorAlgoToBitList(aaiMaskAlgo), aaiMaskAlgo);
     1030            fCompactMask -= 1;
     1031        self.fCompactMask = 0;
     1032        #print('MaskIterator: fMask=%#x -> %u items returned' % (self.fMask, self.cReturned));
     1033        raise StopIteration;
     1034
    8211035
    8221036class DecoderNode(object):
    … …  
    8411055    );
    8421056
    843     def __init__(self, aoInstructions: list[ArmInstruction], fCheckedMask: int, fCheckedValue: int, uDepth: int):
     1057    def __init__(self, aoInstructions, fCheckedMask, fCheckedValue, uDepth):
    8441058        assert (~fCheckedMask & fCheckedValue) == 0;
    8451059        for idxInstr, oInstr in enumerate(aoInstructions):
    8461060            assert ((oInstr.fFixedValue ^ fCheckedValue) & fCheckedMask & oInstr.fFixedMask) == 0, \
    847                     '%s: fFixedValue=%#x fFixedMask=%#x fCheckedValue=%#x fCheckedMask=%#x -> %#x\n %s' \
     1061                    '%s: fFixedValue=%#x fFixedMask=%#x fCheckedValue=%#x fCheckedMask=%#x -> %#x\naoInstructions: len=%s\n %s' \
    8481062                    % (idxInstr, oInstr.fFixedValue, oInstr.fFixedMask, fCheckedValue, fCheckedMask,
    8491063                       (oInstr.fFixedValue ^ fCheckedValue) & fCheckedMask & oInstr.fFixedMask,
    850                        '\n '.join(['%s: %#010x/%#010x %s' % (i, oInstr2.fFixedValue, oInstr2.fFixedMask, oInstr2.sName)
    851                                      for i, oInstr2 in enumerate(aoInstructions[:idxInstr+2])]));
     1064                       len(aoInstructions),
     1065                       '\n '.join(['%s%s: %#010x/%#010x %s' % ('*' if i == idxInstr else ' ', i,
     1066                                                               oInstr2.fFixedValue, oInstr2.fFixedMask, oInstr2.sName)
     1067                                   for i, oInstr2 in enumerate(aoInstructions[:idxInstr+8])]));
    8521068
    8531069        self.aoInstructions     = aoInstructions;   ##< The instructions at this level.
    … …  
    8711087        iDstBit   = 0;
    8721088        while fMask > 0:
    873             if fMask & 1:
    874                 cCount = 1
     1089            # Skip leading zeros.
     1090            cSkip    = (fMask & -fMask).bit_length() - 1;
     1091            assert (fMask & ((1 << cSkip) - 1)) == 0 and ((fMask >> cSkip) & 1), 'fMask=%#x cSkip=%d' % (fMask, cSkip)
     1092            iSrcBit += cSkip;
     1093            fMask  >>= cSkip;
     1094
     1095            # Calculate leading ones the same way.
     1096            cCount1 = (~fMask & -~fMask).bit_length() - 1;
     1097            cCount = 1
     1098            fMask >>= 1;
     1099            while fMask & 1:
    8751100                fMask >>= 1;
    876                 while fMask & 1:
    877                     fMask >>= 1;
    878                     cCount += 1
    879                 aaiAlgo.append([iSrcBit, iDstBit, cCount])
    880                 iSrcBit   += cCount;
    881                 iDstBit   += cCount;
    882             else:
    883                 iSrcBit += 1;
     1101                cCount += 1
     1102            assert cCount1 == cCount;
     1103            aaiAlgo.append([iSrcBit, iDstBit, (1 << cCount) - 1])
     1104            iSrcBit   += cCount;
     1105            iDstBit   += cCount;
    8841106        return aaiAlgo;
    8851107
    8861108    @staticmethod
    887     def compactMaskAsList(dOrderedDict):
     1109    def compactMaskAsList(aiOrderedBits):
    8881110        """
    8891111        Returns an with instructions for extracting the bits from the mask into
    … …  
    8941116        iDstBit = 0;
    8951117        i       = 0;
    896         while i < len(dOrderedDict):
    897             iSrcBit = dOrderedDict[i];
     1118        while i < len(aiOrderedBits):
     1119            iSrcBit = aiOrderedBits[i];
    8981120            cCount  = 1;
    8991121            i      += 1;
    900             while i < len(dOrderedDict) and dOrderedDict[i] == iSrcBit + cCount:
     1122            while i < len(aiOrderedBits) and aiOrderedBits[i] == iSrcBit + cCount:
    9011123                cCount += 1;
    9021124                i      += 1;
    … …  
    9071129    @staticmethod
    9081130    def compactDictAlgoToLambda(aaiAlgo):
    909         assert(aaiAlgo)
     1131        assert aaiAlgo;
    9101132        sBody = '';
    9111133        for iSrcBit, iDstBit, fMask in aaiAlgo:
    … …  
    9241146    @staticmethod
    9251147    def compactDictAlgoToLambdaRev(aaiAlgo):
    926         assert(aaiAlgo)
     1148        assert aaiAlgo;
    9271149        sBody = '';
    9281150        for iSrcBit, iDstBit, fMask in aaiAlgo:
    … …  
    9571179        Recursively constructs the
    9581180        """
     1181        #
    9591182        # Special case: leaf.
     1183        #
    9601184        if len(self.aoInstructions) <= 1:
    9611185            assert len(self.aoChildren) == 0;
    9621186            return 16 if self.fLeafCheckNeeded else 0;
    963 
     1187        sDbgPrefix = 'debug/%u: %s' % (self.uDepth, '  ' * self.uDepth);
     1188
     1189        #
    9641190        # Do an inventory of the fixed masks used by the instructions.
     1191        #
    9651192        dMaskCounts = collections.Counter();
    9661193        for oInstr in self.aoInstructions:
    … …  
    9691196                'dMaskCounts=%s len(self.aoInstructions)=%s\n%s' % (dMaskCounts, len(self.aoInstructions),self.aoInstructions);
    9701197
    971         # Determine the max table size for the number of instructions we have.
    972         cInstructionsAsShift = 1;
    973         while (1 << cInstructionsAsShift) < len(self.aoInstructions):
    974             cInstructionsAsShift += 1;
     1198        ## Determine the max table size for the number of instructions we have.
     1199        #cInstructionsAsShift = 1;
     1200        #while (1 << cInstructionsAsShift) < len(self.aoInstructions):
     1201        #    cInstructionsAsShift += 1;
    9751202        #cMaxTableSizeInBits = self.kacMaxTableSizesInBits[cInstructionsAsShift];
    9761203
    977         # Work thru the possible masks and test out the possible variations (brute force style).
     1204        #
     1205        # Work thru the possible masks and test out the variations (brute force style).
     1206        #
    9781207        uCostBest        = 0x7fffffffffffffff;
    9791208        fChildrenBest    = 0;
    980         aoChildrenBest   = None;
    981         dDictDoneAlready = {}
     1209        aoChildrenBest   = [];
     1210
     1211        dDictDoneAlready = {};
    9821212        for fOrgMask, cOccurences in dMaskCounts.most_common(8):
    9831213            cOccurencesAsShift = 1;
    … …  
    9851215                cOccurencesAsShift += 1;
    9861216            cMaxTableSizeInBits = self.kacMaxTableSizesInBits[cOccurencesAsShift]; # Not quite sure about this...
    987             print('debug: %#010x (%u) - %u instructions - max tab size %u'
    988                   % (fOrgMask, self.popCount(fOrgMask), cOccurences, cMaxTableSizeInBits,));
     1217            if self.uDepth <= 1:
     1218                print('%s===== Start: %#010x (%u) - %u instructions - max tab size %u ====='
     1219                      % (sDbgPrefix, fOrgMask, self.popCount(fOrgMask), cOccurences, cMaxTableSizeInBits,));
    9891220
    9901221            # Skip pointless stuff.
    9911222            if cOccurences >= 2 and fOrgMask > 0 and fOrgMask != 0xffffffff:
    992 
    993                 # Brute force all the mask variations (minus those which are too wide).
     1223                #
     1224                # Brute force relevant mask variations.
     1225                # (The MaskIterator skips masks that are too wide and too fragmented.)
     1226                #
    9941227                for fMask, dOrderedDictMask, aaiMaskToIdxAlgo in MaskIterator(fOrgMask, cMaxTableSizeInBits, dDictDoneAlready):
    995                     print('debug: >>> fMask=%#010x...' % (fMask,));
     1228                    #print('%s>>> fMask=%#010x dOrderedDictMask=%s aaiMaskToIdxAlgo=%s)...'
     1229                    #      % (sDbgPrefix, fMask, dOrderedDictMask, aaiMaskToIdxAlgo));
    9961230                    assert len(dOrderedDictMask) <= cMaxTableSizeInBits;
     1231
     1232                    # Compile the indexing/unindexing functions.
    9971233                    fnToIndex   = self.compactDictAlgoToLambda(aaiMaskToIdxAlgo);
    9981234                    fnFromIndex = self.compactDictAlgoToLambdaRev(aaiMaskToIdxAlgo);
    9991235
     1236                    # Create an temporary table empty with empty lists as entries.
     1237                    ## @todo is there a better way for doing this? collections.defaultdict?
    10001238                    aaoTmp = [];
    1001                     for i in range(1 << len(dOrderedDictMask)):
    1002                         aaoTmp.append(list());
    1003 
     1239                    for _ in range(1 << len(dOrderedDictMask)):
     1240                        aaoTmp.append([]);
     1241
     1242                    # Insert the instructions into the temporary table.
    10041243                    for oInstr in self.aoInstructions:
    10051244                        idx = fnToIndex(oInstr.fFixedValue);
    1006                         #idx = self.toIndexByMask(oInstr.fFixedValue, aaiMaskToIdxAlgo)
    1007                         assert idx == self.toIndexByMask(oInstr.fFixedValue & fMask, aaiMaskToIdxAlgo);
    1008                         print('debug: %#010x -> %#05x %s' % (oInstr.fFixedValue, idx, oInstr.sName));
     1245                        #assert idx == self.toIndexByMask(oInstr.fFixedValue & fMask, aaiMaskToIdxAlgo);
     1246                        #assert idx == fnToIndex(fnFromIndex(idx));
     1247                        #print('%s%#010x -> %#05x %s' % (sDbgPrefix, oInstr.fFixedValue, idx, oInstr.sName));
    10091248                        aoList = aaoTmp[idx];
    10101249                        aoList.append(oInstr);
    10111250
     1251                    # Construct decoder nodes from the aaoTmp lists, construct sub-levels and calculate costs.
     1252                    uCostTmp      = 0; ## @todo calc base cost from table size and depth.
    10121253                    aoChildrenTmp = [];
    1013                     uCostTmp      = 0;
    10141254                    for idx, aoInstrs in enumerate(aaoTmp):
    10151255                        oChild = DecoderNode(aoInstrs,
    … …  
    10201260                        uCostTmp += oChild.constructNextLevel();
    10211261
     1262                    # Is this mask better than the previous?
    10221263                    if uCostTmp < uCostBest:
     1264                        if self.uDepth <= 1:
     1265                            print('%s~~~ New best! fMask=%#010x uCost=%#x (previous %#010x / %#x) ...'
     1266                                  % (sDbgPrefix, fMask, uCostTmp, fChildrenBest, uCostBest, ));
    10231267                        uCostBest      = uCostTmp;
    10241268                        fChildrenBest  = fMask;
    10251269                        aoChildrenBest = aoChildrenTmp;
    10261270
     1271        if self.uDepth <= 1:
     1272            print('%s===== Final: fMask=%#010x uCost=%#x TabSize=%#x Instructions=%u...'
     1273                  % (sDbgPrefix, fChildrenBest, uCostBest, len(aoChildrenBest), len(self.aoInstructions)));
    10271274        if aoChildrenBest is None:
    10281275            pass; ## @todo
     1276
     1277        # Done.
     1278        self.fChildMask = fChildrenBest;
     1279        self.aoChildren = aoChildrenBest;
     1280        self.uCost      = uCostBest;
     1281
    10291282        return uCostBest;
    1030 
    1031 
    1032 
    1033 
    1034 
    1035 
    1036 
    10371283
    10381284
    … …  
    10511297        Creates the decoder to the best our abilities.
    10521298        """
    1053         global g_aoAllArmInstructions;
    10541299        self.oDecoderRoot = DecoderNode(g_aoAllArmInstructions, 0, 0, 0);
    10551300        self.oDecoderRoot.constructNextLevel();
    … …  
    11751420        """ Main function. """
    11761421
     1422        #for _ in MaskIterator(0xffc0ff00, 12, {}):
     1423        #    pass;
     1424        #return 2;
     1425
    11771426        #
    11781427        # Parse arguments.
    … …  
    12151464                                default = '-',
    12161465                                help    = 'The output C++ file for the decoder.');
     1466        # debug:
     1467        oArgParser.add_argument('--print-instructions',
     1468                                dest    = 'fPrintInstructions',
     1469                                action  = 'store_true',
     1470                                default = False,
     1471                                help    = 'List the instructions after loading.');
     1472        oArgParser.add_argument('--print-fixed-mask-stats',
     1473                                dest    = 'fPrintFixedMaskStats',
     1474                                action  = 'store_true',
     1475                                default = False,
     1476                                help    = 'List statistics on fixed bit masks.');
     1477        oArgParser.add_argument('--print-fixed-mask-top-10',
     1478                                dest    = 'fPrintFixedMaskTop10',
     1479                                action  = 'store_true',
     1480                                default = False,
     1481                                help    = 'List the 10 top fixed bit masks.');
     1482        # Do it!
    12171483        oOptions = oArgParser.parse_args(asArgs[1:]);
    12181484
    … …  
    12541520        return 1;
    12551521
     1522def printException(oXcpt):
     1523    print('----- Exception Caught! -----', flush = True);
     1524    cMaxLines = 1;
     1525    try:    cchMaxLen = os.get_terminal_size()[0] * cMaxLines;
     1526    except: cchMaxLen = 80 * cMaxLines;
     1527    cchMaxLen -= len('     =  ...');
     1528
     1529    oTB = traceback.TracebackException.from_exception(oXcpt, limit = None, capture_locals = True);
     1530    # No locals for the outer frame.
     1531    oTB.stack[0].locals = {};
     1532    # Suppress insanely long variable values.
     1533    for oFrameSummary in oTB.stack:
     1534        if oFrameSummary.locals:
     1535            #for sToDelete in ['ddAsmRules', 'aoInstructions',]:
     1536            #    if sToDelete in oFrameSummary.locals:
     1537            #        del oFrameSummary.locals[sToDelete];
     1538            for sKey, sValue in oFrameSummary.locals.items():
     1539                if len(sValue) > cchMaxLen - len(sKey):
     1540                    sValue = sValue[:cchMaxLen - len(sKey)] + ' ...';
     1541                if '\n' in sValue:
     1542                    sValue = sValue.split('\n')[0] + ' ...';
     1543                oFrameSummary.locals[sKey] = sValue;
     1544    idxFrame = 0;
     1545    asFormatted = [];
     1546    oReFirstFrameLine = re.compile(r'^  File ".*", line \d+, in ')
     1547    for sLine in oTB.format():
     1548        if oReFirstFrameLine.match(sLine):
     1549            idxFrame += 1;
     1550        asFormatted.append(sLine);
     1551    for sLine in asFormatted:
     1552        if oReFirstFrameLine.match(sLine):
     1553            idxFrame -= 1;
     1554            sLine = '#%u %s' % (idxFrame, sLine.lstrip());
     1555        print(sLine);
     1556    print('----', flush = True);
    12561557
    12571558if __name__ == '__main__':
     1559    #for fOrgMask in (1, 3, 7, 15, 31):
     1560    #    print('Test %#x:' % (fOrgMask,));
     1561    #    for x in MaskIterator(fOrgMask, 16, {}):
     1562    #        print('MaskIterator: fMask=%#04x aiBits=%20s aaiAlgo=%s' % (x[0],x[1],x[2]));
     1563    fProfileIt = True;
     1564    oProfiler = cProfile.Profile() if fProfileIt else None;
    12581565    try:
    1259         sys.exit(IEMArmGenerator().main(sys.argv));
    1260     except Exception as oXcpt:
    1261         print('Exception Caught!', flush = True);
    1262         cMaxLines = 1;
    1263         try:    cchMaxLen = os.get_terminal_size()[0] * cMaxLines;
    1264         except: cchMaxLen = 80 * cMaxLines;
    1265         cchMaxLen -= len('     =  ...');
    1266 
    1267         oTB = traceback.TracebackException.from_exception(oXcpt, limit = None, capture_locals = True);
    1268         # No locals for the outer frame.
    1269         oTB.stack[0].locals = {};
    1270         # Suppress insanely long variable values.
    1271         for oFrameSummary in oTB.stack:
    1272             if oFrameSummary.locals:
    1273                 #for sToDelete in ['ddAsmRules', 'aoInstructions',]:
    1274                 #    if sToDelete in oFrameSummary.locals:
    1275                 #        del oFrameSummary.locals[sToDelete];
    1276                 for sKey, sValue in oFrameSummary.locals.items():
    1277                     if len(sValue) > cchMaxLen - len(sKey):
    1278                         sValue = sValue[:cchMaxLen - len(sKey)] + ' ...';
    1279                     if '\n' in sValue:
    1280                         sValue = sValue.split('\n')[0] + ' ...';
    1281                     oFrameSummary.locals[sKey] = sValue;
    1282         oTB.print();
    1283 
     1566        if not oProfiler:
     1567            rcExit = IEMArmGenerator().main(sys.argv);
     1568        else:
     1569            rcExit = oProfiler.runcall(IEMArmGenerator().main, sys.argv);
     1570    except Exception as oXcptOuter:
     1571        printException(oXcptOuter);
     1572        rcExit = 2;
     1573    except KeyboardInterrupt as oXcptOuter:
     1574        printException(oXcptOuter);
     1575        rcExit = 2;
     1576    if oProfiler:
     1577        oProfiler.print_stats(sort='tottime');
     1578    sys.exit(rcExit);
     1579
     1580
Note: See TracChangeset for help on using the changeset viewer.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette