Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #include "llvm-version.h"
4 : : #include "passes.h"
5 : :
6 : : #include <llvm/Analysis/LoopInfo.h>
7 : : #include <llvm/Analysis/LoopPass.h>
8 : : #include <llvm/Analysis/LoopIterator.h>
9 : : #include <llvm/Analysis/MemorySSA.h>
10 : : #include <llvm/Analysis/MemorySSAUpdater.h>
11 : : #include <llvm/Analysis/ValueTracking.h>
12 : : #include <llvm/Analysis/ScalarEvolution.h>
13 : : #include <llvm/ADT/Statistic.h>
14 : : #include <llvm/IR/Dominators.h>
15 : : #include <llvm/IR/LegacyPassManager.h>
16 : : #include <llvm/IR/Verifier.h>
17 : : #include <llvm/Transforms/Utils/LoopUtils.h>
18 : :
19 : : #include "llvm-pass-helpers.h"
20 : : #include "julia.h"
21 : : #include "llvm-alloc-helpers.h"
22 : : #include "codegen_shared.h"
23 : :
24 : : #define DEBUG_TYPE "julia-licm"
25 : :
26 : : using namespace llvm;
27 : :
28 : : STATISTIC(HoistedPreserveBegin, "Number of gc_preserve_begin instructions hoisted out of a loop");
29 : : STATISTIC(SunkPreserveEnd, "Number of gc_preserve_end instructions sunk out of a loop");
30 : : STATISTIC(ErasedPreserveEnd, "Number of gc_preserve_end instructions removed from nonterminating loops");
31 : : STATISTIC(HoistedWriteBarrier, "Number of write barriers hoisted out of a loop");
32 : : STATISTIC(HoistedAllocation, "Number of allocations hoisted out of a loop");
33 : :
34 : : /*
35 : : * Julia LICM pass.
36 : : * This takes care of some julia intrinsics that is safe to move around/out of loops but
37 : : * can't be handled by LLVM's LICM. These intrinsics can be moved outside of
38 : : * loop context as well but it is inside a loop where they matter the most.
39 : : */
40 : :
41 : : namespace {
42 : :
43 : : //Stolen and modified from LICM.cpp
44 : 0 : static void eraseInstruction(Instruction &I,
45 : : MemorySSAUpdater &MSSAU) {
46 [ # # ]: 0 : if (MSSAU.getMemorySSA())
47 : 0 : MSSAU.removeMemoryAccess(&I);
48 : 0 : I.eraseFromParent();
49 : 0 : }
50 : :
51 : : //Stolen and modified from LICM.cpp
52 : 9867 : static void moveInstructionBefore(Instruction &I, Instruction &Dest,
53 : : MemorySSAUpdater &MSSAU,
54 : : ScalarEvolution *SE) {
55 : 9867 : I.moveBefore(&Dest);
56 [ - + ]: 9867 : if (MSSAU.getMemorySSA())
57 [ # # ]: 0 : if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
58 : : MSSAU.getMemorySSA()->getMemoryAccess(&I)))
59 : 0 : MSSAU.moveToPlace(OldMemAcc, Dest.getParent(),
60 : : MemorySSA::BeforeTerminator);
61 [ - + ]: 9867 : if (SE)
62 : 0 : SE->forgetValue(&I);
63 : 9867 : }
64 : :
65 : 22454 : static void createNewInstruction(Instruction *New, Instruction *Ref, MemorySSAUpdater &MSSAU) {
66 [ - + - - : 22454 : if (MSSAU.getMemorySSA() && MSSAU.getMemorySSA()->getMemoryAccess(Ref)) {
- + ]
67 : : // Create a new MemoryAccess and let MemorySSA set its defining access.
68 : 0 : MemoryAccess *NewMemAcc = MSSAU.createMemoryAccessInBB(
69 : 0 : New, nullptr, New->getParent(), MemorySSA::Beginning);
70 [ # # ]: 0 : if (NewMemAcc) {
71 [ # # ]: 0 : if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
72 : 0 : MSSAU.insertDef(MemDef, /*RenameUses=*/true);
73 : : else {
74 : 0 : auto *MemUse = cast<MemoryUse>(NewMemAcc);
75 : 0 : MSSAU.insertUse(MemUse, /*RenameUses=*/true);
76 : : }
77 : : }
78 : : }
79 : 22454 : }
80 : :
81 : : //Stolen and modified to update SE from LoopInfo.cpp
82 : : static bool makeLoopInvariant(Loop *L, Value *V, bool &Changed, Instruction *InsertPt, MemorySSAUpdater &MSSAU, ScalarEvolution *SE);
83 : :
84 : 68103 : static bool makeLoopInvariant(Loop *L, Instruction *I, bool &Changed, Instruction *InsertPt, MemorySSAUpdater &MSSAU, ScalarEvolution *SE) {
85 : : // Test if the value is already loop-invariant.
86 [ + + ]: 68103 : if (L->isLoopInvariant(I))
87 : 1516 : return true;
88 [ + + ]: 66587 : if (!isSafeToSpeculativelyExecute(I))
89 : 66439 : return false;
90 [ + + ]: 148 : if (I->mayReadFromMemory())
91 : 90 : return false;
92 : : // EH block instructions are immobile.
93 [ - + ]: 58 : if (I->isEHPad())
94 : 0 : return false;
95 : : // Don't hoist instructions with loop-variant operands.
96 [ + - ]: 58 : for (Value *Operand : I->operands())
97 [ + - ]: 58 : if (!makeLoopInvariant(L, Operand, Changed, InsertPt, MSSAU, SE))
98 : 58 : return false;
99 : :
100 : : // Hoist.
101 : 0 : moveInstructionBefore(*I, *InsertPt, MSSAU, SE);
102 : :
103 : : // There is possibility of hoisting this instruction above some arbitrary
104 : : // condition. Any metadata defined on it can be control dependent on this
105 : : // condition. Conservatively strip it here so that we don't give any wrong
106 : : // information to the optimizer.
107 : 0 : I->dropUnknownNonDebugMetadata();
108 : :
109 : 0 : Changed = true;
110 : 0 : return true;
111 : : }
112 : :
113 : 70328 : static bool makeLoopInvariant(Loop *L, Value *V, bool &Changed, Instruction *InsertPt, MemorySSAUpdater &MSSAU, ScalarEvolution *SE) {
114 [ + + ]: 70328 : if (Instruction *I = dyn_cast<Instruction>(V))
115 : 68103 : return makeLoopInvariant(L, I, Changed, InsertPt, MSSAU, SE);
116 : 2225 : return true; // All non-instructions are loop-invariant.
117 : : }
118 : :
119 : : struct JuliaLICMPassLegacy : public LoopPass {
120 : : static char ID;
121 : 1148 : JuliaLICMPassLegacy() : LoopPass(ID) {};
122 : :
123 : : bool runOnLoop(Loop *L, LPPassManager &LPM) override;
124 : :
125 : : protected:
126 : 1148 : void getAnalysisUsage(AnalysisUsage &AU) const override {
127 : 1148 : getLoopAnalysisUsage(AU);
128 : 1148 : }
129 : : };
130 : :
131 : : struct JuliaLICM : public JuliaPassContext {
132 : : function_ref<DominatorTree &()> GetDT;
133 : : function_ref<LoopInfo &()> GetLI;
134 : : function_ref<MemorySSA *()> GetMSSA;
135 : : function_ref<ScalarEvolution *()> GetSE;
136 : 514150 : JuliaLICM(function_ref<DominatorTree &()> GetDT,
137 : : function_ref<LoopInfo &()> GetLI,
138 : : function_ref<MemorySSA *()> GetMSSA,
139 : 514150 : function_ref<ScalarEvolution *()> GetSE) :
140 : : GetDT(GetDT),
141 : : GetLI(GetLI),
142 : : GetMSSA(GetMSSA),
143 : 514150 : GetSE(GetSE) {}
144 : :
145 : 514150 : bool runOnLoop(Loop *L)
146 : : {
147 : : // Get the preheader block to move instructions into,
148 : : // required to run this pass.
149 : 514150 : BasicBlock *preheader = L->getLoopPreheader();
150 [ - + ]: 514150 : if (!preheader)
151 : 0 : return false;
152 : 514150 : BasicBlock *header = L->getHeader();
153 : 514150 : const llvm::DataLayout &DL = header->getModule()->getDataLayout();
154 : 514150 : initFunctions(*header->getModule());
155 : : // Also require `gc_preserve_begin_func` whereas
156 : : // `gc_preserve_end_func` is optional since the input to
157 : : // `gc_preserve_end_func` must be from `gc_preserve_begin_func`.
158 : : // We also hoist write barriers here, so we don't exit if write_barrier_func exists
159 [ + + + + : 514150 : if (!gc_preserve_begin_func && !write_barrier_func && !write_barrier_binding_func &&
+ + ]
160 [ + + ]: 324916 : !alloc_obj_func)
161 : 159488 : return false;
162 : 354662 : auto LI = &GetLI();
163 : 354662 : auto DT = &GetDT();
164 : 354662 : auto MSSA = GetMSSA();
165 : 354662 : auto SE = GetSE();
166 : 709324 : MemorySSAUpdater MSSAU(MSSA);
167 : :
168 : : // Lazy initialization of exit blocks insertion points.
169 : 354662 : bool exit_pts_init = false;
170 : 709324 : SmallVector<Instruction*, 8> _exit_pts;
171 : 4603 : auto get_exit_pts = [&] () -> ArrayRef<Instruction*> {
172 [ + + ]: 4603 : if (!exit_pts_init) {
173 : 4146 : exit_pts_init = true;
174 : 8292 : SmallVector<BasicBlock*, 8> exit_bbs;
175 : 4146 : L->getUniqueExitBlocks(exit_bbs);
176 [ + + ]: 23955 : for (BasicBlock *bb: exit_bbs) {
177 : 19809 : _exit_pts.push_back(&*bb->getFirstInsertionPt());
178 : : }
179 : : }
180 : 4603 : return _exit_pts;
181 : 354662 : };
182 : :
183 : 354662 : bool changed = false;
184 : : // Scan in the right order so that we'll hoist the `begin`
185 : : // before we consider sinking `end`.
186 : 354662 : LoopBlocksRPO worklist(L);
187 : 354662 : worklist.perform(LI);
188 [ + + ]: 5579460 : for (auto *bb : worklist) {
189 [ + + ]: 36088700 : for (BasicBlock::iterator II = bb->begin(), E = bb->end(); II != E;) {
190 : 30863900 : auto call = dyn_cast<CallInst>(&*II++);
191 [ + + ]: 30863900 : if (!call)
192 : 29387000 : continue;
193 : 1476890 : Value *callee = call->getCalledOperand();
194 : : assert(callee != nullptr);
195 : : // It is always legal to extend the preserve period
196 : : // so we only need to make sure it is legal to move/clone
197 : : // the calls.
198 : : // If all the input arguments dominates the whole loop we can
199 : : // hoist the `begin` and if a `begin` dominates the loop the
200 : : // corresponding `end` can be moved to the loop exit.
201 [ + + ]: 1476890 : if (callee == gc_preserve_begin_func) {
202 : 10302 : bool canhoist = true;
203 [ + + ]: 14830 : for (Use &U : call->args()) {
204 : : // Check if all arguments are generated outside the loop
205 : 10311 : auto origin = dyn_cast<Instruction>(U.get());
206 [ + + ]: 10311 : if (!origin)
207 : 3254 : continue;
208 [ + + ]: 7057 : if (!DT->properlyDominates(origin->getParent(), header)) {
209 : 5783 : canhoist = false;
210 : 5783 : break;
211 : : }
212 : : }
213 [ + + ]: 10302 : if (!canhoist)
214 : 5783 : continue;
215 : 4519 : ++HoistedPreserveBegin;
216 : 4519 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
217 : 4519 : changed = true;
218 : : }
219 [ + + ]: 1466590 : else if (callee == gc_preserve_end_func) {
220 : 10490 : auto begin = cast<Instruction>(call->getArgOperand(0));
221 [ + + ]: 10490 : if (!DT->properlyDominates(begin->getParent(), header))
222 : 5887 : continue;
223 : 4603 : changed = true;
224 : 4603 : auto exit_pts = get_exit_pts();
225 [ - + ]: 4603 : if (exit_pts.empty()) {
226 : 0 : ++ErasedPreserveEnd;
227 : 0 : eraseInstruction(*call, MSSAU);
228 : 0 : continue;
229 : : }
230 : 4603 : ++SunkPreserveEnd;
231 : 4603 : moveInstructionBefore(*call, *exit_pts[0], MSSAU, SE);
232 [ + + ]: 27057 : for (unsigned i = 1; i < exit_pts.size(); i++) {
233 : : // Clone exit
234 : 22454 : auto CI = CallInst::Create(call, {}, exit_pts[i]);
235 : 22454 : createNewInstruction(CI, call, MSSAU);
236 : : }
237 : : }
238 [ + + ]: 1456100 : else if (callee == write_barrier_func ||
239 [ + + ]: 1389980 : callee == write_barrier_binding_func) {
240 : 66559 : bool valid = true;
241 [ + + ]: 67945 : for (std::size_t i = 0; i < call->arg_size(); i++) {
242 [ + + ]: 67915 : if (!makeLoopInvariant(L, call->getArgOperand(i),
243 : : changed, preheader->getTerminator(),
244 : : MSSAU, SE)) {
245 : 66529 : valid = false;
246 : 66529 : break;
247 : : }
248 : : }
249 [ + + ]: 66559 : if (valid) {
250 : 30 : ++HoistedWriteBarrier;
251 : 30 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
252 : 30 : changed = true;
253 : 66559 : }
254 : : }
255 [ + + ]: 1389540 : else if (callee == alloc_obj_func) {
256 : 96898 : jl_alloc::AllocUseInfo use_info;
257 : 96898 : jl_alloc::CheckInst::Stack check_stack;
258 : 96898 : jl_alloc::EscapeAnalysisRequiredArgs required{use_info, check_stack, *this, DL};
259 : 96898 : jl_alloc::runEscapeAnalysis(call, required, jl_alloc::EscapeAnalysisOptionalArgs().with_valid_set(&L->getBlocksSet()));
260 [ + + + + ]: 96898 : if (use_info.escaped || use_info.addrescaped) {
261 : 96113 : continue;
262 : : }
263 : 785 : bool valid = true;
264 [ + + ]: 3140 : for (std::size_t i = 0; i < call->arg_size(); i++) {
265 [ - + ]: 2355 : if (!makeLoopInvariant(L, call->getArgOperand(i), changed,
266 : : preheader->getTerminator(), MSSAU, SE)) {
267 : 0 : valid = false;
268 : 0 : break;
269 : : }
270 : : }
271 [ + + ]: 785 : if (use_info.refstore) {
272 : : // We need to add write barriers to any stores
273 : : // that may start crossing generations
274 : 70 : continue;
275 : : }
276 [ + - ]: 715 : if (valid) {
277 : 715 : ++HoistedAllocation;
278 : 715 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
279 : 715 : changed = true;
280 : : }
281 : : }
282 : : }
283 : : }
284 [ + + - + ]: 354662 : if (changed && SE) {
285 : 0 : SE->forgetLoopDispositions(L);
286 : : }
287 : : assert(!verifyFunction(*L->getHeader()->getParent(), &errs()));
288 : 354662 : return changed;
289 : : }
290 : : };
291 : :
292 : 514150 : bool JuliaLICMPassLegacy::runOnLoop(Loop *L, LPPassManager &LPM) {
293 : 354662 : auto GetDT = [this]() -> DominatorTree & {
294 : 354662 : return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
295 : 514150 : };
296 : 354662 : auto GetLI = [this]() -> LoopInfo & {
297 : 354662 : return getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
298 : 514150 : };
299 : 354662 : auto GetMSSA = []() {
300 : 354662 : return nullptr;
301 : : };
302 : 354662 : auto GetSE = []() {
303 : 354662 : return nullptr;
304 : : };
305 : 514150 : auto juliaLICM = JuliaLICM(GetDT, GetLI, GetMSSA, GetSE);
306 : 514150 : return juliaLICM.runOnLoop(L);
307 : : }
308 : :
309 : : char JuliaLICMPassLegacy::ID = 0;
310 : : static RegisterPass<JuliaLICMPassLegacy>
311 : : Y("JuliaLICM", "LICM for julia specific intrinsics.",
312 : : false, false);
313 : : } //namespace
314 : :
315 : 0 : PreservedAnalyses JuliaLICMPass::run(Loop &L, LoopAnalysisManager &AM,
316 : : LoopStandardAnalysisResults &AR, LPMUpdater &U)
317 : : {
318 : 0 : auto GetDT = [&AR]() -> DominatorTree & {
319 : 0 : return AR.DT;
320 : 0 : };
321 : 0 : auto GetLI = [&AR]() -> LoopInfo & {
322 : 0 : return AR.LI;
323 : 0 : };
324 : 0 : auto GetMSSA = [&AR]() {
325 : 0 : return AR.MSSA;
326 : 0 : };
327 : 0 : auto GetSE = [&AR]() {
328 : 0 : return &AR.SE;
329 : 0 : };
330 : 0 : auto juliaLICM = JuliaLICM(GetDT, GetLI, GetMSSA, GetSE);
331 [ # # ]: 0 : if (juliaLICM.runOnLoop(&L)) {
332 : 0 : auto preserved = getLoopPassPreservedAnalyses();
333 : 0 : preserved.preserveSet<CFGAnalyses>();
334 : 0 : preserved.preserve<MemorySSAAnalysis>();
335 : 0 : return preserved;
336 : : }
337 : 0 : return PreservedAnalyses::all();
338 : : }
339 : :
340 : 1148 : Pass *createJuliaLICMPass()
341 : : {
342 : 1148 : return new JuliaLICMPassLegacy();
343 : : }
344 : :
345 : 0 : extern "C" JL_DLLEXPORT void LLVMExtraJuliaLICMPass_impl(LLVMPassManagerRef PM)
346 : : {
347 : 0 : unwrap(PM)->add(createJuliaLICMPass());
348 : 0 : }
|
