Changeset 3999 in CLRX


Ignore:
Timestamp:
Apr 14, 2018, 9:18:57 PM (3 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Fixed applySSAReplaces (propagation and minSSAId fill up). Working next more complex testcase.

Location:
CLRadeonExtender/trunk
Files:
2 edited

Legend:

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

    r3997 r3999  
    462462        size_t minSSAId;
    463463        bool visited;
     464        bool visited2;
    464465        std::unordered_set<size_t> nexts;
    465         MinSSAGraphNode() : minSSAId(SIZE_MAX), visited(false) { }
     466        MinSSAGraphNode() : minSSAId(SIZE_MAX), visited(false), visited2(false) { }
    466467    };
     468   
     469    typedef std::map<size_t, MinSSAGraphNode, std::greater<size_t> > SSAGraphNodesMap;
     470   
    467471    struct MinSSAGraphStackEntry
    468472    {
    469         std::unordered_map<size_t, MinSSAGraphNode>::iterator nodeIt;
     473        SSAGraphNodesMap::iterator nodeIt;
    470474        std::unordered_set<size_t>::const_iterator nextIt;
    471475        size_t minSSAId;
    472476       
    473477        MinSSAGraphStackEntry(
    474                 std::unordered_map<size_t, MinSSAGraphNode>::iterator _nodeIt,
     478                SSAGraphNodesMap::iterator _nodeIt,
    475479                std::unordered_set<size_t>::const_iterator _nextIt,
    476480                size_t _minSSAId = SIZE_MAX)
     
    481485    for (auto& entry: ssaReplacesMap)
    482486    {
     487        ARDOut << "SSAReplace: " << entry.first.regVar << "." << entry.first.index << "\n";
    483488        VectorSet<SSAReplace>& replaces = entry.second;
    484         std::sort(replaces.begin(), replaces.end());
     489        std::sort(replaces.begin(), replaces.end(), std::greater<SSAReplace>());
    485490        replaces.resize(std::unique(replaces.begin(), replaces.end()) - replaces.begin());
    486491        VectorSet<SSAReplace> newReplaces;
    487492       
    488         std::unordered_map<size_t, MinSSAGraphNode> ssaGraphNodes;
     493        SSAGraphNodesMap ssaGraphNodes;
    489494       
    490495        auto it = replaces.begin();
     
    492497        {
    493498            auto itEnd = std::upper_bound(it, replaces.end(),
    494                             std::make_pair(it->first, size_t(SIZE_MAX)));
    495             {
     499                    std::make_pair(it->first, size_t(0)), std::greater<SSAReplace>());
     500            {
     501                auto itLast = itEnd;
     502                --itLast;
    496503                MinSSAGraphNode& node = ssaGraphNodes[it->first];
    497                 node.minSSAId = std::min(node.minSSAId, it->second);
     504                node.minSSAId = std::min(node.minSSAId, itLast->second);
    498505                for (auto it2 = it; it2 != itEnd; ++it2)
    499                     node.nexts.insert(it->second);
     506                {
     507                    node.nexts.insert(it2->second);
     508                    ssaGraphNodes.insert({ it2->second, MinSSAGraphNode() });
     509                }
    500510            }
    501511            it = itEnd;
    502512        }
     513        /*for (const auto& v: ssaGraphNodes)
     514            ARDOut << "  SSANode: " << v.first << ":" << &v.second << " minSSAID: " <<
     515                            v.second.minSSAId << std::endl;*/
    503516        // propagate min value
    504517        std::stack<MinSSAGraphStackEntry> minSSAStack;
     
    506519                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
    507520        {
     521            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
    508522            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
    509523            // traverse with minimalize SSA id
     
    525539                    if (nodeIt != ssaGraphNodes.end())
    526540                    {
     541                        ARDOut << "  Node: " << &node << " minSSAId: " <<
     542                                node.minSSAId << " to " <<
     543                                nodeIt->first << ": " << &(nodeIt->second) <<
     544                                " minSSAId: " << nodeIt->second.minSSAId << "\n";
    527545                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
    528                                 nodeIt->second.minSSAId });
     546                                std::min(nodeIt->second.minSSAId, node.minSSAId) });
    529547                    }
    530548                    ++entry.nextIt;
     
    533551                {
    534552                    node.minSSAId = std::min(node.minSSAId, entry.minSSAId);
     553                    ARDOut << "    Node: " << &node << " minSSAId: " <<
     554                                node.minSSAId << "\n";
    535555                    minSSAStack.pop();
    536556                    if (!minSSAStack.empty())
     
    541561                }
    542562            }
     563           
    543564            // skip visited nodes
    544565            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
    545566                if (!ssaGraphNodeIt->second.visited)
     567                    break;
     568        }
     569       
     570        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
     571                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
     572        {
     573            // fill up rest of tree
     574            ARDOut << "  Start2 in " << ssaGraphNodeIt->first << "." << "\n";
     575            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
     576            while (!minSSAStack.empty())
     577            {
     578                MinSSAGraphStackEntry& entry = minSSAStack.top();
     579                MinSSAGraphNode& node = entry.nodeIt->second;
     580                bool toPop = false;
     581                if (entry.nextIt == node.nexts.begin())
     582                {
     583                    if (!node.visited2)
     584                        node.visited2 = true;
     585                    else
     586                        toPop = true;
     587                }
     588                if (!toPop && entry.nextIt != node.nexts.end())
     589                {
     590                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
     591                    if (nodeIt != ssaGraphNodes.end())
     592                    {
     593                        ARDOut << "  Node2: " << &node << " minSSAId: " <<
     594                                node.minSSAId << " to " <<
     595                                nodeIt->first << ": " << &(nodeIt->second) <<
     596                                " minSSAId: " << nodeIt->second.minSSAId << "\n";
     597                        node.minSSAId = nodeIt->second.minSSAId =
     598                                std::min(nodeIt->second.minSSAId, node.minSSAId);
     599                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
     600                                 nodeIt->second.minSSAId });
     601                    }
     602                    ++entry.nextIt;
     603                }
     604                else
     605                    minSSAStack.pop();
     606            }
     607           
     608            // skip visited nodes
     609            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
     610                if (!ssaGraphNodeIt->second.visited2)
    546611                    break;
    547612        }
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc2.cpp

    r3998 r3999  
    249249                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
    250250                }, false, false, true }
     251        }
     252    },
     253    {   // 2 - more complex dependencies
     254        {
     255            { 0, 4,
     256                { },
     257                {
     258                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, true) },
     259                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, true) }
     260                }, false, false, false },
     261            { 4, 8,
     262                { },
     263                {
     264                    { { "sa", 2 }, SSAInfo(1, 2, 2, 2, 1, true) },
     265                    { { "sa", 3 }, SSAInfo(1, 2, 2, 2, 1, true) }
     266                }, false, false, false },
     267            { 8, 12,
     268                { },
     269                {
     270                    { { "sa", 2 }, SSAInfo(2, 3, 3, 3, 1, true) },
     271                    { { "sa", 3 }, SSAInfo(2, 3, 3, 3, 1, true) }
     272                }, false, false, false },
     273            { 12, 16,
     274                { },
     275                {
     276                    { { "sa", 2 }, SSAInfo(3, 4, 4, 4, 1, true) },
     277                    { { "sa", 3 }, SSAInfo(3, 4, 4, 4, 1, true) }
     278                }, false, false, false },
     279            { 16, 20,
     280                { },
     281                {
     282                    { { "sa", 2 }, SSAInfo(4, 5, 5, 5, 1, true) },
     283                    { { "sa", 3 }, SSAInfo(4, 5, 5, 5, 1, true) }
     284                }, false, false, false },
     285            { 20, 24,
     286                { },
     287                {
     288                    { { "sa", 2 }, SSAInfo(5, 6, 6, 6, 1, true) },
     289                    { { "sa", 3 }, SSAInfo(5, 6, 6, 6, 1, true) }
     290                }, false, false, false },
     291            { 24, 28,
     292                { },
     293                {
     294                    { { "sa", 2 }, SSAInfo(6, 7, 7, 7, 1, true) },
     295                    { { "sa", 3 }, SSAInfo(6, 7, 7, 7, 1, true) }
     296                }, false, false, false },
     297            { 28, 32,
     298                { },
     299                {
     300                    { { "sa", 2 }, SSAInfo(7, 8, 8, 8, 1, true) },
     301                    { { "sa", 3 }, SSAInfo(7, 8, 8, 8, 1, true) }
     302                }, false, false, false },
     303            { 32, 36,
     304                { },
     305                {
     306                    { { "sa", 2 }, SSAInfo(8, 9, 9, 9, 1, true) },
     307                    { { "sa", 3 }, SSAInfo(8, 9, 9, 9, 1, true) }
     308                }, false, false, false },
     309            { 36, 40,
     310                { },
     311                {
     312                    { { "sa", 2 }, SSAInfo(9, 10, 10, 10, 1, true) },
     313                    { { "sa", 3 }, SSAInfo(9, 10, 10, 10, 1, true) }
     314                }, false, false, false },
     315            { 40, 44,
     316                { },
     317                {
     318                    { { "sa", 2 }, SSAInfo(10, 11, 11, 11, 1, true) },
     319                    { { "sa", 3 }, SSAInfo(10, 11, 11, 11, 1, true) }
     320                }, false, false, false },
     321            { 44, 48,
     322                { },
     323                {
     324                    { { "sa", 2 }, SSAInfo(11, 12, 12, 12, 1, true) },
     325                    { { "sa", 3 }, SSAInfo(11, 12, 12, 12, 1, true) }
     326                }, false, false, false },
     327            { 48, 52,
     328                { },
     329                {
     330                    { { "sa", 2 }, SSAInfo(12, 13, 13, 13, 1, true) },
     331                    { { "sa", 3 }, SSAInfo(12, 13, 13, 13, 1, true) }
     332                }, false, false, false }
     333        },
     334        {   // SSA replaces
     335            { { "sa", 2 }, { { 4, 1 }, { 4, 3 }, { 3, 2 }, { 7, 5 }, { 7, 6 },
     336                        { 11, 7 }, { 12, 7 } } },
     337            { { "sa", 3 }, { { 3, 2 }, { 5, 3 }, { 5, 4 }, { 4, 1 },
     338                        { 13, 4 }, { 12, 5 }, { 10, 2 } } }
     339        },
     340        // expected blocks
     341        {
     342            { 0, 4,
     343                { },
     344                {
     345                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, true) },
     346                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, true) }
     347                }, false, false, false },
     348            { 4, 8,
     349                { },
     350                {
     351                    { { "sa", 2 }, SSAInfo(1, 1, 2, 1, 1, true) },
     352                    { { "sa", 3 }, SSAInfo(1, 1, 2, 1, 1, true) }
     353                }, false, false, false },
     354            { 8, 12,
     355                { },
     356                {
     357                    { { "sa", 2 }, SSAInfo(1, 1, 3, 1, 1, true) },
     358                    { { "sa", 3 }, SSAInfo(1, 1, 3, 1, 1, true) }
     359                }, false, false, false },
     360            { 12, 16,
     361                { },
     362                {
     363                    { { "sa", 2 }, SSAInfo(1, 1, 4, 1, 1, true) },
     364                    { { "sa", 3 }, SSAInfo(1, 1, 4, 1, 1, true) }
     365                }, false, false, false },
     366            { 16, 20,
     367                { },
     368                {
     369                    { { "sa", 2 }, SSAInfo(1, 5, 5, 5, 1, true) },
     370                    { { "sa", 3 }, SSAInfo(1, 1, 5, 1, 1, true) }
     371                }, false, false, false },
     372            { 20, 24,
     373                { },
     374                {
     375                    { { "sa", 2 }, SSAInfo(5, 5, 6, 5, 1, true) },
     376                    { { "sa", 3 }, SSAInfo(1, 6, 6, 6, 1, true) }
     377                }, false, false, false },
     378            { 24, 28,
     379                { },
     380                {
     381                    { { "sa", 2 }, SSAInfo(5, 5, 7, 5, 1, true) },
     382                    { { "sa", 3 }, SSAInfo(6, 7, 7, 7, 1, true) }
     383                }, false, false, false },
     384            { 28, 32,
     385                { },
     386                {
     387                    { { "sa", 2 }, SSAInfo(5, 8, 8, 8, 1, true) },
     388                    { { "sa", 3 }, SSAInfo(7, 8, 8, 8, 1, true) }
     389                }, false, false, false },
     390            { 32, 36,
     391                { },
     392                {
     393                    { { "sa", 2 }, SSAInfo(8, 9, 9, 9, 1, true) },
     394                    { { "sa", 3 }, SSAInfo(8, 9, 9, 9, 1, true) }
     395                }, false, false, false },
     396            { 36, 40,
     397                { },
     398                {
     399                    { { "sa", 2 }, SSAInfo(9, 10, 10, 10, 1, true) },
     400                    { { "sa", 3 }, SSAInfo(9, 1, 10, 1, 1, true) }
     401                }, false, false, false },
     402            { 40, 44,
     403                { },
     404                {
     405                    { { "sa", 2 }, SSAInfo(10, 5, 11, 5, 1, true) },
     406                    { { "sa", 3 }, SSAInfo(1, 11, 11, 11, 1, true) }
     407                }, false, false, false },
     408            { 44, 48,
     409                { },
     410                {
     411                    { { "sa", 2 }, SSAInfo(5, 5, 12, 5, 1, true) },
     412                    { { "sa", 3 }, SSAInfo(11, 1, 12, 1, 1, true) }
     413                }, false, false, false },
     414            { 48, 52,
     415                { },
     416                {
     417                    { { "sa", 2 }, SSAInfo(5, 13, 13, 13, 1, true) },
     418                    { { "sa", 3 }, SSAInfo(1, 1, 13, 1, 1, true) }
     419                }, false, false, false }
    251420        }
    252421    }
Note: See TracChangeset for help on using the changeset viewer.