[CGP] Fix crash on i96 bit multiply

Issue found by llvm-isel-fuzzer on OSS fuzz, https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=3725

If anyone actually cares about > 64 bit arithmetic, there's a lot more to do in this area.  There's a bunch of obviously wrong code in the same function.  I don't have the time to fix all of them and am just using this to understand what the workflow for fixing fuzzer cases might look like.




git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@316967 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 256 insertions, 83 deletions

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 47bdac00ae1..57deddc80d9 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1690,8 +1690,13 @@ SCEVExpander::FindValueInExprValueMap(const SCEV *S,
       // the LCSSA form.
       for (auto const &VOPair : *Set) {
         Value *V = VOPair.first;
+        dbgs() << "found " << *V << "\n";
         ConstantInt *Offset = VOPair.second;
         Instruction *EntInst = nullptr;
+        if (V && isa<Constant>(V))
+          return {V, Offset};
+        if (V && isa<Argument>(V))
+          return {V, Offset};
         if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
             S->getType() == V->getType() &&
             EntInst->getFunction() == InsertPt->getFunction() &&
@@ -1702,6 +1707,9 @@ SCEVExpander::FindValueInExprValueMap(const SCEV *S,
       }
     }
   }
+  if (auto *C = dyn_cast<SCEVConstant>(S))
+    return {C->getValue(), nullptr};
+  dbgs() << "Reject: " << *S << "\n";
   return {nullptr, nullptr};
 }
 
diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp
index 0a417e34084..13bdad71252 100644
--- a/lib/CodeGen/CodeGenPrepare.cpp
+++ b/lib/CodeGen/CodeGenPrepare.cpp
@@ -4032,7 +4032,7 @@ bool AddressingModeMatcher::matchOperationAddr(User *AddrInst, unsigned Opcode,
   case Instruction::Shl: {
     // Can only handle X*C and X << C.
     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
-    if (!RHS)
+    if (!RHS || RHS->getBitWidth() > 64)
       return false;
     int64_t Scale = RHS->getSExtValue();
     if (Opcode == Instruction::Shl)
diff --git a/lib/Transforms/Utils/SimplifyIndVar.cpp b/lib/Transforms/Utils/SimplifyIndVar.cpp
index 5263e8ccc6d..46a105a04c4 100644
--- a/lib/Transforms/Utils/SimplifyIndVar.cpp
+++ b/lib/Transforms/Utils/SimplifyIndVar.cpp
@@ -83,6 +83,7 @@ namespace {
 
     bool eliminateOverflowIntrinsic(CallInst *CI);
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
+    bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                              bool IsSigned);
@@ -161,6 +162,240 @@ Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand)
   return IVSrc;
 }
 
