← Back to branch summary

~ubuntu-branches/ubuntu/hardy/clamav/hardy-security

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Marc Deslauriers, Scott Kitterman
  • Date: 2013-03-21 08:37:54 UTC
  • mfrom: (43.1.79 raring-proposed)
  • Revision ID: package-import@ubuntu.com-20130321083754-r3dnl8aewkny2rxu
Tags: 0.97.7+dfsg-1ubuntu0.08.04.1
https://launchpad.net/bugs/1157385
[ Marc Deslauriers ]
* SECURITY UPDATE: Updated to 0.97.7 to fix multiple security issues.
  (LP: #1157385)
  - CVE numbers pending

[ Scott Kitterman ]
* Changes to adapt to Hardy:
  - Build without llvm support on lpia to fix FTBFS (not a regression as
    llvm has never built on hardy lpia)
  - Drop -T -W from apparmor_parser calls in clamav-daemon and freshclam
    postinsts since it is not supported in Hardy's apparmor
  - Drop deny rule in freshclam apparmor profile since deny is not
    supported in Hardy's apparmor
  - Drop dh_lintian from debian/rules and adjust version of debhelper
    build-dep
  - Drop build-dep and libclamav-dev depends on non-existent libtommath-dev
  - Changed Section to 'utils' for clamav-dbg package
  - Ignore test suite errors on hppa
  - Build-depend on libltdl3-dev instead of libltdl-dev
  - Drop hardening flags changes
  - Drop unneeded versioning on lsb-base (clamav ships it's own status
    function)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp
 
1
//===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file implements Loop Index Splitting Pass. This pass handles three
 
11
// kinds of loops.
 
12
//
 
13
// [1] A loop may be eliminated if the body is executed exactly once.
 
14
//     For example,
 
15
//
 
16
// for (i = 0; i < N; ++i) {
 
17
//   if (i == X) {
 
18
//     body;
 
19
//   }
 
20
// }
 
21
//
 
22
// is transformed to
 
23
//
 
24
// i = X;
 
25
// body;
 
26
//
 
27
// [2] A loop's iteration space may be shrunk if the loop body is executed
 
28
//     for a proper sub-range of the loop's iteration space. For example,
 
29
//
 
30
// for (i = 0; i < N; ++i) {
 
31
//   if (i > A && i < B) {
 
32
//     ...
 
33
//   }
 
34
// }
 
35
//
 
36
// is transformed to iterators from A to B, if A > 0 and B < N.
 
37
//
 
38
// [3] A loop may be split if the loop body is dominated by a branch.
 
39
//     For example,
 
40
//
 
41
// for (i = LB; i < UB; ++i) { if (i < SV) A; else B; }
 
42
//
 
43
// is transformed into
 
44
//
 
45
// AEV = BSV = SV
 
46
// for (i = LB; i < min(UB, AEV); ++i)
 
47
//    A;
 
48
// for (i = max(LB, BSV); i < UB; ++i);
 
49
//    B;
 
50
//
 
51
//===----------------------------------------------------------------------===//
 
52
 
 
53
#define DEBUG_TYPE "loop-index-split"
 
54
#include "llvm/Transforms/Scalar.h"
 
55
#include "llvm/IntrinsicInst.h"
 
56
#include "llvm/LLVMContext.h"
 
57
#include "llvm/Analysis/LoopPass.h"
 
58
#include "llvm/Analysis/ScalarEvolution.h"
 
59
#include "llvm/Analysis/Dominators.h"
 
60
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
61
#include "llvm/Transforms/Utils/Cloning.h"
 
62
#include "llvm/Transforms/Utils/Local.h"
 
63
#include "llvm/ADT/DepthFirstIterator.h"
 
64
#include "llvm/ADT/Statistic.h"
 
65
 
 
66
using namespace llvm;
 
67
 
 
68
STATISTIC(NumIndexSplit, "Number of loop index split");
 
69
STATISTIC(NumIndexSplitRemoved, "Number of loops eliminated by loop index split");
 
70
STATISTIC(NumRestrictBounds, "Number of loop iteration space restricted");
 
71
 
 
72
namespace {
 
73
 
 
74
  class LoopIndexSplit : public LoopPass {
 
75
  public:
 
76
    static char ID; // Pass ID, replacement for typeid
 
77
    LoopIndexSplit() : LoopPass(ID) {}
 
78
 
 
79
    // Index split Loop L. Return true if loop is split.
 
80
    bool runOnLoop(Loop *L, LPPassManager &LPM);
 
81
 
 
82
    void getAnalysisUsage(AnalysisUsage &AU) const {
 
83
      AU.addPreserved<ScalarEvolution>();
 
84
      AU.addRequiredID(LCSSAID);
 
85
      AU.addPreservedID(LCSSAID);
 
86
      AU.addRequired<LoopInfo>();
 
87
      AU.addPreserved<LoopInfo>();
 
88
      AU.addRequiredID(LoopSimplifyID);
 
89
      AU.addPreservedID(LoopSimplifyID);
 
90
      AU.addRequired<DominatorTree>();
 
91
      AU.addRequired<DominanceFrontier>();
 
92
      AU.addPreserved<DominatorTree>();
 
93
      AU.addPreserved<DominanceFrontier>();
 
94
    }
 
95
 
 
96
  private:
 
97
    /// processOneIterationLoop -- Eliminate loop if loop body is executed 
 
98
    /// only once. For example,
 
99
    /// for (i = 0; i < N; ++i) {
 
100
    ///   if ( i == X) {
 
101
    ///     ...
 
102
    ///   }
 
103
    /// }
 
104
    ///
 
105
    bool processOneIterationLoop();
 
106
 
 
107
    // -- Routines used by updateLoopIterationSpace();
 
108
 
 
109
    /// updateLoopIterationSpace -- Update loop's iteration space if loop 
 
110
    /// body is executed for certain IV range only. For example,
 
111
    /// 
 
112
    /// for (i = 0; i < N; ++i) {
 
113
    ///   if ( i > A && i < B) {
 
114
    ///     ...
 
115
    ///   }
 
116
    /// }
 
117
    /// is transformed to iterators from A to B, if A > 0 and B < N.
 
118
    ///
 
119
    bool updateLoopIterationSpace();
 
120
 
 
121
    /// restrictLoopBound - Op dominates loop body. Op compares an IV based value
 
122
    /// with a loop invariant value. Update loop's lower and upper bound based on
 
123
    /// the loop invariant value.
 
124
    bool restrictLoopBound(ICmpInst &Op);
 
125
 
 
126
    // --- Routines used by splitLoop(). --- /
 
127
 
 
128
    bool splitLoop();
 
129
 
 
130
    /// removeBlocks - Remove basic block DeadBB and all blocks dominated by 
 
131
    /// DeadBB. This routine is used to remove split condition's dead branch, 
 
132
    /// dominated by DeadBB. LiveBB dominates split conidition's other branch.
 
133
    void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);
 
134
    
 
135
    /// moveExitCondition - Move exit condition EC into split condition block.
 
136
    void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB,
 
137
                           BasicBlock *ExitBB, ICmpInst *EC, ICmpInst *SC,
 
138
                           PHINode *IV, Instruction *IVAdd, Loop *LP,
 
139
                           unsigned);
 
140
    
 
141
    /// updatePHINodes - CFG has been changed. 
 
142
    /// Before 
 
143
    ///   - ExitBB's single predecessor was Latch
 
144
    ///   - Latch's second successor was Header
 
145
    /// Now
 
146
    ///   - ExitBB's single predecessor was Header
 
147
    ///   - Latch's one and only successor was Header
 
148
    ///
 
149
    /// Update ExitBB PHINodes' to reflect this change.
 
150
    void updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, 
 
151
                        BasicBlock *Header,
 
152
                        PHINode *IV, Instruction *IVIncrement, Loop *LP);
 
