- if (MBBJoined) {
- MBBJoined = false;
- Changed = true;
- for (auto &MI : *MBB)
- OLChanged |= transfer(MI, OpenRanges, OutLocs);
- DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
- DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
-
- if (OLChanged) {
- OLChanged = false;
- for (auto s : MBB->successors())
- if (std::find(BBWorklist.begin(), BBWorklist.end(), s) ==
- BBWorklist.end()) // add if not already present.
- BBWorklist.push_back(s);
+ // This is a standard "union of predecessor outs" dataflow problem.
+ // To solve it, we perform join() and transfer() using the two worklist method
+ // until the ranges converge.
+ // Ranges have converged when both worklists are empty.
+ while (!Worklist.empty() || !Pending.empty()) {
+ // We track what is on the pending worklist to avoid inserting the same
+ // thing twice. We could avoid this with a custom priority queue, but this
+ // is probably not worth it.
+ SmallPtrSet<MachineBasicBlock *, 16> OnPending;
+ while (!Worklist.empty()) {
+ MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
+ Worklist.pop();
+ MBBJoined = join(*MBB, OutLocs, InLocs);
+
+ if (MBBJoined) {
+ MBBJoined = false;
+ Changed = true;
+ for (auto &MI : *MBB)
+ OLChanged |= transfer(MI, OpenRanges, OutLocs);
+ DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
+ DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
+
+ if (OLChanged) {
+ OLChanged = false;
+ for (auto s : MBB->successors())
+ if (!OnPending.count(s)) {
+ OnPending.insert(s);
+ Pending.push(BBToOrder[s]);
+ }
+ }