+#if 0
+bool SimplifyIndvar::isSimpleLoopInvariantPredicate(
+                                ICmpInst::Predicate Pred, const SCEV *LHS,
+                                const SCEV *RHS, const Loop *L,
+                                ICmpInst::Predicate &InvariantPred,
+                                Value *&NewLHS,
+                                Value *&NewRHS) {
+  ICmpInst::Predicate InvariantPredicate;
+  const SCEV *InvariantLHS, *InvariantRHS;
+
+  if (!isa<PHINode>(IVOperand))
+    return false;
+  if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
+                                    InvariantLHS, InvariantRHS))
+    return false;
+
+  // Rewrite the comparison to a loop invariant comparison if it can be done
+  // cheaply, where cheaply means "we don't need to emit any new
+  // instructions".
+
+  Value *NewLHS = nullptr, *NewRHS = nullptr;
+
+  if (LHS == InvariantLHS)
+    NewLHS = LHS;
+  else if (RHS == InvariantLHS)
+    NewLHS = RHS;
+
+  if (LHS == InvariantRHS)
+    NewRHS = LHS;
+  else if (RHS == InvariantRHS)
+    NewRHS = RHS;
+
+
+  if (S == InvariantLHS || X == InvariantLHS)
+    NewLHS =
+      ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
+
+  if (S == InvariantRHS || X == InvariantRHS)
+    NewRHS =
+      ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
+
+  auto *PN = cast<PHINode>(IVOperand);
+  for (unsigned i = 0, e = PN->getNumIncomingValues();
+       i != e && (!NewLHS || !NewRHS);
+       ++i) {
+
+    // If this is a value incoming from the backedge, then it cannot be a loop
+    // invariant value (since we know that IVOperand is an induction variable).
+    if (L->contains(PN->getIncomingBlock(i)))
+      continue;
+
+    // NB! This following assert does not fundamentally have to be true, but
+    // it is true today given how SCEV analyzes induction variables.
+    // Specifically, today SCEV will *not* recognize %iv as an induction
+    // variable in the following case:
+    //
+    // define void @f(i32 %k) {
+    // entry:
+    //   br i1 undef, label %r, label %l
+    //
+    // l:
+    //   %k.inc.l = add i32 %k, 1
+    //   br label %loop
+    //
+    // r:
+    //   %k.inc.r = add i32 %k, 1
+    //   br label %loop
+    //
+    // loop:
+    //   %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
+    //   %iv.inc = add i32 %iv, 1
+    //   br label %loop
+    // }
+    //
+    // but if it starts to, at some point, then the assertion below will have
+    // to be changed to a runtime check.
+
+    Value *Incoming = PN->getIncomingValue(i);
+
+#ifndef NDEBUG
+    if (auto *I = dyn_cast<Instruction>(Incoming))
+      assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
+#endif
+
+    const SCEV *IncomingS = SE->getSCEV(Incoming);
+
+    if (!NewLHS && IncomingS == InvariantLHS)
+      NewLHS = Incoming;
+    if (!NewRHS && IncomingS == InvariantRHS)
+      NewRHS = Incoming;
+  }
+
+  if (!NewLHS || !NewRHS)
+    // We could not find an existing value to replace either LHS or RHS.
+    // Generating new instructions has subtler tradeoffs, so avoid doing that
+    // for now.
+    return false;
+}
+#endif
+
+bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
+                                               Value *IVOperand) {
+  unsigned IVOperIdx = 0;
+  ICmpInst::Predicate Pred = ICmp->getPredicate();
+  if (IVOperand != ICmp->getOperand(0)) {
+    // Swapped
+    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
+    IVOperIdx = 1;
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  // Get the SCEVs for the ICmp operands (in the specific context of the
+  // current loop)
+  Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
+  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
+  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
+
+  ICmpInst::Predicate InvariantPredicate;
+  const SCEV *InvariantLHS, *InvariantRHS;
+
+  if (!isa<PHINode>(IVOperand))
+    return false;
+  if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
+                                    InvariantLHS, InvariantRHS))
+    return false;
+
+  // Rewrite the comparison to a loop invariant comparison if it can be done
+  // cheaply, where cheaply means "we don't need to emit any new
+  // instructions".
+
+  Value *NewLHS = nullptr, *NewRHS = nullptr;
+
+#if 1
+  const Instruction *At = L->getLoopPreheader()->getTerminator();
+  auto *PN = cast<PHINode>(IVOperand);
+#if 0
+  SE->getSCEV(ICmp->getOperand(0));
+  SE->getSCEV(ICmp->getOperand(1));
+
+  for (unsigned i = 0, e = PN->getNumIncomingValues();
+       i != e;
+       ++i) {
+    // If this is a value incoming from the backedge, then it cannot be a loop
+    // invariant value (since we know that IVOperand is an induction variable).
+    if (L->contains(PN->getIncomingBlock(i)))
+      continue;
+    SE->getSCEV(PN->getIncomingValue(i));
+  }
+#endif
+  
+  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
+  NewLHS = Rewriter.getExactExistingExpansion(InvariantLHS, At,
+                                              ICmpLoop);
+  NewRHS = Rewriter.getExactExistingExpansion(InvariantRHS, At,
+                                              ICmpLoop);
+  if (NewLHS)
+    dbgs() << "expand " << InvariantLHS << " as " << *NewLHS << "\n";
+  if (NewRHS)
+    dbgs() << "expand " << InvariantRHS << " as " << *NewRHS << "\n";
+
+#else
+  if (S == InvariantLHS || X == InvariantLHS)
+    NewLHS =
+      ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
+
+  if (S == InvariantRHS || X == InvariantRHS)
+    NewRHS =
+      ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
+
+  auto *PN = cast<PHINode>(IVOperand);
+  for (unsigned i = 0, e = PN->getNumIncomingValues();
+       i != e && (!NewLHS || !NewRHS);
+       ++i) {
+
+    // If this is a value incoming from the backedge, then it cannot be a loop
+    // invariant value (since we know that IVOperand is an induction variable).
+    if (L->contains(PN->getIncomingBlock(i)))
+      continue;
+
+    // NB! This following assert does not fundamentally have to be true, but
+    // it is true today given how SCEV analyzes induction variables.
+    // Specifically, today SCEV will *not* recognize %iv as an induction
+    // variable in the following case:
+    //
+    // define void @f(i32 %k) {
+    // entry:
+    //   br i1 undef, label %r, label %l
+    //
+    // l:
+    //   %k.inc.l = add i32 %k, 1
+    //   br label %loop
+    //
+    // r:
+    //   %k.inc.r = add i32 %k, 1
+    //   br label %loop
+    //
+    // loop:
+    //   %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
+    //   %iv.inc = add i32 %iv, 1
+    //   br label %loop
+    // }
+    //
+    // but if it starts to, at some point, then the assertion below will have
+    // to be changed to a runtime check.
+
+    Value *Incoming = PN->getIncomingValue(i);
+
+#ifndef NDEBUG
+    if (auto *I = dyn_cast<Instruction>(Incoming))
+      assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
+#endif
+
+    const SCEV *IncomingS = SE->getSCEV(Incoming);
+
+    if (!NewLHS && IncomingS == InvariantLHS)
+      NewLHS = Incoming;
+    if (!NewRHS && IncomingS == InvariantRHS)
+      NewRHS = Incoming;
+  }
+#endif
+
+  if (!NewLHS || !NewRHS)
+    // We could not find an existing value to replace either LHS or RHS.
+    // Generating new instructions has subtler tradeoffs, so avoid doing that
+    // for now.
+    return false;
+
+  DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
+  ICmp->setPredicate(InvariantPredicate);
+  ICmp->setOperand(0, NewLHS);
+  ICmp->setOperand(1, NewRHS);
+  return true;
+}
+
 /// SimplifyIVUsers helper for eliminating useless
 /// comparisons against an induction variable.
 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
