Members/tobaru/cbc/CbC_llvm: lib/Analysis/IVUsers.cpp annotate

annotate lib/Analysis/IVUsers.cpp @ 3:9ad51c7bc036

1st commit. remove git dir and add all files.

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Wed, 15 May 2013 06:43:32 +0900
parents
children	54457678186b

rev	line source
3 9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	1 //===- IVUsers.cpp - Induction Variable Users -------------------- C++ --===//
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	2 //
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	3 // The LLVM Compiler Infrastructure
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	4 //
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	5 // This file is distributed under the University of Illinois Open Source
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	6 // License. See LICENSE.TXT for details.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	7 //
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	8 //===----------------------------------------------------------------------===//
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	9 //
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	10 // This file implements bookkeeping for "interesting" users of expressions
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	11 // computed from induction variables.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	12 //
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	13 //===----------------------------------------------------------------------===//
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	14
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	15 #define DEBUG_TYPE "iv-users"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	16 #include "llvm/Analysis/IVUsers.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	17 #include "llvm/ADT/STLExtras.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	18 #include "llvm/Analysis/Dominators.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	19 #include "llvm/Analysis/LoopPass.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	21 #include "llvm/Analysis/ValueTracking.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	22 #include "llvm/Assembly/Writer.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	23 #include "llvm/IR/Constants.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	24 #include "llvm/IR/DataLayout.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	25 #include "llvm/IR/DerivedTypes.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	26 #include "llvm/IR/Instructions.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	27 #include "llvm/IR/Type.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	28 #include "llvm/Support/Debug.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	29 #include "llvm/Support/raw_ostream.h"
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	30 #include <algorithm>
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	31 using namespace llvm;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	32
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	33 char IVUsers::ID = 0;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	34 INITIALIZE_PASS_BEGIN(IVUsers, "iv-users",
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	35 "Induction Variable Users", false, true)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	36 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	37 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	38 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	39 INITIALIZE_PASS_END(IVUsers, "iv-users",
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	40 "Induction Variable Users", false, true)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	41
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	42 Pass *llvm::createIVUsersPass() {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	43 return new IVUsers();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	44 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	45
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	46 /// isInteresting - Test whether the given expression is "interesting" when
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	47 /// used by the given expression, within the context of analyzing the
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	48 /// given loop.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	49 static bool isInteresting(const SCEV S, const Instruction I, const Loop *L,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	50 ScalarEvolution SE, LoopInfo LI) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	51 // An addrec is interesting if it's affine or if it has an interesting start.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	52 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	53 // Keep things simple. Don't touch loop-variant strides unless they're
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	54 // only used outside the loop and we can simplify them.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	55 if (AR->getLoop() == L)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	56 return AR->isAffine() \|\|
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	57 (!L->contains(I) &&
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	58 SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	59 // Otherwise recurse to see if the start value is interesting, and that
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	60 // the step value is not interesting, since we don't yet know how to
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	61 // do effective SCEV expansions for addrecs with interesting steps.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	62 return isInteresting(AR->getStart(), I, L, SE, LI) &&
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	63 !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	64 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	65
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	66 // An add is interesting if exactly one of its operands is interesting.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	67 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	68 bool AnyInterestingYet = false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	69 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	70 OI != OE; ++OI)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	71 if (isInteresting(*OI, I, L, SE, LI)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	72 if (AnyInterestingYet)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	73 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	74 AnyInterestingYet = true;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	75 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	76 return AnyInterestingYet;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	77 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	78
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	79 // Nothing else is interesting here.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	80 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	81 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	82
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	83 /// Return true if all loop headers that dominate this block are in simplified
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	84 /// form.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	85 static bool isSimplifiedLoopNest(BasicBlock BB, const DominatorTree DT,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	86 const LoopInfo *LI,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	87 SmallPtrSet<Loop*,16> &SimpleLoopNests) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	88 Loop *NearestLoop = 0;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	89 for (DomTreeNode *Rung = DT->getNode(BB);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	90 Rung; Rung = Rung->getIDom()) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	91 BasicBlock *DomBB = Rung->getBlock();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	92 Loop *DomLoop = LI->getLoopFor(DomBB);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	93 if (DomLoop && DomLoop->getHeader() == DomBB) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	94 // If the domtree walk reaches a loop with no preheader, return false.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	95 if (!DomLoop->isLoopSimplifyForm())
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	96 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	97 // If we have already checked this loop nest, stop checking.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	98 if (SimpleLoopNests.count(DomLoop))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	99 break;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	100 // If we have not already checked this loop nest, remember the loop
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	101 // header nearest to BB. The nearest loop may not contain BB.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	102 if (!NearestLoop)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	103 NearestLoop = DomLoop;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	104 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	105 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	106 if (NearestLoop)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	107 SimpleLoopNests.insert(NearestLoop);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	108 return true;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	109 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	110
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	111 /// AddUsersImpl - Inspect the specified instruction. If it is a
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	112 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	113 /// return true. Otherwise, return false.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	114 bool IVUsers::AddUsersImpl(Instruction *I,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	115 SmallPtrSet<Loop*,16> &SimpleLoopNests) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	116 // Add this IV user to the Processed set before returning false to ensure that
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	117 // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	118 if (!Processed.insert(I))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	119 return true; // Instruction already handled.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	120
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	121 if (!SE->isSCEVable(I->getType()))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	122 return false; // Void and FP expressions cannot be reduced.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	123
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	124 // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	125 // pass to SCEVExpander. Expressions are not safe to expand if they represent
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	126 // operations that are not safe to speculate, namely integer division.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	127 if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I, TD))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	128 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	129
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	130 // LSR is not APInt clean, do not touch integers bigger than 64-bits.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	131 // Also avoid creating IVs of non-native types. For example, we don't want a
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	132 // 64-bit IV in 32-bit code just because the loop has one 64-bit cast.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	133 uint64_t Width = SE->getTypeSizeInBits(I->getType());
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	134 if (Width > 64 \|\| (TD && !TD->isLegalInteger(Width)))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	135 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	136
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	137 // Get the symbolic expression for this instruction.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	138 const SCEV *ISE = SE->getSCEV(I);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	139
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	140 // If we've come to an uninteresting expression, stop the traversal and
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	141 // call this a user.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	142 if (!isInteresting(ISE, I, L, SE, LI))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	143 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	144
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	145 SmallPtrSet<Instruction *, 4> UniqueUsers;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	146 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	147 UI != E; ++UI) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	148 Instruction User = cast<Instruction>(UI);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	149 if (!UniqueUsers.insert(User))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	150 continue;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	151
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	152 // Do not infinitely recurse on PHI nodes.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	153 if (isa<PHINode>(User) && Processed.count(User))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	154 continue;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	155
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	156 // Only consider IVUsers that are dominated by simplified loop
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	157 // headers. Otherwise, SCEVExpander will crash.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	158 BasicBlock *UseBB = User->getParent();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	159 // A phi's use is live out of its predecessor block.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	160 if (PHINode *PHI = dyn_cast<PHINode>(User)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	161 unsigned OperandNo = UI.getOperandNo();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	162 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	163 UseBB = PHI->getIncomingBlock(ValNo);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	164 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	165 if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	166 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	167
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	168 // Descend recursively, but not into PHI nodes outside the current loop.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	169 // It's important to see the entire expression outside the loop to get
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	170 // choices that depend on addressing mode use right, although we won't
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	171 // consider references outside the loop in all cases.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	172 // If User is already in Processed, we don't want to recurse into it again,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	173 // but do want to record a second reference in the same instruction.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	174 bool AddUserToIVUsers = false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	175 if (LI->getLoopFor(User->getParent()) != L) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	176 if (isa<PHINode>(User) \|\| Processed.count(User) \|\|
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	177 !AddUsersImpl(User, SimpleLoopNests)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	178 DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	179 << " OF SCEV: " << *ISE << '\n');
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	180 AddUserToIVUsers = true;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	181 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	182 } else if (Processed.count(User) \|\| !AddUsersImpl(User, SimpleLoopNests)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	183 DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	184 << " OF SCEV: " << *ISE << '\n');
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	185 AddUserToIVUsers = true;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	186 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	187
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	188 if (AddUserToIVUsers) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	189 // Okay, we found a user that we cannot reduce.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	190 IVUses.push_back(new IVStrideUse(this, User, I));
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	191 IVStrideUse &NewUse = IVUses.back();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	192 // Autodetect the post-inc loop set, populating NewUse.PostIncLoops.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	193 // The regular return value here is discarded; instead of recording
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	194 // it, we just recompute it when we need it.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	195 ISE = TransformForPostIncUse(NormalizeAutodetect,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	196 ISE, User, I,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	197 NewUse.PostIncLoops,
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	198 SE, DT);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	199 DEBUG(if (SE->getSCEV(I) != ISE)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	200 dbgs() << " NORMALIZED TO: " << *ISE << '\n');
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	201 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	202 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	203 return true;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	204 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	205
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	206 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	207 // SCEVExpander can only handle users that are dominated by simplified loop
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	208 // entries. Keep track of all loops that are only dominated by other simple
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	209 // loops so we don't traverse the domtree for each user.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	210 SmallPtrSet<Loop*,16> SimpleLoopNests;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	211
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	212 return AddUsersImpl(I, SimpleLoopNests);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	213 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	214
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	215 IVStrideUse &IVUsers::AddUser(Instruction User, Value Operand) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	216 IVUses.push_back(new IVStrideUse(this, User, Operand));
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	217 return IVUses.back();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	218 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	219
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	220 IVUsers::IVUsers()
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	221 : LoopPass(ID) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	222 initializeIVUsersPass(*PassRegistry::getPassRegistry());
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	223 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	224
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	225 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	226 AU.addRequired<LoopInfo>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	227 AU.addRequired<DominatorTree>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	228 AU.addRequired<ScalarEvolution>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	229 AU.setPreservesAll();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	230 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	231
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	232 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	233
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	234 L = l;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	235 LI = &getAnalysis<LoopInfo>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	236 DT = &getAnalysis<DominatorTree>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	237 SE = &getAnalysis<ScalarEvolution>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	238 TD = getAnalysisIfAvailable<DataLayout>();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	239
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	240 // Find all uses of induction variables in this loop, and categorize
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	241 // them by stride. Start by finding all of the PHI nodes in the header for
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	242 // this loop. If they are induction variables, inspect their uses.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	243 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	244 (void)AddUsersIfInteresting(I);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	245
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	246 return false;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	247 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	248
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	249 void IVUsers::print(raw_ostream &OS, const Module *M) const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	250 OS << "IV Users for loop ";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	251 WriteAsOperand(OS, L->getHeader(), false);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	252 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	253 OS << " with backedge-taken count "
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	254 << *SE->getBackedgeTakenCount(L);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	255 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	256 OS << ":\n";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	257
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	258 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	259 E = IVUses.end(); UI != E; ++UI) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	260 OS << " ";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	261 WriteAsOperand(OS, UI->getOperandValToReplace(), false);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	262 OS << " = " << getReplacementExpr(UI);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	263 for (PostIncLoopSet::const_iterator
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	264 I = UI->PostIncLoops.begin(),
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	265 E = UI->PostIncLoops.end(); I != E; ++I) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	266 OS << " (post-inc with loop ";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	267 WriteAsOperand(OS, (*I)->getHeader(), false);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	268 OS << ")";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	269 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	270 OS << " in ";
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	271 UI->getUser()->print(OS);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	272 OS << '\n';
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	273 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	274 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	275
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	276 #if !defined(NDEBUG) \|\| defined(LLVM_ENABLE_DUMP)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	277 void IVUsers::dump() const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	278 print(dbgs());
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	279 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	280 #endif
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	281
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	282 void IVUsers::releaseMemory() {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	283 Processed.clear();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	284 IVUses.clear();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	285 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	286
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	287 /// getReplacementExpr - Return a SCEV expression which computes the
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	288 /// value of the OperandValToReplace.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	289 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	290 return SE->getSCEV(IU.getOperandValToReplace());
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	291 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	292
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	293 /// getExpr - Return the expression for the use.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	294 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	295 return
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	296 TransformForPostIncUse(Normalize, getReplacementExpr(IU),
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	297 IU.getUser(), IU.getOperandValToReplace(),
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	298 const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	299 SE, DT);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	300 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	301
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	302 static const SCEVAddRecExpr findAddRecForLoop(const SCEV S, const Loop *L) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	303 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	304 if (AR->getLoop() == L)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	305 return AR;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	306 return findAddRecForLoop(AR->getStart(), L);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	307 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	308
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	309 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	310 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	311 I != E; ++I)
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	312 if (const SCEVAddRecExpr AR = findAddRecForLoop(I, L))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	313 return AR;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	314 return 0;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	315 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	316
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	317 return 0;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	318 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	319
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	320 const SCEV IVUsers::getStride(const IVStrideUse &IU, const Loop L) const {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	321 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	322 return AR->getStepRecurrence(*SE);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	323 return 0;
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	324 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	325
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	326 void IVStrideUse::transformToPostInc(const Loop *L) {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	327 PostIncLoops.insert(L);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	328 }
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	329
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	330 void IVStrideUse::deleted() {
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	331 // Remove this user from the list.
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	332 Parent->Processed.erase(this->getUser());
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	333 Parent->IVUses.erase(this);
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	334 // this now dangles!
9ad51c7bc036 1st commit. remove git dir and add all files. Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	335 }

Mercurial > hg > Members > tobaru > cbc > CbC_llvm

annotate lib/Analysis/IVUsers.cpp @ 3:9ad51c7bc036