153
 
 
154
    // --- Utility routines --- /
 
155
 
 
156
    /// cleanBlock - A block is considered clean if all non terminal 
 
157
    /// instructions are either PHINodes or IV based values.
 
158
    bool cleanBlock(BasicBlock *BB);
 
159
 
 
160
    /// IVisLT - If Op is comparing IV based value with an loop invariant and 
 
161
    /// IV based value is less than  the loop invariant then return the loop 
 
162
    /// invariant. Otherwise return NULL.
 
163
    Value * IVisLT(ICmpInst &Op);
 
164
 
 
165
    /// IVisLE - If Op is comparing IV based value with an loop invariant and 
 
166
    /// IV based value is less than or equal to the loop invariant then 
 
167
    /// return the loop invariant. Otherwise return NULL.
 
168
    Value * IVisLE(ICmpInst &Op);
 
169
 
 
170
    /// IVisGT - If Op is comparing IV based value with an loop invariant and 
 
171
    /// IV based value is greater than  the loop invariant then return the loop 
 
172
    /// invariant. Otherwise return NULL.
 
173
    Value * IVisGT(ICmpInst &Op);
 
174
 
 
175
    /// IVisGE - If Op is comparing IV based value with an loop invariant and 
 
176
    /// IV based value is greater than or equal to the loop invariant then 
 
177
    /// return the loop invariant. Otherwise return NULL.
 
178
    Value * IVisGE(ICmpInst &Op);
 
179
 
 
180
  private:
 
181
 
 
182
    // Current Loop information.
 
183
    Loop *L;
 
184
    LPPassManager *LPM;
 
185
    LoopInfo *LI;
 
186
    DominatorTree *DT;
 
187
    DominanceFrontier *DF;
 
188
 
 
189
    PHINode *IndVar;
 
190
    ICmpInst *ExitCondition;
 
191
    ICmpInst *SplitCondition;
 
192
    Value *IVStartValue;
 
193
    Value *IVExitValue;
 
194
    Instruction *IVIncrement;
 
195
    SmallPtrSet<Value *, 4> IVBasedValues;
 
196
  };
 
197
}
 
198
 
 
199
char LoopIndexSplit::ID = 0;
 
200
INITIALIZE_PASS(LoopIndexSplit, "loop-index-split",
 
201
                "Index Split Loops", false, false);
 
202
 
 
203
Pass *llvm::createLoopIndexSplitPass() {
 
204
  return new LoopIndexSplit();
 
205
}
 
206
 
 
207
// Index split Loop L. Return true if loop is split.
 
208
bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
 
209
  L = IncomingLoop;
 
210
  LPM = &LPM_Ref;
 
211
 
 
212
  // If LoopSimplify form is not available, stay out of trouble.
 
213
  if (!L->isLoopSimplifyForm())
 
214
    return false;
 
215
 
 
216
  // FIXME - Nested loops make dominator info updates tricky. 
 
217
  if (!L->getSubLoops().empty())
 
218
    return false;
 
219
 
 
220
  DT = &getAnalysis<DominatorTree>();
 
221
  LI = &getAnalysis<LoopInfo>();
 
222
  DF = &getAnalysis<DominanceFrontier>();
 
223
 
 
224
  // Initialize loop data.
 
225
  IndVar = L->getCanonicalInductionVariable();
 
226
  if (!IndVar) return false;
 
227
 
 
228
  bool P1InLoop = L->contains(IndVar->getIncomingBlock(1));
 
229
  IVStartValue = IndVar->getIncomingValue(!P1InLoop);
 
230
  IVIncrement = dyn_cast<Instruction>(IndVar->getIncomingValue(P1InLoop));
 
231
  if (!IVIncrement) return false;
 
232
  
 
233
  IVBasedValues.clear();
 
234
  IVBasedValues.insert(IndVar);
 
235
  IVBasedValues.insert(IVIncrement);
 
236
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
237
       I != E; ++I) 
 
238
    for(BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); 
 
239
        BI != BE; ++BI) {
 
240
      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BI)) 
 
241
        if (BO != IVIncrement 
 
242
            && (BO->getOpcode() == Instruction::Add
 
243
                || BO->getOpcode() == Instruction::Sub))
 
244
          if (IVBasedValues.count(BO->getOperand(0))
 
245
              && L->isLoopInvariant(BO->getOperand(1)))
 
246
            IVBasedValues.insert(BO);
 
247
    }
 
248
 
 
249
  // Reject loop if loop exit condition is not suitable.
 
250
  BasicBlock *ExitingBlock = L->getExitingBlock();
 
251
  if (!ExitingBlock)
 
252
    return false;
 
253
  BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
 
254
  if (!EBR) return false;
 
255
  ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition());
 
256
  if (!ExitCondition) return false;
 
257
  if (ExitingBlock != L->getLoopLatch()) return false;
 
258
  IVExitValue = ExitCondition->getOperand(1);
 
259
  if (!L->isLoopInvariant(IVExitValue))
 
260
    IVExitValue = ExitCondition->getOperand(0);
 
261
  if (!L->isLoopInvariant(IVExitValue))
 
262
    return false;
 
263
  if (!IVBasedValues.count(
 
264
        ExitCondition->getOperand(IVExitValue == ExitCondition->getOperand(0))))
 
265
    return false;
 
266
 
 
267
  // If start value is more then exit value where induction variable
 
268
  // increments by 1 then we are potentially dealing with an infinite loop.
 
269
  // Do not index split this loop.
 
270
  if (ConstantInt *SV = dyn_cast<ConstantInt>(IVStartValue))
 
271
    if (ConstantInt *EV = dyn_cast<ConstantInt>(IVExitValue))
 
272
      if (SV->getSExtValue() > EV->getSExtValue())
 
273
        return false;
 
274
 
 
275
  if (processOneIterationLoop())
 
276
    return true;
 
277
 
 
278
  if (updateLoopIterationSpace())
 
279
    return true;
 
280
 
 
281
  if (splitLoop())
 
282
    return true;
 
283
 
 
284
  return false;
 
285
}
 
286
 
 
287
// --- Helper routines --- 
 
288
// isUsedOutsideLoop - Returns true iff V is used outside the loop L.
 
289
static bool isUsedOutsideLoop(Value *V, Loop *L) {
 
290
  for(Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 
291
    if (!L->contains(cast<Instruction>(*UI)))
 
292
      return true;
 
293
  return false;
 
294
}
 
295
 
 
296
// Return V+1
 
297
static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt, 
 
298
                         LLVMContext &Context) {
 
299
  Constant *One = ConstantInt::get(V->getType(), 1, Sign);
 
300
  return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt);
 
301
}
 
302
 
 
303
// Return V-1
 
304
static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt,
 
305
                          LLVMContext &Context) {
 
306
  Constant *One = ConstantInt::get(V->getType(), 1, Sign);
 
307
  return BinaryOperator::CreateSub(V, One, "lsp", InsertPt);
 
308
}
 
309
 
 
310
// Return min(V1, V1)
 
311
static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
 
312
 
 
313
  Value *C = new ICmpInst(InsertPt,
 
314
                          Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 
315
                          V1, V2, "lsp");
 
316
  return SelectInst::Create(C, V1, V2, "lsp", InsertPt);
 
317
}
 
318
 
 
319
// Return max(V1, V2)
 
