Changeset 3985 in CLRX


Ignore:
Timestamp:
Apr 10, 2018, 6:01:51 PM (9 days ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Remove stuff to better joining regvar ssaIds between recursion calls.

File:
1 edited

Legend:

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

    r3984 r3985  
    696696    bool isCall;
    697697    bool haveReturn;
    698     std::vector<size_t> recurChangedVarBlocks;
    699698    RetSSAIdMap prevRetSSAIdSets;
    700699};
     
    712711    bool isCall;
    713712    RetSSAIdMap prevRetSSAIdSets;
    714 };
    715 
    716 // for recursion finding collecting regvars changed in recursions
    717 struct CLRX_INTERNAL FlowStackEntry4
    718 {
    719     size_t blockIndex;
    720     size_t nextIndex;
    721     bool isCall;
    722     bool haveReturn;
    723     std::unordered_set<AsmSingleVReg> changedVars;
    724713};
    725714
     
    21472136}
    21482137
    2149 typedef std::unordered_map<size_t, std::unordered_set<AsmSingleVReg> >
    2150                 RecurChangedVarMap;
    2151 
    2152 
    21532138void AsmRegAllocator::createSSAData(ISAUsageHandler& usageHandler)
    21542139{
     
    22482233    std::unordered_set<size_t> recurseBlocks;
    22492234   
    2250     RecurChangedVarMap recurChangedVarMap;
    2251    
    2252     {
    2253     CBlockBitPool haveReturnBlocks(codeBlocks.size(), false);
    2254     std::deque<FlowStackEntry4> flowStack;
    2255     flowStack.push_back({ 0, 0 });
    2256     /*
    2257      * find recursions
    2258      */
    2259     while (!flowStack.empty())
    2260     {
    2261         FlowStackEntry4& entry = flowStack.back();
    2262         CodeBlock& cblock = codeBlocks[entry.blockIndex];
    2263        
    2264         if (entry.nextIndex == 0)
    2265         {
    2266             // process current block
    2267             if (!visited[entry.blockIndex])
    2268                 visited[entry.blockIndex] = true;
    2269             else
    2270             {
    2271                 flowStack.pop_back();
    2272                 continue;
    2273             }
    2274         }
    2275        
    2276         if (!callStack.empty() &&
    2277             entry.blockIndex == callStack.back().callBlock.index &&
    2278             entry.nextIndex-1 == callStack.back().callNextIndex)
    2279         {
    2280             const BlockIndex routineBlock = callStack.back().routineBlock;
    2281             callStack.pop_back(); // just return from call
    2282             callBlocks.erase(routineBlock);
    2283             std::cout << "finding recur: ret: " << routineBlock << std::endl;
    2284         }
    2285        
    2286         if (entry.nextIndex < cblock.nexts.size())
    2287         {
    2288             bool isCall = false;
    2289             size_t nextBlock = cblock.nexts[entry.nextIndex].block;
    2290            
    2291             if (cblock.nexts[entry.nextIndex].isCall)
    2292             {
    2293                 if (!callBlocks.insert(nextBlock).second)
    2294                 {
    2295                     // if already called (then it is recursion)
    2296                     std::cout << "finding recursions: " << nextBlock << std::endl;
    2297                     // uncomment after tests
    2298                     recurChangedVarMap.insert({ nextBlock, { } });
    2299                     entry.nextIndex++;
    2300                     continue;
    2301                 }
    2302                 // comment after tests
    2303                 //recurChangedVarMap.insert({ nextBlock, { } });
    2304                 callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
    2305                 std::cout << "finding recur: call: " << nextBlock << std::endl;
    2306                 isCall = true;
    2307             }
    2308            
    2309             flowStack.push_back({ nextBlock, 0, isCall });
    2310             entry.nextIndex++;
    2311         }
    2312         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2313                 // if have any call then go to next block
    2314                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2315                  !cblock.haveReturn && !cblock.haveEnd)
    2316         {
    2317             flowStack.push_back({ entry.blockIndex+1, 0, false });
    2318             entry.nextIndex++;
    2319         }
    2320         else // back
    2321             flowStack.pop_back();
    2322     }
    2323    
    2324     // collecting changed regvars
    2325     for (auto& changedRegVars: recurChangedVarMap)
    2326     {
    2327         std::cout << " -- ChangedVars for " << changedRegVars.first << std::endl;
    2328         std::fill(visited.begin(), visited.end(), false);
    2329         std::fill(flowStackBlocks.begin(), flowStackBlocks.end(), false);
    2330         flowStack.clear();
    2331         flowStack.push_back({ changedRegVars.first, 0 });
    2332         flowStackBlocks[changedRegVars.first] = true;
    2333         loopBlocks.clear();
    2334        
    2335         std::unordered_map<size_t, std::unordered_set<AsmSingleVReg> > chLoopEnds;
    2336        
    2337         while (!flowStack.empty())
    2338         {
    2339             FlowStackEntry4& entry = flowStack.back();
    2340             CodeBlock& cblock = codeBlocks[entry.blockIndex];
    2341            
    2342             if (entry.nextIndex == 0)
    2343             {
    2344                 // process current block
    2345                 if (!visited[entry.blockIndex])
    2346                 {
    2347                     visited[entry.blockIndex] = true;
    2348                     for (auto& ssaEntry: cblock.ssaInfoMap)
    2349                         if (ssaEntry.second.ssaIdChange!=0)
    2350                             entry.changedVars.insert(ssaEntry.first);
    2351                 }
    2352                 else if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
    2353                 {
    2354                     std::cout << "   collect regvars: add loop end: " <<
    2355                             entry.blockIndex << std::endl;
    2356                     // add loop end
    2357                     std::unordered_set<AsmSingleVReg>& chloopEnd =
    2358                             chLoopEnds[entry.blockIndex];
    2359                     size_t i;
    2360                     for (i = flowStack.size()-1; i > 0 && !flowStack[i-1].haveReturn; ++i)
    2361                     {
    2362                         const FlowStackEntry4& entryx = flowStack[i-1];
    2363                         chloopEnd.insert(entryx.changedVars.begin(),
    2364                                 entryx.changedVars.end());
    2365                         if (entryx.blockIndex == entry.blockIndex)
    2366                             // if loop block
    2367                             break;
    2368                     }
    2369                    
    2370                     flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    2371                     flowStack.pop_back();
    2372                     continue;
    2373                 }
    2374                 else
    2375                 {
    2376                     const bool prevHaveReturn = haveReturnBlocks[entry.blockIndex];
    2377                     const bool isCall = entry.isCall;
    2378                     flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    2379                     flowStack.pop_back();
    2380                     // set up haveReturn
    2381                     FlowStackEntry4& prevEntry = flowStack.back();
    2382                     if (!isCall)
    2383                         // propagate haveReturn only for jumps (no for calls)
    2384                         prevEntry.haveReturn |= prevHaveReturn;
    2385                     haveReturnBlocks[prevEntry.blockIndex] = prevEntry.haveReturn;
    2386                     continue;
    2387                 }
    2388             }
    2389            
    2390             if (entry.nextIndex < cblock.nexts.size())
    2391             {
    2392                 bool isCall = false;
    2393                 size_t nextBlock = cblock.nexts[entry.nextIndex].block;
    2394                 flowStack.push_back({ nextBlock, 0, isCall });
    2395                 if (flowStackBlocks[nextBlock])
    2396                 {
    2397                     if (!cblock.nexts[entry.nextIndex].isCall)
    2398                     {
    2399                         std::cout << "   collect regvars: " << entry.blockIndex <<
    2400                             ": loop detected 2" << std::endl;
    2401                         loopBlocks.insert(nextBlock);
    2402                     }
    2403                     flowStackBlocks[nextBlock] = false; // keep to inserted in popping
    2404                 }
    2405                 else
    2406                     flowStackBlocks[nextBlock] = true;
    2407                 entry.nextIndex++;
    2408             }
    2409             else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2410                     // if have any call then go to next block
    2411                     (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2412                     !cblock.haveReturn && !cblock.haveEnd)
    2413             {
    2414                 flowStack.push_back({ entry.blockIndex+1, 0, false });
    2415                 if (flowStackBlocks[entry.blockIndex+1])
    2416                 {
    2417                     std::cout << "   collect regvars: " << entry.blockIndex <<
    2418                             ": loop detected" << std::endl;
    2419                     loopBlocks.insert(entry.blockIndex+1);
    2420                     // keep to inserted in popping
    2421                     flowStackBlocks[entry.blockIndex+1] = false;
    2422                 }
    2423                 else
    2424                     flowStackBlocks[entry.blockIndex+1] = true;
    2425                 entry.nextIndex++;
    2426             }
    2427             else // back
    2428             {
    2429                 std::unordered_set<AsmSingleVReg> prevChangedVars;
    2430                 const bool isCall = entry.isCall;
    2431                 if (cblock.haveReturn)
    2432                 {
    2433                     entry.haveReturn = true;
    2434                     haveReturnBlocks[entry.blockIndex] = true;
    2435                 }
    2436                 prevChangedVars = entry.changedVars;
    2437                 const bool curHaveReturn = entry.haveReturn;
    2438                 std::cout << "   collect regvars: " << entry.blockIndex << ": " <<
    2439                         int(curHaveReturn) << std::endl;
    2440                
    2441                 if (loopBlocks.find(entry.blockIndex) != loopBlocks.end() &&
    2442                     curHaveReturn)
    2443                 {
    2444                     auto it = chLoopEnds.find(entry.blockIndex);
    2445                     if (it != chLoopEnds.end())
    2446                     {
    2447                         std::cout << "   collect regvars: add loop ends: " <<
    2448                                 entry.blockIndex << std::endl;
    2449                         // add loop ends returns
    2450                         prevChangedVars.insert(it->second.begin(), it->second.end());
    2451                         chLoopEnds.erase(it); // delete it
    2452                     }
    2453                     loopBlocks.erase(entry.blockIndex);
    2454                 }
    2455                
    2456                 flowStack.pop_back();
    2457                 flowStackBlocks[entry.blockIndex] = false;
    2458                
    2459                 // set up haveReturn
    2460                 if (!flowStack.empty())
    2461                 {
    2462                     FlowStackEntry4& prevEntry = flowStack.back();
    2463                     if (!isCall)
    2464                         // propagate haveReturn only for jumps (no for calls)
    2465                         // because, call do not add returns
    2466                         prevEntry.haveReturn |= curHaveReturn;
    2467                     haveReturnBlocks[prevEntry.blockIndex] = prevEntry.haveReturn;
    2468                     if (curHaveReturn)
    2469                         prevEntry.changedVars.insert(prevChangedVars.begin(),
    2470                                     prevChangedVars.end());
    2471                 }
    2472                 else if (curHaveReturn)
    2473                     // put to changed reg vars
    2474                     changedRegVars.second.insert(
    2475                             prevChangedVars.begin(), prevChangedVars.end());
    2476             }
    2477         }
    2478         std::cout << " -- ChangedVars end for " << changedRegVars.first << std::endl;
    2479     }
    2480     }
    2481    
    2482     loopBlocks.clear();
    2483     std::fill(flowStackBlocks.begin(), flowStackBlocks.end(), false);
    2484     callStack.clear();
    2485     callBlocks.clear();
    2486     flowStack.clear();
    2487     flowStack.push_back({ 0, 0 });
    2488     flowStackBlocks[0] = true;
    2489     std::fill(visited.begin(), visited.end(), false);
     2235    /** INFO if you want to get code changedRegVars between recursions you get 3984
     2236     * this stuff has been deleted */
    24902237   
    24912238    std::unordered_map<size_t, std::unordered_map<AsmSingleVReg, size_t> >
     
    26242371            if (cblock.nexts[entry.nextIndex].isCall)
    26252372            {
    2626                 bool nextRecursion = true;
    26272373                if (!callBlocks.insert(nextBlock).second)
    26282374                {
     
    26372383                    else if (entry.blockIndex.pass==1)
    26382384                    {
    2639                         nextRecursion = false;
    26402385                        entry.nextIndex++;
    26412386                        std::cout << " NO call (rec): " << entry.blockIndex << std::endl;
    2642                         //continue;
     2387                        continue;
    26432388                    }
    26442389                }
     
    26462391                    recurseBlocks.find(nextBlock.index) != recurseBlocks.end())
    26472392                {
    2648                     nextRecursion = false;
    26492393                    entry.nextIndex++;
    26502394                    std::cout << " NO call (rec)2: " << entry.blockIndex << std::endl;
    2651                     //continue;
    2652                 }
    2653                
    2654                 if (!nextRecursion)
    2655                 {
    2656                     entry.recurChangedVarBlocks.push_back(nextBlock.index);
    26572395                    continue;
    26582396                }
     
    27102448            }
    27112449           
    2712             if (!entry.recurChangedVarBlocks.empty())
    2713             {
    2714                 // apply to all changed regvars in curSSAIdMap
    2715                 std::cout << "apply recurChangedVarBlocks in " <<
    2716                             entry.blockIndex << std::endl;
    2717                 std::unordered_set<AsmSingleVReg> changedRegVars;
    2718                 for (size_t chrblk: entry.recurChangedVarBlocks)
    2719                 {
    2720                     auto chrbit = recurChangedVarMap.find(chrblk);
    2721                     if (chrbit != recurChangedVarMap.end())
    2722                         changedRegVars.insert(chrbit->second.begin(),
    2723                                     chrbit->second.end());
    2724                 }
    2725                
    2726                 for (const AsmSingleVReg& chvreg: changedRegVars)
    2727                 {
    2728                     curSSAIdMap[chvreg] += 1;
    2729                     totalSSACountMap[chvreg] += 1;
    2730                 }
    2731             }
    2732            
    27332450            flowStack.push_back({ entry.blockIndex+1, 0, false });
    27342451            if (flowStackBlocks[entry.blockIndex+1])
     
    27442461        else // back
    27452462        {
    2746             if (!entry.recurChangedVarBlocks.empty())
    2747             {
    2748                 // apply to all changed regvars in curSSAIdMap
    2749                 std::cout << "revert recurChangedVarBlocks in " <<
    2750                             entry.blockIndex << std::endl;
    2751                 std::unordered_set<AsmSingleVReg> changedRegVars;
    2752                 for (size_t chrblk: entry.recurChangedVarBlocks)
    2753                 {
    2754                     auto chrbit = recurChangedVarMap.find(chrblk);
    2755                     if (chrbit != recurChangedVarMap.end())
    2756                         changedRegVars.insert(chrbit->second.begin(),
    2757                                     chrbit->second.end());
    2758                 }
    2759                
    2760                 for (const AsmSingleVReg& chvreg: changedRegVars)
    2761                     curSSAIdMap[chvreg] -= 1;
    2762             }
    2763            
    27642463            // revert retSSAIdMap
    27652464            revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, nullptr);
Note: See TracChangeset for help on using the changeset viewer.