Changeset 3837 in CLRX


Ignore:
Timestamp:
Feb 22, 2018, 5:51:47 PM (14 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Separate some functional blocks in createSSAData into smaller routines.

File:
1 edited

Legend:

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

    r3658 r3837  
    444444// map of last SSAId for routine, key - varid, value - last SSA ids
    445445typedef std::unordered_map<AsmSingleVReg, std::vector<size_t> > LastSSAIdMap;
    446 
    447 typedef std::unordered_map<AsmSingleVReg, std::vector<bool> > LastOccurMap;
    448446
    449447struct RetSSAEntry
     
    892890}
    893891
     892static void reduceSSAIds(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
     893            RetSSAIdMap& retSSAIdMap, std::unordered_map<size_t, RoutineData>& routineMap,
     894            SSAReplacesMap& ssaReplacesMap,
     895            std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry)
     896{
     897    SSAInfo& sinfo = ssaEntry.second;
     898    size_t& ssaId = curSSAIdMap[ssaEntry.first];
     899    auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
     900    if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
     901    {
     902        auto& ssaIds = ssaIdsIt->second.ssaIds;
     903       
     904        if (ssaIds.size() >= 2)
     905        {
     906            // reduce to minimal ssaId from all calls
     907            std::sort(ssaIds.begin(), ssaIds.end());
     908            ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end()) - ssaIds.begin());
     909            // insert SSA replaces
     910            size_t minSSAId = ssaIds.front();
     911            for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit)
     912                insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId);
     913            ssaId = minSSAId+1; // plus one
     914        }
     915        else if (ssaIds.size() == 1)
     916            ssaId = ssaIds.front()+1; // plus one
     917       
     918        std::cout << "retssa ssaid: " << ssaEntry.first.regVar << ":" <<
     919                ssaEntry.first.index << ": " << ssaId << std::endl;
     920        // replace smallest ssaId in routineMap lastSSAId entry
     921        // reduce SSAIds replaces
     922        for (size_t rblock: ssaIdsIt->second.routines)
     923            routineMap.find(rblock)->second.lastSSAIdMap[ssaEntry.first] =
     924                    std::vector<size_t>({ ssaId-1 });
     925        // finally remove from container (because obsolete)
     926        retSSAIdMap.erase(ssaIdsIt);
     927    }
     928}
     929
     930static void updateRoutineData(RoutineData& rdata,
     931        std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry)
     932{
     933    const SSAInfo& sinfo = ssaEntry.second;
     934    // put first SSAId before write
     935    if (sinfo.readBeforeWrite)
     936    {
     937        //std::cout << "PutCRBW: " << sinfo.ssaIdBefore << std::endl;
     938        rdata.rbwSSAIdMap.insert({ ssaEntry.first, sinfo.ssaIdBefore });
     939    }
     940   
     941    if (sinfo.ssaIdChange != 0)
     942    {
     943        // put last SSAId
     944        //std::cout << "PutC: " << sinfo.ssaIdLast << std::endl;
     945        auto res = rdata.curSSAIdMap.insert({ ssaEntry.first,
     946                { sinfo.ssaIdLast } });
     947        if (!res.second)
     948        {
     949            // if not inserted
     950            std::vector<size_t>& ssaIds = res.first->second;
     951            auto ssaIdIt = ssaIds.end();
     952            if (sinfo.readBeforeWrite)
     953                ssaIdIt = std::find(ssaIds.begin(), ssaIds.end(),
     954                        sinfo.ssaIdBefore);
     955            if (ssaIdIt == ssaIds.end())
     956                ssaIds.push_back(sinfo.ssaIdLast);
     957            else
     958                *ssaIdIt = sinfo.ssaIdLast;
     959        }
     960    }
     961}
     962
     963static void initializePrevRetSSAIds(const RetSSAIdMap& retSSAIdMap,
     964            const RoutineData& rdata, FlowStackEntry& entry)
     965{
     966    for (const auto& v: rdata.lastSSAIdMap)
     967    {
     968        auto res = entry.prevRetSSAIdSets.insert({v.first, {}});
     969        if (!res.second)
     970            continue; // already added, do not change
     971        auto rfit = retSSAIdMap.find(v.first);
     972        if (rfit != retSSAIdMap.end())
     973            res.first->second = rfit->second;
     974    }
     975}
     976
     977static void revertRetSSAIdMap(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
     978            RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, RoutineData* rdata)
     979{
     980    // revert retSSAIdMap
     981    for (auto v: entry.prevRetSSAIdSets)
     982    {
     983        auto rfit = retSSAIdMap.find(v.first);
     984        if (rdata!=nullptr)
     985        {
     986            std::vector<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
     987            for (size_t ssaId: rfit->second.ssaIds)
     988            {
     989                auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId);
     990                if (ssaIdsIt != ssaIds.end())
     991                    ssaIds.erase(ssaIdsIt);
     992            }
     993        }
     994       
     995        if (!v.second.ssaIds.empty())
     996            rfit->second = v.second;
     997        else // erase if empty
     998            retSSAIdMap.erase(v.first);
     999       
     1000        if (rdata!=nullptr)
     1001        {
     1002            std::vector<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
     1003            for (size_t ssaId: v.second.ssaIds)
     1004            {
     1005                auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId);
     1006                if (ssaIdsIt == ssaIds.end())
     1007                    ssaIds.push_back(ssaId);
     1008            }
     1009            if (v.second.ssaIds.empty())
     1010                ssaIds.push_back(curSSAIdMap[v.first]-1);
     1011           
     1012            std::cout << " popentry2 " << entry.blockIndex << ": " <<
     1013                    v.first.regVar << ":" << v.first.index << ":";
     1014            for (size_t v: ssaIds)
     1015                std::cout << " " << v;
     1016            std::cout << std::endl;
     1017        }
     1018    }
     1019}
     1020
     1021static void updateRoutineCurSSAIdMap(RoutineData* rdata,
     1022            const std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry,
     1023            const FlowStackEntry& entry, size_t curSSAId, size_t nextSSAId)
     1024{
     1025    std::vector<size_t>& ssaIds = rdata->curSSAIdMap[ssaEntry.first];
     1026    std::cout << " pushentry " << entry.blockIndex << ": " <<
     1027                ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
     1028    for (size_t v: ssaIds)
     1029        std::cout << " " << v;
     1030    std::cout << std::endl;
     1031   
     1032    {   // if cblock with some children
     1033        auto nit = std::find(ssaIds.begin(), ssaIds.end(), nextSSAId-1);
     1034        if (nit != ssaIds.end() && nextSSAId != curSSAId)
     1035        {
     1036            std::cout << "erase in blk2: " << ssaEntry.first.regVar <<
     1037                    ":" << ssaEntry.first.index << ": " <<
     1038                    entry.blockIndex << " ssaId=" << *nit << std::endl;
     1039            ssaIds.erase(nit);  // just remove
     1040        }
     1041    }
     1042    // push previous SSAId to lastSSAIdMap (later will be replaced)
     1043    /*std::cout << "call back: " << nextSSAId << "," <<
     1044            (curSSAId) << std::endl;*/
     1045    auto fit = std::find(ssaIds.begin(), ssaIds.end(), curSSAId-1);
     1046    if (fit == ssaIds.end())
     1047        ssaIds.push_back(curSSAId-1);
     1048   
     1049    std::cout << " popentry " << entry.blockIndex << ": " <<
     1050                ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
     1051    for (size_t v: ssaIds)
     1052        std::cout << " " << v;
     1053    std::cout << std::endl;
     1054}
     1055
    8941056void AsmRegAllocator::createSSAData(ISAUsageHandler& usageHandler)
    8951057{
     
    9681130    std::unordered_map<size_t, RoutineData> routineMap;
    9691131   
    970     LastOccurMap lastOccurMap;
    971    
    9721132    std::vector<bool> visited(codeBlocks.size(), false);
    9731133    flowStack.push_back({ 0, 0 });
     
    9961156                    }
    9971157                   
    998                     if (sinfo.ssaIdChange != 0)
    999                     {
    1000                         /*std::cout << "loccurpush: " << ssaEntry.first.regVar << ":" <<
    1001                                 ssaEntry.first.index << ": " <<
    1002                                 entry.blockIndex << std::endl;*/
    1003                         lastOccurMap[ssaEntry.first].push_back(false);
    1004                     }
     1158                    reduceSSAIds(curSSAIdMap, retSSAIdMap, routineMap, ssaReplacesMap,
     1159                                 ssaEntry);
    10051160                   
    10061161                    size_t& ssaId = curSSAIdMap[ssaEntry.first];
    1007                     auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
    1008                     if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
    1009                     {
    1010                         auto& ssaIds = ssaIdsIt->second.ssaIds;
    1011                        
    1012                         if (ssaIds.size() >= 2)
    1013                         {
    1014                             // reduce to minimal ssaId from all calls
    1015                             std::sort(ssaIds.begin(), ssaIds.end());
    1016                             ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end()) -
    1017                                     ssaIds.begin());
    1018                             // insert SSA replaces
    1019                             size_t minSSAId = ssaIds.front();
    1020                             for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit)
    1021                                 insertReplace(ssaReplacesMap, ssaEntry.first,
    1022                                         *sit, minSSAId);
    1023                             ssaId = minSSAId+1; // plus one
    1024                         }
    1025                         else if (ssaIds.size() == 1)
    1026                             ssaId = ssaIds.front()+1; // plus one
    1027                        
    1028                         std::cout << "retssa ssaid: " << ssaEntry.first.regVar << ":" <<
    1029                                 ssaEntry.first.index << ": " << ssaId << std::endl;
    1030                         // replace smallest ssaId in routineMap lastSSAId entry
    1031                         // reduce SSAIds replaces
    1032                         for (size_t rblock: ssaIdsIt->second.routines)
    1033                             routineMap.find(rblock)->second.lastSSAIdMap[ssaEntry.first] =
    1034                                     std::vector<size_t>({ ssaId-1 });
    1035                         // finally remove from container (because obsolete)
    1036                         retSSAIdMap.erase(ssaIdsIt);
    1037                     }
    10381162                   
    10391163                    size_t& totalSSACount = totalSSACountMap[ssaEntry.first];
     
    10581182                   
    10591183                    if (!callStack.empty())
    1060                     {
    10611184                        // put data to routine data
    1062                         RoutineData& rdata =
    1063                                 routineMap.find(callStack.back().routineBlock)->second;
    1064                         // put first SSAId before write
    1065                         if (sinfo.readBeforeWrite)
    1066                         {
    1067                             //std::cout << "PutCRBW: " << sinfo.ssaIdBefore << std::endl;
    1068                             rdata.rbwSSAIdMap.insert({ ssaEntry.first, sinfo.ssaIdBefore });
    1069                         }
    1070                        
    1071                         if (sinfo.ssaIdChange != 0)
    1072                         {
    1073                             // put last SSAId
    1074                             //std::cout << "PutC: " << sinfo.ssaIdLast << std::endl;
    1075                             auto res = rdata.curSSAIdMap.insert({ ssaEntry.first,
    1076                                     { sinfo.ssaIdLast } });
    1077                             if (!res.second)
    1078                             {
    1079                                 // if not inserted
    1080                                 std::vector<size_t>& ssaIds = res.first->second;
    1081                                 auto ssaIdIt = ssaIds.end();
    1082                                 if (sinfo.readBeforeWrite)
    1083                                     ssaIdIt = std::find(ssaIds.begin(), ssaIds.end(),
    1084                                             sinfo.ssaIdBefore);
    1085                                 if (ssaIdIt == ssaIds.end())
    1086                                     ssaIds.push_back(sinfo.ssaIdLast);
    1087                                 else
    1088                                     *ssaIdIt = sinfo.ssaIdLast;
    1089                             }
    1090                         }
    1091                     }
     1185                        updateRoutineData(routineMap.find(
     1186                            callStack.back().routineBlock)->second, ssaEntry);
    10921187                }
    10931188            }
     
    11391234                        //std::cout << "joincall:"<< next.block << std::endl;
    11401235                        auto it = routineMap.find(next.block); // must find
    1141                         for (const auto& v: it->second.lastSSAIdMap)
    1142                         {
    1143                             auto res = entry.prevRetSSAIdSets.insert({v.first, {}});
    1144                             if (!res.second)
    1145                                 continue; // already added, do not change
    1146                             auto rfit = retSSAIdMap.find(v.first);
    1147                             if (rfit != retSSAIdMap.end())
    1148                                 res.first->second = rfit->second;
    1149                         }
    1150                        
     1236                        initializePrevRetSSAIds(retSSAIdMap, it->second, entry);
    11511237                        joinRetSSAIdMap(retSSAIdMap, it->second.lastSSAIdMap, next.block);
    11521238                    }
     
    11691255           
    11701256            // revert retSSAIdMap
    1171             for (auto v: entry.prevRetSSAIdSets)
    1172             {
    1173                 auto rfit = retSSAIdMap.find(v.first);
    1174                 if (rdata!=nullptr)
    1175                 {
    1176                     std::vector<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
    1177                     for (size_t ssaId: rfit->second.ssaIds)
    1178                     {
    1179                         auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId);
    1180                         if (ssaIdsIt != ssaIds.end())
    1181                             ssaIds.erase(ssaIdsIt);
    1182                     }
    1183                 }
    1184                
    1185                 if (!v.second.ssaIds.empty())
    1186                     rfit->second = v.second;
    1187                 else // erase if empty
    1188                     retSSAIdMap.erase(v.first);
    1189                
    1190                 if (rdata!=nullptr)
    1191                 {
    1192                     std::vector<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
    1193                     for (size_t ssaId: v.second.ssaIds)
    1194                     {
    1195                         auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId);
    1196                         if (ssaIdsIt == ssaIds.end())
    1197                             ssaIds.push_back(ssaId);
    1198                     }
    1199                     if (v.second.ssaIds.empty())
    1200                         ssaIds.push_back(curSSAIdMap[v.first]-1);
    1201                    
    1202                     std::cout << " popentry2 " << entry.blockIndex << ": " <<
    1203                             v.first.regVar << ":" <<
    1204                             v.first.index << ":";
    1205                     for (size_t v: ssaIds)
    1206                             std::cout << " " << v;
    1207                         std::cout << std::endl;
    1208                    
    1209                 }
    1210             }
     1257            revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, rdata);
    12111258            //
    12121259           
     
    12291276               
    12301277                if (rdata!=nullptr)
     1278                    updateRoutineCurSSAIdMap(rdata, ssaEntry, entry, curSSAId, nextSSAId);
    12311279                {
    1232                     std::vector<size_t>& ssaIds = rdata->curSSAIdMap[ssaEntry.first];
    12331280                   
    1234                     std::cout << " pushentry " << entry.blockIndex << ": " <<
    1235                                 ssaEntry.first.regVar << ":" <<
    1236                                 ssaEntry.first.index << ":";
    1237                     for (size_t v: ssaIds)
    1238                         std::cout << " " << v;
    1239                     std::cout << std::endl;
    1240                    
    1241                     /*if (ssaEntry.second.ssaIdChange != 0 &&
    1242                         lastOccurMap[ssaEntry.first].back())*/
    1243                     {   // if cblock with some children
    1244                         auto nit = std::find(ssaIds.begin(), ssaIds.end(), nextSSAId-1);
    1245                         if (nit != ssaIds.end() && nextSSAId != curSSAId)
    1246                         {
    1247                             std::cout << "erase in blk2: " << ssaEntry.first.regVar <<
    1248                                     ":" << ssaEntry.first.index << ": " <<
    1249                                     entry.blockIndex << " ssaId=" << *nit << std::endl;
    1250                             ssaIds.erase(nit);  // just remove
    1251                         }
    1252                     }
    1253                     // push previous SSAId to lastSSAIdMap (later will be replaced)
    1254                     /*std::cout << "call back: " << nextSSAId << "," <<
    1255                             (curSSAId) << std::endl;*/
    1256                     auto fit = std::find(ssaIds.begin(), ssaIds.end(), curSSAId-1);
    1257                     /*if (entry.blockIndex == callStack.back().routineBlock)
    1258                     {   // just erase if end of traverse in routine
    1259                         if (fit != ssaIds.end())
    1260                         {
    1261                             std::cout << "erase in blk: " << ssaEntry.first.regVar <<
    1262                                     ":" << ssaEntry.first.index << ": " <<
    1263                                     entry.blockIndex << " ssaId=" << *fit << std::endl;
    1264                             ssaIds.erase(fit);
    1265                         }
    1266                     }
    1267                     else*/ if (fit == ssaIds.end())
    1268                         ssaIds.push_back(curSSAId-1);
    1269                    
    1270                     std::cout << " popentry " << entry.blockIndex << ": " <<
    1271                                 ssaEntry.first.regVar << ":" <<
    1272                                 ssaEntry.first.index << ":";
    1273                     for (size_t v: ssaIds)
    1274                         std::cout << " " << v;
    1275                     std::cout << std::endl;
    1276                 }
    1277                
    1278                 if (ssaEntry.second.ssaIdChange != 0)
    1279                 {
    1280                     /*std::cout << "loccurpop: " << ssaEntry.first.regVar << ":" <<
    1281                                 ssaEntry.first.index << ": " <<
    1282                                 entry.blockIndex << std::endl;*/
    1283                     std::vector<bool>& lastOccur = lastOccurMap[ssaEntry.first];
    1284                     // erase indicator for last SSAEntry
    1285                     lastOccur.pop_back();
    1286                     if (!lastOccur.empty())
    1287                         // mark that parent have children
    1288                         lastOccur.back() = true;
    12891281                }
    12901282            }
Note: See TracChangeset for help on using the changeset viewer.