From 96878458002972a4b57c0d7deee379ed7717a545 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 2 Apr 2004 20:56:24 +0000 Subject: [PATCH] Remove obsolete files git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12633 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/InductionVariable.h | 68 ----- lib/Analysis/InductionVariable.cpp | 324 ---------------------- 2 files changed, 392 deletions(-) delete mode 100644 include/llvm/Analysis/InductionVariable.h delete mode 100644 lib/Analysis/InductionVariable.cpp diff --git a/include/llvm/Analysis/InductionVariable.h b/include/llvm/Analysis/InductionVariable.h deleted file mode 100644 index cc4b4b1a446..00000000000 --- a/include/llvm/Analysis/InductionVariable.h +++ /dev/null @@ -1,68 +0,0 @@ -//===- llvm/Analysis/InductionVariable.h - Induction variables --*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This interface is used to identify and classify induction variables that -// exist in the program. Induction variables must contain a PHI node that -// exists in a loop header. Because of this, they are identified and managed by -// this PHI node. -// -// Induction variables are classified into a type. Knowing that an induction -// variable is of a specific type can constrain the values of the start and -// step. For example, a SimpleLinear induction variable must have a start and -// step values that are constants. -// -// Induction variables can be created with or without loop information. If no -// loop information is available, induction variables cannot be recognized to be -// more than SimpleLinear variables. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_INDUCTIONVARIABLE_H -#define LLVM_ANALYSIS_INDUCTIONVARIABLE_H - -#include - -namespace llvm { - -class Value; -class PHINode; -class Instruction; -class LoopInfo; class Loop; - -class InductionVariable { -public: - enum iType { // Identify the type of this induction variable - Canonical, // Starts at 0, counts by 1 - SimpleLinear, // Simple linear: Constant start, constant step - Linear, // General linear: loop invariant start, and step - Unknown, // Unknown type. Start & Step are null - } InductionType; - - Value *Start, *Step, *End; // Start, step, and end expressions for this indvar - PHINode *Phi; // The PHI node that corresponds to this indvar -public: - - // Create an induction variable for the specified value. If it is a PHI, and - // if it's recognizable, classify it and fill in instance variables. - // - InductionVariable(PHINode *PN, LoopInfo *LoopInfo = 0); - - // Classify Induction - static enum iType Classify(const Value *Start, const Value *Step, - const Loop *L = 0); - - // Get number of times this loop will execute. Returns NULL if unpredictable. - Value* getExecutionCount(LoopInfo *LoopInfo); - - void print(std::ostream &OS) const; -}; - -} // End llvm namespace - -#endif diff --git a/lib/Analysis/InductionVariable.cpp b/lib/Analysis/InductionVariable.cpp deleted file mode 100644 index 8f622973f96..00000000000 --- a/lib/Analysis/InductionVariable.cpp +++ /dev/null @@ -1,324 +0,0 @@ -//===- InductionVariable.cpp - Induction variable classification ----------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements identification and classification of induction -// variables. Induction variables must contain a PHI node that exists in a -// loop header. Because of this, they are identified an managed by this PHI -// node. -// -// Induction variables are classified into a type. Knowing that an induction -// variable is of a specific type can constrain the values of the start and -// step. For example, a SimpleLinear induction variable must have a start and -// step values that are constants. -// -// Induction variables can be created with or without loop information. If no -// loop information is available, induction variables cannot be recognized to be -// more than SimpleLinear variables. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/InductionVariable.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/Expressions.h" -#include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/Constants.h" -#include "llvm/Support/CFG.h" -#include "llvm/Assembly/Writer.h" -#include "Support/Debug.h" -using namespace llvm; - -static bool isLoopInvariant(const Value *V, const Loop *L) { - if (const Instruction *I = dyn_cast(V)) - return !L->contains(I->getParent()); - // non-instructions all dominate instructions/blocks - return true; -} - -enum InductionVariable::iType -InductionVariable::Classify(const Value *Start, const Value *Step, - const Loop *L) { - // Check for canonical and simple linear expressions now... - if (const ConstantInt *CStart = dyn_cast(Start)) - if (const ConstantInt *CStep = dyn_cast(Step)) { - if (CStart->isNullValue() && CStep->equalsInt(1)) - return Canonical; - else - return SimpleLinear; - } - - // Without loop information, we cannot do any better, so bail now... - if (L == 0) return Unknown; - - if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L)) - return Linear; - return Unknown; -} - -// Create an induction variable for the specified value. If it is a PHI, and -// if it's recognizable, classify it and fill in instance variables. -// -InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) { - InductionType = Unknown; // Assume the worst - Phi = P; - - // If the PHI node has more than two predecessors, we don't know how to - // handle it. - // - if (Phi->getNumIncomingValues() != 2) return; - - // FIXME: Handle FP induction variables. - if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy) - return; - - // If we have loop information, make sure that this PHI node is in the header - // of a loop... - // - const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0; - if (L && L->getHeader() != Phi->getParent()) - return; - - Value *V1 = Phi->getIncomingValue(0); - Value *V2 = Phi->getIncomingValue(1); - - if (L == 0) { // No loop information? Base everything on expression analysis - ExprType E1 = ClassifyExpr(V1); - ExprType E2 = ClassifyExpr(V2); - - if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression - std::swap(E1, E2); - - // E1 must be a constant incoming value, and E2 must be a linear expression - // with respect to the PHI node. - // - if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear || - E2.Var != Phi) - return; - - // Okay, we have found an induction variable. Save the start and step values - const Type *ETy = Phi->getType(); - if (isa(ETy)) ETy = Type::ULongTy; - - Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0)); - Step = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0)); - } else { - // Okay, at this point, we know that we have loop information... - - // Make sure that V1 is the incoming value, and V2 is from the backedge of - // the loop. - if (L->contains(Phi->getIncomingBlock(0))) // Wrong order. Swap now. - std::swap(V1, V2); - - Start = V1; // We know that Start has to be loop invariant... - Step = 0; - - if (V2 == Phi) { // referencing the PHI directly? Must have zero step - Step = Constant::getNullValue(Phi->getType()); - } else if (BinaryOperator *I = dyn_cast(V2)) { - if (I->getOpcode() == Instruction::Add) { - if (I->getOperand(0) == Phi) - Step = I->getOperand(1); - else if (I->getOperand(1) == Phi) - Step = I->getOperand(0); - } else if (I->getOpcode() == Instruction::Sub && - I->getOperand(0) == Phi) { - // If the incoming value is a constant, just form a constant negative - // step. Otherwise, negate the step outside of the loop and use it. - Value *V = I->getOperand(1); - Constant *Zero = Constant::getNullValue(V->getType()); - if (Constant *CV = dyn_cast(V)) - Step = ConstantExpr::get(Instruction::Sub, Zero, CV); - else if (Instruction *I = dyn_cast(V)) { - BasicBlock::iterator InsertPt = I; - for (++InsertPt; isa(InsertPt); ++InsertPt) - /*empty*/; - Step = BinaryOperator::create(Instruction::Sub, Zero, V, - V->getName()+".neg", InsertPt); - - } else { - // Must be loop invariant - Step = BinaryOperator::create(Instruction::Sub, Zero, V, - V->getName()+".neg", - Phi->getParent()->getParent()->begin()->begin()); - } - } - } else if (GetElementPtrInst *GEP = dyn_cast(V2)) { - if (GEP->getNumOperands() == 2 && - GEP->getOperand(0) == Phi) - Step = GEP->getOperand(1); - } - - if (Step == 0) { // Unrecognized step value... - ExprType StepE = ClassifyExpr(V2); - if (StepE.ExprTy != ExprType::Linear || - StepE.Var != Phi) return; - - const Type *ETy = Phi->getType(); - if (isa(ETy)) ETy = Type::ULongTy; - Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0)); - } else { // We were able to get a step value, simplify with expr analysis - ExprType StepE = ClassifyExpr(Step); - if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) { - // No offset from variable? Grab the variable - Step = StepE.Var; - } else if (StepE.ExprTy == ExprType::Constant) { - if (StepE.Offset) - Step = (Value*)StepE.Offset; - else - Step = Constant::getNullValue(Step->getType()); - const Type *ETy = Phi->getType(); - if (isa(ETy)) ETy = Type::ULongTy; - Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0)); - } - } - } - - // Classify the induction variable type now... - InductionType = InductionVariable::Classify(Start, Step, L); -} - - -Value *InductionVariable::getExecutionCount(LoopInfo *LoopInfo) { - if (InductionType != Canonical) return 0; - - DEBUG(std::cerr << "entering getExecutionCount\n"); - - // Don't recompute if already available - if (End) { - DEBUG(std::cerr << "returning cached End value.\n"); - return End; - } - - const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0; - if (!L) { - DEBUG(std::cerr << "null loop. oops\n"); - return 0; - } - - // >1 backedge => cannot predict number of iterations - if (Phi->getNumIncomingValues() != 2) { - DEBUG(std::cerr << ">2 incoming values. oops\n"); - return 0; - } - - // Find final node: predecessor of the loop header that's also an exit - BasicBlock *terminator = 0; - for (pred_iterator PI = pred_begin(L->getHeader()), - PE = pred_end(L->getHeader()); PI != PE; ++PI) - if (L->isLoopExit(*PI)) { - terminator = *PI; - break; - } - - // Break in the loop => cannot predict number of iterations - // break: any block which is an exit node whose successor is not in loop, - // and this block is not marked as the terminator - // - const std::vector &blocks = L->getBlocks(); - for (std::vector::const_iterator I = blocks.begin(), - e = blocks.end(); I != e; ++I) - if (L->isLoopExit(*I) && *I != terminator) - for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) - if (!L->contains(*SI)) { - DEBUG(std::cerr << "break found in loop"); - return 0; - } - - BranchInst *B = dyn_cast(terminator->getTerminator()); - if (!B) { - DEBUG(std::cerr << "Terminator is not a cond branch!"); - return 0; - } - SetCondInst *SCI = dyn_cast(B->getCondition()); - if (!SCI) { - DEBUG(std::cerr << "Not a cond branch on setcc!\n"); - return 0; - } - - DEBUG(std::cerr << "sci:" << *SCI); - Value *condVal0 = SCI->getOperand(0); - Value *condVal1 = SCI->getOperand(1); - - // The induction variable is the one coming from the backedge - Value *indVar = Phi->getIncomingValue(L->contains(Phi->getIncomingBlock(1))); - - - // Check to see if indVar is one of the parameters in SCI and if the other is - // loop-invariant, it is the UB - if (indVar == condVal0) { - if (isLoopInvariant(condVal1, L)) - End = condVal1; - else { - DEBUG(std::cerr << "not loop invariant 1\n"); - return 0; - } - } else if (indVar == condVal1) { - if (isLoopInvariant(condVal0, L)) - End = condVal0; - else { - DEBUG(std::cerr << "not loop invariant 0\n"); - return 0; - } - } else { - DEBUG(std::cerr << "Loop condition doesn't directly uses indvar\n"); - return 0; - } - - switch (SCI->getOpcode()) { - case Instruction::SetLT: - case Instruction::SetNE: return End; // already done - case Instruction::SetLE: - // if compared to a constant int N, then predict N+1 iterations - if (ConstantSInt *ubSigned = dyn_cast(End)) { - DEBUG(std::cerr << "signed int constant\n"); - return ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1); - } else if (ConstantUInt *ubUnsigned = dyn_cast(End)) { - DEBUG(std::cerr << "unsigned int constant\n"); - return ConstantUInt::get(ubUnsigned->getType(), - ubUnsigned->getValue()+1); - } else { - DEBUG(std::cerr << "symbolic bound\n"); - // new expression N+1, insert right before the SCI. FIXME: If End is loop - // invariant, then so is this expression. We should insert it in the loop - // preheader if it exists. - return BinaryOperator::create(Instruction::Add, End, - ConstantInt::get(End->getType(), 1), - "tripcount", SCI); - } - - default: - return 0; // cannot predict - } -} - - -void InductionVariable::print(std::ostream &o) const { - switch (InductionType) { - case InductionVariable::Canonical: o << "Canonical "; break; - case InductionVariable::SimpleLinear: o << "SimpleLinear "; break; - case InductionVariable::Linear: o << "Linear "; break; - case InductionVariable::Unknown: o << "Unrecognized "; break; - } - o << "Induction Variable: "; - if (Phi) { - WriteAsOperand(o, Phi); - o << ":\n" << Phi; - } else { - o << "\n"; - } - if (InductionType == InductionVariable::Unknown) return; - - o << " Start = "; WriteAsOperand(o, Start); - o << " Step = " ; WriteAsOperand(o, Step); - if (End) { - o << " End = " ; WriteAsOperand(o, End); - } - o << "\n"; -} -- 2.34.1