[If Converter] Convert recursion to iteration

[ahatanak]

Summary

I have a large program that has a CFG structure that looks like this:

BB0:

if (condition0)
  goto BB1
goto BB2

BB1:

goto BB2

BB2:

if (condition1)
  goto BB3
goto BB4

BB3:
...
(repeat until BB7488)

When I compile this program targeting armv7, function IfConverter::AnalyzeBlock gets called recursively a large number of times, which eventually results in hitting the stack limit and segfaulting.

This patch changes the function to use iteration instead of recursion to avoid the segfault.

[MatzeB]

LGTM with small nitpicks below:

lib/CodeGen/IfConversion.cpp

772 ↗

(On Diff #28060)

Use ///

780 ↗

(On Diff #28060)

• Adding a BBState &State = BBStack.back(); would avoid three repeated BBStack.back() calls later.

• "MachineBasicBlock *" instead of "auto" is friendlier for the reader.

[ahatanak]

Thank you Matthias. I'll commit this patch shortly.

llvm/trunk/lib/CodeGen/IfConversion.cpp

private:
     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
                      const BranchProbability &Prediction) const;
     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
                        bool FalseBranch, unsigned &Dups,
                        const BranchProbability &Prediction) const;
     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
                       unsigned &Dups1, unsigned &Dups2) const;
     void ScanInstructions(BBInfo &BBI);
-    BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
-                         std::vector<IfcvtToken*> &Tokens);
+    void AnalyzeBlock(MachineBasicBlock *MBB, std::vector<IfcvtToken*> &Tokens);
     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
                              bool isTriangle = false, bool RevBranch = false);
     void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens);
     void InvalidatePreds(MachineBasicBlock *BB);
     void RemoveExtraEdges(BBInfo &BBI);
     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
   }
 
   return true;
 }
 
 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
 /// the specified block. Record its successors and whether it looks like an
 /// if-conversion candidate.
-IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
-                                             std::vector<IfcvtToken*> &Tokens) {
+void IfConverter::AnalyzeBlock(MachineBasicBlock *MBB,
+  struct BBState {
+    BBState(MachineBasicBlock *BB) : MBB(BB), SuccsAnalyzed(false) {}
+    MachineBasicBlock *MBB;
+
+    /// This flag is true if MBB's successors have been analyzed.
+    bool SuccsAnalyzed;
+  };
+
+  // Push MBB to the stack.
+  SmallVector<BBState, 16> BBStack(1, MBB);
+
+  while (!BBStack.empty()) {
+    BBState &State = BBStack.back();
+    MachineBasicBlock *BB = State.MBB;
     BBInfo &BBI = BBAnalysis[BB->getNumber()];
 
-  if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
-    return BBI;
+    if (!State.SuccsAnalyzed) {
+      if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
+        BBStack.pop_back();
+        continue;
+      }
 
       BBI.BB = BB;
       BBI.IsBeingAnalyzed = true;
 
       ScanInstructions(BBI);
 
-  // Unanalyzable or ends with fallthrough or unconditional branch, or if is not
-  // considered for ifcvt anymore.
+      // Unanalyzable or ends with fallthrough or unconditional branch, or if is
+      // not considered for ifcvt anymore.
       if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
         BBI.IsBeingAnalyzed = false;
         BBI.IsAnalyzed = true;
-    return BBI;
+        BBStack.pop_back();
+        continue;
       }
 
       // Do not ifcvt if either path is a back edge to the entry block.
       if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
         BBI.IsBeingAnalyzed = false;
         BBI.IsAnalyzed = true;
-    return BBI;
+        BBStack.pop_back();
+        continue;
       }
 
       // Do not ifcvt if true and false fallthrough blocks are the same.
       if (!BBI.FalseBB) {
         BBI.IsBeingAnalyzed = false;
         BBI.IsAnalyzed = true;
-    return BBI;
+        BBStack.pop_back();
+        continue;
       }
 
-  BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
-  BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
+      // Push the False and True blocks to the stack.
+      State.SuccsAnalyzed = true;
+      BBStack.push_back(BBI.FalseBB);
+      BBStack.push_back(BBI.TrueBB);
+      continue;
+    }
+
+    BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
+    BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
 
     if (TrueBBI.IsDone && FalseBBI.IsDone) {
       BBI.IsBeingAnalyzed = false;
       BBI.IsAnalyzed = true;
-    return BBI;
+      BBStack.pop_back();
+      continue;
     }
 
-  SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
+    SmallVector<MachineOperand, 4>
+        RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
     bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
 
     unsigned Dups = 0;
     unsigned Dups2 = 0;
     bool TNeedSub = !TrueBBI.Predicate.empty();
     bool FNeedSub = !FalseBBI.Predicate.empty();
     bool Enqueued = false;
 
     BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
 
     if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
         MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) +
                                          TrueBBI.ExtraCost), TrueBBI.ExtraCost2,
                            *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) +
                                         FalseBBI.ExtraCost),FalseBBI.ExtraCost2,
                          Prediction) &&
         FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
         FeasibilityAnalysis(FalseBBI, RevCond)) {
       // Diamond:
       //   EBB
       //   / \_
       //  |   |
       // TBB FBB
       //   \ /
       //  TailBB
       // Note TailBB can be empty.
       Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
                                       Dups2));
       Enqueued = true;
     }
 
     if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
                            TrueBBI.ExtraCost2, Prediction) &&
         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
       // Triangle:
       //   EBB
       //   | \_
       //   |  |
       //   | TBB
       //   |  /
       //   FBB
       Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
       Enqueued = true;
     }
 
     if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
                            TrueBBI.ExtraCost2, Prediction) &&
         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
       Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
       Enqueued = true;
     }
 
     if (ValidSimple(TrueBBI, Dups, Prediction) &&
         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
                            TrueBBI.ExtraCost2, Prediction) &&
         FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
       // Simple (split, no rejoin):
       //   EBB
       //   | \_
       //   |  |
       //   | TBB---> exit
       //   |
       //   FBB
       Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
       Enqueued = true;
     }
 
     if (CanRevCond) {
       // Try the other path...
       if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
                         Prediction.getCompl()) &&
           MeetIfcvtSizeLimit(*FalseBBI.BB,
                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
           FeasibilityAnalysis(FalseBBI, RevCond, true)) {
         Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
         Enqueued = true;
       }
 
       if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
                         Prediction.getCompl()) &&
           MeetIfcvtSizeLimit(*FalseBBI.BB,
                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
                            FalseBBI.ExtraCost2, Prediction.getCompl()) &&
         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
         Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
         Enqueued = true;
       }
 
       if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
           MeetIfcvtSizeLimit(*FalseBBI.BB,
                              FalseBBI.NonPredSize + FalseBBI.ExtraCost,
                              FalseBBI.ExtraCost2, Prediction.getCompl()) &&
           FeasibilityAnalysis(FalseBBI, RevCond)) {
         Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
         Enqueued = true;
       }
     }
 
     BBI.IsEnqueued = Enqueued;
     BBI.IsBeingAnalyzed = false;
     BBI.IsAnalyzed = true;
-  return BBI;
+    BBStack.pop_back();
+  }
 }
 
 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
 /// candidates.
 void IfConverter::AnalyzeBlocks(MachineFunction &MF,
                                 std::vector<IfcvtToken*> &Tokens) {
   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
     MachineBasicBlock *BB = I;