Lines Matching full:mbb
126 bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
127 return (MBB && !MBB->empty() && MBB->back().isReturn());
197 /// for the given MBB by looking forward in the MCFG at MBB's
200 bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
203 // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB))
205 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
206 SE = MBB->succ_end(); SI != SE; ++SI) {
208 if (SUCC != MBB)
214 CSRegSet prevAnticOut = AnticOut[MBB];
217 AnticOut[MBB] = AnticIn[SUCC];
220 AnticOut[MBB] &= AnticIn[SUCC];
222 if (prevAnticOut != AnticOut[MBB])
226 // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]);
227 CSRegSet prevAnticIn = AnticIn[MBB];
228 AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
229 if (prevAnticIn != AnticIn[MBB])
235 /// for the given MBB by looking backward in the MCFG at MBB's
238 bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
241 // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB))
243 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
244 PE = MBB->pred_end(); PI != PE; ++PI) {
246 if (PRED != MBB)
252 CSRegSet prevAvailIn = AvailIn[MBB];
255 AvailIn[MBB] = AvailOut[PRED];
258 AvailIn[MBB] &= AvailOut[PRED];
260 if (prevAvailIn != AvailIn[MBB])
264 // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]);
265 CSRegSet prevAvailOut = AvailOut[MBB];
266 AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
267 if (prevAvailOut != AvailOut[MBB])
288 MachineBasicBlock* MBB = MBBI;
290 // Calculate anticipated in, out regs at MBB from
291 // anticipated at successors of MBB.
292 changed |= calcAnticInOut(MBB);
294 // Calculate available in, out regs at MBB from
295 // available at predecessors of MBB.
296 changed |= calcAvailInOut(MBB);
308 << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n"
313 MachineBasicBlock* MBB = MBBI;
314 dumpSets(MBB);
323 /// propagateUsesAroundLoop - copy used register info from MBB to all blocks
327 void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
328 if (! MBB || !LP)
334 if (LBB == MBB)
336 if (CSRUsed[LBB].contains(CSRUsed[MBB]))
338 CSRUsed[LBB] |= CSRUsed[MBB];
373 for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
374 MBB != E; ++MBB)
375 if (isReturnBlock(MBB))
376 ReturnBlocks.push_back(MBB);
409 MachineBasicBlock* MBB = MBBI;
410 for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
427 // CSR Reg is defined/used in block MBB.
428 CSRUsed[MBB].set(inx);
430 if (MBB != EntryBlock)
437 if (CSRUsed[MBB].empty())
440 // Propagate CSRUsed[MBB] in loops
441 if (MachineLoop* LP = LI.getLoopFor(MBB)) {
459 propagateUsesAroundLoop(MBB, PLP);
462 propagateUsesAroundLoop(MBB, LP);
487 // Check if MBB uses CSRs and dominates all exit nodes.
495 MachineBasicBlock* MBB = MBBI;
496 if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
500 if (! DT.dominates(MBB, ReturnBlocks[ri])) {
505 CSRUsedInChokePoints |= CSRUsed[MBB];
509 << getBasicBlockName(MBB) << "\n");
556 bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
558 if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
560 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
561 SE = MBB->succ_end(); SI != SE; ++SI) {
568 if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
569 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
570 PE = MBB->pred_end(); PI != PE; ++PI) {
583 if (!CSRSave[MBB].empty())
584 prop = CSRSave[MBB];
585 else if (!CSRRestore[MBB].empty())
586 prop = CSRRestore[MBB];
588 prop = CSRUsed[MBB];
592 // Propagate selected bits to successors, predecessors of MBB.
594 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
595 SE = MBB->succ_end(); SI != SE; ++SI) {
598 if (SUCC == MBB)
605 dbgs() << getBasicBlockName(MBB)
610 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
611 PE = MBB->pred_end(); PI != PE; ++PI) {
614 if (PRED == MBB)
621 dbgs() << getBasicBlockName(MBB)
638 MachineBasicBlock* MBB = I->first;
644 loopSpills = CSRSave[MBB];
645 if (CSRSave[MBB].empty()) {
648 } else if (CSRRestore[MBB].contains(CSRSave[MBB]))
659 dbgs() << "LOOP " << getBasicBlockName(MBB)
671 /// in MBB using AnticIn sets of MBB's predecessors, keeping track
672 /// of changes to spilled reg sets. Add MBB to the set of blocks
676 bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
680 // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB)
683 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
684 PE = MBB->pred_end(); PI != PE; ++PI) {
686 if (PRED != MBB)
704 // Compute spills required at MBB:
705 CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
707 if (! CSRSave[MBB].empty()) {
708 if (MBB == EntryBlock) {
710 CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
712 // Reset all regs spilled in MBB that are also spilled in EntryBlock.
713 if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
714 CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
718 placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
719 prevSpills[MBB] = CSRSave[MBB];
723 blks.push_back(MBB);
725 DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
726 dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
727 << stringifyCSRegSet(CSRSave[MBB]) << "\n");
733 /// in MBB using AvailOut sets of MBB's succcessors, keeping track
734 /// of changes to restored reg sets. Add MBB to the set of blocks
738 bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
742 // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB)
745 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
746 SE = MBB->succ_end(); SI != SE; ++SI) {
748 if (SUCC != MBB)
760 if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
768 // Compute restores required at MBB:
769 CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
771 // Postprocess restore placements at MBB.
775 if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
777 CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
779 placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
780 prevRestores[MBB] = CSRRestore[MBB];
784 blks.push_back(MBB);
786 DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
787 dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = "
788 << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
821 MachineBasicBlock* MBB = MBBI;
823 // Place spills for CSRs in MBB.
824 SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
826 // Place restores for CSRs in MBB.
827 SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
836 MachineBasicBlock* MBB = cvBlocks.pop_back_val();
837 changed |= addUsesForMEMERegion(MBB, ncvBlocks);
930 /// Spills: walk df from each MBB
932 /// from MBB to all exit blocks.
933 /// Restores: walk idf from each MBB in restore set ensuring that
934 /// all CSRs restored at MBB are spilled on all paths
935 /// reaching MBB.
941 MachineBasicBlock* MBB = MBBI;
942 if (isReturnBlock(MBB) || MBB->succ_size() == 0)
947 MachineBasicBlock* MBB = BI->first;
954 DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
956 << " RESTORE[" << getBasicBlockName(MBB) << "] = "
957 << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
959 if (CSRRestore[MBB].intersects(spilled)) {
960 restored |= (CSRRestore[MBB] & spilled);
963 // Walk depth first from MBB to find restores of all CSRs spilled at MBB:
965 // paths from MBB to all return blocks.
966 for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB),
967 BE = df_end(MBB); BI != BE; ++BI) {
969 if (SBB == MBB)
971 // Stop when we encounter spills of any CSRs spilled at MBB that
976 // Collect the CSRs spilled at MBB that are restored
977 // at this DF successor of MBB.
981 // we have seen so far exhaust the spills at MBB, then
988 << " spilled at " << getBasicBlockName(MBB)
1000 MachineBasicBlock* MBB = BI->first;
1007 DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
1008 << stringifyCSRegSet(CSRSave[MBB])
1009 << " RESTORE[" << getBasicBlockName(MBB) << "] = "
1012 if (CSRSave[MBB].intersects(restored)) {
1013 spilled |= (CSRSave[MBB] & restored);
1015 // Walk inverse depth first from MBB to find spills of all
1016 // CSRs restored at MBB:
1017 for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB),
1018 BE = idf_end(MBB); BI != BE; ++BI) {
1020 if (PBB == MBB)
1022 // Stop when we encounter restores of any CSRs restored at MBB that
1027 // Collect the CSRs restored at MBB that are spilled
1028 // at this DF predecessor of MBB.
1036 << " restored at " << getBasicBlockName(MBB)
1043 std::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) {
1044 if (!MBB)
1047 if (MBB->getBasicBlock())
1048 return MBB->getBasicBlock()->getName().str();
1051 name << "_MBB_" << MBB->getNumber();
1084 void PEI::dumpUsed(MachineBasicBlock* MBB) {
1086 if (MBB)
1087 dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
1088 << stringifyCSRegSet(CSRUsed[MBB]) << "\n";
1095 MachineBasicBlock* MBB = MBBI;
1096 dumpUsed(MBB);
1100 void PEI::dumpSets(MachineBasicBlock* MBB) {
1102 if (MBB)
1103 dbgs() << getBasicBlockName(MBB) << " | "
1104 << stringifyCSRegSet(CSRUsed[MBB]) << " | "
1105 << stringifyCSRegSet(AnticIn[MBB]) << " | "
1106 << stringifyCSRegSet(AnticOut[MBB]) << " | "
1107 << stringifyCSRegSet(AvailIn[MBB]) << " | "
1108 << stringifyCSRegSet(AvailOut[MBB]) << "\n";
1112 void PEI::dumpSets1(MachineBasicBlock* MBB) {
1114 if (MBB)
1115 dbgs() << getBasicBlockName(MBB) << " | "
1116 << stringifyCSRegSet(CSRUsed[MBB]) << " | "
1117 << stringifyCSRegSet(AnticIn[MBB]) << " | "
1118 << stringifyCSRegSet(AnticOut[MBB]) << " | "
1119 << stringifyCSRegSet(AvailIn[MBB]) << " | "
1120 << stringifyCSRegSet(AvailOut[MBB]) << " | "
1121 << stringifyCSRegSet(CSRSave[MBB]) << " | "
1122 << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
1129 MachineBasicBlock* MBB = MBBI;
1130 dumpSets1(MBB);
1136 for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
1137 MBB != E; ++MBB) {
1138 if (!CSRSave[MBB].empty()) {
1139 dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
1140 << stringifyCSRegSet(CSRSave[MBB]);
1141 if (CSRRestore[MBB].empty())
1145 if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty())
1147 << "RESTORE[" << getBasicBlockName(MBB) << "] = "
1148 << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