320
static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
 
321
 
 
322
  Value *C = new ICmpInst(InsertPt, 
 
323
                          Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 
324
                          V1, V2, "lsp");
 
325
  return SelectInst::Create(C, V2, V1, "lsp", InsertPt);
 
326
}
 
327
 
 
328
/// processOneIterationLoop -- Eliminate loop if loop body is executed 
 
329
/// only once. For example,
 
330
/// for (i = 0; i < N; ++i) {
 
331
///   if ( i == X) {
 
332
///     ...
 
333
///   }
 
334
/// }
 
335
///
 
336
bool LoopIndexSplit::processOneIterationLoop() {
 
337
  SplitCondition = NULL;
 
338
  BasicBlock *Latch = L->getLoopLatch();
 
339
  BasicBlock *Header = L->getHeader();
 
340
  BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator());
 
341
  if (!BR) return false;
 
342
  if (!isa<BranchInst>(Latch->getTerminator())) return false;
 
343
  if (BR->isUnconditional()) return false;
 
344
  SplitCondition = dyn_cast<ICmpInst>(BR->getCondition());
 
345
  if (!SplitCondition) return false;
 
346
  if (SplitCondition == ExitCondition) return false;
 
347
  if (SplitCondition->getPredicate() != ICmpInst::ICMP_EQ) return false;
 
348
  if (BR->getOperand(1) != Latch) return false;
 
349
  if (!IVBasedValues.count(SplitCondition->getOperand(0))
 
350
      && !IVBasedValues.count(SplitCondition->getOperand(1)))
 
351
    return false;
 
352
 
 
353
  // If IV is used outside the loop then this loop traversal is required.
 
354
  // FIXME: Calculate and use last IV value. 
 
355
  if (isUsedOutsideLoop(IVIncrement, L))
 
356
    return false;
 
357
 
 
358
  // If BR operands are not IV or not loop invariants then skip this loop.
 
359
  Value *OPV = SplitCondition->getOperand(0);
 
360
  Value *SplitValue = SplitCondition->getOperand(1);
 
361
  if (!L->isLoopInvariant(SplitValue))
 
362
    std::swap(OPV, SplitValue);
 
363
  if (!L->isLoopInvariant(SplitValue))
 
364
    return false;
 
365
  Instruction *OPI = dyn_cast<Instruction>(OPV);
 
366
  if (!OPI) 
 
367
    return false;
 
368
  if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L))
 
369
    return false;
 
370
  Value *StartValue = IVStartValue;
 
371
  Value *ExitValue = IVExitValue;;
 
372
 
 
373
  if (OPV != IndVar) {
 
374
    // If BR operand is IV based then use this operand to calculate
 
375
    // effective conditions for loop body.
 
376
    BinaryOperator *BOPV = dyn_cast<BinaryOperator>(OPV);
 
377
    if (!BOPV) 
 
378
      return false;
 
379
    if (BOPV->getOpcode() != Instruction::Add) 
 
380
      return false;
 
381
    StartValue = BinaryOperator::CreateAdd(OPV, StartValue, "" , BR);
 
382
    ExitValue = BinaryOperator::CreateAdd(OPV, ExitValue, "" , BR);
 
383
  }
 
384
 
 
385
  if (!cleanBlock(Header))
 
386
    return false;
 
387
 
 
388
  if (!cleanBlock(Latch))
 
389
    return false;
 
390
    
 
391
  // If the merge point for BR is not loop latch then skip this loop.
 
392
  if (BR->getSuccessor(0) != Latch) {
 
393
    DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
 
394
    assert (DF0 != DF->end() && "Unable to find dominance frontier");
 
395
    if (!DF0->second.count(Latch))
 
396
      return false;
 
397
  }
 
398
  
 
399
  if (BR->getSuccessor(1) != Latch) {
 
400
    DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
 
401
    assert (DF1 != DF->end() && "Unable to find dominance frontier");
 
402
    if (!DF1->second.count(Latch))
 
403
      return false;
 
404
  }
 
405
    
 
406
  // Now, Current loop L contains compare instruction
 
407
  // that compares induction variable, IndVar, against loop invariant. And
 
408
  // entire (i.e. meaningful) loop body is dominated by this compare
 
409
  // instruction. In such case eliminate 
 
410
  // loop structure surrounding this loop body. For example,
 
411
  //     for (int i = start; i < end; ++i) {
 
412
  //         if ( i == somevalue) {
 
413
  //           loop_body
 
414
  //         }
 
415
  //     }
 
416
  // can be transformed into
 
417
  //     if (somevalue >= start && somevalue < end) {
 
418
  //        i = somevalue;
 
419
  //        loop_body
 
420
  //     }
 
421
 
 
422
  // Replace index variable with split value in loop body. Loop body is executed
 
423
  // only when index variable is equal to split value.
 
424
  IndVar->replaceAllUsesWith(SplitValue);
 
425
 
 
426
  // Replace split condition in header.
 
427
  // Transform 
 
428
  //      SplitCondition : icmp eq i32 IndVar, SplitValue
 
429
  // into
 
430
  //      c1 = icmp uge i32 SplitValue, StartValue
 
431
  //      c2 = icmp ult i32 SplitValue, ExitValue
 
432
  //      and i32 c1, c2 
 
433
  Instruction *C1 = new ICmpInst(BR, ExitCondition->isSigned() ? 
 
434
                                 ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 
435
                                 SplitValue, StartValue, "lisplit");
 
436
 
 
437
  CmpInst::Predicate C2P  = ExitCondition->getPredicate();
 
438
  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
 
439
  if (LatchBR->getOperand(1) != Header)
 
440
    C2P = CmpInst::getInversePredicate(C2P);
 
441
  Instruction *C2 = new ICmpInst(BR, C2P, SplitValue, ExitValue, "lisplit");
 
442
  Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
 
443
 
 
444
  SplitCondition->replaceAllUsesWith(NSplitCond);
 
445
  SplitCondition->eraseFromParent();
 
446
 
 
447
  // Remove Latch to Header edge.
 
448
  BasicBlock *LatchSucc = NULL;
 
449
  Header->removePredecessor(Latch);
 
450
  for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 
451
       SI != E; ++SI) {
 
452
    if (Header != *SI)
 
453
      LatchSucc = *SI;
 
454
  }
 
455
 
 
456
  // Clean up latch block.
 
457
  Value *LatchBRCond = LatchBR->getCondition();
 
458
  LatchBR->setUnconditionalDest(LatchSucc);
 
459
  RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond);
 
460
  
 
461
  LPM->deleteLoopFromQueue(L);
 
462
 
 
463
  // Update Dominator Info.
 
464
  // Only CFG change done is to remove Latch to Header edge. This
 
465
  // does not change dominator tree because Latch did not dominate
 
466
  // Header.
 
467
  if (DF) {
 
468
    DominanceFrontier::iterator HeaderDF = DF->find(Header);
 
469
    if (HeaderDF != DF->end()) 
 
470
      DF->removeFromFrontier(HeaderDF, Header);
 
471
 
 
472
    DominanceFrontier::iterator LatchDF = DF->find(Latch);
 
473
    if (LatchDF != DF->end()) 
 
474
      DF->removeFromFrontier(LatchDF, Header);
 
475
  }
 
476
 
 
477
  ++NumIndexSplitRemoved;
 
478
  return true;
 
479
}
 
480
 
 
481
/// restrictLoopBound - Op dominates loop body. Op compares an IV based value 
 
482
/// with a loop invariant value. Update loop's lower and upper bound based on 
 
483
/// the loop invariant value.
 
