From 55c7a22c04d86ed5f1f201295ee6ef0695958536 Mon Sep 17 00:00:00 2001
From: Quentin Colombet <qcolombet@apple.com>
Date: Thu, 7 Jan 2016 01:23:49 +0000
Subject: [PATCH] [ShrinkWrapping] Give up on irreducible CFGs. We need to know
 whether or not a given basic block is in a loop for the analysis to be
 correct. Loop information may be incomplete on irreducible CFGs, therefore we
 may generate incorrect code if we use it in those situations.

This fixes PR25988.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257012 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/ShrinkWrap.cpp              | 47 +++++++++++++++++++
 test/CodeGen/X86/x86-shrink-wrapping.ll | 61 +++++++++++++++++++++++++
 2 files changed, 108 insertions(+)

diff --git a/lib/CodeGen/ShrinkWrap.cpp b/lib/CodeGen/ShrinkWrap.cpp
index 2ff86aaa51c..d361a6c4ad0 100644
--- a/lib/CodeGen/ShrinkWrap.cpp
+++ b/lib/CodeGen/ShrinkWrap.cpp
@@ -47,6 +47,7 @@
 // MachineFrameInfo is updated with this information.
 //===----------------------------------------------------------------------===//
 #include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 // To check for profitability.
@@ -384,6 +385,41 @@ void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
   }
 }
 
+/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI.
+/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the
+/// loop header.
+static bool isProperBackedge(const MachineLoopInfo &MLI,
+                             const MachineBasicBlock *SrcBB,
+                             const MachineBasicBlock *DestBB) {
+  for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop;
+       Loop = Loop->getParentLoop()) {
+    if (Loop->getHeader() == DestBB)
+      return true;
+  }
+  return false;
+}
+
+/// Check if the CFG of \p MF is irreducible.
+static bool isIrreducibleCFG(const MachineFunction &MF,
+                             const MachineLoopInfo &MLI) {
+  const MachineBasicBlock *Entry = &*MF.begin();
+  ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry);
+  BitVector VisitedBB(MF.getNumBlockIDs());
+  for (const MachineBasicBlock *MBB : RPOT) {
+    VisitedBB.set(MBB->getNumber());
+    for (const MachineBasicBlock *SuccBB : MBB->successors()) {
+      if (!VisitedBB.test(SuccBB->getNumber()))
+        continue;
+      // We already visited SuccBB, thus MBB->SuccBB must be a backedge.
+      // Check that the head matches what we have in the loop information.
+      // Otherwise, we have an irreducible graph.
+      if (!isProperBackedge(MLI, MBB, SuccBB))
+        return true;
+    }
+  }
+  return false;
+}
+
 bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
   if (MF.empty() || !isShrinkWrapEnabled(MF))
     return false;
@@ -392,6 +428,17 @@ bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
 
   init(MF);
 
+  if (isIrreducibleCFG(MF, *MLI)) {
+    // If MF is irreducible, a block may be in a loop without
+    // MachineLoopInfo reporting it. I.e., we may use the
+    // post-dominance property in loops, which lead to incorrect
+    // results. Moreover, we may miss that the prologue and
+    // epilogue are not in the same loop, leading to unbalanced
+    // construction/deconstruction of the stack frame.
+    DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n");
+    return false;
+  }
+
   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
   std::unique_ptr<RegScavenger> RS(
       TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
diff --git a/test/CodeGen/X86/x86-shrink-wrapping.ll b/test/CodeGen/X86/x86-shrink-wrapping.ll
index b5a3174f10e..609e2cc1158 100644
--- a/test/CodeGen/X86/x86-shrink-wrapping.ll
+++ b/test/CodeGen/X86/x86-shrink-wrapping.ll
@@ -923,3 +923,64 @@ exit:
 }
 
 attributes #3 = { nounwind }
+
+@irreducibleCFGa = common global i32 0, align 4
+@irreducibleCFGf = common global i8 0, align 1
+@irreducibleCFGb = common global i32 0, align 4
+
+; Check that we do not run shrink-wrapping on irreducible CFGs until
+; it is actually supported.
+; At the moment, on those CFGs the loop information may be incorrect
+; and since we use that information to do the placement, we may end up
+; inserting the prologue/epilogue at incorrect places.
+; PR25988.
+;
+; CHECK-LABEL: irreducibleCFG:
+; CHECK: %entry
+; Make sure the prologue happens in the entry block.
+; CHECK-NEXT: pushq
+; ...
+; Make sure the epilogue happens in the exit block.
+; CHECK-NOT: popq
+; CHECK: popq
+; CHECK-NEXT: popq
+; CHECK-NEXT: retq
+define i32 @irreducibleCFG() #4 {
+entry:
+  %i0 = load i32, i32* @irreducibleCFGa, align 4
+  %.pr = load i8, i8* @irreducibleCFGf, align 1
+  %bool = icmp eq i8 %.pr, 0
+  br i1 %bool, label %split, label %preheader
+
+preheader:
+  br label %preheader
+
+split:
+  %i1 = load i32, i32* @irreducibleCFGb, align 4
+  %tobool1.i = icmp ne i32 %i1, 0
+  br i1 %tobool1.i, label %for.body4.i, label %for.cond8.i.preheader
+
+for.body4.i:
+  %call.i = tail call i32 (...) @something(i32 %i0)
+  br label %for.cond8
+
+for.cond8:
+  %p1 = phi i32 [ %inc18.i, %for.inc ], [ 0, %for.body4.i ]
+  %.pr1.pr = load i32, i32* @irreducibleCFGb, align 4
+  br label %for.cond8.i.preheader
+
+for.cond8.i.preheader:
+  %.pr1 = phi i32 [ %.pr1.pr, %for.cond8 ], [ %i1, %split ]
+  %p13 = phi i32 [ %p1, %for.cond8 ], [ 0, %split ]
+  br label %for.inc
+
+fn1.exit:
+  ret i32 0
+
+for.inc:
+  %inc18.i = add nuw nsw i32 %p13, 1
+  %cmp = icmp slt i32 %inc18.i, 7
+  br i1 %cmp, label %for.cond8, label %fn1.exit
+}
+
+attributes #4 = { "no-frame-pointer-elim"="true" }
-- 
2.34.1