Changeset 4151 in CLRX


Ignore:
Timestamp:
May 12, 2018, 1:26:10 PM (3 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Fixed fillUpInsideRoutine: always zeroing visited, check ssaId while filling blocks. check whether is path have return.
Some small fixes in testcases. Add next testcase for testing a end program paths in the routine.

Location:
CLRadeonExtender/trunk
Files:
3 edited

Legend:

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

    r4148 r4151  
    266266    size_t nextIndex;
    267267    bool isCall;
     268    bool havePath;
    268269};
    269270
  • CLRadeonExtender/trunk/amdasm/AsmRegAllocLive.cpp

    r4150 r4151  
    127127}
    128128
    129 static void fillUpInsideRoutine(std::unordered_set<size_t>& visited,
    130             const std::vector<CodeBlock>& codeBlocks,
     129static void fillUpInsideRoutine(const std::vector<CodeBlock>& codeBlocks,
    131130            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    132131            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    133             size_t startBlock, const AsmSingleVReg& svreg, Liveness& lv,
    134             cxuint lvRType /* lv register type */, size_t vidx,
    135             const std::unordered_set<size_t>& haveReturnBlocks)
     132            size_t startBlock, size_t routineBlock, const AsmSingleVReg& svreg,
     133            Liveness& lv, cxuint lvRType /* lv register type */, size_t vidx,
     134            size_t ssaId, const RoutineDataLv& rdata,
     135            std::unordered_set<size_t>& havePathBlocks)
    136136{
     137    const std::unordered_set<size_t>& haveReturnBlocks = rdata.haveReturnBlocks;
    137138    std::deque<FlowStackEntry3> flowStack;
     139    std::unordered_set<size_t> visited;
     140   
    138141    flowStack.push_back({ startBlock, 0 });
    139142   
     
    141144        // already filled, then do nothing
    142145        //return;
     146    size_t startSSAId = ssaId;
     147    bool fromStartPos = false;
     148    if (routineBlock == startBlock)
     149    {
     150        const CodeBlock& cblock = codeBlocks[startBlock];
     151        auto sinfoIt = cblock.ssaInfoMap.find(svreg);
     152        auto rbwIt = rdata.rbwSSAIdMap.find(svreg);
     153        if (sinfoIt != cblock.ssaInfoMap.end())
     154        {
     155            const SSAInfo& sinfo = sinfoIt->second;
     156            if (sinfo.readBeforeWrite && sinfo.ssaIdBefore==ssaId)
     157                fromStartPos = true;
     158            else if (sinfo.ssaIdChange == 0 || sinfo.ssaIdLast != ssaId)
     159                // do nothing (last SSAId doesnt match or no change
     160                return;
     161        }
     162        else if (rbwIt != rdata.rbwSSAIdMap.end())
     163        {
     164            fromStartPos = true;
     165            startSSAId = rbwIt->second;
     166        }
     167        else
     168            return; // do nothing
     169    }
     170    if (startSSAId != ssaId)
     171        return; // also, do nothing
    143172   
    144173    while (!flowStack.empty())
     
    147176        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    148177       
     178        bool endOfPath = false;
    149179        if (entry.nextIndex == 0)
    150180        {
     
    152182                haveReturnBlocks.find(entry.blockIndex) != haveReturnBlocks.end())
    153183            {
    154                 size_t cbStart = cblock.start;
     184                auto sinfoIt = cblock.ssaInfoMap.find(svreg);
     185                if (flowStack.size() > 1 && sinfoIt != cblock.ssaInfoMap.end())
     186                {
     187                    if (!sinfoIt->second.readBeforeWrite)
     188                    {
     189                        // no read before write skip this path
     190                        flowStack.pop_back();
     191                        continue;
     192                    }
     193                    else
     194                        // we end path at first read
     195                        endOfPath = true;
     196                }
     197                /*size_t cbStart = cblock.start;
    155198                if (flowStack.size() == 1)
    156199                {
     
    165208                addVIdxToCallEntry(entry.blockIndex, lvRType, vidx,
    166209                        codeBlocks, vidxCallMap, vidxRoutineMap);
     210                */
    167211            }
    168212            else
    169213            {
     214                const bool prevPath = havePathBlocks.find(entry.blockIndex) !=
     215                        havePathBlocks.end();
    170216                flowStack.pop_back();
     217                // propagate haveReturn to previous block
     218                if (prevPath)
     219                {
     220                    flowStack.back().havePath = true;
     221                    havePathBlocks.insert(flowStack.back().blockIndex);
     222                }
    171223                continue;
    172224            }
     
    174226       
    175227        // skip calls
    176         for (; entry.nextIndex < cblock.nexts.size() &&
     228        if (!endOfPath)
     229            for (; entry.nextIndex < cblock.nexts.size() &&
    177230                    cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++);
    178231       
    179         if (entry.nextIndex < cblock.nexts.size())
     232        if (!endOfPath && entry.nextIndex < cblock.nexts.size())
    180233        {
    181234            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    182235            entry.nextIndex++;
    183236        }
    184         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
     237        else if (!endOfPath &&
     238            ((entry.nextIndex==0 && cblock.nexts.empty()) ||
    185239                // if have any call then go to next block
    186240                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
     
    190244            entry.nextIndex++;
    191245        }
    192         else // back
     246        else
     247        {
     248            if (endOfPath || cblock.haveReturn)
     249            {
     250                havePathBlocks.insert(entry.blockIndex);
     251                // we have path only if have return and if have path
     252                entry.havePath = true;
     253            }
     254           
     255            const bool curHavePath = entry.havePath;
     256            if (curHavePath)
     257            {
     258                auto sinfoIt = cblock.ssaInfoMap.find(svreg);
     259                size_t cbStart = cblock.start;
     260                size_t cbEnd = cblock.end;
     261                if (flowStack.size() == 1 && !fromStartPos)
     262                {
     263                    // if first block, then get last occurrence in this path
     264                    if (sinfoIt != cblock.ssaInfoMap.end())
     265                        cbStart = sinfoIt->second.lastPos+1;
     266                }
     267                if (endOfPath && sinfoIt != cblock.ssaInfoMap.end())
     268                    cbEnd = sinfoIt->second.firstPos;
     269                // fill up block
     270                lv.insert(cbStart, cbEnd);
     271                if (cblock.end == cbEnd)
     272                    addVIdxToCallEntry(entry.blockIndex, lvRType, vidx,
     273                            codeBlocks, vidxCallMap, vidxRoutineMap);
     274            }
     275           
     276            // back
    193277            flowStack.pop_back();
     278            // propagate have Path
     279            if (!flowStack.empty())
     280            {
     281                if (curHavePath)
     282                    havePathBlocks.insert(flowStack.back().blockIndex);
     283                flowStack.back().havePath |= curHavePath;
     284            }
     285        }
    194286    }
    195287}
     
    209301        size_t lastAccessIndex; // last access pos index
    210302        bool inSubroutines;
    211         const std::unordered_set<size_t>* haveReturnBlocks;
     303        size_t routineBlock;
     304        const RoutineDataLv* rdata;
    212305    };
     306   
     307    std::unordered_set<size_t> havePathBlocks;
    213308   
    214309    FlowStackCIter flitEnd = flowStack.end();
     
    220315    Liveness& lv = livenesses[lvRegType][vidx];
    221316   
    222     std::unordered_set<size_t> visited;
    223    
    224317    std::stack<JoinEntry> rjStack; // routine join stack
    225318    if (flowStkStart.inSubroutines)
    226319        rjStack.push({ flowStack[flowStkStart.stackPos].blockIndex,
    227                             0, 0, true, nullptr });
     320                            0, 0, true, SIZE_MAX, nullptr });
    228321   
    229322    while (!rjStack.empty())
     
    237330            if (cblock.nexts[entry.nextIndex].isCall)
    238331            {
     332                const size_t routineBlock = cblock.nexts[entry.nextIndex].block;
    239333                const RoutineDataLv& rdata =
    240                         routineMap.find(cblock.nexts[entry.nextIndex].block)->second;
     334                        routineMap.find(routineBlock)->second;
    241335                auto lastAccessIt = rdata.lastAccessMap.find(svreg);
    242336                if (lastAccessIt != rdata.lastAccessMap.end())
     
    247341                                lastAccessIt->second[entry.lastAccessIndex];
    248342                        rjStack.push({ lastAccess.blockIndex, 0, 0,
    249                                 lastAccess.inSubroutines, &rdata.haveReturnBlocks });
     343                                lastAccess.inSubroutines, routineBlock, &rdata });
    250344                        entry.lastAccessIndex++;
    251345                        if (entry.lastAccessIndex == lastAccessIt->second.size())
     
    274368             * (that with subroutines calls) will be skipped */
    275369            if (rjStack.size() > 1)
    276                 fillUpInsideRoutine(visited, codeBlocks, vidxCallMap, vidxRoutineMap,
    277                         entry.blockIndex + (entry.inSubroutines), svreg,
    278                         lv, lvRegType, vidx, *entry.haveReturnBlocks);
     370                fillUpInsideRoutine(codeBlocks, vidxCallMap, vidxRoutineMap,
     371                        entry.blockIndex + (entry.inSubroutines),
     372                        entry.routineBlock, svreg, lv, lvRegType, vidx, ssaId,
     373                        *entry.rdata, havePathBlocks);
    279374            rjStack.pop();
    280375        }
     
    10241119            VectorSet<LastAccessBlockPos>& sset = res.first->second;
    10251120            // filter before inserting (remove everything that do not point to calls)
    1026             sset.resize(std::remove_if(sset.begin(), sset.end(),
     1121            /*sset.resize(std::remove_if(sset.begin(), sset.end(),
    10271122                [](const LastAccessBlockPos& b)
    1028                 { return !b.inSubroutines; }) - sset.begin());
     1123                { return !b.inSubroutines; }) - sset.begin());*/
    10291124            sset.insertValue({ routineBlock, false });
    10301125        }
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc3.cpp

    r4150 r4151  
    12991299                    { 104, 105 }, { 112, 121 }, { 128, 129 } }, // 4: sa[0]'0
    13001300                { { 0, 5 } }, // 5: sa[1]'0
    1301                 { { 0, 9 }, { 48, 88 }, { 89, 112 } }, // 6: sa[2]'0
     1301                { { 0, 9 }, { 48, 57 }, { 64, 88 }, { 89, 112 } }, // 6: sa[2]'0
    13021302                { { 57, 64 }, { 88, 89 } }, // 7: sa[2]'1
    13031303                { { 0, 13 }, { 48, 112 } }, // 8: sa[3]'0
     
    17001700                { { 0, 8 }, { 16, 28 }, { 32, 40 } }, // 6: sa[1]'0
    17011701                { { 1, 8 }, { 16, 17 } }, // 7: sa[2]'0
    1702                 { { 8, 9 }, { 17, 48 } }, // 8: sa[2]'1
     1702                { { 8, 9 }, { 17, 32 }, { 33, 48 } }, // 8: sa[2]'1
    17031703                { { 9, 10 } }  // 9: sa[2]'2
    17041704            },
     
    17461746                { { 0, 5 } }, // 3: S3
    17471747                { { 0, 1 } }, // 4: S4
    1748                 { { 1, 10 }, { 16, 48 } }, // 5: s6
     1748                { { 1, 10 }, { 16, 32 }, { 33, 48 } }, // 5: s6
    17491749                { { 0, 9 }, { 16, 48 } }, // 6: sa[0]'0
    17501750                { { 0, 8 }, { 16, 28 }, { 32, 40 } } // 7: sa[1]'0
     
    18431843        true, ""
    18441844    },
    1845         {   // 29 - two routines with var sharing (output-input) 2
     1845    {   // 29 - two routines with var sharing (output-input) 2
    18461846        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
    18471847        s_mov_b32 sa[2], s4             # 0
     
    20972097                { { 41, 42 } }, // 13: sa[3]'2
    20982098                { { 0, 36 }, { 48, 61 }, { 68, 69 } }, // 14: sa[4]'0
     2099                { { 9, 41 } }  // 15: sa[5]'0
     2100            },
     2101            { },
     2102            { },
     2103            { }
     2104        },
     2105        { }, // linearDepMaps
     2106        {   // vidxRoutineMap
     2107            { 2, { { { 0, 1, 6, 7, 8, 9, 11, 12, 14 }, { }, { }, { } } } }
     2108        },
     2109        {   // vidxCallMap
     2110            { 0, { { { 15 }, { }, { }, { } } } }
     2111        },
     2112        true, ""
     2113    },
     2114    {   // 33 - routine with ends (s_endpgm, no return) 3
     2115        R"ffDXD(.regvar sa:s:8, va:v:8
     2116        s_mov_b32 sa[2], s4             # 0
     2117        s_mov_b32 sa[3], s5             # 4
     2118        s_mov_b32 sa[5], s5             # 8
     2119       
     2120        s_getpc_b64 s[2:3]              # 12
     2121        s_add_u32 s2, s2, routine-.     # 16
     2122        s_add_u32 s3, s3, routine-.+4   # 24
     2123        .cf_call routine
     2124        s_swappc_b64 s[0:1], s[2:3]     # 32
     2125       
     2126        s_lshl_b32 sa[2], sa[2], 3      # 36
     2127        s_lshl_b32 sa[3], sa[3], sa[5]  # 40
     2128        s_endpgm                        # 44
     2129       
     2130routine:
     2131        s_xor_b32 sa[2], sa[2], sa[4]   # 48
     2132        s_cbranch_scc1 bb1              # 52
     2133       
     2134        s_min_u32 sa[2], sa[2], sa[4]   # 56
     2135        s_endpgm                        # 60
     2136       
     2137bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 64
     2138        s_xor_b32 sa[3], sa[3], sa[4]   # 68
     2139        .cf_ret
     2140        s_setpc_b64 s[0:1]              # 72
     2141)ffDXD",
     2142        {   // livenesses
     2143            {   // for SGPRs
     2144                { { 33, 36 }, { 48, 56 }, { 64, 73 } }, // 0: S0
     2145                { { 33, 36 }, { 48, 56 }, { 64, 73 } }, // 1: S1
     2146                { { 13, 33 } }, // 2: S2
     2147                { { 13, 33 } }, // 3: S3
     2148                { { 0, 1 } }, // 4: S4
     2149                { { 0, 9 } }, // 5: S5
     2150                { { 1, 36 }, { 48, 49 } }, // 6: sa[2]'0
     2151                { { 49, 57 }, { 64, 65 } }, // 7: sa[2]'1
     2152                { { 57, 58 } }, // 8: sa[2]'2
     2153                { { 36, 37 }, { 65, 76 } }, // 9: sa[2]'3
     2154                { { 37, 38 } }, // 10: sa[2]'4
     2155                { { 5, 36 }, { 48, 56 }, { 64, 69 } }, // 11: sa[3]'0
     2156                { { 36, 41 }, { 69, 76 } }, // 12: sa[3]'1
     2157                { { 41, 42 } }, // 13: sa[3]'2
     2158                { { 0, 36 }, { 48, 57 }, { 64, 69 } }, // 14: sa[4]'0
    20992159                { { 9, 41 } }  // 15: sa[5]'0
    21002160            },
Note: See TracChangeset for help on using the changeset viewer.