-/// addUsesForMEMERegion - add uses of CSRs spilled or restored in
-/// multi-entry, multi-exit (MEME) regions so spill and restore
-/// placement will not break code that enters or leaves a
-/// shrink-wrapped region by inducing spills with no matching
-/// restores or restores with no matching spills. A MEME region
-/// is a subgraph of the MCFG with multiple entry edges, multiple
-/// exit edges, or both. This code propagates use information
-/// through the MCFG until all paths requiring spills and restores
-/// _outside_ the computed minimal placement regions have been covered.
-///
-bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
- SmallVector<MachineBasicBlock*, 4>& blks) {
- if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
- bool processThisBlock = false;
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI) {
- MachineBasicBlock* SUCC = *SI;
- if (SUCC->pred_size() > 1) {
- processThisBlock = true;
- break;
- }
- }
- if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- MachineBasicBlock* PRED = *PI;
- if (PRED->succ_size() > 1) {
- processThisBlock = true;
- break;
- }
- }
- }
- if (! processThisBlock)
- return false;
- }
-
- CSRegSet prop;
- if (!CSRSave[MBB].empty())
- prop = CSRSave[MBB];
- else if (!CSRRestore[MBB].empty())
- prop = CSRRestore[MBB];
- else
- prop = CSRUsed[MBB];
- if (prop.empty())
- return false;
-
- // Propagate selected bits to successors, predecessors of MBB.
- bool addedUses = false;
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI) {
- MachineBasicBlock* SUCC = *SI;
- // Self-loop
- if (SUCC == MBB)
- continue;
- if (! CSRUsed[SUCC].contains(prop)) {
- CSRUsed[SUCC] |= prop;
- addedUses = true;
- blks.push_back(SUCC);
- DEBUG(if (ShrinkWrapDebugging >= Iterations)
- DOUT << getBasicBlockName(MBB)
- << "(" << stringifyCSRegSet(prop) << ")->"
- << "successor " << getBasicBlockName(SUCC) << "\n");
- }
- }
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- MachineBasicBlock* PRED = *PI;
- // Self-loop
- if (PRED == MBB)
- continue;
- if (! CSRUsed[PRED].contains(prop)) {
- CSRUsed[PRED] |= prop;
- addedUses = true;
- blks.push_back(PRED);
- DEBUG(if (ShrinkWrapDebugging >= Iterations)
- DOUT << getBasicBlockName(MBB)
- << "(" << stringifyCSRegSet(prop) << ")->"
- << "predecessor " << getBasicBlockName(PRED) << "\n");
- }
- }
- return addedUses;
-}
-
-/// addUsesForTopLevelLoops - add uses for CSRs used inside top
-/// level loops to the exit blocks of those loops.
-///
-bool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) {
- bool addedUses = false;
-
- // Place restores for top level loops where needed.
- for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator
- I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) {
- MachineBasicBlock* MBB = I->first;
- MachineLoop* LP = I->second;
- MachineBasicBlock* HDR = LP->getHeader();
- SmallVector<MachineBasicBlock*, 4> exitBlocks;
- CSRegSet loopSpills;
-
- loopSpills = CSRSave[MBB];
- if (CSRSave[MBB].empty()) {
- loopSpills = CSRUsed[HDR];
- assert(!loopSpills.empty() && "No CSRs used in loop?");
- } else if (CSRRestore[MBB].contains(CSRSave[MBB]))
- continue;
-
- LP->getExitBlocks(exitBlocks);
- assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?");
- for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
- MachineBasicBlock* EXB = exitBlocks[i];
- if (! CSRUsed[EXB].contains(loopSpills)) {
- CSRUsed[EXB] |= loopSpills;
- addedUses = true;
- DEBUG(if (ShrinkWrapDebugging >= Iterations)
- DOUT << "LOOP " << getBasicBlockName(MBB)
- << "(" << stringifyCSRegSet(loopSpills) << ")->"
- << getBasicBlockName(EXB) << "\n");
- if (EXB->succ_size() > 1 || EXB->pred_size() > 1)
- blks.push_back(EXB);
- }
- }
- }
- return addedUses;
-}
-
-/// calcSpillPlacements - determine which CSRs should be spilled
-/// in MBB using AnticIn sets of MBB's predecessors, keeping track
-/// of changes to spilled reg sets. Add MBB to the set of blocks
-/// that need to be processed for propagating use info to cover
-/// multi-entry/exit regions.
-///
-bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
- SmallVector<MachineBasicBlock*, 4> &blks,
- CSRegBlockMap &prevSpills) {
- bool placedSpills = false;
- // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB)
- CSRegSet anticInPreds;
- SmallVector<MachineBasicBlock*, 4> predecessors;
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- MachineBasicBlock* PRED = *PI;
- if (PRED != MBB)
- predecessors.push_back(PRED);
- }
- unsigned i = 0, e = predecessors.size();
- if (i != e) {
- MachineBasicBlock* PRED = predecessors[i];
- anticInPreds = UsedCSRegs - AnticIn[PRED];
- for (++i; i != e; ++i) {
- PRED = predecessors[i];
- anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
- }
- } else {
- // Handle uses in entry blocks (which have no predecessors).
- // This is necessary because the DFA formulation assumes the
- // entry and (multiple) exit nodes cannot have CSR uses, which
- // is not the case in the real world.
- anticInPreds = UsedCSRegs;
- }
- // Compute spills required at MBB:
- CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
-
- if (! CSRSave[MBB].empty()) {
- if (MBB == EntryBlock) {
- for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
- CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
- } else {
- // Reset all regs spilled in MBB that are also spilled in EntryBlock.
- if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
- CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
- }
- }
- }
- placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
- prevSpills[MBB] = CSRSave[MBB];
- // Remember this block for adding restores to successor
- // blocks for multi-entry region.
- if (placedSpills)
- blks.push_back(MBB);
-
- DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
- DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
- << stringifyCSRegSet(CSRSave[MBB]) << "\n");
-
- return placedSpills;
-}
-
-/// calcRestorePlacements - determine which CSRs should be restored
-/// in MBB using AvailOut sets of MBB's succcessors, keeping track
-/// of changes to restored reg sets. Add MBB to the set of blocks
-/// that need to be processed for propagating use info to cover
-/// multi-entry/exit regions.
-///
-bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
- SmallVector<MachineBasicBlock*, 4> &blks,
- CSRegBlockMap &prevRestores) {
- bool placedRestores = false;
- // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB)
- CSRegSet availOutSucc;
- SmallVector<MachineBasicBlock*, 4> successors;
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI) {
- MachineBasicBlock* SUCC = *SI;
- if (SUCC != MBB)
- successors.push_back(SUCC);
- }
- unsigned i = 0, e = successors.size();
- if (i != e) {
- MachineBasicBlock* SUCC = successors[i];
- availOutSucc = UsedCSRegs - AvailOut[SUCC];
- for (++i; i != e; ++i) {
- SUCC = successors[i];
- availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
- }
- } else {
- if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
- // Handle uses in return blocks (which have no successors).
- // This is necessary because the DFA formulation assumes the
- // entry and (multiple) exit nodes cannot have CSR uses, which
- // is not the case in the real world.
- availOutSucc = UsedCSRegs;
- }
- }
- // Compute restores required at MBB:
- CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
-
- // Postprocess restore placements at MBB.
- // Remove the CSRs that are restored in the return blocks.
- // Lest this be confusing, note that:
- // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks.
- if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
- if (! CSRSave[EntryBlock].empty())
- CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
- }
- placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
- prevRestores[MBB] = CSRRestore[MBB];
- // Remember this block for adding saves to predecessor
- // blocks for multi-entry region.
- if (placedRestores)
- blks.push_back(MBB);
-
- DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
- DOUT << "RESTORE[" << getBasicBlockName(MBB) << "] = "
- << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
-
- return placedRestores;
-}
-
-/// placeSpillsAndRestores - place spills and restores of CSRs
-/// used in MBBs in minimal regions that contain the uses.
-///
-void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
- CSRegBlockMap prevCSRSave;
- CSRegBlockMap prevCSRRestore;
- SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks;
- bool changed = true;
- unsigned iterations = 0;
-
- // Iterate computation of spill and restore placements in the MCFG until:
- // 1. CSR use info has been fully propagated around the MCFG, and
- // 2. computation of CSRSave[], CSRRestore[] reach fixed points.
- while (changed) {
- changed = false;
- ++iterations;
-
- DEBUG(if (ShrinkWrapDebugging >= Iterations)
- DOUT << "iter " << iterations
- << " --------------------------------------------------\n");
-
- // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG,
- // which determines the placements of spills and restores.
- // Keep track of changes to spills, restores in each iteration to
- // minimize the total iterations.
- bool SRChanged = false;
- for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
- MBBI != MBBE; ++MBBI) {
- MachineBasicBlock* MBB = MBBI;
-
- // Place spills for CSRs in MBB.
- SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
-
- // Place restores for CSRs in MBB.
- SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
- }
-
- // Add uses of CSRs used inside loops where needed.
- changed |= addUsesForTopLevelLoops(cvBlocks);
-
- // Add uses for CSRs spilled or restored at branch, join points.
- if (changed || SRChanged) {
- while (! cvBlocks.empty()) {
- MachineBasicBlock* MBB = cvBlocks.pop_back_val();
- changed |= addUsesForMEMERegion(MBB, ncvBlocks);
- }
- if (! ncvBlocks.empty()) {
- cvBlocks = ncvBlocks;
- ncvBlocks.clear();
- }
- }
-
- if (changed) {
- calculateAnticAvail(Fn);
- CSRSave.clear();
- CSRRestore.clear();
- }