1 //===- InductionVars.cpp - Induction Variable Cannonicalization code --------=//
3 // This file implements induction variable cannonicalization of loops.
5 // Specifically, after this executes, the following is true:
6 // - There is a single induction variable for each loop (at least loops that
7 // used to contain at least one induction variable)
8 // - This induction variable starts at 0 and steps by 1 per iteration
9 // - This induction variable is represented by the first PHI node in the
10 // Header block, allowing it to be found easily.
11 // - All other preexisting induction variables are adjusted to operate in
12 // terms of this primary induction variable
14 // This code assumes the following is true to perform its full job:
15 // - The CFG has been simplified to not have multiple entrances into an
16 // interval header. Interval headers should only have two predecessors,
17 // one from inside of the loop and one from outside of the loop.
19 //===----------------------------------------------------------------------===//
21 #include "llvm/ConstPoolVals.h"
22 #include "llvm/Analysis/IntervalPartition.h"
23 #include "llvm/Opt/AllOpts.h"
24 #include "llvm/Assembly/Writer.h"
25 #include "llvm/Tools/STLExtras.h"
26 #include "llvm/iOther.h"
29 // isLoopInvariant - Return true if the specified value/basic block source is
30 // an interval invariant computation.
32 static bool isLoopInvariant(cfg::Interval *Int, Value *V) {
33 assert(V->getValueType() == Value::ConstantVal ||
34 V->getValueType() == Value::InstructionVal ||
35 V->getValueType() == Value::MethodArgumentVal);
37 if (V->getValueType() != Value::InstructionVal)
38 return true; // Constants and arguments are always loop invariant
40 BasicBlock *ValueBlock = ((Instruction*)V)->getParent();
41 assert(ValueBlock && "Instruction not embedded in basic block!");
43 // For now, only consider values from outside of the interval, regardless of
44 // whether the expression could be lifted out of the loop by some LICM.
46 // TODO: invoke LICM library if we find out it would be useful.
48 return !Int->contains(ValueBlock);
52 // isLinearInductionVariableH - Return isLIV if the expression V is a linear
53 // expression defined in terms of loop invariant computations, and a single
54 // instance of the PHI node PN. Return isLIC if the expression V is a loop
55 // invariant computation. Return isNLIV if the expression is a negated linear
56 // induction variable. Return isOther if it is neither.
58 // Currently allowed operators are: ADD, SUB, NEG
59 // TODO: This should allow casts!
61 enum LIVType { isLIV, isLIC, isNLIV, isOther };
63 // neg - Negate the sign of a LIV expression.
64 inline LIVType neg(LIVType T) {
65 assert(T == isLIV || T == isNLIV && "Negate Only works on LIV expressions");
66 return T == isLIV ? isNLIV : isLIV;
69 static LIVType isLinearInductionVariableH(cfg::Interval *Int, Value *V,
71 if (V == PN) { return isLIV; } // PHI node references are (0+PHI)
72 if (isLoopInvariant(Int, V)) return isLIC;
74 assert(V->getValueType() == Value::InstructionVal &&
75 "loop noninvariant computations must be instructions!");
77 Instruction *I = (Instruction*)V;
78 switch (I->getInstType()) { // Handle each instruction seperately
79 case Instruction::Neg: {
80 Value *SubV = ((UnaryOperator*)I)->getOperand(0);
81 LIVType SubLIVType = isLinearInductionVariableH(Int, SubV, PN);
83 case isLIC: // Loop invariant & other computations remain the same
84 case isOther: return SubLIVType;
85 case isLIV: // Return the opposite signed LIV type
86 case isNLIV: return neg(isLIV);
89 case Instruction::Add:
90 case Instruction::Sub: {
91 Value *SubV1 = ((BinaryOperator*)I)->getOperand(0);
92 Value *SubV2 = ((BinaryOperator*)I)->getOperand(1);
93 LIVType SubLIVType1 = isLinearInductionVariableH(Int, SubV1, PN);
94 if (SubLIVType1 == isOther) return isOther; // Early bailout
95 LIVType SubLIVType2 = isLinearInductionVariableH(Int, SubV2, PN);
97 switch (SubLIVType2) {
98 case isOther: return isOther; // Unknown subexpression type
99 case isLIC: return SubLIVType1; // Constant offset, return type #1
102 // So now we know that we have a linear induction variable on the RHS of
103 // the ADD or SUB instruction. SubLIVType1 cannot be isOther, so it is
104 // either a Loop Invariant computation, or a LIV type.
105 if (SubLIVType1 == isLIC) {
106 // Loop invariant computation, we know this is a LIV then.
107 return (I->getInstType() == Instruction::Add) ?
108 SubLIVType2 : neg(SubLIVType2);
111 // If the LHS is also a LIV Expression, we cannot add two LIVs together
112 if (I->getInstType() == Instruction::Add) return isOther;
114 // We can only subtract two LIVs if they are the same type, which yields
115 // a LIC, because the LIVs cancel each other out.
116 return (SubLIVType1 == SubLIVType2) ? isLIC : isOther;
121 default: // Any other instruction is not a LINEAR induction var
126 // isLinearInductionVariable - Return true if the specified expression is a
127 // "linear induction variable", which is an expression involving a single
128 // instance of the PHI node and a loop invariant value that is added or
129 // subtracted to the PHI node. This is calculated by walking the SSA graph
131 static inline bool isLinearInductionVariable(cfg::Interval *Int, Value *V,
133 return isLinearInductionVariableH(Int, V, PN) == isLIV;
137 // isSimpleInductionVar - Return true iff the cannonical induction variable PN
138 // has an initializer of the constant value 0, and has a step size of constant
140 static inline bool isSimpleInductionVar(PHINode *PN) {
141 assert(PN->getNumIncomingValues() == 2 && "Must have cannonical PHI node!");
142 Value *Initializer = PN->getIncomingValue(0);
143 if (Initializer->getValueType() != Value::ConstantVal)
146 if (Initializer->getType()->isSigned()) { // Signed constant value...
147 if (((ConstPoolSInt*)Initializer)->getValue() != 0) return false;
148 } else if (Initializer->getType()->isUnsigned()) { // Unsigned constant value
149 if (((ConstPoolUInt*)Initializer)->getValue() != 0) return false;
151 return false; // Not signed or unsigned? Must be FP type or something
154 // How do I check for 0 for any integral value? Use
155 // ConstPoolVal::getNullConstant?
157 Value *StepExpr = PN->getIncomingValue(1);
158 assert(StepExpr->getValueType() == Value::InstructionVal && "No ADD node?");
159 assert(((Instruction*)StepExpr)->getInstType() == Instruction::Add &&
160 "No ADD node? Not a cannonical PHI!");
161 BinaryOperator *I = (BinaryOperator*)StepExpr;
162 assert(I->getOperand(0)->getValueType() == Value::InstructionVal &&
163 ((Instruction*)I->getOperand(0))->getInstType() == Instruction::PHINode &&
164 "PHI node should be first operand of ADD instruction!");
166 // Get the right hand side of the ADD node. See if it is a constant 1.
167 Value *StepSize = I->getOperand(1);
168 if (StepSize->getValueType() != Value::ConstantVal) return false;
170 if (StepSize->getType()->isSigned()) { // Signed constant value...
171 if (((ConstPoolSInt*)StepSize)->getValue() != 1) return false;
172 } else if (StepSize->getType()->isUnsigned()) { // Unsigned constant value
173 if (((ConstPoolUInt*)StepSize)->getValue() != 1) return false;
175 return false; // Not signed or unsigned? Must be FP type or something
178 // At this point, we know the initializer is a constant value 0 and the step
179 // size is a constant value 1. This is our simple induction variable!
183 // ProcessInterval - This function is invoked once for each interval in the
184 // IntervalPartition of the program. It looks for auxilliary induction
185 // variables in loops. If it finds one, it:
186 // * Cannonicalizes the induction variable. This consists of:
187 // A. Making the first element of the PHI node be the loop invariant
188 // computation, and the second element be the linear induction portion.
189 // B. Changing the first element of the linear induction portion of the PHI
190 // node to be of the form ADD(PHI, <loop invariant expr>).
191 // * Add the induction variable PHI to a list of induction variables found.
193 // After this, a list of cannonical induction variables is known. This list
194 // is searched to see if there is an induction variable that counts from
195 // constant 0 with a step size of constant 1. If there is not one, one is
196 // injected into the loop. Thus a "simple" induction variable is always known
198 // One a simple induction variable is known, all other induction variables are
199 // modified to refer to the "simple" induction variable.
201 static bool ProcessInterval(cfg::Interval *Int) {
202 if (!Int->isLoop()) return false; // Not a loop? Ignore it!
204 vector<PHINode *> InductionVars;
206 BasicBlock *Header = Int->getHeaderNode();
207 // Loop over all of the PHI nodes in the interval header...
208 for (BasicBlock::InstListType::iterator I = Header->getInstList().begin(),
209 E = Header->getInstList().end();
210 I != E && (*I)->getInstType() == Instruction::PHINode; ++I) {
212 PHINode *PN = (PHINode*)*I;
213 if (PN->getNumIncomingValues() != 2) { // These should be eliminated by now.
214 cerr << "Found interval header with more than 2 predecessors! Ignoring\n";
215 return false; // Todo, make an assertion.
218 // For this to be an induction variable, one of the arguments must be a
219 // loop invariant expression, and the other must be an expression involving
220 // the PHI node, along with possible additions and subtractions of loop
223 BasicBlock *BB1 = PN->getIncomingBlock(0);
224 Value *V1 = PN->getIncomingValue(0);
225 BasicBlock *BB2 = PN->getIncomingBlock(1);
226 Value *V2 = PN->getIncomingValue(1);
228 // Figure out which computation is loop invariant...
229 if (!isLoopInvariant(Int, V1)) {
230 // V1 is *not* loop invariant. Check to see if V2 is:
231 if (isLoopInvariant(Int, V2)) {
232 // They *are* loop invariant. Exchange BB1/BB2 and V1/V2 so that
233 // V1 is always the loop invariant computation.
234 swap(V1, V2); swap(BB1, BB2);
236 // Neither value is loop invariant. Must not be an induction variable.
237 // This case can happen if there is an unreachable loop in the CFG that
238 // has two tail loops in it that was not split by the cleanup phase
244 // At this point, we know that BB1/V1 are loop invariant. We don't know
245 // anything about BB2/V2. Check now to see if V2 is a linear induction
248 cerr << "Found loop invariant computation: " << V1;
250 if (!isLinearInductionVariable(Int, V2, PN))
251 continue; // No, it is not a linear ind var, ignore the PHI node.
252 cerr << "Found linear induction variable: " << V2;
254 // TODO: Cannonicalize V2
256 // Add this PHI node to the list of induction variables found...
257 InductionVars.push_back(PN);
260 // No induction variables found?
261 if (InductionVars.empty()) return false;
263 // Search to see if there is already a "simple" induction variable.
264 vector<PHINode*>::iterator It =
265 find_if(InductionVars.begin(), InductionVars.end(), isSimpleInductionVar);
267 PHINode *PrimaryIndVar;
269 // A simple induction variable was not found, inject one now...
270 if (It == InductionVars.end()) {
271 cerr << "WARNING, Induction variable injection not implemented yet!\n";
272 // TODO: Inject induction variable
273 PrimaryIndVar = 0; // Point it at the new indvar
275 // Move the PHI node for this induction variable to the start of the PHI
276 // list in HeaderNode... we do not need to do this for the inserted case
277 // because the inserted node will always be placed at the beginning of
281 BasicBlock::InstListType::iterator i =
282 find(Header->getInstList().begin(), Header->getInstList().end(),
284 assert(i != Header->getInstList().end() &&
285 "How could Primary IndVar not be in the header!?!!?");
287 if (i != Header->getInstList().begin())
288 iter_swap(i, Header->getInstList().begin());
291 // Now we know that there is a simple induction variable PrimaryIndVar.
292 // Simplify all of the other induction variables to use this induction
293 // variable as their counter, and destroy the PHI nodes that correspond to
299 cerr << "Found Interval Header with indvars (primary indvar should be first "
300 << "phi): \n" << Header << "\nPrimaryIndVar = " << PrimaryIndVar;
302 return false; // TODO: true;
306 // ProcessIntervalPartition - This function loops over the interval partition
307 // processing each interval with ProcessInterval
309 static bool ProcessIntervalPartition(cfg::IntervalPartition &IP) {
310 // This currently just prints out information about the interval structure
312 static unsigned N = 0;
313 cerr << "\n***********Interval Partition #" << (++N) << "************\n\n";
314 copy(IP.begin(), IP.end(), ostream_iterator<cfg::Interval*>(cerr, "\n"));
316 cerr << "\n*********** PERFORMING WORK ************\n\n";
318 // Loop over all of the intervals in the partition and look for induction
319 // variables in intervals that represent loops.
321 return reduce_apply(IP.begin(), IP.end(), bitwise_or<bool>(), false,
322 ptr_fun(ProcessInterval));
325 #include "llvm/Analysis/LoopDepth.h"
327 // DoInductionVariableCannonicalize - Simplify induction variables in loops.
328 // This function loops over an interval partition of a program, reducing it
329 // until the graph is gone.
331 bool DoInductionVariableCannonicalize(Method *M) {
332 if (1) { // Print basic blocks with their depth
333 LoopDepthCalculator LDC(M);
334 for (Method::iterator I = M->getBasicBlocks().begin();
335 I != M->getBasicBlocks().end(); ++I) {
336 cerr << "Basic Block Depth: " << LDC.getLoopDepth(*I) << *I;
342 cfg::IntervalPartition *IP = new cfg::IntervalPartition(M);
343 bool Changed = false;
345 while (!IP->isDegeneratePartition()) {
346 Changed |= ProcessIntervalPartition(*IP);
348 // Calculate the reduced version of this graph until we get to an
349 // irreducible graph or a degenerate graph...
351 cfg::IntervalPartition *NewIP = new cfg::IntervalPartition(*IP, false);
352 if (NewIP->size() == IP->size()) {
353 cerr << "IRREDUCIBLE GRAPH FOUND!!!\n";