484
bool LoopIndexSplit::restrictLoopBound(ICmpInst &Op) {
 
485
  bool Sign = Op.isSigned();
 
486
  Instruction *PHTerm = L->getLoopPreheader()->getTerminator();
 
487
 
 
488
  if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) {
 
489
    BranchInst *EBR = 
 
490
      cast<BranchInst>(ExitCondition->getParent()->getTerminator());
 
491
    ExitCondition->setPredicate(ExitCondition->getInversePredicate());
 
492
    BasicBlock *T = EBR->getSuccessor(0);
 
493
    EBR->setSuccessor(0, EBR->getSuccessor(1));
 
494
    EBR->setSuccessor(1, T);
 
495
  }
 
496
 
 
497
  LLVMContext &Context = Op.getContext();
 
498
 
 
499
  // New upper and lower bounds.
 
500
  Value *NLB = NULL;
 
501
  Value *NUB = NULL;
 
502
  if (Value *V = IVisLT(Op)) {
 
503
    // Restrict upper bound.
 
504
    if (IVisLE(*ExitCondition)) 
 
505
      V = getMinusOne(V, Sign, PHTerm, Context);
 
506
    NUB = getMin(V, IVExitValue, Sign, PHTerm);
 
507
  } else if (Value *V = IVisLE(Op)) {
 
508
    // Restrict upper bound.
 
509
    if (IVisLT(*ExitCondition)) 
 
510
      V = getPlusOne(V, Sign, PHTerm, Context);
 
511
    NUB = getMin(V, IVExitValue, Sign, PHTerm);
 
512
  } else if (Value *V = IVisGT(Op)) {
 
513
    // Restrict lower bound.
 
514
    V = getPlusOne(V, Sign, PHTerm, Context);
 
515
    NLB = getMax(V, IVStartValue, Sign, PHTerm);
 
516
  } else if (Value *V = IVisGE(Op))
 
517
    // Restrict lower bound.
 
518
    NLB = getMax(V, IVStartValue, Sign, PHTerm);
 
519
 
 
520
  if (!NLB && !NUB) 
 
521
    return false;
 
522
 
 
523
  if (NLB) {
 
524
    unsigned i = IndVar->getBasicBlockIndex(L->getLoopPreheader());
 
525
    IndVar->setIncomingValue(i, NLB);
 
526
  }
 
527
 
 
528
  if (NUB) {
 
529
    unsigned i = (ExitCondition->getOperand(0) != IVExitValue);
 
530
    ExitCondition->setOperand(i, NUB);
 
531
  }
 
532
  return true;
 
533
}
 
534
 
 
535
/// updateLoopIterationSpace -- Update loop's iteration space if loop 
 
536
/// body is executed for certain IV range only. For example,
 
537
/// 
 
538
/// for (i = 0; i < N; ++i) {
 
539
///   if ( i > A && i < B) {
 
540
///     ...
 
541
///   }
 
542
/// }
 
543
/// is transformed to iterators from A to B, if A > 0 and B < N.
 
544
///
 
545
bool LoopIndexSplit::updateLoopIterationSpace() {
 
546
  SplitCondition = NULL;
 
547
  if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE
 
548
      || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 
549
    return false;
 
550
  BasicBlock *Latch = L->getLoopLatch();
 
551
  BasicBlock *Header = L->getHeader();
 
552
  BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator());
 
553
  if (!BR) return false;
 
554
  if (!isa<BranchInst>(Latch->getTerminator())) return false;
 
555
  if (BR->isUnconditional()) return false;
 
556
  BinaryOperator *AND = dyn_cast<BinaryOperator>(BR->getCondition());
 
557
  if (!AND) return false;
 
558
  if (AND->getOpcode() != Instruction::And) return false;
 
559
  ICmpInst *Op0 = dyn_cast<ICmpInst>(AND->getOperand(0));
 
560
  ICmpInst *Op1 = dyn_cast<ICmpInst>(AND->getOperand(1));
 
561
  if (!Op0 || !Op1)
 
562
    return false;
 
563
  IVBasedValues.insert(AND);
 
564
  IVBasedValues.insert(Op0);
 
565
  IVBasedValues.insert(Op1);
 
566
  if (!cleanBlock(Header)) return false;
 
567
  BasicBlock *ExitingBlock = ExitCondition->getParent();
 
568
  if (!cleanBlock(ExitingBlock)) return false;
 
569
 
 
570
  // If the merge point for BR is not loop latch then skip this loop.
 
571
  if (BR->getSuccessor(0) != Latch) {
 
572
    DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
 
573
    assert (DF0 != DF->end() && "Unable to find dominance frontier");
 
574
    if (!DF0->second.count(Latch))
 
575
      return false;
 
576
  }
 
577
  
 
578
  if (BR->getSuccessor(1) != Latch) {
 
579
    DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
 
580
    assert (DF1 != DF->end() && "Unable to find dominance frontier");
 
581
    if (!DF1->second.count(Latch))
 
582
      return false;
 
583
  }
 
584
    
 
585
  // Verify that loop exiting block has only two predecessor, where one pred
 
586
  // is split condition block. The other predecessor will become exiting block's
 
587
  // dominator after CFG is updated. TODO : Handle CFG's where exiting block has
 
588
  // more then two predecessors. This requires extra work in updating dominator
 
589
  // information.
 
590
  BasicBlock *ExitingBBPred = NULL;
 
591
  for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock);
 
592
       PI != PE; ++PI) {
 
593
    BasicBlock *BB = *PI;
 
594
    if (Header == BB)
 
595
      continue;
 
596
    if (ExitingBBPred)
 
597
      return false;
 
598
    else
 
599
      ExitingBBPred = BB;
 
600
  }
 
601
 
 
602
  if (!restrictLoopBound(*Op0))
 
603
    return false;
 
604
 
 
605
  if (!restrictLoopBound(*Op1))
 
606
    return false;
 
607
 
 
608
  // Update CFG.
 
609
  if (BR->getSuccessor(0) == ExitingBlock)
 
610
    BR->setUnconditionalDest(BR->getSuccessor(1));
 
611
  else
 
612
    BR->setUnconditionalDest(BR->getSuccessor(0));
 
613
 
 
614
  AND->eraseFromParent();
 
615
  if (Op0->use_empty())
 
616
    Op0->eraseFromParent();
 
617
  if (Op1->use_empty())
 
618
    Op1->eraseFromParent();
 
619
 
 
620
  // Update domiantor info. Now, ExitingBlock has only one predecessor, 
 
621
  // ExitingBBPred, and it is ExitingBlock's immediate domiantor.
 
622
  DT->changeImmediateDominator(ExitingBlock, ExitingBBPred);
 
623
 
 
624
  BasicBlock *ExitBlock = ExitingBlock->getTerminator()->getSuccessor(1);
 
625
  if (L->contains(ExitBlock))
 
626
    ExitBlock = ExitingBlock->getTerminator()->getSuccessor(0);
 
627
 
 
628
  // If ExitingBlock is a member of the loop basic blocks' DF list then
 
629
  // replace ExitingBlock with header and exit block in the DF list
 
630
  DominanceFrontier::iterator ExitingBlockDF = DF->find(ExitingBlock);
 
