1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
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 pass performs lightweight instruction simplification on loop bodies.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "loop-instsimplify"
15 #include "llvm/Instructions.h"
16 #include "llvm/Analysis/Dominators.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Target/TargetData.h"
22 #include "llvm/Transforms/Scalar.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "llvm/ADT/Statistic.h"
27 STATISTIC(NumSimplified
, "Number of redundant instructions simplified");
30 class LoopInstSimplify
: public LoopPass
{
32 static char ID
; // Pass ID, replacement for typeid
33 LoopInstSimplify() : LoopPass(ID
) {
34 initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry());
37 bool runOnLoop(Loop
*, LPPassManager
&);
39 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
41 AU
.addRequired
<LoopInfo
>();
42 AU
.addRequiredID(LoopSimplifyID
);
43 AU
.addPreservedID(LoopSimplifyID
);
44 AU
.addPreservedID(LCSSAID
);
49 char LoopInstSimplify::ID
= 0;
50 INITIALIZE_PASS_BEGIN(LoopInstSimplify
, "loop-instsimplify",
51 "Simplify instructions in loops", false, false)
52 INITIALIZE_PASS_DEPENDENCY(DominatorTree
)
53 INITIALIZE_PASS_DEPENDENCY(LoopInfo
)
54 INITIALIZE_PASS_DEPENDENCY(LCSSA
)
55 INITIALIZE_PASS_END(LoopInstSimplify
, "loop-instsimplify",
56 "Simplify instructions in loops", false, false)
58 Pass
*llvm::createLoopInstSimplifyPass() {
59 return new LoopInstSimplify();
62 bool LoopInstSimplify::runOnLoop(Loop
*L
, LPPassManager
&LPM
) {
63 DominatorTree
*DT
= getAnalysisIfAvailable
<DominatorTree
>();
64 LoopInfo
*LI
= &getAnalysis
<LoopInfo
>();
65 const TargetData
*TD
= getAnalysisIfAvailable
<TargetData
>();
67 SmallVector
<BasicBlock
*, 8> ExitBlocks
;
68 L
->getUniqueExitBlocks(ExitBlocks
);
69 array_pod_sort(ExitBlocks
.begin(), ExitBlocks
.end());
71 SmallPtrSet
<const Instruction
*, 8> S1
, S2
, *ToSimplify
= &S1
, *Next
= &S2
;
73 // The bit we are stealing from the pointer represents whether this basic
74 // block is the header of a subloop, in which case we only process its phis.
75 typedef PointerIntPair
<BasicBlock
*, 1> WorklistItem
;
76 SmallVector
<WorklistItem
, 16> VisitStack
;
77 SmallPtrSet
<BasicBlock
*, 32> Visited
;
87 VisitStack
.push_back(WorklistItem(L
->getHeader(), false));
89 while (!VisitStack
.empty()) {
90 WorklistItem Item
= VisitStack
.pop_back_val();
91 BasicBlock
*BB
= Item
.getPointer();
92 bool IsSubloopHeader
= Item
.getInt();
94 // Simplify instructions in the current basic block.
95 for (BasicBlock::iterator BI
= BB
->begin(), BE
= BB
->end(); BI
!= BE
;) {
96 Instruction
*I
= BI
++;
98 // The first time through the loop ToSimplify is empty and we try to
99 // simplify all instructions. On later iterations ToSimplify is not
100 // empty and we only bother simplifying instructions that are in it.
101 if (!ToSimplify
->empty() && !ToSimplify
->count(I
))
104 // Don't bother simplifying unused instructions.
105 if (!I
->use_empty()) {
106 Value
*V
= SimplifyInstruction(I
, TD
, DT
);
107 if (V
&& LI
->replacementPreservesLCSSAForm(I
, V
)) {
108 // Mark all uses for resimplification next time round the loop.
109 for (Value::use_iterator UI
= I
->use_begin(), UE
= I
->use_end();
111 Next
->insert(cast
<Instruction
>(*UI
));
113 I
->replaceAllUsesWith(V
);
118 LocalChanged
|= RecursivelyDeleteTriviallyDeadInstructions(I
);
120 if (IsSubloopHeader
&& !isa
<PHINode
>(I
))
124 // Add all successors to the worklist, except for loop exit blocks and the
125 // bodies of subloops. We visit the headers of loops so that we can process
126 // their phis, but we contract the rest of the subloop body and only follow
127 // edges leading back to the original loop.
128 for (succ_iterator SI
= succ_begin(BB
), SE
= succ_end(BB
); SI
!= SE
;
130 BasicBlock
*SuccBB
= *SI
;
131 if (!Visited
.insert(SuccBB
))
134 const Loop
*SuccLoop
= LI
->getLoopFor(SuccBB
);
135 if (SuccLoop
&& SuccLoop
->getHeader() == SuccBB
136 && L
->contains(SuccLoop
)) {
137 VisitStack
.push_back(WorklistItem(SuccBB
, true));
139 SmallVector
<BasicBlock
*, 8> SubLoopExitBlocks
;
140 SuccLoop
->getExitBlocks(SubLoopExitBlocks
);
142 for (unsigned i
= 0; i
< SubLoopExitBlocks
.size(); ++i
) {
143 BasicBlock
*ExitBB
= SubLoopExitBlocks
[i
];
144 if (LI
->getLoopFor(ExitBB
) == L
&& Visited
.insert(ExitBB
))
145 VisitStack
.push_back(WorklistItem(ExitBB
, false));
151 bool IsExitBlock
= std::binary_search(ExitBlocks
.begin(),
152 ExitBlocks
.end(), SuccBB
);
156 VisitStack
.push_back(WorklistItem(SuccBB
, false));
160 // Place the list of instructions to simplify on the next loop iteration
162 std::swap(ToSimplify
, Next
);
165 Changed
|= LocalChanged
;
166 } while (LocalChanged
);