Changeset 4054 in CLRX


Ignore:
Timestamp:
Apr 30, 2018, 4:14:20 PM (5 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Add yet another simple testcase for createSSAData. Tentative a working joining a visited paths (createLivenesses).

Location:
CLRadeonExtender/trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp

    r4052 r4054  
    728728 */
    729729
     730/* join livenesses between consecutive code blocks */
    730731static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
    731732        const std::vector<CodeBlock>& codeBlocks, const LastVRegMap& lastVRegMap,
     
    776777}
    777778
    778 static void putCrossBlockForLoop(const std::deque<FlowStackEntry3>& flowStack,
    779         const std::vector<CodeBlock>& codeBlocks,
    780         std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
    781         size_t regTypesNum, const cxuint* regRanges)
    782 {
    783     auto flitStart = flowStack.end();
    784     --flitStart;
    785     size_t curBlock = flitStart->blockIndex;
    786     // find step in way
    787     while (flitStart->blockIndex != curBlock) --flitStart;
    788     auto flitEnd = flowStack.end();
    789     --flitEnd;
    790     std::unordered_map<AsmSingleVReg, std::pair<size_t, size_t> > varMap;
    791    
    792     // collect var to check
    793     size_t flowPos = 0;
    794     for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
    795     {
    796         const CodeBlock& cblock = codeBlocks[flit->blockIndex];
    797         for (const auto& entry: cblock.ssaInfoMap)
    798         {
    799             const SSAInfo& sinfo = entry.second;
    800             size_t lastSSAId = (sinfo.ssaIdChange != 0) ? sinfo.ssaIdLast :
    801                     (sinfo.readBeforeWrite) ? sinfo.ssaIdBefore : 0;
    802             varMap[entry.first] = { lastSSAId, flowPos };
    803         }
    804     }
    805     // find connections
    806     flowPos = 0;
    807     for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
    808     {
    809         const CodeBlock& cblock = codeBlocks[flit->blockIndex];
    810         for (const auto& entry: cblock.ssaInfoMap)
    811         {
    812             const SSAInfo& sinfo = entry.second;
    813             auto varMapIt = varMap.find(entry.first);
    814             if (!sinfo.readBeforeWrite || varMapIt == varMap.end() ||
    815                 flowPos > varMapIt->second.second ||
    816                 sinfo.ssaIdBefore != varMapIt->second.first)
     779static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
     780        const std::vector<CodeBlock>& codeBlocks, const VarIndexMap* vregIndexMaps,
     781        std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
     782{
     783    size_t nextBlock = prevFlowStack.back().blockIndex;
     784    auto pfEnd = prevFlowStack.end();
     785    --pfEnd;
     786    ARDOut << "startJoinLv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
     787    // key - varreg, value - last position in previous flowStack
     788    std::unordered_map<AsmSingleVReg, size_t> stackVarMap;
     789   
     790    for (auto pfit = prevFlowStack.begin(); pfit != pfEnd; ++pfit)
     791    {
     792        const FlowStackEntry3& entry = *pfit;
     793        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
     794        for (const auto& sentry: cblock.ssaInfoMap)
     795            stackVarMap[sentry.first] = pfit - prevFlowStack.begin();
     796    }
     797   
     798    // traverse by graph from next block
     799    std::deque<FlowStackEntry3> flowStack;
     800    flowStack.push_back({ nextBlock, 0 });
     801    std::vector<bool> visited(codeBlocks.size(), false);
     802   
     803    // already read in current path
     804    // key - vreg, value - source block where vreg of conflict found
     805    std::unordered_map<AsmSingleVReg, size_t> alreadyReadMap;
     806   
     807    while (!flowStack.empty())
     808    {
     809        FlowStackEntry3& entry = flowStack.back();
     810        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
     811       
     812        if (entry.nextIndex == 0)
     813        {
     814            // process current block
     815            //if (!visited[entry.blockIndex])
     816            {
     817                //visited[entry.blockIndex] = true;
     818                ARDOut << "  lvjoin: " << entry.blockIndex << "\n";
     819                for (const auto& sentry: cblock.ssaInfoMap)
     820                {
     821                    const SSAInfo& sinfo = sentry.second;
     822                    auto res = alreadyReadMap.insert({ sentry.first, entry.blockIndex });
     823                   
     824                    if (res.second && sinfo.readBeforeWrite)
     825                    {
     826                        // join liveness for this variable ssaId>.
     827                        // only if in previous block previous SSAID is
     828                        // read before all writes
     829                        auto it = stackVarMap.find(sentry.first);
     830                       
     831                        const size_t pfStart = (it != stackVarMap.end() ? it->second : 0);
     832                        //if (it == stackVarMap.end())
     833                            //continue;
     834                        // fill up previous part
     835                        Liveness& lv = getLiveness(sentry.first, 0, sinfo,
     836                                livenesses, vregIndexMaps, regTypesNum, regRanges);
     837                        auto flit = prevFlowStack.begin() + pfStart;
     838                        {
     839                            // fill up liveness for first code block
     840                            const CodeBlock& cblock = codeBlocks[flit->blockIndex];
     841                            auto ssaInfoIt = cblock.ssaInfoMap.find(sentry.first);
     842                            size_t prevLastPos = (ssaInfoIt != cblock.ssaInfoMap.end()) ?
     843                                    ssaInfoIt->second.lastPos+1 : cblock.start;
     844                                cblock.ssaInfoMap.find(sentry.first)->second;
     845                            lv.insert(prevLastPos, cblock.end);
     846                        }
     847                       
     848                        for (++flit; flit != pfEnd; ++flit)
     849                        {
     850                            const CodeBlock& cblock = codeBlocks[flit->blockIndex];
     851                            lv.insert(cblock.start, cblock.end);
     852                        }
     853                       
     854                        // fill up next part
     855                        auto newFlitEnd = flowStack.end();
     856                        --newFlitEnd; // end at previous this code block
     857                        for (flit = flowStack.begin(); flit != newFlitEnd; ++flit)
     858                        {
     859                            const CodeBlock& cblock = codeBlocks[flit->blockIndex];
     860                            lv.insert(cblock.start, cblock.end);
     861                        }
     862                        // fill up new last code block
     863                        {
     864                            const CodeBlock& cblock = codeBlocks[flit->blockIndex];
     865                            const SSAInfo& nextSInfo =
     866                                cblock.ssaInfoMap.find(sentry.first)->second;
     867                            lv.insert(cblock.start, nextSInfo.firstPos);
     868                        }
     869                    }
     870                }
     871            }
     872            /*else
     873            {
     874                flowStack.pop_back();
    817875                continue;
    818             // just connect
    819            
    820             cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
    821             const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    822             const std::vector<size_t>& ssaIdIndices =
    823                         vregIndexMap.find(entry.first)->second;
    824             Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
    825            
    826             if (flowPos == varMapIt->second.second)
    827             {
    828                 // fill whole loop
    829                 for (auto flit2 = flitStart; flit != flitEnd; ++flit)
     876            }*/
     877        }
     878       
     879        if (entry.nextIndex < cblock.nexts.size())
     880        {
     881            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
     882            entry.nextIndex++;
     883        }
     884        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
     885                // if have any call then go to next block
     886                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
     887                 !cblock.haveReturn && !cblock.haveEnd)
     888        {
     889            // add toResolveMap ssaIds inside called routines
     890            /*for (const auto& next: cblock.nexts)
     891                if (next.isCall)
    830892                {
    831                     const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
    832                     lv.insert(cblock.start, cblock.end);
    833                 }
    834                 continue;
    835             }
    836            
    837             size_t flowPos2 = 0;
    838             for (auto flit2 = flitStart; flowPos2 < flowPos; ++flit2, flowPos++)
    839             {
    840                 const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
    841                 lv.insert(cblock.start, cblock.end);
    842             }
    843             // insert liveness for last block in loop of last SSAId (prev round)
    844             auto flit2 = flitStart + flowPos;
    845             const CodeBlock& firstBlk = codeBlocks[flit2->blockIndex];
    846             lv.insert(firstBlk.start,
    847                     firstBlk.ssaInfoMap.find(entry.first)->second.firstPos);
    848             // insert liveness for first block in loop of last SSAId
    849             flit2 = flitStart + (varMapIt->second.second+1);
    850             const CodeBlock& lastBlk = codeBlocks[flit2->blockIndex];
    851             lv.insert(lastBlk.ssaInfoMap.find(entry.first)->second.lastPos, lastBlk.end);
    852             // fill up loop end
    853             for (++flit2; flit2 != flitEnd; ++flit2)
    854             {
    855                 const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
    856                 lv.insert(cblock.start, cblock.end);
    857             }
     893                    const RoutineData& rdata = routineMap.find(next.block)->second;
     894                    for (const auto& v: rdata.rbwSSAIdMap)
     895                        alreadyReadMap.insert({v.first, entry.blockIndex });
     896                    for (const auto& v: rdata.lastSSAIdMap)
     897                        alreadyReadMap.insert({v.first, entry.blockIndex });
     898                }*/
     899           
     900            flowStack.push_back({ entry.blockIndex+1, 0 });
     901            entry.nextIndex++;
     902        }
     903        else // back
     904        {
     905            // remove old to resolve in leaved way to allow collecting next ssaId
     906            // before write (can be different due to earlier visit)
     907            /*for (const auto& next: cblock.nexts)
     908                if (next.isCall)
     909                {
     910                    const RoutineData& rdata = routineMap.find(next.block)->second;
     911                    for (const auto& v: rdata.rbwSSAIdMap)
     912                    {
     913                        auto it = alreadyReadMap.find(v.first);
     914                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     915                            alreadyReadMap.erase(it);
     916                    }
     917                    for (const auto& v: rdata.lastSSAIdMap)
     918                    {
     919                        auto it = alreadyReadMap.find(v.first);
     920                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     921                            alreadyReadMap.erase(it);
     922                    }
     923                }*/
     924           
     925            for (const auto& sentry: cblock.ssaInfoMap)
     926            {
     927                auto it = alreadyReadMap.find(sentry.first);
     928                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     929                    // remove old to resolve in leaved way to allow collecting next ssaId
     930                    // before write (can be different due to earlier visit)
     931                    alreadyReadMap.erase(it);
     932            }
     933            ARDOut << "  popjoin\n";
     934           
     935            /*if (cblocksToCache.count(entry.blockIndex)==2 &&
     936                !resSecondPointsCache.hasKey(entry.blockIndex))
     937                // add to cache
     938                addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
     939                            entry.blockIndex);*/
     940           
     941            flowStack.pop_back();
    858942        }
    859943    }
     
    10141098            {
    10151099                // if loop
    1016                 putCrossBlockForLoop(flowStack, codeBlocks,
    1017                         livenesses, vregIndexMaps, regTypesNum, regRanges);
     1100                /*putCrossBlockForLoop(flowStack, codeBlocks,
     1101                        livenesses, vregIndexMaps, regTypesNum, regRanges);*/
    10181102                flowStack.pop_back();
    10191103                continue;
     
    11541238    }
    11551239   
     1240    // after, that resolve joins (join with already visited code)
     1241    flowStack.clear();
     1242    std::fill(visited.begin(), visited.end(), false);
     1243   
     1244    flowStack.push_back({ 0, 0 });
     1245   
     1246    while (!flowStack.empty())
     1247    {
     1248        FlowStackEntry3& entry = flowStack.back();
     1249        CodeBlock& cblock = codeBlocks[entry.blockIndex];
     1250       
     1251        if (entry.nextIndex == 0)
     1252        {
     1253            // process current block
     1254            if (!visited[entry.blockIndex])
     1255                visited[entry.blockIndex] = true;
     1256            else
     1257            {
     1258                joinRegVarLivenesses(flowStack, codeBlocks, vregIndexMaps,
     1259                            livenesses, regTypesNum, regRanges);
     1260                // back, already visited
     1261                flowStack.pop_back();
     1262                continue;
     1263            }
     1264        }
     1265       
     1266        if (entry.nextIndex < cblock.nexts.size())
     1267        {
     1268            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
     1269            entry.nextIndex++;
     1270        }
     1271        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
     1272                // if have any call then go to next block
     1273                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
     1274                 !cblock.haveReturn && !cblock.haveEnd)
     1275        {
     1276            flowStack.push_back({ entry.blockIndex+1, 0 });
     1277            entry.nextIndex++;
     1278        }
     1279        else // back
     1280            flowStack.pop_back();
     1281    }
     1282   
    11561283    // move livenesses to AsmRegAllocator outLivenesses
    11571284    for (size_t regType = 0; regType < regTypesNum; regType++)
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc3.cpp

    r4053 r4054  
    590590        {   // linearDepMaps
    591591            {   // for SGPRs
     592                { 0, { 0, { }, { 1 } } },
     593                { 1, { 0, { 0 }, { } } }
     594            },
     595            { },
     596            { },
     597            { }
     598        },
     599        true, ""
     600    },
     601    {   // 9 - simple joins
     602        R"ffDXD(.regvar sa:s:12, va:v:8
     603        s_mov_b32 sa[2], s2     # 0
     604        .cf_jump a1,a2,a3
     605        s_setpc_b64 s[0:1]      # 4
     606       
     607a1:     s_add_u32 sa[2], sa[2], sa[3]   # 8
     608        s_add_u32 sa[2], sa[2], sa[3]   # 12
     609        s_branch end                    # 16
     610a2:     s_add_u32 sa[2], sa[2], sa[4]   # 20
     611        s_add_u32 sa[2], sa[2], sa[4]   # 24
     612        s_branch end                    # 28
     613a3:     s_add_u32 sa[2], sa[2], sa[5]   # 32
     614        s_add_u32 sa[2], sa[2], sa[5]   # 36
     615        s_branch end                    # 40
     616
     617end:    s_xor_b32 sa[2], sa[2], s3      # 44
     618        s_endpgm                        # 48
     619)ffDXD",
     620        {   // livenesses
     621            {   // for SGPRs
     622                { { 0, 5 } }, // 0: S0
     623                { { 0, 5 } }, // 1: S1
     624                { { 0, 1 } }, // 2: S2
     625                { { 0, 45 } }, // 3: S3
     626                { { 1, 9 }, { 20, 21 }, { 32, 33 } }, // 4: sa[2]'0
     627                { { 9, 13 } }, // 5: sa[2]'1
     628                { { 13, 20 }, { 25, 32 }, { 37, 45 } }, // 6: sa[2]'2
     629                { { 45, 46 } }, // 7: sa[2]'3
     630                { { 21, 25 } }, // 8: sa[2]'4
     631                { { 33, 37 } }, // 9: sa[2]'5
     632                { { 0, 13 } }, // 10: sa[3]'0
     633                { { 0, 8 }, { 20, 25 } }, // 11: sa[4]'0
     634                { { 0, 8 }, { 32, 37 } }  // 12: sa[5]'0
     635            },
     636            { },
     637            { },
     638            { }
     639        },
     640        {   // linearDepMaps
     641            { // for SGPRs
    592642                { 0, { 0, { }, { 1 } } },
    593643                { 1, { 0, { 0 }, { } } }
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAllocCase3.cpp

    r4022 r4054  
    31243124        true, ""
    31253125    },
     3126    {   // 21 - simple join from 3 ways
     3127        R"ffDXD(.regvar sa:s:12, va:v:8
     3128        s_mov_b32 sa[2], s2
     3129        .cf_jump a1,a2,a3
     3130        s_setpc_b64 s[0:1]
     3131       
     3132a1:     s_add_u32 sa[2], sa[2], sa[3]
     3133        s_add_u32 sa[2], sa[2], sa[3]
     3134        s_branch end
     3135a2:     s_add_u32 sa[2], sa[2], sa[4]
     3136        s_add_u32 sa[2], sa[2], sa[4]
     3137        s_branch end
     3138a3:     s_add_u32 sa[2], sa[2], sa[5]
     3139        s_add_u32 sa[2], sa[2], sa[5]
     3140        s_branch end
     3141
     3142end:    s_xor_b32 sa[2], sa[2], s3
     3143        s_endpgm
     3144)ffDXD",
     3145        {
     3146            {   // block 0 - start
     3147                0, 8,
     3148                { { 1, false }, { 2, false }, { 3, false } },
     3149                {
     3150                    { { "", 0 }, SSAInfo(0, 0, 0, 0, 0, true) },
     3151                    { { "", 1 }, SSAInfo(0, 0, 0, 0, 0, true) },
     3152                    { { "", 2 }, SSAInfo(0, 0, 0, 0, 0, true) },
     3153                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, false) }
     3154                }, false, false, true },
     3155            {   // block 1 - a1
     3156                8, 20,
     3157                { { 4, false } },
     3158                {
     3159                    { { "sa", 2 }, SSAInfo(1, 2, 2, 3, 2, true) },
     3160                    { { "sa", 3 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
     3161                }, false, false, true },
     3162            {   // block 2 - a2
     3163                20, 32,
     3164                { { 4, false } },
     3165                {
     3166                    { { "sa", 2 }, SSAInfo(1, 5, 5, 6, 2, true) },
     3167                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
     3168                }, false, false, true },
     3169            {   // block 3 - a3
     3170                32, 44,
     3171                { { 4, false } },
     3172                {
     3173                    { { "sa", 2 }, SSAInfo(1, 7, 7, 8, 2, true) },
     3174                    { { "sa", 5 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
     3175                }, false, false, true
     3176            },
     3177            {   // block 4 - end
     3178                44, 52,
     3179                { },
     3180                {
     3181                    { { "", 3 }, SSAInfo(0, 0, 0, 0, 0, true) },
     3182                    { { "sa", 2 }, SSAInfo(3, 4, 4, 4, 1, true) }
     3183                }, false, false, true }
     3184        },
     3185        {   // SSA replaces
     3186            { { "sa", 2 }, { { 6, 3 }, { 8, 3 } } }
     3187        },
     3188        true, ""
     3189    },
    31263190    { nullptr }
    31273191};
Note: See TracChangeset for help on using the changeset viewer.