631
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
632
       I != E; ++I) {
 
633
    BasicBlock *BB = *I;
 
634
    if (BB == Header || BB == ExitingBlock)
 
635
      continue;
 
636
    DominanceFrontier::iterator BBDF = DF->find(BB);
 
637
    DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
 
638
    DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
 
639
    while (DomSetI != DomSetE) {
 
640
      DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
 
641
      ++DomSetI;
 
642
      BasicBlock *DFBB = *CurrentItr;
 
643
      if (DFBB == ExitingBlock) {
 
644
        BBDF->second.erase(DFBB);
 
645
        for (DominanceFrontier::DomSetType::iterator 
 
646
               EBI = ExitingBlockDF->second.begin(),
 
647
               EBE = ExitingBlockDF->second.end(); EBI != EBE; ++EBI) 
 
648
          BBDF->second.insert(*EBI);
 
649
      }
 
650
    }
 
651
  }
 
652
  ++NumRestrictBounds;
 
653
  return true;
 
654
}
 
655
 
 
656
/// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 
657
/// This routine is used to remove split condition's dead branch, dominated by
 
658
/// DeadBB. LiveBB dominates split conidition's other branch.
 
659
void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, 
 
660
                                  BasicBlock *LiveBB) {
 
661
 
 
662
  // First update DeadBB's dominance frontier. 
 
663
  SmallVector<BasicBlock *, 8> FrontierBBs;
 
664
  DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
 
665
  if (DeadBBDF != DF->end()) {
 
666
    SmallVector<BasicBlock *, 8> PredBlocks;
 
667
    
 
668
    DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second;
 
669
    for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(),
 
670
           DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) 
 
671
      {
 
672
      BasicBlock *FrontierBB = *DeadBBSetI;
 
673
      FrontierBBs.push_back(FrontierBB);
 
674
 
 
675
      // Rremove any PHI incoming edge from blocks dominated by DeadBB.
 
676
      PredBlocks.clear();
 
677
      for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
 
678
          PI != PE; ++PI) {
 
679
        BasicBlock *P = *PI;
 
680
        if (DT->dominates(DeadBB, P))
 
681
          PredBlocks.push_back(P);
 
682
      }
 
683
 
 
684
      for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end();
 
685
          FBI != FBE; ++FBI) {
 
686
        if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
 
687
          for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(),
 
688
                PE = PredBlocks.end(); PI != PE; ++PI) {
 
689
            BasicBlock *P = *PI;
 
690
            PN->removeIncomingValue(P);
 
691
          }
 
692
        }
 
693
        else
 
694
          break;
 
695
      }      
 
696
    }
 
697
  }
 
698
  
 
699
  // Now remove DeadBB and all nodes dominated by DeadBB in df order.
 
700
  SmallVector<BasicBlock *, 32> WorkList;
 
701
  DomTreeNode *DN = DT->getNode(DeadBB);
 
702
  for (df_iterator<DomTreeNode*> DI = df_begin(DN),
 
703
         E = df_end(DN); DI != E; ++DI) {
 
704
    BasicBlock *BB = DI->getBlock();
 
705
    WorkList.push_back(BB);
 
706
    BB->replaceAllUsesWith(UndefValue::get(
 
707
                                       Type::getLabelTy(DeadBB->getContext())));
 
708
  }
 
709
 
 
710
  while (!WorkList.empty()) {
 
711
    BasicBlock *BB = WorkList.pop_back_val();
 
712
    LPM->deleteSimpleAnalysisValue(BB, LP);
 
713
    for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); 
 
714
        BBI != BBE; ) {
 
715
      Instruction *I = BBI;
 
716
      ++BBI;
 
717
      I->replaceAllUsesWith(UndefValue::get(I->getType()));
 
718
      LPM->deleteSimpleAnalysisValue(I, LP);
 
719
      I->eraseFromParent();
 
720
    }
 
721
    DT->eraseNode(BB);
 
722
    DF->removeBlock(BB);
 
723
    LI->removeBlock(BB);
 
724
    BB->eraseFromParent();
 
725
  }
 
726
 
 
727
  // Update Frontier BBs' dominator info.
 
728
  while (!FrontierBBs.empty()) {
 
729
    BasicBlock *FBB = FrontierBBs.pop_back_val();
 
730
    BasicBlock *NewDominator = FBB->getSinglePredecessor();
 
731
    if (!NewDominator) {
 
732
      pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
 
733
      NewDominator = *PI;
 
734
      ++PI;
 
735
      if (NewDominator != LiveBB) {
 
736
        for(; PI != PE; ++PI) {
 
737
          BasicBlock *P = *PI;
 
738
          if (P == LiveBB) {
 
739
            NewDominator = LiveBB;
 
740
            break;
 
741
          }
 
742
          NewDominator = DT->findNearestCommonDominator(NewDominator, P);
 
743
        }
 
744
      }
 
745
    }
 
746
    assert (NewDominator && "Unable to fix dominator info.");
 
747
    DT->changeImmediateDominator(FBB, NewDominator);
 
748
    DF->changeImmediateDominator(FBB, NewDominator, DT);
 
749
  }
 
750
 
 
751
}
 
752
 
 
753
// moveExitCondition - Move exit condition EC into split condition block CondBB.
 
754
void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB,
 
755
                                       BasicBlock *ExitBB, ICmpInst *EC, 
 
756
                                       ICmpInst *SC, PHINode *IV, 
 
757
                                       Instruction *IVAdd, Loop *LP,
 
758
                                       unsigned ExitValueNum) {
 
759
 
 
760
  BasicBlock *ExitingBB = EC->getParent();
 
761
  Instruction *CurrentBR = CondBB->getTerminator();
 
762
 
 
763
  // Move exit condition into split condition block.
 
764
  EC->moveBefore(CurrentBR);
 
765
  EC->setOperand(ExitValueNum == 0 ? 1 : 0, IV);
 
766
 
 
767
  // Move exiting block's branch into split condition block. Update its branch
 
768
  // destination.
 
769
  BranchInst *ExitingBR = cast<BranchInst>(ExitingBB->getTerminator());
 
770
  ExitingBR->moveBefore(CurrentBR);
 
771
  BasicBlock *OrigDestBB = NULL;
 
772
  if (ExitingBR->getSuccessor(0) == ExitBB) {
 
773
    OrigDestBB = ExitingBR->getSuccessor(1);
 
774
    ExitingBR->setSuccessor(1, ActiveBB);
 
775
  }
 
776
  else {
 
777
    OrigDestBB = ExitingBR->getSuccessor(0);
 
778
    ExitingBR->setSuccessor(0, ActiveBB);
 
779
  }
 
780
    
 
781
  // Remove split condition and current split condition branch.
 
782
  SC->eraseFromParent();
 
783
  CurrentBR->eraseFromParent();
 
784
 
 
785
  // Connect exiting block to original destination.
 
786
  BranchInst::Create(OrigDestBB, ExitingBB);
 
787
 
 
788
  // Update PHINodes
 
789
  updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP);
 
790
 
 
791
  // Fix dominator info.
 
792
  // ExitBB is now dominated by CondBB
 
793
  DT->changeImmediateDominator(ExitBB, CondBB);
 
794
  DF->changeImmediateDominator(ExitBB, CondBB, DT);
 
795
 
 
796
  // Blocks outside the loop may have been in the dominance frontier of blocks
 
797
  // inside the condition; this is now impossible because the blocks inside the
 
798
  // condition no loger dominate the exit.  Remove the relevant blocks from
 
799
  // the dominance frontiers.
 
800
  for (Loop::block_iterator I = LP->block_begin(), E = LP->block_end();
 
801
       I != E; ++I) {
 
802
    if (!DT->properlyDominates(CondBB, *I)) continue;
 
803
    DominanceFrontier::iterator BBDF = DF->find(*I);
 
804
    DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
 
805
    DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
 
806
    while (DomSetI != DomSetE) {
 
807
      DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
 
808
      ++DomSetI;
 
809
      BasicBlock *DFBB = *CurrentItr;
 
810
      if (!LP->contains(DFBB))
 
811
        BBDF->second.erase(DFBB);
 
812
    }
 
813
  }
 
