blob: bddaba5a15c4018f25189dd84c2f0127f8de17e2 [file] [log] [blame]
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +00001//===- LoopInstSimplify.cpp - Loop Instruction Simplification 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 pass performs lightweight instruction simplification on loop bodies.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "loop-instsimplify"
Chandler Carruthed0881b2012-12-03 16:50:05 +000015#include "llvm/Transforms/Scalar.h"
Jakub Staszakf23980a2013-02-09 01:04:28 +000016#include "llvm/ADT/STLExtras.h"
Chandler Carruth8a8cd2b2014-01-07 11:48:04 +000017#include "llvm/ADT/Statistic.h"
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000018#include "llvm/Analysis/InstructionSimplify.h"
Cameron Zwariche9249692011-01-04 00:12:46 +000019#include "llvm/Analysis/LoopInfo.h"
Cameron Zwarich4c51d122011-01-05 05:15:53 +000020#include "llvm/Analysis/LoopPass.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000021#include "llvm/IR/DataLayout.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000022#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000023#include "llvm/IR/Instructions.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000024#include "llvm/Support/Debug.h"
Chad Rosierc24b86f2011-12-01 03:08:23 +000025#include "llvm/Target/TargetLibraryInfo.h"
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000026#include "llvm/Transforms/Utils/Local.h"
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000027using namespace llvm;
28
29STATISTIC(NumSimplified, "Number of redundant instructions simplified");
30
31namespace {
Cameron Zwarich4c51d122011-01-05 05:15:53 +000032 class LoopInstSimplify : public LoopPass {
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000033 public:
34 static char ID; // Pass ID, replacement for typeid
Cameron Zwarich4c51d122011-01-05 05:15:53 +000035 LoopInstSimplify() : LoopPass(ID) {
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000036 initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry());
37 }
38
Cameron Zwarich4c51d122011-01-05 05:15:53 +000039 bool runOnLoop(Loop*, LPPassManager&);
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000040
Cameron Zwarichb2a41e92011-01-04 18:19:19 +000041 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000042 AU.setPreservesCFG();
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000043 AU.addRequired<LoopInfo>();
Cameron Zwarich4c51d122011-01-05 05:15:53 +000044 AU.addRequiredID(LoopSimplifyID);
Cameron Zwaricha42e5912011-01-09 12:35:16 +000045 AU.addPreservedID(LoopSimplifyID);
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000046 AU.addPreservedID(LCSSAID);
Cameron Zwarich25cb63c2011-02-11 06:08:25 +000047 AU.addPreserved("scalar-evolution");
Chad Rosierc24b86f2011-12-01 03:08:23 +000048 AU.addRequired<TargetLibraryInfo>();
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000049 }
50 };
51}
Nadav Rotem465834c2012-07-24 10:51:42 +000052
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000053char LoopInstSimplify::ID = 0;
54INITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify",
55 "Simplify instructions in loops", false, false)
Chad Rosierc24b86f2011-12-01 03:08:23 +000056INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
Chandler Carruth73523022014-01-13 13:07:17 +000057INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000058INITIALIZE_PASS_DEPENDENCY(LoopInfo)
59INITIALIZE_PASS_DEPENDENCY(LCSSA)
60INITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify",
61 "Simplify instructions in loops", false, false)
62
Cameron Zwarichb4ab2572011-01-08 17:07:11 +000063Pass *llvm::createLoopInstSimplifyPass() {
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000064 return new LoopInstSimplify();
65}
66
Cameron Zwarich4c51d122011-01-05 05:15:53 +000067bool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
Paul Robinsonaf4e64d2014-02-06 00:07:05 +000068 if (skipOptnoneFunction(L))
69 return false;
70
Chandler Carruth73523022014-01-13 13:07:17 +000071 DominatorTreeWrapperPass *DTWP =
72 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
73 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : 0;
Cameron Zwarichb2a41e92011-01-04 18:19:19 +000074 LoopInfo *LI = &getAnalysis<LoopInfo>();
Rafael Espindola93512512014-02-25 17:30:31 +000075 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
76 const DataLayout *DL = DLP ? &DLP->getDataLayout() : 0;
Chad Rosierc24b86f2011-12-01 03:08:23 +000077 const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>();
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000078
Cameron Zwarich4c51d122011-01-05 05:15:53 +000079 SmallVector<BasicBlock*, 8> ExitBlocks;
80 L->getUniqueExitBlocks(ExitBlocks);
81 array_pod_sort(ExitBlocks.begin(), ExitBlocks.end());
82
Cameron Zwarich5a2bb992011-01-05 05:47:47 +000083 SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
84
Cameron Zwarich80bd9af2011-01-08 15:52:22 +000085 // The bit we are stealing from the pointer represents whether this basic
86 // block is the header of a subloop, in which case we only process its phis.
87 typedef PointerIntPair<BasicBlock*, 1> WorklistItem;
88 SmallVector<WorklistItem, 16> VisitStack;
Cameron Zwarich4c51d122011-01-05 05:15:53 +000089 SmallPtrSet<BasicBlock*, 32> Visited;
90
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +000091 bool Changed = false;
92 bool LocalChanged;
93 do {
94 LocalChanged = false;
95
Cameron Zwarich4c51d122011-01-05 05:15:53 +000096 VisitStack.clear();
97 Visited.clear();
98
Cameron Zwarich80bd9af2011-01-08 15:52:22 +000099 VisitStack.push_back(WorklistItem(L->getHeader(), false));
Cameron Zwarich4c51d122011-01-05 05:15:53 +0000100
101 while (!VisitStack.empty()) {
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000102 WorklistItem Item = VisitStack.pop_back_val();
Cameron Zwarichb4ab2572011-01-08 17:07:11 +0000103 BasicBlock *BB = Item.getPointer();
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000104 bool IsSubloopHeader = Item.getInt();
Cameron Zwarich4c51d122011-01-05 05:15:53 +0000105
106 // Simplify instructions in the current basic block.
107 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
Cameron Zwarichb2a41e92011-01-04 18:19:19 +0000108 Instruction *I = BI++;
Cameron Zwarich5a2bb992011-01-05 05:47:47 +0000109
110 // The first time through the loop ToSimplify is empty and we try to
111 // simplify all instructions. On later iterations ToSimplify is not
112 // empty and we only bother simplifying instructions that are in it.
113 if (!ToSimplify->empty() && !ToSimplify->count(I))
114 continue;
115
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000116 // Don't bother simplifying unused instructions.
117 if (!I->use_empty()) {
Rafael Espindola612886f2014-02-21 01:53:35 +0000118 Value *V = SimplifyInstruction(I, DL, TLI, DT);
Cameron Zwariche9249692011-01-04 00:12:46 +0000119 if (V && LI->replacementPreservesLCSSAForm(I, V)) {
Cameron Zwarich5a2bb992011-01-05 05:47:47 +0000120 // Mark all uses for resimplification next time round the loop.
121 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
122 UI != UE; ++UI)
123 Next->insert(cast<Instruction>(*UI));
124
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000125 I->replaceAllUsesWith(V);
126 LocalChanged = true;
127 ++NumSimplified;
128 }
129 }
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000130 LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000131
132 if (IsSubloopHeader && !isa<PHINode>(I))
133 break;
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000134 }
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000135
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000136 // Add all successors to the worklist, except for loop exit blocks and the
137 // bodies of subloops. We visit the headers of loops so that we can process
138 // their phis, but we contract the rest of the subloop body and only follow
139 // edges leading back to the original loop.
Cameron Zwarich4c51d122011-01-05 05:15:53 +0000140 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
141 ++SI) {
142 BasicBlock *SuccBB = *SI;
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000143 if (!Visited.insert(SuccBB))
144 continue;
145
146 const Loop *SuccLoop = LI->getLoopFor(SuccBB);
147 if (SuccLoop && SuccLoop->getHeader() == SuccBB
148 && L->contains(SuccLoop)) {
149 VisitStack.push_back(WorklistItem(SuccBB, true));
150
151 SmallVector<BasicBlock*, 8> SubLoopExitBlocks;
152 SuccLoop->getExitBlocks(SubLoopExitBlocks);
153
154 for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) {
155 BasicBlock *ExitBB = SubLoopExitBlocks[i];
156 if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB))
157 VisitStack.push_back(WorklistItem(ExitBB, false));
158 }
159
160 continue;
161 }
162
Cameron Zwarich4c51d122011-01-05 05:15:53 +0000163 bool IsExitBlock = std::binary_search(ExitBlocks.begin(),
Cameron Zwarich80bd9af2011-01-08 15:52:22 +0000164 ExitBlocks.end(), SuccBB);
165 if (IsExitBlock)
166 continue;
167
168 VisitStack.push_back(WorklistItem(SuccBB, false));
Cameron Zwarich4c51d122011-01-05 05:15:53 +0000169 }
170 }
171
Cameron Zwarich5a2bb992011-01-05 05:47:47 +0000172 // Place the list of instructions to simplify on the next loop iteration
173 // into ToSimplify.
174 std::swap(ToSimplify, Next);
175 Next->clear();
176
Cameron Zwariche9249692011-01-04 00:12:46 +0000177 Changed |= LocalChanged;
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000178 } while (LocalChanged);
179
Cameron Zwarichcab9a0a2011-01-03 00:25:16 +0000180 return Changed;
181}