From 070e540a3e7eb67d874444ade78bf007c4764aa5 Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Fri, 16 Mar 2012 03:16:56 +0000
Subject: LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.

Only record IVUsers that are dominated by simplified loop
headers. Otherwise SCEVExpander will crash while looking for a
preheader.

I previously tried to work around this in LSR itself, but that was
insufficient. This way, LSR can continue to run if some uses are not
in simple loops, as long as we don't attempt to analyze those users.

Fixes <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce

llvm-svn: 152892
---
 llvm/lib/Analysis/IVUsers.cpp | 46 ++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 41 insertions(+), 5 deletions(-)

(limited to 'llvm/lib/Analysis/IVUsers.cpp')

diff --git a/llvm/lib/Analysis/IVUsers.cpp b/llvm/lib/Analysis/IVUsers.cpp
index cad22f8f1a6..c598b72c0de 100644
--- a/llvm/lib/Analysis/IVUsers.cpp
+++ b/llvm/lib/Analysis/IVUsers.cpp
@@ -79,10 +79,30 @@ static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
   return false;
 }
 
+/// Return true if this loop and all loop headers that dominate it are in
+/// simplified form.
+static bool isSimplifiedLoopNest(Loop *L, const DominatorTree *DT,
+                                 const LoopInfo *LI) {
+  if (!L->isLoopSimplifyForm())
+    return false;
+
+  for (DomTreeNode *Rung = DT->getNode(L->getLoopPreheader());
+       Rung; Rung = Rung->getIDom()) {
+    BasicBlock *BB = Rung->getBlock();
+    const Loop *DomLoop = LI->getLoopFor(BB);
+    if (DomLoop && DomLoop->getHeader() == BB) {
+      if (!DomLoop->isLoopSimplifyForm())
+        return false;
+    }
+  }
+  return true;
+}
+
 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 /// return true.  Otherwise, return false.
-bool IVUsers::AddUsersIfInteresting(Instruction *I) {
+bool IVUsers::AddUsersIfInteresting(Instruction *I,
+                                    SmallPtrSet<Loop*,16> &SimpleLoopNests) {
   // Add this IV user to the Processed set before returning false to ensure that
   // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
   if (!Processed.insert(I))
@@ -117,6 +137,16 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
     if (isa<PHINode>(User) && Processed.count(User))
       continue;
 
+    Loop *UserLoop = LI->getLoopFor(User->getParent());
+
+    // Only consider IVUsers that are dominated by simplified loop
+    // headers. Otherwise, SCEVExpander will crash.
+    if (UserLoop && !SimpleLoopNests.count(UserLoop)) {
+      if (!isSimplifiedLoopNest(UserLoop, DT, LI))
+        return false;
+      SimpleLoopNests.insert(UserLoop);
+    }
+
     // Descend recursively, but not into PHI nodes outside the current loop.
     // It's important to see the entire expression outside the loop to get
     // choices that depend on addressing mode use right, although we won't
@@ -124,14 +154,15 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
     // If User is already in Processed, we don't want to recurse into it again,
     // but do want to record a second reference in the same instruction.
     bool AddUserToIVUsers = false;
-    if (LI->getLoopFor(User->getParent()) != L) {
+    if (UserLoop != L) {
       if (isa<PHINode>(User) || Processed.count(User) ||
-          !AddUsersIfInteresting(User)) {
+          !AddUsersIfInteresting(User, SimpleLoopNests)) {
         DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
                      << "   OF SCEV: " << *ISE << '\n');
         AddUserToIVUsers = true;
       }
-    } else if (Processed.count(User) || !AddUsersIfInteresting(User)) {
+    } else if (Processed.count(User)
+               || !AddUsersIfInteresting(User, SimpleLoopNests)) {
       DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
                    << "   OF SCEV: " << *ISE << '\n');
       AddUserToIVUsers = true;
@@ -180,11 +211,16 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
   SE = &getAnalysis<ScalarEvolution>();
   TD = getAnalysisIfAvailable<TargetData>();
 
+  // SCEVExpander can only handle users that are dominated by simplified loop
+  // entries. Keep track of all loops that are only dominated by other simple
+  // loops so we don't traverse the domtree for each user.
+  SmallPtrSet<Loop*,16> SimpleLoopNests;
+
   // Find all uses of induction variables in this loop, and categorize
   // them by stride.  Start by finding all of the PHI nodes in the header for
   // this loop.  If they are induction variables, inspect their uses.
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
-    (void)AddUsersIfInteresting(I);
+    (void)AddUsersIfInteresting(I, SimpleLoopNests);
 
   return false;
 }
-- 
cgit v1.2.3