814
}
 
815
 
 
816
/// updatePHINodes - CFG has been changed. 
 
817
/// Before 
 
818
///   - ExitBB's single predecessor was Latch
 
819
///   - Latch's second successor was Header
 
820
/// Now
 
821
///   - ExitBB's single predecessor is Header
 
822
///   - Latch's one and only successor is Header
 
823
///
 
824
/// Update ExitBB PHINodes' to reflect this change.
 
825
void LoopIndexSplit::updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, 
 
826
                                    BasicBlock *Header,
 
827
                                    PHINode *IV, Instruction *IVIncrement,
 
828
                                    Loop *LP) {
 
829
 
 
830
  for (BasicBlock::iterator BI = ExitBB->begin(), BE = ExitBB->end(); 
 
831
       BI != BE; ) {
 
832
    PHINode *PN = dyn_cast<PHINode>(BI);
 
833
    ++BI;
 
834
    if (!PN)
 
835
      break;
 
836
 
 
837
    Value *V = PN->getIncomingValueForBlock(Latch);
 
838
    if (PHINode *PHV = dyn_cast<PHINode>(V)) {
 
839
      // PHV is in Latch. PHV has one use is in ExitBB PHINode. And one use
 
840
      // in Header which is new incoming value for PN.
 
841
      Value *NewV = NULL;
 
842
      for (Value::use_iterator UI = PHV->use_begin(), E = PHV->use_end(); 
 
843
           UI != E; ++UI) 
 
844
        if (PHINode *U = dyn_cast<PHINode>(*UI)) 
 
845
          if (LP->contains(U)) {
 
846
            NewV = U;
 
847
            break;
 
848
          }
 
849
 
 
850
      // Add incoming value from header only if PN has any use inside the loop.
 
851
      if (NewV)
 
852
        PN->addIncoming(NewV, Header);
 
853
 
 
854
    } else if (Instruction *PHI = dyn_cast<Instruction>(V)) {
 
855
      // If this instruction is IVIncrement then IV is new incoming value 
 
856
      // from header otherwise this instruction must be incoming value from 
 
857
      // header because loop is in LCSSA form.
 
858
      if (PHI == IVIncrement)
 
859
        PN->addIncoming(IV, Header);
 
860
      else
 
861
        PN->addIncoming(V, Header);
 
862
    } else
 
863
      // Otherwise this is an incoming value from header because loop is in 
 
864
      // LCSSA form.
 
865
      PN->addIncoming(V, Header);
 
866
    
 
867
    // Remove incoming value from Latch.
 
868
    PN->removeIncomingValue(Latch);
 
869
  }
 
870
}
 
871
 
 
872
bool LoopIndexSplit::splitLoop() {
 
873
  SplitCondition = NULL;
 
874
  if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE
 
875
      || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 
876
    return false;
 
877
  BasicBlock *Header = L->getHeader();
 
878
  BasicBlock *Latch = L->getLoopLatch();
 
879
  BranchInst *SBR = NULL; // Split Condition Branch
 
880
  BranchInst *EBR = cast<BranchInst>(ExitCondition->getParent()->getTerminator());
 
881
  // If Exiting block includes loop variant instructions then this
 
882
  // loop may not be split safely.
 
883
  BasicBlock *ExitingBlock = ExitCondition->getParent();
 
884
  if (!cleanBlock(ExitingBlock)) return false;
 
885
 
 
886
  LLVMContext &Context = Header->getContext();
 
887
 
 
888
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
889
       I != E; ++I) {
 
890
    BranchInst *BR = dyn_cast<BranchInst>((*I)->getTerminator());
 
891
    if (!BR || BR->isUnconditional()) continue;
 
892
    ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 
893
    if (!CI || CI == ExitCondition 
 
894
        || CI->getPredicate() == ICmpInst::ICMP_NE
 
895
        || CI->getPredicate() == ICmpInst::ICMP_EQ)
 
896
      continue;
 
897
 
 
898
    // Unable to handle triangle loops at the moment.
 
899
    // In triangle loop, split condition is in header and one of the
 
900
    // the split destination is loop latch. If split condition is EQ
 
901
    // then such loops are already handle in processOneIterationLoop().
 
902
    if (Header == (*I)
 
903
        && (Latch == BR->getSuccessor(0) || Latch == BR->getSuccessor(1)))
 
904
      continue;
 
905
 
 
906
    // If the block does not dominate the latch then this is not a diamond.
 
907
    // Such loop may not benefit from index split.
 
908
    if (!DT->dominates((*I), Latch))
 
909
      continue;
 
910
 
 
911
    // If split condition branches heads do not have single predecessor, 
 
912
    // SplitCondBlock, then is not possible to remove inactive branch.
 
913
    if (!BR->getSuccessor(0)->getSinglePredecessor() 
 
914
        || !BR->getSuccessor(1)->getSinglePredecessor())
 
915
      return false;
 
916
 
 
917
    // If the merge point for BR is not loop latch then skip this condition.
 
918
    if (BR->getSuccessor(0) != Latch) {
 
919
      DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
 
920
      assert (DF0 != DF->end() && "Unable to find dominance frontier");
 
921
      if (!DF0->second.count(Latch))
 
922
        continue;
 
923
    }
 
924
    
 
925
    if (BR->getSuccessor(1) != Latch) {
 
926
      DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
 
927
      assert (DF1 != DF->end() && "Unable to find dominance frontier");
 
928
      if (!DF1->second.count(Latch))
 
929
        continue;
 
930
    }
 
931
    SplitCondition = CI;
 
932
    SBR = BR;
 
933
    break;
 
934
  }
 
935
   
 
936
  if (!SplitCondition)
 
937
    return false;
 
938
 
 
939
  // If the predicate sign does not match then skip.
 
940
  if (ExitCondition->isSigned() != SplitCondition->isSigned())
 
941
    return false;
 
942
 
 
943
  unsigned EVOpNum = (ExitCondition->getOperand(1) == IVExitValue);
 
944
  unsigned SVOpNum = IVBasedValues.count(SplitCondition->getOperand(0));
 
945
  Value *SplitValue = SplitCondition->getOperand(SVOpNum);
 
946
  if (!L->isLoopInvariant(SplitValue))
 
947
    return false;
 
948
  if (!IVBasedValues.count(SplitCondition->getOperand(!SVOpNum)))
 
949
    return false;
 
950
 
 
951
  // Check for side effects.
 
952
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
953
       I != E; ++I) {
 
954
    BasicBlock *BB = *I;
 
955
 
 
956
    assert(DT->dominates(Header, BB));
 
957
    if (DT->properlyDominates(SplitCondition->getParent(), BB))
 
958
      continue;
 
959
 
 
960
    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 
961
         BI != BE; ++BI) {
 
962
      Instruction *Inst = BI;
 
963
 
 
964
      if (!Inst->isSafeToSpeculativelyExecute() && !isa<PHINode>(Inst)
 
965
          && !isa<BranchInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst))
 
966
        return false;
 
967
    }
 
968
  }
 
969
 
 
970
  // Normalize loop conditions so that it is easier to calculate new loop
 
971
  // bounds.
 
972
  if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) {
 
973
    ExitCondition->setPredicate(ExitCondition->getInversePredicate());
 
974
    BasicBlock *T = EBR->getSuccessor(0);
 
975
    EBR->setSuccessor(0, EBR->getSuccessor(1));
 
976
    EBR->setSuccessor(1, T);
 
977
  }
 
