Changeset 3582 in CLRX


Ignore:
Timestamp:
Jan 5, 2018, 3:48:57 PM (12 days ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Revert changes in AsmRegAlloc?. Fixed haveCalls if point have both calls and jumps.

Location:
CLRadeonExtender/trunk
Files:
2 edited

Legend:

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

    r3581 r3582  
    394394            curIt->nexts.push_back({ size_t(it - codeBlocks.begin()),
    395395                        entry.type == AsmCodeFlowType::CALL });
    396             curIt->haveCalls = entry.type == AsmCodeFlowType::CALL;
     396            curIt->haveCalls |= entry.type == AsmCodeFlowType::CALL;
    397397            if (entry.type == AsmCodeFlowType::CJUMP ||
    398398                 entry.type == AsmCodeFlowType::CALL)
     
    440440};
    441441
     442// map of last SSAId for routine, key - varid, value - last SSA ids
     443
     444typedef std::unordered_map<AsmSingleVReg, std::vector<size_t> > LastSSAIdMap;
     445struct RoutineData
     446{
     447    bool processed;
     448    LastSSAIdMap regVarMap;
     449};
     450
    442451struct FlowStackEntry
    443452{
    444453    size_t blockIndex;
    445454    size_t nextIndex;
     455    LastSSAIdMap replacedMultiSSAIds;
     456        // ssaIds from called routine already visited before call
    446457    std::unordered_map<AsmSingleVReg, size_t> prevSSAIds;
     458};
     459
     460struct CallStackEntry
     461{
     462    size_t callBlock; // index
     463    size_t callNextIndex; // index of call next
    447464};
    448465
     
    464481
    465482static void resolveSSAConflicts(const std::deque<FlowStackEntry>& prevFlowStack,
     483        const std::stack<CallStackEntry>& prevCallStack,
    466484        const std::vector<bool>& prevVisited,
     485        const std::unordered_map<size_t, RoutineData>& routineMap,
    467486        const std::vector<CodeBlock>& codeBlocks,
    468487        SSAReplacesMap& replacesMap)
     
    471490    auto pfEnd = prevFlowStack.end();
    472491    --pfEnd;
    473     std::unordered_map<AsmSingleVReg, size_t> stackVarMap;
     492    LastSSAIdMap stackVarMap;
    474493    for (auto pfit = prevFlowStack.begin(); pfit != pfEnd; ++pfit)
    475494    {
     
    480499            const SSAInfo& sinfo = sentry.second;
    481500            if (sinfo.ssaIdChange != 0)
    482                 stackVarMap[sentry.first] = sinfo.ssaId + sinfo.ssaIdChange - 1;
    483         }
    484     }
    485    
     501                stackVarMap[sentry.first] = { sinfo.ssaId + sinfo.ssaIdChange - 1 };
     502        }
     503        for (const NextBlock& next: cblock.nexts)
     504            if (next.isCall)
     505            {
     506                const LastSSAIdMap& regVarMap =
     507                        routineMap.find(next.block)->second.regVarMap;
     508                for (const auto& sentry: regVarMap)
     509                    stackVarMap[sentry.first] = sentry.second;
     510            }
     511    }
     512   
     513    std::stack<CallStackEntry> callStack = prevCallStack;
    486514    // traverse by graph from next block
    487515    std::deque<FlowStackEntry> flowStack;
     
    515543                        if (it != stackVarMap.end())
    516544                            // found, resolve by set ssaIdLast
    517                             if (it->second > sinfo.ssaIdBefore)
    518                                 insertReplace(replacesMap, sentry.first, it->second,
    519                                             sinfo.ssaIdBefore);
     545                            for (size_t ssaId: it->second)
     546                                if (ssaId > sinfo.ssaIdBefore)
     547                                    insertReplace(replacesMap, sentry.first, ssaId,
     548                                                sinfo.ssaIdBefore);
    520549                        res.first->second.handled = true;
    521550                    }
     
    530559        }
    531560       
     561        if (!callStack.empty() &&
     562            entry.blockIndex == callStack.top().callBlock &&
     563            entry.nextIndex-1 == callStack.top().callNextIndex)
     564            callStack.pop(); // just return from call
     565       
    532566        if (entry.nextIndex < cblock.nexts.size() &&
    533567            prevVisited[cblock.nexts[entry.nextIndex].block])
    534568        {
    535569            if (cblock.nexts[entry.nextIndex].isCall)
    536                 ;//callStack.push({ entry.blockIndex, entry.nextIndex });
     570                callStack.push({ entry.blockIndex, entry.nextIndex });
    537571            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    538572            entry.nextIndex++;
     
    559593            }
    560594            flowStack.pop_back();
     595        }
     596    }
     597}
     598
     599static void joinRoutineData(LastSSAIdMap& dest, const LastSSAIdMap& src,
     600                const std::unordered_map<AsmSingleVReg, SSAInfo>& prevSSAInfoMap)
     601{
     602    for (const auto& entry: src)
     603    {
     604        if (entry.first.regVar==nullptr)
     605            continue;
     606        auto res = dest.insert(entry); // find
     607        if (res.second)
     608            continue; // added new
     609        auto ssaInfoIt = prevSSAInfoMap.find(entry.first);
     610        std::vector<size_t>& destEntry = res.first->second;
     611        if (ssaInfoIt->second.ssaIdChange!=0)
     612        {
     613            if (ssaInfoIt != prevSSAInfoMap.end())
     614            {
     615                auto it = std::find(destEntry.begin(), destEntry.end(),
     616                                    ssaInfoIt->second.ssaIdLast);
     617                if (it != destEntry.end())
     618                    destEntry.erase(it); // remove old way
     619            }
     620            // add new ways
     621            for (size_t ssaId: entry.second)
     622            {
     623                auto it = std::find(destEntry.begin(), destEntry.end(), ssaId);
     624                if (it == destEntry.end())
     625                    destEntry.push_back(ssaId);
     626            }
     627        }
     628    }
     629}
     630
     631static void joinLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src)
     632{
     633    for (const auto& entry: src)
     634    {
     635        auto res = dest.insert(entry); // find
     636        if (res.second)
     637            continue; // added new
     638        std::vector<size_t>& destEntry = res.first->second;
     639        // add new ways
     640        for (size_t ssaId: entry.second)
     641        {
     642            auto it = std::find(destEntry.begin(), destEntry.end(), ssaId);
     643            if (it == destEntry.end())
     644                destEntry.push_back(ssaId);
     645        }
     646    }
     647}
     648
     649static void removeLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src)
     650{
     651    for (const auto& entry: src)
     652    {
     653        auto destIt = dest.find(entry.first); // find
     654        std::vector<size_t>& destEntry = destIt->second;
     655        // add new ways
     656        for (size_t ssaId: entry.second)
     657        {
     658            auto it = std::find(destEntry.begin(), destEntry.end(), ssaId);
     659            if (it != destEntry.end())
     660                destEntry.erase(it);
    561661        }
    562662    }
     
    620720    }
    621721   
     722    std::stack<CallStackEntry> callStack;
    622723    std::deque<FlowStackEntry> flowStack;
    623724    // total SSA count
     
    625726    // last SSA ids in current way in code flow
    626727    std::unordered_map<AsmSingleVReg, size_t> curSSAIdMap;
     728    // routine map - routine datas map, value - last SSA ids map
     729    std::unordered_map<size_t, RoutineData> routineMap;
     730    // initialize routineMap
     731    for (const CodeBlock& cblock: codeBlocks)
     732        for (const NextBlock& next: cblock.nexts)
     733            // all forks and calls
     734            routineMap[next.block].processed = false;
     735   
     736    LastSSAIdMap lastMultiSSAIdMap; // current SSA id from visited calls
     737    std::unordered_set<size_t> selectedRoutines;
    627738    std::vector<bool> visited(codeBlocks.size(), false);
    628739    flowStack.push_back({ 0, 0 });
     
    662773                    ssaId = totalSSACount;
    663774                }
     775                // check if routineMap
     776                auto rit = routineMap.find(entry.blockIndex);
     777                if (rit != routineMap.end() && !rit->second.processed)
     778                    selectedRoutines.insert(entry.blockIndex);
     779                // add routine regvar map
     780                for (size_t routine: selectedRoutines)
     781                {
     782                    LastSSAIdMap& regVarMap = routineMap.find(routine)->second.regVarMap;
     783                    for (const auto& ssaEntry: cblock.ssaInfoMap)
     784                    {
     785                        const SSAInfo& sinfo = ssaEntry.second;
     786                        if (sinfo.ssaIdChange!=0 && ssaEntry.first.regVar!=nullptr)
     787                        {
     788                            std::vector<size_t>& ssas = regVarMap[ssaEntry.first];
     789                            auto lmsit = lastMultiSSAIdMap.find(ssaEntry.first);
     790                            if (lmsit != lastMultiSSAIdMap.end())
     791                            {
     792                                // if many parallel ssaId from routine returns
     793                                const std::vector<size_t>& ssaIdsToRemove = lmsit->second;
     794                                for (size_t s: ssaIdsToRemove)
     795                                {
     796                                    auto ssaIt = std::find(ssas.begin(), ssas.end(), s);
     797                                    if (ssaIt != ssas.end())
     798                                        ssas.erase(ssaIt);
     799                                    // add new
     800                                    ssas.push_back(sinfo.ssaIdLast);
     801                                }
     802                                // add to replaced ssaid to revert changes at pop
     803                                entry.replacedMultiSSAIds.insert(*lmsit);
     804                                lastMultiSSAIdMap.erase(lmsit);
     805                            }
     806                            else
     807                            {
     808                                auto ssaIt = std::find(ssas.begin(), ssas.end(),
     809                                            sinfo.ssaId-1);
     810                                if (ssaIt != ssas.end()) // update this point
     811                                    *ssaIt = sinfo.ssaIdLast;
     812                                else if (std::find(ssas.begin(), ssas.end(),
     813                                        sinfo.ssaIdLast) == ssas.end())
     814                                    // otherwise add new way
     815                                    ssas.push_back(sinfo.ssaIdLast);
     816                            }
     817                        }
     818                    }
     819                }
    664820            }
    665821            else
    666822            {
    667                 resolveSSAConflicts(flowStack, visited, codeBlocks, ssaReplacesMap);
     823                // join routine data
     824                auto rit = routineMap.find(entry.blockIndex);
     825                if (rit != routineMap.end() && rit->second.processed)
     826                {
     827                    // just join with selected routines
     828                    // if this ways to return are visited before
     829                    auto fcit = flowStack.end();
     830                    --fcit;
     831                    --fcit; // before this codeblock
     832                    const std::unordered_map<AsmSingleVReg, SSAInfo>& prevSSAInfoMap =
     833                            codeBlocks[fcit->blockIndex].ssaInfoMap;
     834                    for (size_t routine: selectedRoutines)
     835                        joinRoutineData(routineMap.find(routine)->second.regVarMap,
     836                                rit->second.regVarMap, prevSSAInfoMap);
     837                }
     838                resolveSSAConflicts(flowStack, callStack, visited, routineMap, codeBlocks,
     839                                    ssaReplacesMap);
    668840                // back, already visited
    669841                flowStack.pop_back();
     
    672844        }
    673845       
     846        if (!callStack.empty() &&
     847            entry.blockIndex == callStack.top().callBlock &&
     848            entry.nextIndex-1 == callStack.top().callNextIndex)
     849            callStack.pop(); // just return from call
     850       
    674851        if (entry.nextIndex < cblock.nexts.size())
    675852        {
    676853            if (cblock.nexts[entry.nextIndex].isCall)
    677                 ;//callStack.push({ entry.blockIndex, entry.nextIndex });
     854                callStack.push({ entry.blockIndex, entry.nextIndex });
    678855           
    679856            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
     
    685862                 !cblock.haveReturn && !cblock.haveEnd)
    686863        {
     864            if (entry.nextIndex!=0) // if back from call
     865            {
     866                // expand lastMultiSSAIdMap from all calls
     867                for (const NextBlock& next: cblock.nexts)
     868                if (next.isCall)
     869                    {
     870                        auto it = routineMap.find(next.block); // must find
     871                        joinLastSSAIdMap(lastMultiSSAIdMap, it->second.regVarMap);
     872                    }
     873            }
    687874            flowStack.push_back({ entry.blockIndex+1, 0 });
    688875            entry.nextIndex++;
     
    690877        else // back
    691878        {
     879            // revert lastMultiSSAIdMap changes (add removed entries)
     880            if (cblock.haveCalls)
     881            {
     882                //remove all return parallel ssaids
     883                for(const NextBlock& next: cblock.nexts)
     884                    if (!next.isCall)
     885                    {
     886                        auto it = routineMap.find(next.block); // must find
     887                        removeLastSSAIdMap(lastMultiSSAIdMap, it->second.regVarMap);
     888                    }
     889            }
     890            else // normal block (revert changes in lastMultiSSAIdMap)
     891                lastMultiSSAIdMap.insert(entry.replacedMultiSSAIds.begin(),
     892                                entry.replacedMultiSSAIds.end());
     893            // erase at pop from selectedRoutines
     894            selectedRoutines.erase(entry.blockIndex);
    692895            for (const auto& ssaEntry: cblock.ssaInfoMap)
    693896            {
     
    702905    }
    703906}
    704 
     907   
    705908void AsmRegAllocator::applySSAReplaces()
    706909{
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc.cpp

    r3575 r3582  
    505505        },
    506506        true, ""
    507     }
     507    },
     508    {   /* 13 - subroutines 2 (one is jump) */
     509        R"ffDXD(
     510        v_mov_b32 v1, v2
     511        v_mov_b32 v1, v3
     512        .cf_call l0, l1
     513        .cf_jump l2
     514        s_setpc_b64 s[0:1]
     515        v_sub_f32 v1, v3, v6    # 12
     516        s_branch j0
     517b0:     v_add_u32 v4, vcc, v6, v11  # 20
     518        v_mac_f32 v6, v6, v6
     519        s_endpgm
     520l0:     # 32
     521        v_add_f32 v1, v2, v3
     522        v_add_f32 v1, v2, v3
     523        .cf_ret
     524        s_swappc_b64 s[0:1], s[0:1]
     525l1:     # 44
     526        v_add_f32 v1, v2, v3
     527        v_add_f32 v1, v2, v3
     528        v_add_f32 v1, v2, v3
     529        .cf_ret
     530        s_swappc_b64 s[0:1], s[0:1]
     531l2:     # 60
     532        v_add_f32 v1, v2, v3
     533        v_add_f32 v1, v2, v3
     534        v_add_f32 v1, v2, v3
     535        v_add_f32 v1, v2, v3
     536        v_add_f32 v1, v2, v3
     537        .cf_ret
     538        s_swappc_b64 s[0:1], s[0:1]
     539j0:     # 84
     540        v_lshrrev_b32 v4, 3, v2
     541        v_lshrrev_b32 v4, 3, v2
     542        s_branch b0
     543)ffDXD",
     544        {
     545            { 0, 12,
     546                { { 1, false }, { 5, false }, { 3, true }, { 4, true } },
     547                true, false, true },
     548            { 12, 20, { { 6, false } }, false, false, true },
     549            { 20, 32, { }, false, false, true },
     550            { 32, 44, { }, false, true, true },
     551            { 44, 60, { }, false, true, true },
     552            { 60, 84, { }, false, true, true },
     553            { 84, 96, { { 2, false } }, false, false, true }
     554        },
     555        true, ""
     556    },
    508557};
    509558
Note: See TracChangeset for help on using the changeset viewer.