IndVarSimplify.cpp

  //  - We depend on having a preheader; in particular,
  //    Loop::getCanonicalInductionVariable only supports loops with preheaders,
  //    and we're in trouble if we can't find the induction variable even when
  //    we've manually inserted one.
  if (!L->isLoopSimplifyForm())
    return false;

  if (!DisableIVRewrite)
    IU = &getAnalysis<IVUsers>();
  LI = &getAnalysis<LoopInfo>();
  SE = &getAnalysis<ScalarEvolution>();
  DT = &getAnalysis<DominatorTree>();
  TD = getAnalysisIfAvailable<TargetData>();

  DeadInsts.clear();
  Changed = false;

  // If there are any floating-point recurrences, attempt to
  // transform them to use integer recurrences.
  RewriteNonIntegerIVs(L);

  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);

  // Create a rewriter object which we'll use to transform the code with.
  SCEVExpander Rewriter(*SE, "indvars");

  // Eliminate redundant IV users.
  //
  // Simplification works best when run before other consumers of SCEV. We
  // attempt to avoid evaluating SCEVs for sign/zero extend operations until
  // other expressions involving loop IVs have been evaluated. This helps SCEV
  // set no-wrap flags before normalizing sign/zero extension.
  if (DisableIVRewrite) {
    Rewriter.disableCanonicalMode();
    SimplifyIVUsersNoRewrite(L, Rewriter);
  }

  // Check to see if this loop has a computable loop-invariant execution count.
  // If so, this means that we can compute the final value of any expressions
  // that are recurrent in the loop, and substitute the exit values from the
  // loop into any instructions outside of the loop that use the final values of
  // the current expressions.
  //
  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
    RewriteLoopExitValues(L, Rewriter);

  // Eliminate redundant IV users.
  if (!DisableIVRewrite)
    SimplifyIVUsers(Rewriter);

  // Eliminate redundant IV cycles.
  if (DisableIVRewrite)
    SimplifyCongruentIVs(L);

  // Compute the type of the largest recurrence expression, and decide whether
  // a canonical induction variable should be inserted.
  Type *LargestType = 0;
  bool NeedCannIV = false;
  bool ReuseIVForExit = DisableIVRewrite && !ForceLFTR;
  bool ExpandBECount = canExpandBackedgeTakenCount(L, SE);
  if (ExpandBECount && !ReuseIVForExit) {
    // If we have a known trip count and a single exit block, we'll be
    // rewriting the loop exit test condition below, which requires a
    // canonical induction variable.
    NeedCannIV = true;
    Type *Ty = BackedgeTakenCount->getType();
    if (DisableIVRewrite) {
      // In this mode, SimplifyIVUsers may have already widened the IV used by
      // the backedge test and inserted a Trunc on the compare's operand. Get
      // the wider type to avoid creating a redundant narrow IV only used by the
      // loop test.
      LargestType = getBackedgeIVType(L);
    }
    if (!LargestType ||
        SE->getTypeSizeInBits(Ty) >
        SE->getTypeSizeInBits(LargestType))
      LargestType = SE->getEffectiveSCEVType(Ty);
  }
  if (!DisableIVRewrite) {
    for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) {
      NeedCannIV = true;
      Type *Ty =
        SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType());
      if (!LargestType ||
          SE->getTypeSizeInBits(Ty) >
          SE->getTypeSizeInBits(LargestType))
        LargestType = Ty;
    }
  }

  // Now that we know the largest of the induction variable expressions
  // in this loop, insert a canonical induction variable of the largest size.
  PHINode *IndVar = 0;
  if (NeedCannIV) {
    // Check to see if the loop already has any canonical-looking induction
    // variables. If any are present and wider than the planned canonical
    // induction variable, temporarily remove them, so that the Rewriter
    // doesn't attempt to reuse them.
    SmallVector<PHINode *, 2> OldCannIVs;
    while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) {
      if (SE->getTypeSizeInBits(OldCannIV->getType()) >
          SE->getTypeSizeInBits(LargestType))
        OldCannIV->removeFromParent();
      else
        break;
      OldCannIVs.push_back(OldCannIV);
    }

    IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);

    ++NumInserted;
    Changed = true;
    DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n');

    // Now that the official induction variable is established, reinsert
    // any old canonical-looking variables after it so that the IR remains
    // consistent. They will be deleted as part of the dead-PHI deletion at
    // the end of the pass.
    while (!OldCannIVs.empty()) {
      PHINode *OldCannIV = OldCannIVs.pop_back_val();
      OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI());
    }
  }
  else if (ExpandBECount && ReuseIVForExit && needsLFTR(L, DT)) {
    IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT, TD);
  }
  // If we have a trip count expression, rewrite the loop's exit condition
  // using it.  We can currently only handle loops with a single exit.
  Value *NewICmp = 0;
  if (ExpandBECount && IndVar) {
    // Check preconditions for proper SCEVExpander operation. SCEV does not
    // express SCEVExpander's dependencies, such as LoopSimplify. Instead any
    // pass that uses the SCEVExpander must do it. This does not work well for
    // loop passes because SCEVExpander makes assumptions about all loops, while
    // LoopPassManager only forces the current loop to be simplified.
    //
    // FIXME: SCEV expansion has no way to bail out, so the caller must
    // explicitly check any assumptions made by SCEV. Brittle.
    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount);
    if (!AR || AR->getLoop()->getLoopPreheader())
      NewICmp =
        LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, Rewriter);
  }
  // Rewrite IV-derived expressions.
  if (!DisableIVRewrite)
    RewriteIVExpressions(L, Rewriter);

  // Clear the rewriter cache, because values that are in the rewriter's cache
  // can be deleted in the loop below, causing the AssertingVH in the cache to
  // trigger.
  Rewriter.clear();

  // Now that we're done iterating through lists, clean up any instructions
  // which are now dead.
  while (!DeadInsts.empty())
    if (Instruction *Inst =
          dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
      RecursivelyDeleteTriviallyDeadInstructions(Inst);

  // The Rewriter may not be used from this point on.

  // Loop-invariant instructions in the preheader that aren't used in the
  // loop may be sunk below the loop to reduce register pressure.
  SinkUnusedInvariants(L);

  // For completeness, inform IVUsers of the IV use in the newly-created
  // loop exit test instruction.
  if (IU && NewICmp) {
    ICmpInst *NewICmpInst = dyn_cast<ICmpInst>(NewICmp);
    if (NewICmpInst)
      IU->AddUsersIfInteresting(cast<Instruction>(NewICmpInst->getOperand(0)));
  }
  // Clean up dead instructions.
  Changed |= DeleteDeadPHIs(L->getHeader());
  // Check a post-condition.
  assert(L->isLCSSAForm(*DT) &&
         "Indvars did not leave the loop in lcssa form!");

  // Verify that LFTR, and any other change have not interfered with SCEV's
  // ability to compute trip count.
#ifndef NDEBUG
  if (DisableIVRewrite && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
    SE->forgetLoop(L);
    const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
    if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
        SE->getTypeSizeInBits(NewBECount->getType()))
      NewBECount = SE->getTruncateOrNoop(NewBECount,
                                         BackedgeTakenCount->getType());
    else
      BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
                                                 NewBECount->getType());
    assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV");
  }
#endif

  return Changed;
}