978
 
 
979
  if (IVisGT(*SplitCondition) || IVisGE(*SplitCondition)) {
 
980
    SplitCondition->setPredicate(SplitCondition->getInversePredicate());
 
981
    BasicBlock *T = SBR->getSuccessor(0);
 
982
    SBR->setSuccessor(0, SBR->getSuccessor(1));
 
983
    SBR->setSuccessor(1, T);
 
984
  }
 
985
 
 
986
  //[*] Calculate new loop bounds.
 
987
  Value *AEV = SplitValue;
 
988
  Value *BSV = SplitValue;
 
989
  bool Sign = SplitCondition->isSigned();
 
990
  Instruction *PHTerm = L->getLoopPreheader()->getTerminator();
 
991
 
 
992
  if (IVisLT(*ExitCondition)) {
 
993
    if (IVisLT(*SplitCondition)) {
 
994
      /* Do nothing */
 
995
    }
 
996
    else if (IVisLE(*SplitCondition)) {
 
997
      AEV = getPlusOne(SplitValue, Sign, PHTerm, Context);
 
998
      BSV = getPlusOne(SplitValue, Sign, PHTerm, Context);
 
999
    } else {
 
1000
      assert (0 && "Unexpected split condition!");
 
1001
    }
 
1002
  }
 
1003
  else if (IVisLE(*ExitCondition)) {
 
1004
    if (IVisLT(*SplitCondition)) {
 
1005
      AEV = getMinusOne(SplitValue, Sign, PHTerm, Context);
 
1006
    }
 
1007
    else if (IVisLE(*SplitCondition)) {
 
1008
      BSV = getPlusOne(SplitValue, Sign, PHTerm, Context);
 
1009
    } else {
 
1010
      assert (0 && "Unexpected split condition!");
 
1011
    }
 
1012
  } else {
 
1013
    assert (0 && "Unexpected exit condition!");
 
1014
  }
 
1015
  AEV = getMin(AEV, IVExitValue, Sign, PHTerm);
 
1016
  BSV = getMax(BSV, IVStartValue, Sign, PHTerm);
 
1017
 
 
1018
  // [*] Clone Loop
 
1019
  ValueMap<const Value *, Value *> VMap;
 
1020
  Loop *BLoop = CloneLoop(L, LPM, LI, VMap, this);
 
1021
  Loop *ALoop = L;
 
1022
 
 
1023
  // [*] ALoop's exiting edge enters BLoop's header.
 
1024
  //    ALoop's original exit block becomes BLoop's exit block.
 
1025
  PHINode *B_IndVar = cast<PHINode>(VMap[IndVar]);
 
1026
  BasicBlock *A_ExitingBlock = ExitCondition->getParent();
 
1027
  BranchInst *A_ExitInsn =
 
1028
    dyn_cast<BranchInst>(A_ExitingBlock->getTerminator());
 
1029
  assert (A_ExitInsn && "Unable to find suitable loop exit branch");
 
1030
  BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1);
 
1031
  BasicBlock *B_Header = BLoop->getHeader();
 
1032
  if (ALoop->contains(B_ExitBlock)) {
 
1033
    B_ExitBlock = A_ExitInsn->getSuccessor(0);
 
1034
    A_ExitInsn->setSuccessor(0, B_Header);
 
1035
  } else
 
1036
    A_ExitInsn->setSuccessor(1, B_Header);
 
1037
 
 
1038
  // [*] Update ALoop's exit value using new exit value.
 
1039
  ExitCondition->setOperand(EVOpNum, AEV);
 
1040
 
 
1041
  // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from
 
1042
  //     original loop's preheader. Add incoming PHINode values from
 
1043
  //     ALoop's exiting block. Update BLoop header's domiantor info.
 
1044
 
 
1045
  // Collect inverse map of Header PHINodes.
 
1046
  DenseMap<Value *, Value *> InverseMap;
 
1047
  for (BasicBlock::iterator BI = ALoop->getHeader()->begin(), 
 
1048
         BE = ALoop->getHeader()->end(); BI != BE; ++BI) {
 
1049
    if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 
1050
      PHINode *PNClone = cast<PHINode>(VMap[PN]);
 
1051
      InverseMap[PNClone] = PN;
 
1052
    } else
 
1053
      break;
 
1054
  }
 
1055
 
 
1056
  BasicBlock *A_Preheader = ALoop->getLoopPreheader();
 
1057
  for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 
1058
       BI != BE; ++BI) {
 
1059
    if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 
1060
      // Remove incoming value from original preheader.
 
1061
      PN->removeIncomingValue(A_Preheader);
 
1062
 
 
1063
      // Add incoming value from A_ExitingBlock.
 
1064
      if (PN == B_IndVar)
 
1065
        PN->addIncoming(BSV, A_ExitingBlock);
 
1066
      else { 
 
1067
        PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
 
1068
        Value *V2 = NULL;
 
1069
        // If loop header is also loop exiting block then
 
1070
        // OrigPN is incoming value for B loop header.
 
1071
        if (A_ExitingBlock == ALoop->getHeader())
 
1072
          V2 = OrigPN;
 
1073
        else
 
1074
          V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock);
 
1075
        PN->addIncoming(V2, A_ExitingBlock);
 
1076
      }
 
1077
    } else
 
1078
      break;
 
1079
  }
 
1080
 
 
1081
  DT->changeImmediateDominator(B_Header, A_ExitingBlock);
 
1082
  DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT);
 
1083
  
 
1084
  // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit
 
1085
  //     block. Remove incoming PHINode values from ALoop's exiting block.
 
1086
  //     Add new incoming values from BLoop's incoming exiting value.
 
1087
  //     Update BLoop exit block's dominator info..
 
1088
  BasicBlock *B_ExitingBlock = cast<BasicBlock>(VMap[A_ExitingBlock]);
 
1089
  for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end();
 
1090
       BI != BE; ++BI) {
 
1091
    if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 
1092
      PN->addIncoming(VMap[PN->getIncomingValueForBlock(A_ExitingBlock)], 
 
1093
                                                            B_ExitingBlock);
 
1094
      PN->removeIncomingValue(A_ExitingBlock);
 
1095
    } else
 
1096
      break;
 
1097
  }
 
1098
 
 
1099
  DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
 
1100
  DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
 
1101
 
 
1102
  //[*] Split ALoop's exit edge. This creates a new block which
 
1103
  //    serves two purposes. First one is to hold PHINode defnitions
 
1104
  //    to ensure that ALoop's LCSSA form. Second use it to act
 
1105
  //    as a preheader for BLoop.
 
1106
  BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this);
 
1107
 
 
1108
  //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes
 
1109
  //    in A_ExitBlock to redefine outgoing PHI definitions from ALoop.
 
1110
  for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 
1111
      BI != BE; ++BI) {
 
1112
    if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 
1113
      Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock);
 
1114
      PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName());
 
1115
      newPHI->addIncoming(V1, A_ExitingBlock);
 
1116
      A_ExitBlock->getInstList().push_front(newPHI);
 
1117
      PN->removeIncomingValue(A_ExitBlock);
 
1118
      PN->addIncoming(newPHI, A_ExitBlock);
 
1119
    } else
 
1120
      break;
 
1121
  }
 
1122
 
 
1123
  //[*] Eliminate split condition's inactive branch from ALoop.
 
1124
  BasicBlock *A_SplitCondBlock = SplitCondition->getParent();
 
1125
  BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator());
 
