Changeset 4117 in CLRX


Ignore:
Timestamp:
May 8, 2018, 7:17:58 PM (6 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Add varRoutineMap and varCallMap (holds lv indices for used variables inside routine or in call) to AsmRegAllocator?.
These fields will be used for generating interference graph.

Location:
CLRadeonExtender/trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • CLRadeonExtender/trunk/CLRX/amdasm/Assembler.h

    r4089 r4117  
    355355        VectorSet<size_t> nextVidxes;
    356356    };
     357   
     358    struct VVarSetEntry
     359    {
     360        std::unordered_set<size_t> vvars[MAX_REGTYPES_NUM];
     361    };
    357362private:
    358363    Assembler& assembler;
     
    367372    Array<cxuint> graphColorMaps[MAX_REGTYPES_NUM];
    368373    std::unordered_map<size_t, LinearDep> linearDepMaps[MAX_REGTYPES_NUM];
     374    // key - routine block, value - set of svvregs (lv indexes) used in routine
     375    std::unordered_map<size_t, VVarSetEntry> varRoutineMap;
     376    // key - call block, value - set of svvregs (lv indexes) used between this call point
     377    std::unordered_map<size_t, VVarSetEntry> varCallMap;
    369378   
    370379public:
     
    396405    const VarIndexMap* getVregIndexMaps() const
    397406    { return vregIndexMaps; }
     407   
     408    const std::unordered_map<size_t, VVarSetEntry>& getVarRoutineMap() const
     409    { return varRoutineMap; }
     410    const std::unordered_map<size_t, VVarSetEntry>& getVarCallMap() const
     411    { return varCallMap; }
    398412};
    399413
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp

    r4116 r4117  
    702702}
    703703
    704 static Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
    705         const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
    706         const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
     704static void getLivenessIndex(const AsmSingleVReg& svreg, size_t ssaIdIdx,
     705        const AsmRegAllocator::SSAInfo& ssaInfo,
     706        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
     707        cxuint& regType, size_t& lvIndex)
    707708{
    708709    size_t ssaId;
     
    718719        ssaId = ssaInfo.ssaIdLast;
    719720   
    720     cxuint regType = getRegType(regTypesNum, regRanges, svreg); // regtype
     721    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
    721722    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    722723    const std::vector<size_t>& ssaIdIndices = vregIndexMap.find(svreg)->second;
    723     ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaIdIdx: " <<
     724    /*ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaIdIdx: " <<
    724725            ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
    725             svreg.index << "\n";
    726     return livenesses[regType][ssaIdIndices[ssaId]];
    727 }
    728 
    729 static Liveness& getLiveness2(const AsmSingleVReg& svreg,
    730         size_t ssaId, std::vector<Liveness>* livenesses,
     726            svreg.index << "\n";*/
     727    //return livenesses[regType][ssaIdIndices[ssaId]];
     728    lvIndex = ssaIdIndices[ssaId];
     729}
     730
     731static inline Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
     732        const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
    731733        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
    732734{
    733     cxuint regType = getRegType(regTypesNum, regRanges, svreg); // regtype
     735    cxuint regType;
     736    size_t lvIndex;
     737    getLivenessIndex(svreg, ssaIdIdx, ssaInfo, vregIndexMaps, regTypesNum, regRanges,
     738            regType, lvIndex);
     739    return livenesses[regType][lvIndex];
     740}
     741
     742static void getLiveness2Index(const AsmSingleVReg& svreg, size_t ssaId,
     743        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
     744        cxuint& regType, size_t& lvIndex)
     745{
     746    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
    734747    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    735748    const std::vector<size_t>& ssaIdIndices = vregIndexMap.find(svreg)->second;
    736     ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaId: " <<
    737             ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";
    738     return livenesses[regType][ssaIdIndices[ssaId]];
    739 }
    740 
     749    /*ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaId: " <<
     750            ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";*/
     751    lvIndex = ssaIdIndices[ssaId];
     752}
     753
     754
     755static void addVVRegsToCallEntry(size_t blockIndex, cxuint regType, size_t lvIndex,
     756            const std::vector<CodeBlock>& codeBlocks,
     757            std::unordered_map<size_t, VVarSetEntry>& varCallMap,
     758            const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap)
     759{
     760    const CodeBlock& cblock = codeBlocks[blockIndex];
     761    if (cblock.haveCalls)
     762    {
     763        VVarSetEntry& varCallEntry = varCallMap[blockIndex];
     764        for (const NextBlock& next: cblock.nexts)
     765            if (next.isCall)
     766            {
     767                const auto& allLvs = varRoutineMap.find(next.block)->second;
     768                if (allLvs.vvars[regType].find(lvIndex) == allLvs.vvars[regType].end())
     769                    // add callLiveTime only if vreg not present in routine
     770                    varCallEntry.vvars[regType].insert(lvIndex);
     771            }
     772    }
     773}
    741774
    742775static void fillUpInsideRoutine(std::vector<bool>& visited,
    743776            const std::vector<CodeBlock>& codeBlocks,
    744             size_t startBlock, const AsmSingleVReg& svreg, Liveness& lv)
     777            std::unordered_map<size_t, VVarSetEntry>& varCallMap,
     778            const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap,
     779            size_t startBlock, const AsmSingleVReg& svreg, Liveness& lv,
     780            cxuint lvRType /* lv register type */, size_t lvIndex)
    745781{
    746782    std::deque<FlowStackEntry3> flowStack;
     
    771807                // just insert
    772808                lv.insert(cbStart, cblock.end);
     809               
     810                addVVRegsToCallEntry(entry.blockIndex, lvRType, lvIndex,
     811                        codeBlocks, varCallMap, varRoutineMap);
    773812            }
    774813            else
     
    799838static void joinVRegRecur(const std::deque<FlowStackEntry3>& flowStack,
    800839            const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
     840            std::unordered_map<size_t, VVarSetEntry>& varCallMap,
     841            const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap,
    801842            LastVRegStackPos flowStkStart, const AsmSingleVReg& svreg, size_t ssaId,
    802843            const VarIndexMap* vregIndexMaps, std::vector<Liveness>* livenesses,
     
    814855    if (skipLastBlock)
    815856        --flitEnd; // before last element
    816     Liveness& lv = getLiveness2(svreg, ssaId, livenesses, vregIndexMaps,
    817                     regTypesNum, regRanges);
     857    cxuint lvRegType;
     858    size_t lvIndex;
     859    getLiveness2Index(svreg, ssaId, vregIndexMaps, regTypesNum, regRanges,
     860                      lvRegType, lvIndex);
     861    Liveness& lv = livenesses[lvRegType][lvIndex];
    818862   
    819863    if (flitEnd != flowStack.begin())
     
    875919            /* if inSubroutines, then first block
    876920             * (that with subroutines calls) will be skipped */
    877             fillUpInsideRoutine(visited, codeBlocks,
    878                     entry.blockIndex + (entry.inSubroutines), svreg, lv);
     921            fillUpInsideRoutine(visited, codeBlocks, varCallMap, varRoutineMap,
     922                    entry.blockIndex + (entry.inSubroutines), svreg,
     923                    lv, lvRegType, lvIndex);
    879924            rjStack.pop();
    880925        }
     
    890935        if (sinfoIt != lastBlk.ssaInfoMap.end())
    891936        {
     937            if (flit->nextIndex > lastBlk.nexts.size())
     938                // only if pass this routine
     939                addVVRegsToCallEntry(flit->blockIndex, lvRegType, lvIndex,
     940                        codeBlocks, varCallMap, varRoutineMap);
    892941            // if begin at some point at last block
    893942            lastPos = sinfoIt->second.lastPos;
     
    900949    {
    901950        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
     951        if (flit->nextIndex > cblock.nexts.size())
     952            // only if pass this routine
     953            addVVRegsToCallEntry(flit->blockIndex, lvRegType, lvIndex, codeBlocks,
     954                        varCallMap, varRoutineMap);
    902955        lv.insert(cblock.start, cblock.end);
    903956    }
     
    911964static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
    912965        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
     966        std::unordered_map<size_t, VVarSetEntry>& varCallMap,
     967        const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap,
    913968        const LastVRegMap& lastVRegMap, std::vector<Liveness>* livenesses,
    914969        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
     
    924979                lvrit->second.back() : LastVRegStackPos{ 0, false };
    925980           
    926             joinVRegRecur(flowStack, codeBlocks, routineMap, flowStackStart,
    927                     entry.first, entry.second.ssaIdBefore, vregIndexMaps, livenesses,
    928                     regTypesNum, regRanges, true);
     981            joinVRegRecur(flowStack, codeBlocks, routineMap, varCallMap, varRoutineMap,
     982                    flowStackStart, entry.first, entry.second.ssaIdBefore,
     983                    vregIndexMaps, livenesses, regTypesNum, regRanges, true);
    929984        }
    930985}
     
    10771132static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
    10781133        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
     1134        std::unordered_map<size_t, VVarSetEntry>& varCallMap,
     1135        const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap,
    10791136        const PrevWaysIndexMap& prevWaysIndexMap,
    10801137        const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
     
    11821239                                        it->second : LastVRegStackPos{ 0, false });
    11831240                           
    1184                             joinVRegRecur(prevFlowStack, codeBlocks, routineMap, stackPos,
    1185                                 sentry.first, sentry.second.ssaIdBefore, vregIndexMaps,
    1186                                 livenesses, regTypesNum, regRanges, true);
     1241                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
     1242                                varCallMap, varRoutineMap,
     1243                                stackPos, sentry.first, sentry.second.ssaIdBefore,
     1244                                vregIndexMaps, livenesses, regTypesNum, regRanges, true);
    11871245                        }
    11881246                    }
     
    12051263                                        it->second : LastVRegStackPos{ 0, false });
    12061264                           
    1207                             joinVRegRecur(prevFlowStack, codeBlocks, routineMap, stackPos,
    1208                                 rsentry.first, rsentry.second, vregIndexMaps,
     1265                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
     1266                                varCallMap, varRoutineMap,
     1267                                stackPos, rsentry.first, rsentry.second, vregIndexMaps,
    12091268                                livenesses, regTypesNum, regRanges, true);
    12101269                        }
     
    13691428}
    13701429
    1371 static void joinRoutineDataLv(RoutineDataLv& dest, RoutineCurAccessMap& curSVRegMap,
    1372             FlowStackEntry4& entry, const RoutineDataLv& src)
     1430static void joinRoutineDataLv(RoutineDataLv& dest, VVarSetEntry& destVars,
     1431            RoutineCurAccessMap& curSVRegMap, FlowStackEntry4& entry,
     1432            const RoutineDataLv& src, const VVarSetEntry& srcVars)
    13731433{
    13741434    dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
    1375     dest.allLivenesses.insert(src.allLivenesses.begin(), src.allLivenesses.end());
     1435    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
     1436        destVars.vvars[i].insert(srcVars.vvars[i].begin(), srcVars.vvars[i].end());
    13761437   
    13771438    // join source lastAccessMap with curSVRegMap
     
    13941455
    13951456static void createRoutineDataLv(const std::vector<CodeBlock>& codeBlocks,
    1396         const RoutineLvMap& routineMap, RoutineDataLv& rdata,
     1457        const RoutineLvMap& routineMap,
     1458        const std::unordered_map<size_t, VVarSetEntry>& varRoutineMap,
     1459        RoutineDataLv& rdata, VVarSetEntry& routineVars,
    13971460        size_t routineBlock, const VarIndexMap* vregIndexMaps,
    1398         std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
     1461        size_t regTypesNum, const cxuint* regRanges)
    13991462{
    14001463    std::deque<FlowStackEntry4> flowStack;
     
    14491512                    // add SSA indices to allSSAs
    14501513                    if (sinfo.readBeforeWrite)
    1451                         rdata.allLivenesses.insert(livenesses[regType].data() +
    1452                                     ssaIdIndices[sinfo.ssaIdBefore]);
     1514                        routineVars.vvars[regType].insert(ssaIdIndices[sinfo.ssaIdBefore]);
    14531515                    if (sinfo.ssaIdChange != 0)
    14541516                    {
    1455                         rdata.allLivenesses.insert(livenesses[regType].data() +
    1456                                     ssaIdIndices[sinfo.ssaIdFirst]);
     1517                        routineVars.vvars[regType].insert(ssaIdIndices[sinfo.ssaIdFirst]);
    14571518                        for (size_t i = 1; i < sinfo.ssaIdChange; i++)
    1458                             rdata.allLivenesses.insert(livenesses[regType].data() +
    1459                                         ssaIdIndices[sinfo.ssaId+i]);
    1460                         rdata.allLivenesses.insert(livenesses[regType].data() +
    1461                                     ssaIdIndices[sinfo.ssaIdLast]);
     1519                            routineVars.vvars[regType].insert(ssaIdIndices[sinfo.ssaId+i]);
     1520                        routineVars.vvars[regType].insert(ssaIdIndices[sinfo.ssaIdLast]);
    14621521                    }
    14631522                }
     
    14821541           
    14831542            for (size_t srcRoutBlock: calledRoutines)
    1484                 joinRoutineDataLv(rdata, curSVRegMap, entry,
    1485                         routineMap.find(srcRoutBlock)->second);
     1543                joinRoutineDataLv(rdata, routineVars, curSVRegMap, entry,
     1544                        routineMap.find(srcRoutBlock)->second,
     1545                        varRoutineMap.find(srcRoutBlock)->second);
    14861546        }
    14871547       
     
    16521712                ARDOut << "joinpush: " << entry.blockIndex << "\n";
    16531713                if (flowStack.size() > 1)
    1654                     putCrossBlockLivenesses(flowStack, codeBlocks, routineMap, lastVRegMap,
     1714                    putCrossBlockLivenesses(flowStack, codeBlocks, routineMap,
     1715                            varCallMap, varRoutineMap, lastVRegMap,
    16551716                            livenesses, vregIndexMaps, regTypesNum, regRanges);
    16561717                // update last vreg position
     
    17841845            const size_t routineBlock = callStack.back().routineBlock;
    17851846            auto res = routineMap.insert({ routineBlock, { } });
     1847           
    17861848            if (res.second)
    1787                 createRoutineDataLv(codeBlocks, routineMap, res.first->second,
    1788                         routineBlock, vregIndexMaps, livenesses,
    1789                         regTypesNum, regRanges);
     1849            {
     1850                auto varRes = varRoutineMap.insert({ routineBlock, VVarSetEntry{} });
     1851                createRoutineDataLv(codeBlocks, routineMap, varRoutineMap,
     1852                        res.first->second, varRes.first->second,
     1853                        routineBlock, vregIndexMaps, regTypesNum, regRanges);
     1854            }
    17901855            else
    17911856            {
     
    17981863                            lvrit->second.back() : LastVRegStackPos{ 0, false };
    17991864                   
    1800                     joinVRegRecur(flowStack, codeBlocks, routineMap, flowStackStart,
    1801                             entry.first, entry.second, vregIndexMaps,
     1865                    joinVRegRecur(flowStack, codeBlocks, routineMap,
     1866                            varCallMap, varRoutineMap,
     1867                            flowStackStart, entry.first, entry.second, vregIndexMaps,
    18021868                            livenesses, regTypesNum, regRanges, false);
    18031869                }
     
    19021968            {
    19031969                joinRegVarLivenesses(flowStack, codeBlocks, routineMap,
     1970                        varCallMap, varRoutineMap,
    19041971                        prevWaysIndexMap, waysToCache, cblocksToCache,
    19051972                        joinFirstPointsCache, joinSecondPointsCache,
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.h

    r4110 r4117  
    4545typedef AsmRegAllocator::SSAInfo SSAInfo;
    4646typedef std::pair<const AsmSingleVReg, SSAInfo> SSAEntry;
     47typedef AsmRegAllocator::VVarSetEntry VVarSetEntry;
    4748
    4849//  BlockIndex
     
    232233    // holds all vreg SSA's used in routine (used while creating call point)
    233234    // includes subroutines called in this routines
    234     std::unordered_set<Liveness*> allLivenesses;
     235    std::unordered_set<size_t> allSSAs[MAX_REGTYPES_NUM];
    235236    // key - svreg, value - list of the last codeblocks where is svreg
    236237    LastAccessMap lastAccessMap;
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc3.cpp

    r4116 r4117  
    10001000        {
    10011001            {   // for SGPRs
    1002                 { { 29, 32 }, { 44, 53 }, { SIZE_MAX-1, SIZE_MAX } }, // 0: S0
     1002                { { 29, 32 }, { 44, 53 } }, // 0: S0
    10031003                { }, // 1: S1
    10041004                { }, // 2: S2
Note: See TracChangeset for help on using the changeset viewer.