From bbaeda3fe5d132d4b58f7606663704e408ef9796 Mon Sep 17 00:00:00 2001
From: Tobias Grosser <tobias@grosser.es>
Date: Thu, 10 Nov 2016 05:20:29 +0000
Subject: [PATCH] Do not allow switch statements in loop latches

In r248701 "Allow switch instructions in SCoPs" support for switch statements
has been introduced, but support for switch statements in loop latches was
incomplete. This change completely disables switch statements in loop latches.

The original commit changed addLoopBoundsToHeaderDomain to support non-branch
terminator instructions, but this change was incorrect: it added a check for
BI != null to the if-branch of a condition, but BI was used in the else branch
es well. As a result, when a non-branch terminator instruction is encounted a
nullptr dereference is triggered. Due to missing test coverage, this bug was
overlooked.

r249273 "[FIX] Approximate non-affine loops correctly" added code to disallow
switch statements for non-affine loops, if they appear in either a loop latch
or a loop exit. We adapt this code to now prohibit switch statements in
loop latches even if the control condition is affine.

We could possibly add support for switch statements in loop latches, but such
support should be evaluated and tested separately.

This fixes llvm.org/PR30952

Reported-by: Eli Friedman <efriedma@codeaurora.org>
llvm-svn: 286426
---
 polly/lib/Analysis/ScopDetection.cpp          | 16 ++++++++--------
 polly/lib/Analysis/ScopInfo.cpp               |  4 +++-
 polly/test/ScopDetect/switch-in-loop-patch.ll | 21 +++++++++++++++++++++
 3 files changed, 32 insertions(+), 9 deletions(-)
 create mode 100644 polly/test/ScopDetect/switch-in-loop-patch.ll

diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 599b8c8..8700ae2 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -341,16 +341,16 @@ bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
   Loop *L = LI->getLoopFor(&BB);
   const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L);
 
+  if (IsLoopBranch && L->isLoopLatch(&BB))
+    return false;
+
   if (isAffine(ConditionSCEV, L, Context))
     return true;
 
-  if (!IsLoopBranch && AllowNonAffineSubRegions &&
+  if (AllowNonAffineSubRegions &&
       addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
     return true;
 
-  if (IsLoopBranch)
-    return false;
-
   return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
                                      ConditionSCEV, ConditionSCEV, SI);
 }
@@ -359,6 +359,10 @@ bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
                                   Value *Condition, bool IsLoopBranch,
                                   DetectionContext &Context) const {
 
+  // Constant integer conditions are always affine.
+  if (isa<ConstantInt>(Condition))
+    return true;
+
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
     auto Opcode = BinOp->getOpcode();
     if (Opcode == Instruction::And || Opcode == Instruction::Or) {
@@ -425,10 +429,6 @@ bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
   if (isa<UndefValue>(Condition))
     return invalid<ReportUndefCond>(Context, /*Assert=*/true, TI, &BB);
 
-  // Constant integer conditions are always affine.
-  if (isa<ConstantInt>(Condition))
-    return true;
-
   if (BranchInst *BI = dyn_cast<BranchInst>(TI))
     return isValidBranch(BB, BI, Condition, IsLoopBranch, Context);
 
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 187a8f7..b7a1bdd 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -2792,7 +2792,9 @@ bool Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
 
     TerminatorInst *TI = LatchBB->getTerminator();
     BranchInst *BI = dyn_cast<BranchInst>(TI);
-    if (BI && BI->isUnconditional())
+    assert(BI && "Only branch instructions allowed in loop latches");
+
+    if (BI->isUnconditional())
       BackedgeCondition = isl_set_copy(LatchBBDom);
     else {
       SmallVector<isl_set *, 8> ConditionSets;
diff --git a/polly/test/ScopDetect/switch-in-loop-patch.ll b/polly/test/ScopDetect/switch-in-loop-patch.ll
new file mode 100644
index 0000000..6694446
--- /dev/null
+++ b/polly/test/ScopDetect/switch-in-loop-patch.ll
@@ -0,0 +1,21 @@
+; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s
+
+; CHECK-NOT: Valid
+
+; Verify that we do not detect loops where the loop latch is a switch statement.
+; Such loops are not yet supported by Polly.
+
+define void @f() {
+b:
+  br label %d
+
+d:
+  switch i8 0, label %e [
+    i8 71, label %d
+    i8 56, label %d
+  ]
+
+e:
+ ret void
+}
+
-- 
2.7.4