1126
  BasicBlock *A_InactiveBranch = NULL;
 
1127
  BasicBlock *A_ActiveBranch = NULL;
 
1128
  A_ActiveBranch = A_BR->getSuccessor(0);
 
1129
  A_InactiveBranch = A_BR->getSuccessor(1);
 
1130
  A_BR->setUnconditionalDest(A_ActiveBranch);
 
1131
  removeBlocks(A_InactiveBranch, L, A_ActiveBranch);
 
1132
 
 
1133
  //[*] Eliminate split condition's inactive branch in from BLoop.
 
1134
  BasicBlock *B_SplitCondBlock = cast<BasicBlock>(VMap[A_SplitCondBlock]);
 
1135
  BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator());
 
1136
  BasicBlock *B_InactiveBranch = NULL;
 
1137
  BasicBlock *B_ActiveBranch = NULL;
 
1138
  B_ActiveBranch = B_BR->getSuccessor(1);
 
1139
  B_InactiveBranch = B_BR->getSuccessor(0);
 
1140
  B_BR->setUnconditionalDest(B_ActiveBranch);
 
1141
  removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch);
 
1142
 
 
1143
  BasicBlock *A_Header = ALoop->getHeader();
 
1144
  if (A_ExitingBlock == A_Header)
 
1145
    return true;
 
1146
 
 
1147
  //[*] Move exit condition into split condition block to avoid
 
1148
  //    executing dead loop iteration.
 
1149
  ICmpInst *B_ExitCondition = cast<ICmpInst>(VMap[ExitCondition]);
 
1150
  Instruction *B_IndVarIncrement = cast<Instruction>(VMap[IVIncrement]);
 
1151
  ICmpInst *B_SplitCondition = cast<ICmpInst>(VMap[SplitCondition]);
 
1152
 
 
1153
  moveExitCondition(A_SplitCondBlock, A_ActiveBranch, A_ExitBlock, ExitCondition,
 
1154
                    cast<ICmpInst>(SplitCondition), IndVar, IVIncrement, 
 
1155
                    ALoop, EVOpNum);
 
1156
 
 
1157
  moveExitCondition(B_SplitCondBlock, B_ActiveBranch, 
 
1158
                    B_ExitBlock, B_ExitCondition,
 
1159
                    B_SplitCondition, B_IndVar, B_IndVarIncrement, 
 
1160
                    BLoop, EVOpNum);
 
1161
 
 
1162
  ++NumIndexSplit;
 
1163
  return true;
 
1164
}
 
1165
 
 
1166
/// cleanBlock - A block is considered clean if all non terminal instructions 
 
1167
/// are either, PHINodes, IV based.
 
1168
bool LoopIndexSplit::cleanBlock(BasicBlock *BB) {
 
1169
  Instruction *Terminator = BB->getTerminator();
 
1170
  for(BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 
 
1171
      BI != BE; ++BI) {
 
1172
    Instruction *I = BI;
 
1173
 
 
1174
    if (isa<PHINode>(I) || I == Terminator || I == ExitCondition
 
1175
        || I == SplitCondition || IVBasedValues.count(I) 
 
1176
        || isa<DbgInfoIntrinsic>(I))
 
1177
      continue;
 
1178
 
 
1179
    if (I->mayHaveSideEffects())
 
1180
      return false;
 
1181
 
 
1182
    // I is used only inside this block then it is OK.
 
1183
    bool usedOutsideBB = false;
 
1184
    for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 
 
1185
         UI != UE; ++UI) {
 
1186
      Instruction *U = cast<Instruction>(*UI);
 
1187
      if (U->getParent() != BB)
 
1188
        usedOutsideBB = true;
 
1189
    }
 
1190
    if (!usedOutsideBB)
 
1191
      continue;
 
1192
 
 
1193
    // Otherwise we have a instruction that may not allow loop spliting.
 
1194
    return false;
 
1195
  }
 
1196
  return true;
 
1197
}
 
1198
 
 
1199
/// IVisLT - If Op is comparing IV based value with an loop invariant and 
 
1200
/// IV based value is less than  the loop invariant then return the loop 
 
1201
/// invariant. Otherwise return NULL.
 
1202
Value * LoopIndexSplit::IVisLT(ICmpInst &Op) {
 
1203
  ICmpInst::Predicate P = Op.getPredicate();
 
1204
  if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) 
 
1205
      && IVBasedValues.count(Op.getOperand(0)) 
 
1206
      && L->isLoopInvariant(Op.getOperand(1)))
 
1207
    return Op.getOperand(1);
 
1208
 
 
1209
  if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) 
 
1210
      && IVBasedValues.count(Op.getOperand(1)) 
 
1211
      && L->isLoopInvariant(Op.getOperand(0)))
 
1212
    return Op.getOperand(0);
 
1213
 
 
1214
  return NULL;
 
1215
}
 
1216
 
 
1217
/// IVisLE - If Op is comparing IV based value with an loop invariant and 
 
1218
/// IV based value is less than or equal to the loop invariant then 
 
1219
/// return the loop invariant. Otherwise return NULL.
 
1220
Value * LoopIndexSplit::IVisLE(ICmpInst &Op) {
 
1221
  ICmpInst::Predicate P = Op.getPredicate();
 
1222
  if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE)
 
1223
      && IVBasedValues.count(Op.getOperand(0)) 
 
1224
      && L->isLoopInvariant(Op.getOperand(1)))
 
1225
    return Op.getOperand(1);
 
1226
 
 
1227
  if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE) 
 
1228
      && IVBasedValues.count(Op.getOperand(1)) 
 
1229
      && L->isLoopInvariant(Op.getOperand(0)))
 
1230
    return Op.getOperand(0);
 
1231
 
 
1232
  return NULL;
 
1233
}
 
1234
 
 
1235
/// IVisGT - If Op is comparing IV based value with an loop invariant and 
 
1236
/// IV based value is greater than  the loop invariant then return the loop 
 
1237
/// invariant. Otherwise return NULL.
 
1238
Value * LoopIndexSplit::IVisGT(ICmpInst &Op) {
 
1239
  ICmpInst::Predicate P = Op.getPredicate();
 
1240
  if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) 
 
1241
      && IVBasedValues.count(Op.getOperand(0)) 
 
1242
      && L->isLoopInvariant(Op.getOperand(1)))
 
1243
    return Op.getOperand(1);
 
1244
 
 
1245
  if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) 
 
1246
      && IVBasedValues.count(Op.getOperand(1)) 
 
1247
      && L->isLoopInvariant(Op.getOperand(0)))
 
1248
    return Op.getOperand(0);
 
1249
 
 
1250
  return NULL;
 
1251
}
 
1252
 
 
1253
/// IVisGE - If Op is comparing IV based value with an loop invariant and 
 
1254
/// IV based value is greater than or equal to the loop invariant then 
 
1255
/// return the loop invariant. Otherwise return NULL.
 
1256
Value * LoopIndexSplit::IVisGE(ICmpInst &Op) {
 
1257
  ICmpInst::Predicate P = Op.getPredicate();
 
1258
  if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE)
 
1259
      && IVBasedValues.count(Op.getOperand(0)) 
 
1260
      && L->isLoopInvariant(Op.getOperand(1)))
 
1261
    return Op.getOperand(1);
 
1262
 
 
1263
  if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE) 
 
1264
      && IVBasedValues.count(Op.getOperand(1)) 
 
1265
      && L->isLoopInvariant(Op.getOperand(0)))
 
1266
    return Op.getOperand(0);
 
1267
 
 
1268
  return NULL;
 
1269
}
 
1270