//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===////// The LLVM Compiler Infrastructure//// This file is distributed under the University of Illinois Open Source// License. See LICENSE.TXT for details.////===----------------------------------------------------------------------===////// This transformation analyzes and transforms the induction variables (and// computations derived from them) into simpler forms suitable for subsequent// analysis and transformation.//// This transformation makes the following changes to each loop with an// identifiable induction variable:// 1. All loops are transformed to have a SINGLE canonical induction variable// which starts at zero and steps by one.// 2. The canonical induction variable is guaranteed to be the first PHI node// in the loop header block.// 3. The canonical induction variable is guaranteed to be in a wide enough// type so that IV expressions need not be (directly) zero-extended or// sign-extended.// 4. Any pointer arithmetic recurrences are raised to use array subscripts.//// If the trip count of a loop is computable, this pass also makes the following// changes:// 1. The exit condition for the loop is canonicalized to compare the// induction value against the exit value. This turns loops like:// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'// 2. Any use outside of the loop of an expression derived from the indvar// is changed to compute the derived value outside of the loop, eliminating// the dependence on the exit value of the induction variable. If the only// purpose of the loop is to compute the exit value of some derived// expression, this transformation will make the loop dead.//// This transformation should be followed by strength reduction after all of the// desired loop transformations have been performed.////===----------------------------------------------------------------------===//#define DEBUG_TYPE "indvars"#include"llvm/Transforms/Scalar.h"#include"llvm/BasicBlock.h"#include"llvm/Constants.h"#include"llvm/Instructions.h"#include"llvm/IntrinsicInst.h"#include"llvm/LLVMContext.h"#include"llvm/Type.h"#include"llvm/Analysis/Dominators.h"#include"llvm/Analysis/IVUsers.h"#include"llvm/Analysis/ScalarEvol