@@ -180,9 +415,6 @@ void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
   const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
 
-  ICmpInst::Predicate InvariantPredicate;
-  const SCEV *InvariantLHS, *InvariantRHS;
-
   // If the condition is always true or always false, replace it with
   // a constant value.
   if (SE->isKnownPredicate(Pred, S, X)) {
@@ -193,85 +425,8 @@ void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
     DeadInsts.emplace_back(ICmp);
     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
-  } else if (isa<PHINode>(IVOperand) &&
-             SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
-                                          InvariantLHS, InvariantRHS)) {
-
-    // Rewrite the comparison to a loop invariant comparison if it can be done
-    // cheaply, where cheaply means "we don't need to emit any new
-    // instructions".
-
-    Value *NewLHS = nullptr, *NewRHS = nullptr;
-
-    if (S == InvariantLHS || X == InvariantLHS)
-      NewLHS =
-          ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
-
-    if (S == InvariantRHS || X == InvariantRHS)
-      NewRHS =
-          ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
-
-    auto *PN = cast<PHINode>(IVOperand);
-    for (unsigned i = 0, e = PN->getNumIncomingValues();
-         i != e && (!NewLHS || !NewRHS);
-         ++i) {
-
-      // If this is a value incoming from the backedge, then it cannot be a loop
-      // invariant value (since we know that IVOperand is an induction variable).
-      if (L->contains(PN->getIncomingBlock(i)))
-        continue;
-
-      // NB! This following assert does not fundamentally have to be true, but
-      // it is true today given how SCEV analyzes induction variables.
-      // Specifically, today SCEV will *not* recognize %iv as an induction
-      // variable in the following case:
-      //
-      // define void @f(i32 %k) {
-      // entry:
-      //   br i1 undef, label %r, label %l
-      //
-      // l:
-      //   %k.inc.l = add i32 %k, 1
-      //   br label %loop
-      //
-      // r:
-      //   %k.inc.r = add i32 %k, 1
-      //   br label %loop
-      //
-      // loop:
-      //   %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
-      //   %iv.inc = add i32 %iv, 1
-      //   br label %loop
-      // }
-      //
-      // but if it starts to, at some point, then the assertion below will have
-      // to be changed to a runtime check.
-
-      Value *Incoming = PN->getIncomingValue(i);
-
-#ifndef NDEBUG
-      if (auto *I = dyn_cast<Instruction>(Incoming))
-        assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
-#endif
-
-      const SCEV *IncomingS = SE->getSCEV(Incoming);
-
-      if (!NewLHS && IncomingS == InvariantLHS)
-        NewLHS = Incoming;
-      if (!NewRHS && IncomingS == InvariantRHS)
-        NewRHS = Incoming;
-    }
-
-    if (!NewLHS || !NewRHS)
-      // We could not find an existing value to replace either LHS or RHS.
-      // Generating new instructions has subtler tradeoffs, so avoid doing that
-      // for now.
-      return;
-
-    DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
-    ICmp->setPredicate(InvariantPredicate);
-    ICmp->setOperand(0, NewLHS);
-    ICmp->setOperand(1, NewRHS);
+  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
+    // fallthrough to end of function
   } else if (ICmpInst::isSigned(OriginalPred) &&
              SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
     // If we were unable to make anything above, all we can is to canonicalize
diff --git a/test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll b/test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll
index 9d2e3fff59d..a8589ff4949 100644
--- a/test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll
+++ b/test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll
@@ -268,3 +268,13 @@ entry:
   call void @foo(i32 %v)
   ret void
 }
+
+; Found by fuzzer, getSExtValue of > 64 bit constant
+define void @i96_mul(i1* %base, i96 %offset) {
+BB:
+  ;; RHS = 0x7FFFFFFFFFFFFFFFFFFFFFFF
+  %B84 = mul i96 %offset, 39614081257132168796771975167
+  %G23 = getelementptr i1, i1* %base, i96 %B84
+  store i1 false, i1* %G23
+  ret void
+}