Changeset 3857 in CLRX


Ignore:
Timestamp:
Feb 27, 2018, 3:22:52 PM (14 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Add ressecond point to cache before using.

File:
1 edited

Legend:

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

    r3856 r3857  
    626626};
    627627
    628 struct CLRX_INTERNAL ResSecCacheConNode
    629 {
    630     size_t next; // block index
    631     // already read in path to next Cache construction node
    632     std::vector<AsmSingleVReg> alreadyRead;
    633 };
    634 
    635 // hold all readBeforeWrite SSAIds for whole subtree for cache block point
    636 // does not hold readBeforeWrite SSAIds for next subtrees
    637 struct CLRX_INTERNAL ResSecCacheConEntry
    638 {
    639     LastSSAIdMap rbwSSAIdMap;
    640     std::vector<ResSecCacheConNode> nodes;
    641 };
    642 
    643628class ResSecondPointsToCache: public std::vector<bool>
    644629{
     
    669654}
    670655
    671 static void handleSSAEntryWhileResolving(SSAReplacesMap& replacesMap,
    672             const LastSSAIdMap& stackVarMap,
     656static void handleSSAEntryWhileResolving(SSAReplacesMap* replacesMap,
     657            const LastSSAIdMap* stackVarMap,
    673658            std::unordered_map<AsmSingleVReg, size_t>& alreadyReadMap,
    674659            FlowStackEntry2& entry, const SSAEntry& sentry,
     
    687672        }
    688673       
    689         // resolve conflict for this variable ssaId>.
    690         // only if in previous block previous SSAID is
    691         // read before all writes
    692         auto it = stackVarMap.find(sentry.first);
    693        
    694         if (it != stackVarMap.end())
    695         {
    696             // found, resolve by set ssaIdLast
    697             for (size_t ssaId: it->second)
    698             {
    699                 if (ssaId > sinfo.ssaIdBefore)
     674        if (stackVarMap != nullptr)
     675        {
     676           
     677            // resolve conflict for this variable ssaId>.
     678            // only if in previous block previous SSAID is
     679            // read before all writes
     680            auto it = stackVarMap->find(sentry.first);
     681           
     682            if (it != stackVarMap->end())
     683            {
     684                // found, resolve by set ssaIdLast
     685                for (size_t ssaId: it->second)
    700686                {
    701                     std::cout << "  insertreplace: " << sentry.first.regVar << ":" <<
    702                         sentry.first.index  << ": " <<
    703                         ssaId << ", " << sinfo.ssaIdBefore << std::endl;
    704                     insertReplace(replacesMap, sentry.first, ssaId,
    705                                 sinfo.ssaIdBefore);
    706                 }
    707                 else if (ssaId < sinfo.ssaIdBefore)
    708                 {
    709                     std::cout << "  insertreplace2: " << sentry.first.regVar << ":" <<
    710                         sentry.first.index  << ": " <<
    711                         ssaId << ", " << sinfo.ssaIdBefore << std::endl;
    712                     insertReplace(replacesMap, sentry.first,
    713                                     sinfo.ssaIdBefore, ssaId);
    714                 }
    715                 /*else
    716                     std::cout << "  noinsertreplace: " <<
    717                         ssaId << "," << sinfo.ssaIdBefore << std::endl;*/
    718             }
    719         }
    720     }
    721 }
    722 
    723 typedef std::unordered_map<size_t, std::pair<size_t, size_t> > PrevWaysIndexMap;
    724 
    725 static void useResSecPointCache(SSAReplacesMap& replacesMap,
    726         const LastSSAIdMap& stackVarMap,
    727         const std::unordered_map<AsmSingleVReg, size_t>& alreadyReadMap,
    728         const RBWSSAIdMap* resSecondPoints, size_t nextBlock,
    729         RBWSSAIdMap* destCacheSecPoints)
    730 {
    731     std::cout << "use resSecPointCache for " << nextBlock << std::endl;
    732     for (const auto& sentry: *resSecondPoints)
    733     {
    734         const bool alreadyRead = alreadyReadMap.find(sentry.first) != alreadyReadMap.end();
    735         if (destCacheSecPoints != nullptr && !alreadyRead)
    736         {
    737             auto res = destCacheSecPoints->insert(sentry);
    738             if (!res.second)
    739                 for (size_t srcSSAId: sentry.second)
    740                     res.first->second.insertValue(srcSSAId);
    741         }
    742         auto it = stackVarMap.find(sentry.first);
    743        
    744         if (it != stackVarMap.end() && !alreadyRead)
    745         {
    746             // found, resolve by set ssaIdLast
    747             for (size_t ssaId: it->second)
    748             {
    749                 for (size_t secSSAId: sentry.second)
    750                 {
    751                     if (ssaId > secSSAId)
     687                    if (ssaId > sinfo.ssaIdBefore)
    752688                    {
    753                         std::cout << "  insertreplace: " <<
    754                             sentry.first.regVar << ":" <<
     689                        std::cout << "  insertreplace: " << sentry.first.regVar << ":" <<
    755690                            sentry.first.index  << ": " <<
    756                             ssaId << ", " << secSSAId << std::endl;
    757                         insertReplace(replacesMap, sentry.first, ssaId,
    758                                     secSSAId);
     691                            ssaId << ", " << sinfo.ssaIdBefore << std::endl;
     692                        insertReplace(*replacesMap, sentry.first, ssaId,
     693                                    sinfo.ssaIdBefore);
    759694                    }
    760                     else if (ssaId < secSSAId)
     695                    else if (ssaId < sinfo.ssaIdBefore)
    761696                    {
    762                         std::cout << "  insertreplace2: " <<
    763                             sentry.first.regVar << ":" <<
     697                        std::cout << "  insertreplace2: " << sentry.first.regVar << ":" <<
    764698                            sentry.first.index  << ": " <<
    765                             ssaId << ", " << secSSAId << std::endl;
    766                         insertReplace(replacesMap, sentry.first,
    767                                         secSSAId, ssaId);
     699                            ssaId << ", " << sinfo.ssaIdBefore << std::endl;
     700                        insertReplace(*replacesMap, sentry.first,
     701                                        sinfo.ssaIdBefore, ssaId);
    768702                    }
    769703                    /*else
     
    776710}
    777711
    778 static void resolveSSAConflicts(const std::deque<FlowStackEntry2>& prevFlowStack,
    779         const std::unordered_map<size_t, RoutineData>& routineMap,
    780         const std::vector<CodeBlock>& codeBlocks,
    781         const PrevWaysIndexMap& prevWaysIndexMap,
    782         const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
    783         SimpleCache<size_t, LastSSAIdMap>& resFirstPointsCache,
    784         SimpleCache<size_t, RBWSSAIdMap>& resSecondPointsCache,
    785         SSAReplacesMap& replacesMap)
    786 {
    787     size_t nextBlock = prevFlowStack.back().blockIndex;
    788     auto pfEnd = prevFlowStack.end();
    789     --pfEnd;
    790     std::cout << "startResolv: " << (pfEnd-1)->blockIndex << "," << nextBlock << std::endl;
    791     LastSSAIdMap stackVarMap;
    792    
    793     size_t pfStartIndex = 0;
    794     {
    795         auto pfPrev = pfEnd;
    796         --pfPrev;
    797         auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
    798         if (it != prevWaysIndexMap.end())
    799         {
    800             const LastSSAIdMap* cached = resFirstPointsCache.use(it->second.first);
    801             if (cached!=nullptr)
    802             {
    803                 std::cout << "use pfcached: " << it->second.first << ", " <<
    804                         it->second.second << std::endl;
    805                 stackVarMap = *cached;
    806                 pfStartIndex = it->second.second+1;
    807             }
    808         }
    809     }
    810    
    811     for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
    812     {
    813         const FlowStackEntry2& entry = *pfit;
    814         std::cout << "  apply: " << entry.blockIndex << std::endl;
    815         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    816         for (const auto& sentry: cblock.ssaInfoMap)
    817         {
    818             const SSAInfo& sinfo = sentry.second;
    819             if (sinfo.ssaIdChange != 0)
    820                 stackVarMap[sentry.first] = { sinfo.ssaId + sinfo.ssaIdChange - 1 };
    821         }
    822         if (entry.nextIndex > cblock.nexts.size())
    823             for (const NextBlock& next: cblock.nexts)
    824                 if (next.isCall)
     712typedef std::unordered_map<size_t, std::pair<size_t, size_t> > PrevWaysIndexMap;
     713
     714static void useResSecPointCache(SSAReplacesMap* replacesMap,
     715        const LastSSAIdMap* stackVarMap,
     716        const std::unordered_map<AsmSingleVReg, size_t>& alreadyReadMap,
     717        const RBWSSAIdMap* resSecondPoints, size_t nextBlock,
     718        RBWSSAIdMap* destCacheSecPoints)
     719{
     720    std::cout << "use resSecPointCache for " << nextBlock << std::endl;
     721    for (const auto& sentry: *resSecondPoints)
     722    {
     723        const bool alreadyRead = alreadyReadMap.find(sentry.first) != alreadyReadMap.end();
     724        if (destCacheSecPoints != nullptr && !alreadyRead)
     725        {
     726            auto res = destCacheSecPoints->insert(sentry);
     727            if (!res.second)
     728                for (size_t srcSSAId: sentry.second)
     729                    res.first->second.insertValue(srcSSAId);
     730        }
     731       
     732        if (stackVarMap != nullptr)
     733        {
     734            auto it = stackVarMap->find(sentry.first);
     735           
     736            if (it != stackVarMap->end() && !alreadyRead)
     737            {
     738                // found, resolve by set ssaIdLast
     739                for (size_t ssaId: it->second)
    825740                {
    826                     std::cout << "  applycall: " << entry.blockIndex << ": " <<
    827                             entry.nextIndex << ": " << next.block << std::endl;
    828                     const LastSSAIdMap& regVarMap =
    829                             routineMap.find(next.block)->second.lastSSAIdMap;
    830                     for (const auto& sentry: regVarMap)
    831                         stackVarMap[sentry.first] = sentry.second;
     741                    for (size_t secSSAId: sentry.second)
     742                    {
     743                        if (ssaId > secSSAId)
     744                        {
     745                            std::cout << "  insertreplace: " <<
     746                                sentry.first.regVar << ":" <<
     747                                sentry.first.index  << ": " <<
     748                                ssaId << ", " << secSSAId << std::endl;
     749                            insertReplace(*replacesMap, sentry.first, ssaId,
     750                                        secSSAId);
     751                        }
     752                        else if (ssaId < secSSAId)
     753                        {
     754                            std::cout << "  insertreplace2: " <<
     755                                sentry.first.regVar << ":" <<
     756                                sentry.first.index  << ": " <<
     757                                ssaId << ", " << secSSAId << std::endl;
     758                            insertReplace(*replacesMap, sentry.first,
     759                                            secSSAId, ssaId);
     760                        }
     761                        /*else
     762                            std::cout << "  noinsertreplace: " <<
     763                                ssaId << "," << sinfo.ssaIdBefore << std::endl;*/
     764                    }
    832765                }
    833        
    834         // put to first point cache
    835         if (waysToCache[pfit->blockIndex] && !resFirstPointsCache.hasKey(pfit->blockIndex))
    836         {
    837             std::cout << "put pfcache " << pfit->blockIndex << std::endl;
    838             resFirstPointsCache.put(pfit->blockIndex, stackVarMap);
    839         }
    840     }
    841    
    842     RBWSSAIdMap* resSecondPoints = resSecondPointsCache.use(nextBlock);
    843    
    844     RBWSSAIdMap cacheSecPoints;
    845     const bool toCache = (resSecondPoints == nullptr) &&
    846                 cblocksToCache.count(nextBlock)>=2;
    847    
     766            }
     767        }
     768    }
     769}
     770
     771static void addResSecCacheEntry(const std::unordered_map<size_t, RoutineData>& routineMap,
     772                const std::vector<CodeBlock>& codeBlocks,
     773                SimpleCache<size_t, RBWSSAIdMap>& resSecondPointsCache,
     774                size_t nextBlock)
     775{
     776    std::cout << "addResSecCacheEntry: " << nextBlock << std::endl;
    848777    //std::stack<CallStackEntry> callStack = prevCallStack;
    849778    // traverse by graph from next block
     
    852781    std::vector<bool> visited(codeBlocks.size(), false);
    853782   
    854     // holds second point in resolving construction entries
    855     // key - first block index, value - cache con entry
    856     std::unordered_map<size_t, ResSecCacheConEntry> resSecCacheConstrBlocks;
    857     // already read in current path
    858     // key - vreg, value - source block where vreg of conflict found
    859783    std::unordered_map<AsmSingleVReg, size_t> alreadyReadMap;
     784   
     785    RBWSSAIdMap cacheSecPoints;
    860786   
    861787    while (!flowStack.empty())
     
    875801                if (resSecondPoints == nullptr)
    876802                    for (auto& sentry: cblock.ssaInfoMap)
    877                         handleSSAEntryWhileResolving(replacesMap, stackVarMap,
     803                        handleSSAEntryWhileResolving(nullptr, nullptr,
    878804                                alreadyReadMap, entry, sentry,
    879                                 toCache ? &cacheSecPoints : nullptr);
     805                                &cacheSecPoints);
    880806                else // to use cache
    881807                {
    882                     useResSecPointCache(replacesMap, stackVarMap, alreadyReadMap,
    883                             resSecondPoints, entry.blockIndex,
    884                             toCache ? &cacheSecPoints : nullptr);
     808                    useResSecPointCache(nullptr, nullptr, alreadyReadMap,
     809                            resSecondPoints, entry.blockIndex, &cacheSecPoints);
    885810                    flowStack.pop_back();
    886811                    continue;
     
    889814            else
    890815            {
    891                 cblocksToCache.increase(entry.blockIndex);
    892                 std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
    893                             cblocksToCache.count(entry.blockIndex) << std::endl;
    894816                // back, already visited
    895817                std::cout << "resolv already: " << entry.blockIndex << std::endl;
     
    962884            }
    963885            std::cout << "  popresolv" << std::endl;
     886            flowStack.pop_back();
     887        }
     888    }
     889   
     890    resSecondPointsCache.put(nextBlock, cacheSecPoints);
     891}
     892
     893
     894static void resolveSSAConflicts(const std::deque<FlowStackEntry2>& prevFlowStack,
     895        const std::unordered_map<size_t, RoutineData>& routineMap,
     896        const std::vector<CodeBlock>& codeBlocks,
     897        const PrevWaysIndexMap& prevWaysIndexMap,
     898        const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
     899        SimpleCache<size_t, LastSSAIdMap>& resFirstPointsCache,
     900        SimpleCache<size_t, RBWSSAIdMap>& resSecondPointsCache,
     901        SSAReplacesMap& replacesMap)
     902{
     903    size_t nextBlock = prevFlowStack.back().blockIndex;
     904    auto pfEnd = prevFlowStack.end();
     905    --pfEnd;
     906    std::cout << "startResolv: " << (pfEnd-1)->blockIndex << "," << nextBlock << std::endl;
     907    LastSSAIdMap stackVarMap;
     908   
     909    size_t pfStartIndex = 0;
     910    {
     911        auto pfPrev = pfEnd;
     912        --pfPrev;
     913        auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
     914        if (it != prevWaysIndexMap.end())
     915        {
     916            const LastSSAIdMap* cached = resFirstPointsCache.use(it->second.first);
     917            if (cached!=nullptr)
     918            {
     919                std::cout << "use pfcached: " << it->second.first << ", " <<
     920                        it->second.second << std::endl;
     921                stackVarMap = *cached;
     922                pfStartIndex = it->second.second+1;
     923            }
     924        }
     925    }
     926   
     927    for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
     928    {
     929        const FlowStackEntry2& entry = *pfit;
     930        std::cout << "  apply: " << entry.blockIndex << std::endl;
     931        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
     932        for (const auto& sentry: cblock.ssaInfoMap)
     933        {
     934            const SSAInfo& sinfo = sentry.second;
     935            if (sinfo.ssaIdChange != 0)
     936                stackVarMap[sentry.first] = { sinfo.ssaId + sinfo.ssaIdChange - 1 };
     937        }
     938        if (entry.nextIndex > cblock.nexts.size())
     939            for (const NextBlock& next: cblock.nexts)
     940                if (next.isCall)
     941                {
     942                    std::cout << "  applycall: " << entry.blockIndex << ": " <<
     943                            entry.nextIndex << ": " << next.block << std::endl;
     944                    const LastSSAIdMap& regVarMap =
     945                            routineMap.find(next.block)->second.lastSSAIdMap;
     946                    for (const auto& sentry: regVarMap)
     947                        stackVarMap[sentry.first] = sentry.second;
     948                }
     949       
     950        // put to first point cache
     951        if (waysToCache[pfit->blockIndex] && !resFirstPointsCache.hasKey(pfit->blockIndex))
     952        {
     953            std::cout << "put pfcache " << pfit->blockIndex << std::endl;
     954            resFirstPointsCache.put(pfit->blockIndex, stackVarMap);
     955        }
     956    }
     957   
     958    RBWSSAIdMap cacheSecPoints;
     959    const bool toCache = (!resSecondPointsCache.hasKey(nextBlock)) &&
     960                cblocksToCache.count(nextBlock)>=2;
     961   
     962    //std::stack<CallStackEntry> callStack = prevCallStack;
     963    // traverse by graph from next block
     964    std::deque<FlowStackEntry2> flowStack;
     965    flowStack.push_back({ nextBlock, 0 });
     966    std::vector<bool> visited(codeBlocks.size(), false);
     967   
     968    // already read in current path
     969    // key - vreg, value - source block where vreg of conflict found
     970    std::unordered_map<AsmSingleVReg, size_t> alreadyReadMap;
     971   
     972    while (!flowStack.empty())
     973    {
     974        FlowStackEntry2& entry = flowStack.back();
     975        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
     976       
     977        if (entry.nextIndex == 0)
     978        {
     979            // process current block
     980            if (!visited[entry.blockIndex])
     981            {
     982                visited[entry.blockIndex] = true;
     983                std::cout << "  resolv: " << entry.blockIndex << std::endl;
     984               
     985                const RBWSSAIdMap* resSecondPoints = resSecondPointsCache.use(nextBlock);
     986                if (resSecondPoints == nullptr)
     987                    for (auto& sentry: cblock.ssaInfoMap)
     988                        handleSSAEntryWhileResolving(&replacesMap, &stackVarMap,
     989                                alreadyReadMap, entry, sentry,
     990                                toCache ? &cacheSecPoints : nullptr);
     991                else // to use cache
     992                {
     993                    useResSecPointCache(&replacesMap, &stackVarMap, alreadyReadMap,
     994                            resSecondPoints, entry.blockIndex,
     995                            toCache ? &cacheSecPoints : nullptr);
     996                    flowStack.pop_back();
     997                    continue;
     998                }
     999            }
     1000            else
     1001            {
     1002                cblocksToCache.increase(entry.blockIndex);
     1003                std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
     1004                            cblocksToCache.count(entry.blockIndex) << std::endl;
     1005                // back, already visited
     1006                std::cout << "resolv already: " << entry.blockIndex << std::endl;
     1007                flowStack.pop_back();
     1008                continue;
     1009            }
     1010        }
     1011       
     1012        /*if (!callStack.empty() &&
     1013            entry.blockIndex == callStack.top().callBlock &&
     1014            entry.nextIndex-1 == callStack.top().callNextIndex)
     1015            callStack.pop(); // just return from call
     1016        */
     1017        if (entry.nextIndex < cblock.nexts.size())
     1018        {
     1019            /*if (cblock.nexts[entry.nextIndex].isCall)
     1020                callStack.push({ entry.blockIndex, entry.nextIndex,
     1021                            cblock.nexts[entry.nextIndex].block });*/
     1022            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
     1023            entry.nextIndex++;
     1024        }
     1025        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
     1026                // if have any call then go to next block
     1027                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
     1028                 !cblock.haveReturn && !cblock.haveEnd)
     1029        {
     1030            // add toResolveMap ssaIds inside called routines
     1031            for (const auto& next: cblock.nexts)
     1032                if (next.isCall)
     1033                {
     1034                    const RoutineData& rdata = routineMap.find(next.block)->second;
     1035                    for (const auto& v: rdata.rbwSSAIdMap)
     1036                        alreadyReadMap.insert({v.first, entry.blockIndex });
     1037                    for (const auto& v: rdata.lastSSAIdMap)
     1038                        alreadyReadMap.insert({v.first, entry.blockIndex });
     1039                }
     1040           
     1041            flowStack.push_back({ entry.blockIndex+1, 0 });
     1042            entry.nextIndex++;
     1043        }
     1044        else // back
     1045        {
     1046            // remove old to resolve in leaved way to allow collecting next ssaId
     1047            // before write (can be different due to earlier visit)
     1048            for (const auto& next: cblock.nexts)
     1049                if (next.isCall)
     1050                {
     1051                    const RoutineData& rdata = routineMap.find(next.block)->second;
     1052                    for (const auto& v: rdata.rbwSSAIdMap)
     1053                    {
     1054                        auto it = alreadyReadMap.find(v.first);
     1055                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     1056                            alreadyReadMap.erase(it);
     1057                    }
     1058                    for (const auto& v: rdata.lastSSAIdMap)
     1059                    {
     1060                        auto it = alreadyReadMap.find(v.first);
     1061                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     1062                            alreadyReadMap.erase(it);
     1063                    }
     1064                }
     1065           
     1066            for (const auto& sentry: cblock.ssaInfoMap)
     1067            {
     1068                auto it = alreadyReadMap.find(sentry.first);
     1069                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
     1070                    // remove old to resolve in leaved way to allow collecting next ssaId
     1071                    // before write (can be different due to earlier visit)
     1072                    alreadyReadMap.erase(it);
     1073            }
     1074            std::cout << "  popresolv" << std::endl;
     1075           
     1076            if (cblocksToCache.count(entry.blockIndex)==2 &&
     1077                !resSecondPointsCache.hasKey(entry.blockIndex))
     1078                // add to cache
     1079                addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
     1080                            entry.blockIndex);
     1081           
    9641082            flowStack.pop_back();
    9651083        }
     
    15151633        }
    15161634        else // back
     1635        {
     1636            if (cblocksToCache.count(entry.blockIndex)==2 &&
     1637                !resSecondPointsCache.hasKey(entry.blockIndex))
     1638                // add to cache
     1639                addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
     1640                            entry.blockIndex);
    15171641            flowStack2.pop_back();
     1642        }
    15181643    }
    15191644}
Note: See TracChangeset for help on using the changeset viewer.