Changeset 3581 in CLRX


Ignore:
Timestamp:
Jan 4, 2018, 7:37:05 PM (13 days ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Cleanup before rewriting createSSAData.

File:
1 edited

Legend:

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

    r3580 r3581  
    440440};
    441441
    442 // map of last SSAId for routine, key - varid, value - last SSA ids
    443 
    444 typedef std::unordered_map<AsmSingleVReg, std::vector<size_t> > LastSSAIdMap;
    445 struct RoutineData
    446 {
    447     bool processed;
    448     LastSSAIdMap regVarMap;
    449 };
    450 
    451442struct FlowStackEntry
    452443{
    453444    size_t blockIndex;
    454445    size_t nextIndex;
    455     LastSSAIdMap replacedMultiSSAIds;
    456         // ssaIds from called routine already visited before call
    457446    std::unordered_map<AsmSingleVReg, size_t> prevSSAIds;
    458 };
    459 
    460 struct CallStackEntry
    461 {
    462     size_t callBlock; // index
    463     size_t callNextIndex; // index of call next
    464447};
    465448
     
    481464
    482465static void resolveSSAConflicts(const std::deque<FlowStackEntry>& prevFlowStack,
    483         const std::stack<CallStackEntry>& prevCallStack,
    484466        const std::vector<bool>& prevVisited,
    485         const std::unordered_map<size_t, RoutineData>& routineMap,
    486467        const std::vector<CodeBlock>& codeBlocks,
    487468        SSAReplacesMap& replacesMap)
     
    490471    auto pfEnd = prevFlowStack.end();
    491472    --pfEnd;
    492     LastSSAIdMap stackVarMap;
     473    std::unordered_map<AsmSingleVReg, size_t> stackVarMap;
    493474    for (auto pfit = prevFlowStack.begin(); pfit != pfEnd; ++pfit)
    494475    {
     
    499480            const SSAInfo& sinfo = sentry.second;
    500481            if (sinfo.ssaIdChange != 0)
    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;
     482                stackVarMap[sentry.first] = sinfo.ssaId + sinfo.ssaIdChange - 1;
     483        }
     484    }
     485   
    514486    // traverse by graph from next block
    515487    std::deque<FlowStackEntry> flowStack;
     
    543515                        if (it != stackVarMap.end())
    544516                            // found, resolve by set ssaIdLast
    545                             for (size_t ssaId: it->second)
    546                                 if (ssaId > sinfo.ssaIdBefore)
    547                                     insertReplace(replacesMap, sentry.first, ssaId,
    548                                                 sinfo.ssaIdBefore);
     517                            if (it->second > sinfo.ssaIdBefore)
     518                                insertReplace(replacesMap, sentry.first, it->second,
     519                                            sinfo.ssaIdBefore);
    549520                        res.first->second.handled = true;
    550521                    }
     
    559530        }
    560531       
    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        
    566532        if (entry.nextIndex < cblock.nexts.size() &&
    567533            prevVisited[cblock.nexts[entry.nextIndex].block])
    568534        {
    569535            if (cblock.nexts[entry.nextIndex].isCall)
    570                 callStack.push({ entry.blockIndex, entry.nextIndex });
     536                ;//callStack.push({ entry.blockIndex, entry.nextIndex });
    571537            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    572538            entry.nextIndex++;
     
    593559            }
    594560            flowStack.pop_back();
    595         }
    596     }
    597 }
    598 
    599 static 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 
    631 static 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 
    649 static 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);
    661561        }
    662562    }
     
    720620    }
    721621   
    722     std::stack<CallStackEntry> callStack;
    723622    std::deque<FlowStackEntry> flowStack;
    724623    // total SSA count
     
    726625    // last SSA ids in current way in code flow
    727626    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;
    738627    std::vector<bool> visited(codeBlocks.size(), false);
    739628    flowStack.push_back({ 0, 0 });
     
    773662                    ssaId = totalSSACount;
    774663                }
    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                 }
    820664            }
    821665            else
    822666            {
    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);
     667                resolveSSAConflicts(flowStack, visited, codeBlocks, ssaReplacesMap);
    840668                // back, already visited
    841669                flowStack.pop_back();
     
    844672        }
    845673       
    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        
    851674        if (entry.nextIndex < cblock.nexts.size())
    852675        {
    853676            if (cblock.nexts[entry.nextIndex].isCall)
    854                 callStack.push({ entry.blockIndex, entry.nextIndex });
     677                ;//callStack.push({ entry.blockIndex, entry.nextIndex });
    855678           
    856679            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
     
    862685                 !cblock.haveReturn && !cblock.haveEnd)
    863686        {
    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             }
    874687            flowStack.push_back({ entry.blockIndex+1, 0 });
    875688            entry.nextIndex++;
     
    877690        else // back
    878691        {
    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);
    895692            for (const auto& ssaEntry: cblock.ssaInfoMap)
    896693            {
     
    905702    }
    906703}
    907    
     704
    908705void AsmRegAllocator::applySSAReplaces()
    909706{
Note: See TracChangeset for help on using the changeset viewer.