Changeset 3955 in CLRX


Ignore:
Timestamp:
Mar 31, 2018, 4:59:53 PM (4 weeks ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Apply CBlockBitPool.

File:
1 edited

Legend:

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

    r3954 r3955  
    605605}
    606606
     607class CLRX_INTERNAL CBlockBitPool: public std::vector<bool>
     608{
     609public:
     610    CBlockBitPool(size_t n = 0, bool v = false) : std::vector<bool>(n<<1, v)
     611    { }
     612   
     613    reference operator[](BlockIndex i)
     614    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
     615    const_reference operator[](BlockIndex i) const
     616    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
     617};
     618
    607619/** Simple cache **/
    608620
     
    707719};
    708720
    709 class ResSecondPointsToCache: public std::vector<bool>
     721typedef std::unordered_map<BlockIndex, RoutineData> RoutineMap;
     722
     723class CLRX_INTERNAL ResSecondPointsToCache: public CBlockBitPool
    710724{
    711725public:
    712     explicit ResSecondPointsToCache(size_t n) : std::vector<bool>(n<<1, false)
     726    explicit ResSecondPointsToCache(size_t n) : CBlockBitPool(n<<1, false)
    713727    { }
    714728   
    715     void increase(size_t i)
    716     {
     729    void increase(BlockIndex ip)
     730    {
     731        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
    717732        if ((*this)[i<<1])
    718733            (*this)[(i<<1)+1] = true;
     
    721736    }
    722737   
    723     cxuint count(size_t i) const
    724     { return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1]; }
     738    cxuint count(BlockIndex ip) const
     739    {
     740        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
     741        return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1];
     742    }
    725743};
    726744
     
    861879
    862880// add new res second cache entry with readBeforeWrite for all encountered regvars
    863 static void addResSecCacheEntry(
    864                 const std::unordered_map<BlockIndex, RoutineData>& routineMap,
     881static void addResSecCacheEntry(const RoutineMap& routineMap,
    865882                const std::vector<CodeBlock>& codeBlocks,
    866883                SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
     
    872889    std::deque<FlowStackEntry2> flowStack;
    873890    flowStack.push_back({ nextBlock, 0 });
    874     std::vector<bool> visited(codeBlocks.size(), false);
     891    CBlockBitPool visited(codeBlocks.size(), false);
    875892   
    876893    std::unordered_map<AsmSingleVReg, BlockIndex> alreadyReadMap;
     
    886903        {
    887904            // process current block
    888             if (!visited[entry.blockIndex.index])
    889             {
    890                 visited[entry.blockIndex.index] = true;
     905            if (!visited[entry.blockIndex])
     906            {
     907                visited[entry.blockIndex] = true;
    891908                std::cout << "  resolv (cache): " << entry.blockIndex << std::endl;
    892909               
     
    978995
    979996// apply calls (changes from these calls) from code blocks to stack var map
    980 static void applyCallToStackVarMap(const CodeBlock& cblock,
    981         const std::unordered_map<BlockIndex, RoutineData>& routineMap,
     997static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineMap& routineMap,
    982998        LastSSAIdMap& stackVarMap, BlockIndex blockIndex, size_t nextIndex)
    983999{
     
    10081024// it emits SSA replaces from these conflicts
    10091025static void resolveSSAConflicts(const std::deque<FlowStackEntry2>& prevFlowStack,
    1010         const std::unordered_map<BlockIndex, RoutineData>& routineMap,
    1011         const std::vector<CodeBlock>& codeBlocks,
     1026        const RoutineMap& routineMap, const std::vector<CodeBlock>& codeBlocks,
    10121027        const PrevWaysIndexMap& prevWaysIndexMap,
    1013         const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
     1028        const CBlockBitPool& waysToCache, ResSecondPointsToCache& cblocksToCache,
    10141029        SimpleCache<BlockIndex, LastSSAIdMap>& resFirstPointsCache,
    10151030        SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
     
    10631078       
    10641079        // put to first point cache
    1065         if (waysToCache[pfit->blockIndex.index] &&
     1080        if (waysToCache[pfit->blockIndex] &&
    10661081            !resFirstPointsCache.hasKey(pfit->blockIndex))
    10671082        {
     
    10731088    RBWSSAIdMap cacheSecPoints;
    10741089    const bool toCache = (!resSecondPointsCache.hasKey(nextBlock)) &&
    1075                 cblocksToCache.count(nextBlock.index)>=2;
     1090                cblocksToCache.count(nextBlock)>=2;
    10761091   
    10771092    //std::stack<CallStackEntry> callStack = prevCallStack;
     
    10791094    std::deque<FlowStackEntry2> flowStack;
    10801095    flowStack.push_back({ nextBlock, 0 });
    1081     std::vector<bool> visited(codeBlocks.size(), false);
     1096    CBlockBitPool visited(codeBlocks.size(), false);
    10821097   
    10831098    // already read in current path
     
    10931108        {
    10941109            // process current block
    1095             if (!visited[entry.blockIndex.index])
    1096             {
    1097                 visited[entry.blockIndex.index] = true;
     1110            if (!visited[entry.blockIndex])
     1111            {
     1112                visited[entry.blockIndex] = true;
    10981113                std::cout << "  resolv: " << entry.blockIndex << std::endl;
    10991114               
     
    11161131            else
    11171132            {
    1118                 cblocksToCache.increase(entry.blockIndex.index);
     1133                cblocksToCache.increase(entry.blockIndex);
    11191134                std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
    1120                             cblocksToCache.count(entry.blockIndex.index) << std::endl;
     1135                            cblocksToCache.count(entry.blockIndex) << std::endl;
    11211136                // back, already visited
    11221137                std::cout << "resolv already: " << entry.blockIndex << std::endl;
     
    11821197            std::cout << "  popresolv" << std::endl;
    11831198           
    1184             if (cblocksToCache.count(entry.blockIndex.index)==2 &&
     1199            if (cblocksToCache.count(entry.blockIndex)==2 &&
    11851200                !resSecondPointsCache.hasKey(entry.blockIndex))
    11861201                // add to cache
     
    13371352static void reduceSSAIdsForCalls(FlowStackEntry& entry,
    13381353            const std::vector<CodeBlock>& codeBlocks,
    1339             RetSSAIdMap& retSSAIdMap,
    1340             std::unordered_map<BlockIndex, RoutineData>& routineMap,
     1354            RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
    13411355            SSAReplacesMap& ssaReplacesMap)
    13421356{
     
    14201434// and emits SSA replaces for these ssaids
    14211435static bool reduceSSAIds(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1422             RetSSAIdMap& retSSAIdMap,
    1423             std::unordered_map<BlockIndex, RoutineData>& routineMap,
     1436            RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
    14241437            SSAReplacesMap& ssaReplacesMap, FlowStackEntry& entry, SSAEntry& ssaEntry)
    14251438{
     
    16381651        const ResSecondPointsToCache& subroutToCache,
    16391652        SimpleCache<BlockIndex, RoutineData>& subroutinesCache,
    1640         const std::unordered_map<BlockIndex, RoutineData>& routineMap, RoutineData& rdata,
     1653        const RoutineMap& routineMap, RoutineData& rdata,
    16411654        BlockIndex routineBlock, bool noMainLoop = false,
    1642         const std::vector<bool>& prevFlowStackBlocks = {})
     1655        const CBlockBitPool& prevFlowStackBlocks = {})
    16431656{
    16441657    std::cout << "--------- createRoutineData ----------------\n";
    1645     std::vector<bool> visited(codeBlocks.size(), false);
     1658    CBlockBitPool visited(codeBlocks.size(), false);
    16461659   
    16471660    VectorSet<BlockIndex> activeLoops;
    16481661    SubrLoopsMap subrLoopsMap;
    16491662    SubrLoopsMap loopSubrsMap;
    1650     std::unordered_map<BlockIndex, RoutineData> subrDataForLoopMap;
     1663    RoutineMap subrDataForLoopMap;
    16511664    std::deque<FlowStackEntry> flowStack;
    1652     std::vector<bool> flowStackBlocks(codeBlocks.size(), false);
     1665    CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
    16531666    if (!prevFlowStackBlocks.empty())
    16541667        flowStackBlocks = prevFlowStackBlocks;
     
    16561669    RetSSAIdMap retSSAIdMap;
    16571670    flowStack.push_back({ routineBlock, 0 });
    1658     flowStackBlocks[routineBlock.index] = true;
     1671    flowStackBlocks[routineBlock] = true;
    16591672   
    16601673    while (!flowStack.empty())
     
    16821695           
    16831696            RoutineData subrData;
    1684             const bool oldFB = flowStackBlocks[entry.blockIndex.index];
    1685             flowStackBlocks[entry.blockIndex.index] = !oldFB;
     1697            const bool oldFB = flowStackBlocks[entry.blockIndex];
     1698            flowStackBlocks[entry.blockIndex] = !oldFB;
    16861699            createRoutineData(codeBlocks, curSSAIdMap, loopBlocks, subroutToCache,
    16871700                subroutinesCache, routineMap, subrData, entry.blockIndex, true,
    16881701                flowStackBlocks);
    16891702            RoutineData subrDataCopy;
    1690             flowStackBlocks[entry.blockIndex.index] = oldFB;
     1703            flowStackBlocks[entry.blockIndex] = oldFB;
    16911704           
    16921705            if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
     
    17581771            bool isLoop = loopBlocks.find(entry.blockIndex) != loopBlocks.end();
    17591772           
    1760             if (!prevFlowStackBlocks.empty() && prevFlowStackBlocks[entry.blockIndex.index])
     1773            if (!prevFlowStackBlocks.empty() && prevFlowStackBlocks[entry.blockIndex])
    17611774            {
    17621775                tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
    17631776               
    1764                 flowStackBlocks[entry.blockIndex.index] =
    1765                         !flowStackBlocks[entry.blockIndex.index];
     1777                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    17661778                flowStack.pop_back();
    17671779                continue;
     
    17831795                        cachedRdata = &rit->second;
    17841796                }
    1785                 if (!isLoop && visited[entry.blockIndex.index] && cachedRdata == nullptr &&
    1786                     subroutToCache.count(entry.blockIndex.index)!=0)
     1797                if (!isLoop && visited[entry.blockIndex] && cachedRdata == nullptr &&
     1798                    subroutToCache.count(entry.blockIndex)!=0)
    17871799                {
    17881800                    auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
     
    18251837                }
    18261838                std::cout << "procretend2" << std::endl;
    1827                 flowStackBlocks[entry.blockIndex.index] =
    1828                             !flowStackBlocks[entry.blockIndex.index];
     1839                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    18291840                flowStack.pop_back();
    18301841                continue;
    18311842            }
    1832             else if (!visited[entry.blockIndex.index])
     1843            else if (!visited[entry.blockIndex])
    18331844            {
    18341845                // set up loops for which subroutine is present
    1835                 if (subroutToCache.count(entry.blockIndex.index)!=0 && !activeLoops.empty())
     1846                if (subroutToCache.count(entry.blockIndex)!=0 && !activeLoops.empty())
    18361847                {
    18371848                    subrLoopsMap.insert({ entry.blockIndex, activeLoops });
     
    18471858                    activeLoops.insertValue(entry.blockIndex);
    18481859                std::cout << "proc: " << entry.blockIndex << std::endl;
    1849                 visited[entry.blockIndex.index] = true;
     1860                visited[entry.blockIndex] = true;
    18501861               
    18511862                for (const auto& ssaEntry: cblock.ssaInfoMap)
     
    18621873            {
    18631874                tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
    1864                 flowStackBlocks[entry.blockIndex.index] =
    1865                         !flowStackBlocks[entry.blockIndex.index];
     1875                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    18661876                flowStack.pop_back();
    18671877                continue;
     
    18771887        if (entry.nextIndex < cblock.nexts.size())
    18781888        {
    1879             const size_t nextBlock = cblock.nexts[entry.nextIndex].block;
     1889            const BlockIndex nextBlock = cblock.nexts[entry.nextIndex].block;
    18801890            flowStack.push_back({ nextBlock, 0 });
    18811891            // negate - if true (already in flowstack, then popping keep this state)
     
    19031913            flowStack.push_back({ nextBlock, 0 });
    19041914            // negate - if true (already in flowstack, then popping keep this state)
    1905             flowStackBlocks[nextBlock.index] = !flowStackBlocks[nextBlock.index];
     1915            flowStackBlocks[nextBlock] = !flowStackBlocks[nextBlock];
    19061916            entry.nextIndex++;
    19071917        }
     
    19551965           
    19561966            if ((!noMainLoop || flowStack.size() > 1) &&
    1957                 subroutToCache.count(entry.blockIndex.index)!=0)
     1967                subroutToCache.count(entry.blockIndex)!=0)
    19581968            { //put to cache
    19591969                std::cout << "-- subrcache for " << entry.blockIndex << std::endl;
     
    19611971            }
    19621972           
    1963             flowStackBlocks[entry.blockIndex.index] = false;
     1973            flowStackBlocks[entry.blockIndex] = false;
    19641974            std::cout << "pop: " << entry.blockIndex << std::endl;
    19651975            flowStack.pop_back();
     
    20492059    std::unordered_map<AsmSingleVReg, size_t> curSSAIdMap;
    20502060    // routine map - routine datas map, value - last SSA ids map
    2051     std::unordered_map<BlockIndex, RoutineData> routineMap;
     2061    RoutineMap routineMap;
    20522062    // key - current res first key, value - previous first key and its flowStack pos
    20532063    PrevWaysIndexMap prevWaysIndexMap;
    20542064    // to track ways last block indices pair: block index, flowStackPos)
    20552065    std::pair<BlockIndex, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
    2056     std::vector<bool> isRoutineGen(codeBlocks.size(), false);
    2057    
    2058     std::vector<bool> waysToCache(codeBlocks.size(), false);
    2059     std::vector<bool> flowStackBlocks(codeBlocks.size(), false);
     2066    CBlockBitPool isRoutineGen(codeBlocks.size(), false);
     2067   
     2068    CBlockBitPool waysToCache(codeBlocks.size(), false);
     2069    CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
    20602070    // subroutToCache - true if given block begin subroutine to cache
    20612071    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
    2062     std::vector<bool> visited(codeBlocks.size(), false);
     2072    CBlockBitPool visited(codeBlocks.size(), false);
    20632073    flowStack.push_back({ 0, 0 });
    20642074    flowStackBlocks[0] = true;
     
    20752085        {
    20762086            // process current block
    2077             if (!visited[entry.blockIndex.index])
     2087            if (!visited[entry.blockIndex])
    20782088            {
    20792089                std::cout << "proc: " << entry.blockIndex << std::endl;
    2080                 visited[entry.blockIndex.index] = true;
     2090                visited[entry.blockIndex] = true;
    20812091               
    20822092                for (auto& ssaEntry: cblock.ssaInfoMap)
     
    21232133            {
    21242134                // handle caching for res second point
    2125                 cblocksToCache.increase(entry.blockIndex.index);
     2135                cblocksToCache.increase(entry.blockIndex);
    21262136                std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
    2127                             cblocksToCache.count(entry.blockIndex.index) << std::endl;
     2137                            cblocksToCache.count(entry.blockIndex) << std::endl;
    21282138                // back, already visited
    2129                 flowStackBlocks[entry.blockIndex.index] =
    2130                         !flowStackBlocks[entry.blockIndex.index];
     2139                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    21312140                flowStack.pop_back();
    21322141               
     
    21352144                {
    21362145                    // mark point of way to cache (res first point)
    2137                     waysToCache[lastCommonCacheWayPoint.first.index] = true;
     2146                    waysToCache[lastCommonCacheWayPoint.first] = true;
    21382147                    std::cout << "mark to pfcache " <<
    21392148                            lastCommonCacheWayPoint.first << ", " <<
     
    21542163            const BlockIndex routineBlock = callStack.back().routineBlock;
    21552164            RoutineData& prevRdata = routineMap.find(routineBlock)->second;
    2156             if (!isRoutineGen[routineBlock.index])
     2165            if (!isRoutineGen[routineBlock])
    21572166            {
    21582167                createRoutineData(codeBlocks, curSSAIdMap, loopBlocks,
     
    21602169                            routineBlock);
    21612170                //prevRdata.compare(myRoutineData);
    2162                 isRoutineGen[routineBlock.index] = true;
     2171                isRoutineGen[routineBlock] = true;
    21632172            }
    21642173           
     
    22182227            }
    22192228            flowStack.push_back({ entry.blockIndex+1, 0, false });
    2220             if (flowStackBlocks[(entry.blockIndex+1).index])
     2229            if (flowStackBlocks[entry.blockIndex+1])
    22212230            {
    22222231                loopBlocks.insert(entry.blockIndex+1);
    22232232                 // keep to inserted in popping
    2224                 flowStackBlocks[(entry.blockIndex+1).index] = false;
     2233                flowStackBlocks[entry.blockIndex+1] = false;
    22252234            }
    22262235            else
    2227                 flowStackBlocks[(entry.blockIndex+1).index] = true;
     2236                flowStackBlocks[entry.blockIndex+1] = true;
    22282237            entry.nextIndex++;
    22292238        }
     
    22532262           
    22542263            std::cout << "pop: " << entry.blockIndex << std::endl;
    2255             flowStackBlocks[entry.blockIndex.index] = false;
     2264            flowStackBlocks[entry.blockIndex] = false;
    22562265            flowStack.pop_back();
    22572266            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
     
    22862295        {
    22872296            // process current block
    2288             if (!visited[entry.blockIndex.index])
    2289                 visited[entry.blockIndex.index] = true;
     2297            if (!visited[entry.blockIndex])
     2298                visited[entry.blockIndex] = true;
    22902299            else
    22912300            {
     
    23152324        else // back
    23162325        {
    2317             if (cblocksToCache.count(entry.blockIndex.index)==2 &&
     2326            if (cblocksToCache.count(entry.blockIndex)==2 &&
    23182327                !resSecondPointsCache.hasKey(entry.blockIndex))
    23192328                // add to cache
Note: See TracChangeset for help on using the changeset viewer.