1
//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This transformation analyzes and transforms the induction variables (and
11
// computations derived from them) into simpler forms suitable for subsequent
12
// analysis and transformation.
14
// This transformation makes the following changes to each loop with an
15
// identifiable induction variable:
16
// 1. All loops are transformed to have a SINGLE canonical induction variable
17
// which starts at zero and steps by one.
18
// 2. The canonical induction variable is guaranteed to be the first PHI node
19
// in the loop header block.
20
// 3. The canonical induction variable is guaranteed to be in a wide enough
21
// type so that IV expressions need not be (directly) zero-extended or
23
// 4. Any pointer arithmetic recurrences are raised to use array subscripts.
25
// If the trip count of a loop is computable, this pass also makes the following
27
// 1. The exit condition for the loop is canonicalized to compare the
28
// induction value against the exit value. This turns loops like:
29
// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
30
// 2. Any use outside of the loop of an expression derived from the indvar
31
// is changed to compute the derived value outside of the loop, eliminating
32
// the dependence on the exit value of the induction variable. If the only
33
// purpose of the loop is to compute the exit value of some derived
34
// expression, this transformation will make the loop dead.
36
// This transformation should be followed by strength reduction after all of the
37
// desired loop transformations have been performed.
39
//===----------------------------------------------------------------------===//
41
#define DEBUG_TYPE "indvars"
42
#include "llvm/Transforms/Scalar.h"
43
#include "llvm/BasicBlock.h"
44
#include "llvm/Constants.h"
45
#include "llvm/Instructions.h"
46
#include "llvm/LLVMContext.h"
47
#include "llvm/Type.h"
48
#include "llvm/Analysis/Dominators.h"
49
#include "llvm/Analysis/IVUsers.h"
50
#include "llvm/Analysis/ScalarEvolutionExpander.h"
51
#include "llvm/Analysis/LoopInfo.h"
52
#include "llvm/Analysis/LoopPass.h"
53
#include "llvm/Support/CFG.h"
54
#include "llvm/Support/CommandLine.h"
55
#include "llvm/Support/Debug.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include "llvm/Transforms/Utils/Local.h"
58
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
59
#include "llvm/ADT/SmallVector.h"
60
#include "llvm/ADT/Statistic.h"
61
#include "llvm/ADT/STLExtras.h"
64
STATISTIC(NumRemoved , "Number of aux indvars removed");
65
STATISTIC(NumInserted, "Number of canonical indvars added");
66
STATISTIC(NumReplaced, "Number of exit values replaced");
67
STATISTIC(NumLFTR , "Number of loop exit tests replaced");
70
class IndVarSimplify : public LoopPass {
78
static char ID; // Pass identification, replacement for typeid
79
IndVarSimplify() : LoopPass(&ID) {}
81
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
83
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
84
AU.addRequired<DominatorTree>();
85
AU.addRequired<LoopInfo>();
86
AU.addRequired<ScalarEvolution>();
87
AU.addRequiredID(LoopSimplifyID);
88
AU.addRequiredID(LCSSAID);
89
AU.addRequired<IVUsers>();
90
AU.addPreserved<ScalarEvolution>();
91
AU.addPreservedID(LoopSimplifyID);
92
AU.addPreservedID(LCSSAID);
93
AU.addPreserved<IVUsers>();
99
void RewriteNonIntegerIVs(Loop *L);
101
ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
103
BasicBlock *ExitingBlock,
105
SCEVExpander &Rewriter);
106
void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
108
void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter);
110
void SinkUnusedInvariants(Loop *L);
112
void HandleFloatingPointIV(Loop *L, PHINode *PH);
116
char IndVarSimplify::ID = 0;
117
static RegisterPass<IndVarSimplify>
118
X("indvars", "Canonicalize Induction Variables");
120
Pass *llvm::createIndVarSimplifyPass() {
121
return new IndVarSimplify();
124
/// LinearFunctionTestReplace - This method rewrites the exit condition of the
125
/// loop to be a canonical != comparison against the incremented loop induction
126
/// variable. This pass is able to rewrite the exit tests of any loop where the
127
/// SCEV analysis can determine a loop-invariant trip count of the loop, which
128
/// is actually a much broader range than just linear tests.
129
ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
130
const SCEV *BackedgeTakenCount,
132
BasicBlock *ExitingBlock,
134
SCEVExpander &Rewriter) {
135
// If the exiting block is not the same as the backedge block, we must compare
136
// against the preincremented value, otherwise we prefer to compare against
137
// the post-incremented value.
139
const SCEV *RHS = BackedgeTakenCount;
140
if (ExitingBlock == L->getLoopLatch()) {
141
// Add one to the "backedge-taken" count to get the trip count.
142
// If this addition may overflow, we have to be more pessimistic and
143
// cast the induction variable before doing the add.
144
const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
146
SE->getAddExpr(BackedgeTakenCount,
147
SE->getIntegerSCEV(1, BackedgeTakenCount->getType()));
148
if ((isa<SCEVConstant>(N) && !N->isZero()) ||
149
SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) {
150
// No overflow. Cast the sum.
151
RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType());
153
// Potential overflow. Cast before doing the add.
154
RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
156
RHS = SE->getAddExpr(RHS,
157
SE->getIntegerSCEV(1, IndVar->getType()));
160
// The BackedgeTaken expression contains the number of times that the
161
// backedge branches to the loop header. This is one less than the
162
// number of times the loop executes, so use the incremented indvar.
163
CmpIndVar = L->getCanonicalInductionVariableIncrement();
165
// We have to use the preincremented value...
166
RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
171
// Expand the code for the iteration count.
172
assert(RHS->isLoopInvariant(L) &&
173
"Computed iteration count is not loop invariant!");
174
Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI);
176
// Insert a new icmp_ne or icmp_eq instruction before the branch.
177
ICmpInst::Predicate Opcode;
178
if (L->contains(BI->getSuccessor(0)))
179
Opcode = ICmpInst::ICMP_NE;
181
Opcode = ICmpInst::ICMP_EQ;
183
DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
184
<< " LHS:" << *CmpIndVar << '\n'
186
<< (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
187
<< " RHS:\t" << *RHS << "\n");
189
ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond");
191
Value *OrigCond = BI->getCondition();
192
// It's tempting to use replaceAllUsesWith here to fully replace the old
193
// comparison, but that's not immediately safe, since users of the old
194
// comparison may not be dominated by the new comparison. Instead, just
195
// update the branch to use the new comparison; in the common case this
196
// will make old comparison dead.
197
BI->setCondition(Cond);
198
RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
205
/// RewriteLoopExitValues - Check to see if this loop has a computable
206
/// loop-invariant execution count. If so, this means that we can compute the
207
/// final value of any expressions that are recurrent in the loop, and
208
/// substitute the exit values from the loop into any instructions outside of
209
/// the loop that use the final values of the current expressions.
211
/// This is mostly redundant with the regular IndVarSimplify activities that
212
/// happen later, except that it's more powerful in some cases, because it's
213
/// able to brute-force evaluate arbitrary instructions as long as they have
214
/// constant operands at the beginning of the loop.
215
void IndVarSimplify::RewriteLoopExitValues(Loop *L,
216
SCEVExpander &Rewriter) {
217
// Verify the input to the pass in already in LCSSA form.
218
assert(L->isLCSSAForm());
220
SmallVector<BasicBlock*, 8> ExitBlocks;
221
L->getUniqueExitBlocks(ExitBlocks);
223
// Find all values that are computed inside the loop, but used outside of it.
224
// Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
225
// the exit blocks of the loop to find them.
226
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
227
BasicBlock *ExitBB = ExitBlocks[i];
229
// If there are no PHI nodes in this exit block, then no values defined
230
// inside the loop are used on this path, skip it.
231
PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
234
unsigned NumPreds = PN->getNumIncomingValues();
236
// Iterate over all of the PHI nodes.
237
BasicBlock::iterator BBI = ExitBB->begin();
238
while ((PN = dyn_cast<PHINode>(BBI++))) {
240
continue; // dead use, don't replace it
242
// SCEV only supports integer expressions for now.
243
if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy())
246
// It's necessary to tell ScalarEvolution about this explicitly so that
247
// it can walk the def-use list and forget all SCEVs, as it may not be
248
// watching the PHI itself. Once the new exit value is in place, there
249
// may not be a def-use connection between the loop and every instruction
250
// which got a SCEVAddRecExpr for that loop.
253
// Iterate over all of the values in all the PHI nodes.
254
for (unsigned i = 0; i != NumPreds; ++i) {
255
// If the value being merged in is not integer or is not defined
256
// in the loop, skip it.
257
Value *InVal = PN->getIncomingValue(i);
258
if (!isa<Instruction>(InVal))
261
// If this pred is for a subloop, not L itself, skip it.
262
if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
263
continue; // The Block is in a subloop, skip it.
265
// Check that InVal is defined in the loop.
266
Instruction *Inst = cast<Instruction>(InVal);
267
if (!L->contains(Inst))
270
// Okay, this instruction has a user outside of the current loop
271
// and varies predictably *inside* the loop. Evaluate the value it
272
// contains when the loop exits, if possible.
273
const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
274
if (!ExitValue->isLoopInvariant(L))
280
Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
282
DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
283
<< " LoopVal = " << *Inst << "\n");
285
PN->setIncomingValue(i, ExitVal);
287
// If this instruction is dead now, delete it.
288
RecursivelyDeleteTriviallyDeadInstructions(Inst);
291
// Completely replace a single-pred PHI. This is safe, because the
292
// NewVal won't be variant in the loop, so we don't need an LCSSA phi
294
PN->replaceAllUsesWith(ExitVal);
295
RecursivelyDeleteTriviallyDeadInstructions(PN);
299
// Clone the PHI and delete the original one. This lets IVUsers and
300
// any other maps purge the original user from their records.
301
PHINode *NewPN = cast<PHINode>(PN->clone());
303
NewPN->insertBefore(PN);
304
PN->replaceAllUsesWith(NewPN);
305
PN->eraseFromParent();
311
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
312
// First step. Check to see if there are any floating-point recurrences.
313
// If there are, change them into integer recurrences, permitting analysis by
314
// the SCEV routines.
316
BasicBlock *Header = L->getHeader();
318
SmallVector<WeakVH, 8> PHIs;
319
for (BasicBlock::iterator I = Header->begin();
320
PHINode *PN = dyn_cast<PHINode>(I); ++I)
323
for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
324
if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
325
HandleFloatingPointIV(L, PN);
327
// If the loop previously had floating-point IV, ScalarEvolution
328
// may not have been able to compute a trip count. Now that we've done some
329
// re-writing, the trip count may be computable.
334
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
335
IU = &getAnalysis<IVUsers>();
336
LI = &getAnalysis<LoopInfo>();
337
SE = &getAnalysis<ScalarEvolution>();
338
DT = &getAnalysis<DominatorTree>();
341
// If there are any floating-point recurrences, attempt to
342
// transform them to use integer recurrences.
343
RewriteNonIntegerIVs(L);
345
BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
346
const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
348
// Create a rewriter object which we'll use to transform the code with.
349
SCEVExpander Rewriter(*SE);
351
// Check to see if this loop has a computable loop-invariant execution count.
352
// If so, this means that we can compute the final value of any expressions
353
// that are recurrent in the loop, and substitute the exit values from the
354
// loop into any instructions outside of the loop that use the final values of
355
// the current expressions.
357
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
358
RewriteLoopExitValues(L, Rewriter);
360
// Compute the type of the largest recurrence expression, and decide whether
361
// a canonical induction variable should be inserted.
362
const Type *LargestType = 0;
363
bool NeedCannIV = false;
364
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
365
LargestType = BackedgeTakenCount->getType();
366
LargestType = SE->getEffectiveSCEVType(LargestType);
367
// If we have a known trip count and a single exit block, we'll be
368
// rewriting the loop exit test condition below, which requires a
369
// canonical induction variable.
373
for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) {
375
SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType());
377
SE->getTypeSizeInBits(Ty) >
378
SE->getTypeSizeInBits(LargestType))
383
// Now that we know the largest of the induction variable expressions
384
// in this loop, insert a canonical induction variable of the largest size.
387
// Check to see if the loop already has any canonical-looking induction
388
// variables. If any are present and wider than the planned canonical
389
// induction variable, temporarily remove them, so that the Rewriter
390
// doesn't attempt to reuse them.
391
SmallVector<PHINode *, 2> OldCannIVs;
392
while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) {
393
if (SE->getTypeSizeInBits(OldCannIV->getType()) >
394
SE->getTypeSizeInBits(LargestType))
395
OldCannIV->removeFromParent();
398
OldCannIVs.push_back(OldCannIV);
401
IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);
405
DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n');
407
// Now that the official induction variable is established, reinsert
408
// any old canonical-looking variables after it so that the IR remains
409
// consistent. They will be deleted as part of the dead-PHI deletion at
410
// the end of the pass.
411
while (!OldCannIVs.empty()) {
412
PHINode *OldCannIV = OldCannIVs.pop_back_val();
413
OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI());
417
// If we have a trip count expression, rewrite the loop's exit condition
418
// using it. We can currently only handle loops with a single exit.
419
ICmpInst *NewICmp = 0;
420
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
421
!BackedgeTakenCount->isZero() &&
424
"LinearFunctionTestReplace requires a canonical induction variable");
425
// Can't rewrite non-branch yet.
426
if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
427
NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
428
ExitingBlock, BI, Rewriter);
431
// Rewrite IV-derived expressions. Clears the rewriter cache.
432
RewriteIVExpressions(L, Rewriter);
434
// The Rewriter may not be used from this point on.
436
// Loop-invariant instructions in the preheader that aren't used in the
437
// loop may be sunk below the loop to reduce register pressure.
438
SinkUnusedInvariants(L);
440
// For completeness, inform IVUsers of the IV use in the newly-created
441
// loop exit test instruction.
443
IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
445
// Clean up dead instructions.
446
Changed |= DeleteDeadPHIs(L->getHeader());
447
// Check a post-condition.
448
assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
452
void IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) {
453
SmallVector<WeakVH, 16> DeadInsts;
455
// Rewrite all induction variable expressions in terms of the canonical
456
// induction variable.
458
// If there were induction variables of other sizes or offsets, manually
459
// add the offsets to the primary induction variable and cast, avoiding
460
// the need for the code evaluation methods to insert induction variables
461
// of different sizes.
462
for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) {
463
const SCEV *Stride = UI->getStride();
464
Value *Op = UI->getOperandValToReplace();
465
const Type *UseTy = Op->getType();
466
Instruction *User = UI->getUser();
468
// Compute the final addrec to expand into code.
469
const SCEV *AR = IU->getReplacementExpr(*UI);
471
// Evaluate the expression out of the loop, if possible.
472
if (!L->contains(UI->getUser())) {
473
const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop());
474
if (ExitVal->isLoopInvariant(L))
478
// FIXME: It is an extremely bad idea to indvar substitute anything more
479
// complex than affine induction variables. Doing so will put expensive
480
// polynomial evaluations inside of the loop, and the str reduction pass
481
// currently can only reduce affine polynomials. For now just disable
482
// indvar subst on anything more complex than an affine addrec, unless
483
// it can be expanded to a trivial value.
484
if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L))
487
// Determine the insertion point for this user. By default, insert
488
// immediately before the user. The SCEVExpander class will automatically
489
// hoist loop invariants out of the loop. For PHI nodes, there may be
490
// multiple uses, so compute the nearest common dominator for the
492
Instruction *InsertPt = User;
493
if (PHINode *PHI = dyn_cast<PHINode>(InsertPt))
494
for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
495
if (PHI->getIncomingValue(i) == Op) {
496
if (InsertPt == User)
497
InsertPt = PHI->getIncomingBlock(i)->getTerminator();
500
DT->findNearestCommonDominator(InsertPt->getParent(),
501
PHI->getIncomingBlock(i))
505
// Now expand it into actual Instructions and patch it into place.
506
Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
508
// Patch the new value into place.
510
NewVal->takeName(Op);
511
User->replaceUsesOfWith(Op, NewVal);
512
UI->setOperandValToReplace(NewVal);
513
DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n'
514
<< " into = " << *NewVal << "\n");
518
// The old value may be dead now.
519
DeadInsts.push_back(Op);
522
// Clear the rewriter cache, because values that are in the rewriter's cache
523
// can be deleted in the loop below, causing the AssertingVH in the cache to
526
// Now that we're done iterating through lists, clean up any instructions
527
// which are now dead.
528
while (!DeadInsts.empty())
529
if (Instruction *Inst =
530
dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
531
RecursivelyDeleteTriviallyDeadInstructions(Inst);
534
/// If there's a single exit block, sink any loop-invariant values that
535
/// were defined in the preheader but not used inside the loop into the
536
/// exit block to reduce register pressure in the loop.
537
void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
538
BasicBlock *ExitBlock = L->getExitBlock();
539
if (!ExitBlock) return;
541
BasicBlock *Preheader = L->getLoopPreheader();
542
if (!Preheader) return;
544
Instruction *InsertPt = ExitBlock->getFirstNonPHI();
545
BasicBlock::iterator I = Preheader->getTerminator();
546
while (I != Preheader->begin()) {
548
// New instructions were inserted at the end of the preheader.
551
// Don't move instructions which might have side effects, since the side
552
// effects need to complete before instructions inside the loop. Also
553
// don't move instructions which might read memory, since the loop may
554
// modify memory. Note that it's okay if the instruction might have
555
// undefined behavior: LoopSimplify guarantees that the preheader
556
// dominates the exit block.
557
if (I->mayHaveSideEffects() || I->mayReadFromMemory())
559
// Don't sink static AllocaInsts out of the entry block, which would
560
// turn them into dynamic allocas!
561
if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
562
if (AI->isStaticAlloca())
564
// Determine if there is a use in or before the loop (direct or
566
bool UsedInLoop = false;
567
for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
569
BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
570
if (PHINode *P = dyn_cast<PHINode>(UI)) {
572
PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
573
UseBB = P->getIncomingBlock(i);
575
if (UseBB == Preheader || L->contains(UseBB)) {
580
// If there is, the def must remain in the preheader.
583
// Otherwise, sink it to the exit block.
584
Instruction *ToMove = I;
586
if (I != Preheader->begin())
590
ToMove->moveBefore(InsertPt);
597
/// Return true if it is OK to use SIToFPInst for an induction variable
598
/// with given initial and exit values.
599
static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV,
600
uint64_t intIV, uint64_t intEV) {
602
if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative())
605
// If the iteration range can be handled by SIToFPInst then use it.
606
APInt Max = APInt::getSignedMaxValue(32);
607
if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV)))
613
/// convertToInt - Convert APF to an integer, if possible.
614
static bool convertToInt(const APFloat &APF, uint64_t *intVal) {
616
bool isExact = false;
617
if (&APF.getSemantics() == &APFloat::PPCDoubleDouble)
619
if (APF.convertToInteger(intVal, 32, APF.isNegative(),
620
APFloat::rmTowardZero, &isExact)
629
/// HandleFloatingPointIV - If the loop has floating induction variable
630
/// then insert corresponding integer induction variable if possible.
632
/// for(double i = 0; i < 10000; ++i)
634
/// is converted into
635
/// for(int i = 0; i < 10000; ++i)
638
void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
640
unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
641
unsigned BackEdge = IncomingEdge^1;
643
// Check incoming value.
644
ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge));
645
if (!InitValue) return;
646
uint64_t newInitValue =
647
Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
648
if (!convertToInt(InitValue->getValueAPF(), &newInitValue))
651
// Check IV increment. Reject this PH if increment operation is not
652
// an add or increment value can not be represented by an integer.
653
BinaryOperator *Incr =
654
dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge));
656
if (Incr->getOpcode() != Instruction::FAdd) return;
657
ConstantFP *IncrValue = NULL;
658
unsigned IncrVIndex = 1;
659
if (Incr->getOperand(1) == PH)
661
IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex));
662
if (!IncrValue) return;
663
uint64_t newIncrValue =
664
Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
665
if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue))
668
// Check Incr uses. One user is PH and the other users is exit condition used
669
// by the conditional terminator.
670
Value::use_iterator IncrUse = Incr->use_begin();
671
Instruction *U1 = cast<Instruction>(IncrUse++);
672
if (IncrUse == Incr->use_end()) return;
673
Instruction *U2 = cast<Instruction>(IncrUse++);
674
if (IncrUse != Incr->use_end()) return;
676
// Find exit condition.
677
FCmpInst *EC = dyn_cast<FCmpInst>(U1);
679
EC = dyn_cast<FCmpInst>(U2);
682
if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) {
683
if (!BI->isConditional()) return;
684
if (BI->getCondition() != EC) return;
687
// Find exit value. If exit value can not be represented as an integer then
688
// do not handle this floating point PH.
689
ConstantFP *EV = NULL;
690
unsigned EVIndex = 1;
691
if (EC->getOperand(1) == Incr)
693
EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex));
695
uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
696
if (!convertToInt(EV->getValueAPF(), &intEV))
699
// Find new predicate for integer comparison.
700
CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
701
switch (EC->getPredicate()) {
702
case CmpInst::FCMP_OEQ:
703
case CmpInst::FCMP_UEQ:
704
NewPred = CmpInst::ICMP_EQ;
706
case CmpInst::FCMP_OGT:
707
case CmpInst::FCMP_UGT:
708
NewPred = CmpInst::ICMP_UGT;
710
case CmpInst::FCMP_OGE:
711
case CmpInst::FCMP_UGE:
712
NewPred = CmpInst::ICMP_UGE;
714
case CmpInst::FCMP_OLT:
715
case CmpInst::FCMP_ULT:
716
NewPred = CmpInst::ICMP_ULT;
718
case CmpInst::FCMP_OLE:
719
case CmpInst::FCMP_ULE:
720
NewPred = CmpInst::ICMP_ULE;
725
if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return;
727
// Insert new integer induction variable.
728
PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()),
729
PH->getName()+".int", PH);
730
NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()),
732
PH->getIncomingBlock(IncomingEdge));
734
Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
735
ConstantInt::get(Type::getInt32Ty(PH->getContext()),
737
Incr->getName()+".int", Incr);
738
NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
740
// The back edge is edge 1 of newPHI, whatever it may have been in the
742
ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()),
744
Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
745
Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
746
ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(),
747
NewPred, LHS, RHS, EC->getName());
749
// In the following deletions, PH may become dead and may be deleted.
750
// Use a WeakVH to observe whether this happens.
753
// Delete old, floating point, exit comparison instruction.
755
EC->replaceAllUsesWith(NewEC);
756
RecursivelyDeleteTriviallyDeadInstructions(EC);
758
// Delete old, floating point, increment instruction.
759
Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
760
RecursivelyDeleteTriviallyDeadInstructions(Incr);
762
// Replace floating induction variable, if it isn't already deleted.
763
// Give SIToFPInst preference over UIToFPInst because it is faster on
764
// platforms that are widely used.
765
if (WeakPH && !PH->use_empty()) {
766
if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
767
SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
768
PH->getParent()->getFirstNonPHI());
769
PH->replaceAllUsesWith(Conv);
771
UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
772
PH->getParent()->getFirstNonPHI());
773
PH->replaceAllUsesWith(Conv);
775
RecursivelyDeleteTriviallyDeadInstructions(PH);
778
// Add a new IVUsers entry for the newly-created integer PHI.
779
IU->AddUsersIfInteresting(NewPHI);
added
removed
libclamav/c++/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
