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 : 0 : static void moveInstructionBefore(Instruction &I, Instruction &Dest,
53 : : MemorySSAUpdater &MSSAU,
54 : : ScalarEvolution *SE) {
55 : 0 : I.moveBefore(&Dest);
56 [ # # ]: 0 : 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 [ # # ]: 0 : if (SE)
62 : 0 : SE->forgetValue(&I);
63 : 0 : }
64 : :
65 : 0 : static void createNewInstruction(Instruction *New, Instruction *Ref, MemorySSAUpdater &MSSAU) {
66 [ # # # # : 0 : 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 : 0 : }
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 : 0 : 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 [ # # ]: 0 : if (L->isLoopInvariant(I))
87 : 0 : return true;
88 [ # # ]: 0 : if (!isSafeToSpeculativelyExecute(I))
89 : 0 : return false;
90 [ # # ]: 0 : if (I->mayReadFromMemory())
91 : 0 : return false;
92 : : // EH block instructions are immobile.
93 [ # # ]: 0 : if (I->isEHPad())
94 : 0 : return false;
95 : : // Don't hoist instructions with loop-variant operands.
96 [ # # ]: 0 : for (Value *Operand : I->operands())
97 [ # # ]: 0 : if (!makeLoopInvariant(L, Operand, Changed, InsertPt, MSSAU, SE))
98 : 0 : 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 : 0 : static bool makeLoopInvariant(Loop *L, Value *V, bool &Changed, Instruction *InsertPt, MemorySSAUpdater &MSSAU, ScalarEvolution *SE) {
114 [ # # ]: 0 : if (Instruction *I = dyn_cast<Instruction>(V))
115 : 0 : return makeLoopInvariant(L, I, Changed, InsertPt, MSSAU, SE);
116 : 0 : return true; // All non-instructions are loop-invariant.
117 : : }
118 : :
119 : : struct JuliaLICMPassLegacy : public LoopPass {
120 : : static char ID;
121 : 4 : JuliaLICMPassLegacy() : LoopPass(ID) {};
122 : :
123 : : bool runOnLoop(Loop *L, LPPassManager &LPM) override;
124 : :
125 : : protected:
126 : 4 : void getAnalysisUsage(AnalysisUsage &AU) const override {
127 : 4 : getLoopAnalysisUsage(AU);
128 : 4 : }
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 : 4 : JuliaLICM(function_ref<DominatorTree &()> GetDT,
137 : : function_ref<LoopInfo &()> GetLI,
138 : : function_ref<MemorySSA *()> GetMSSA,
139 : 4 : function_ref<ScalarEvolution *()> GetSE) :
140 : : GetDT(GetDT),
141 : : GetLI(GetLI),
142 : : GetMSSA(GetMSSA),
143 : 4 : GetSE(GetSE) {}
144 : :
145 : 4 : bool runOnLoop(Loop *L)
146 : : {
147 : : // Get the preheader block to move instructions into,
148 : : // required to run this pass.
149 : 4 : BasicBlock *preheader = L->getLoopPreheader();
150 [ - + ]: 4 : if (!preheader)
151 : 0 : return false;
152 : 4 : BasicBlock *header = L->getHeader();
153 : 4 : const llvm::DataLayout &DL = header->getModule()->getDataLayout();
154 : 4 : 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 [ - + - - : 4 : if (!gc_preserve_begin_func && !write_barrier_func && !write_barrier_binding_func &&
- - ]
160 [ # # ]: 0 : !alloc_obj_func)
161 : 0 : return false;
162 : 4 : auto LI = &GetLI();
163 : 4 : auto DT = &GetDT();
164 : 4 : auto MSSA = GetMSSA();
165 : 4 : auto SE = GetSE();
166 : 8 : MemorySSAUpdater MSSAU(MSSA);
167 : :
168 : : // Lazy initialization of exit blocks insertion points.
169 : 4 : bool exit_pts_init = false;
170 : 8 : SmallVector<Instruction*, 8> _exit_pts;
171 : 0 : auto get_exit_pts = [&] () -> ArrayRef<Instruction*> {
172 [ # # ]: 0 : if (!exit_pts_init) {
173 : 0 : exit_pts_init = true;
174 : 0 : SmallVector<BasicBlock*, 8> exit_bbs;
175 : 0 : L->getUniqueExitBlocks(exit_bbs);
176 [ # # ]: 0 : for (BasicBlock *bb: exit_bbs) {
177 : 0 : _exit_pts.push_back(&*bb->getFirstInsertionPt());
178 : : }
179 : : }
180 : 0 : return _exit_pts;
181 : 4 : };
182 : :
183 : 4 : bool changed = false;
184 : : // Scan in the right order so that we'll hoist the `begin`
185 : : // before we consider sinking `end`.
186 : 4 : LoopBlocksRPO worklist(L);
187 : 4 : worklist.perform(LI);
188 [ + + ]: 16 : for (auto *bb : worklist) {
189 [ + + ]: 224 : for (BasicBlock::iterator II = bb->begin(), E = bb->end(); II != E;) {
190 : 212 : auto call = dyn_cast<CallInst>(&*II++);
191 [ + + ]: 212 : if (!call)
192 : 160 : continue;
193 : 52 : 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 [ + + ]: 52 : if (callee == gc_preserve_begin_func) {
202 : 8 : bool canhoist = true;
203 [ + - ]: 8 : for (Use &U : call->args()) {
204 : : // Check if all arguments are generated outside the loop
205 : 8 : auto origin = dyn_cast<Instruction>(U.get());
206 [ - + ]: 8 : if (!origin)
207 : 0 : continue;
208 [ + - ]: 8 : if (!DT->properlyDominates(origin->getParent(), header)) {
209 : 8 : canhoist = false;
210 : 8 : break;
211 : : }
212 : : }
213 [ + - ]: 8 : if (!canhoist)
214 : 8 : continue;
215 : 0 : ++HoistedPreserveBegin;
216 : 0 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
217 : 0 : changed = true;
218 : : }
219 [ + + ]: 44 : else if (callee == gc_preserve_end_func) {
220 : 8 : auto begin = cast<Instruction>(call->getArgOperand(0));
221 [ + - ]: 8 : if (!DT->properlyDominates(begin->getParent(), header))
222 : 8 : continue;
223 : 0 : changed = true;
224 : 0 : auto exit_pts = get_exit_pts();
225 [ # # ]: 0 : if (exit_pts.empty()) {
226 : 0 : ++ErasedPreserveEnd;
227 : 0 : eraseInstruction(*call, MSSAU);
228 : 0 : continue;
229 : : }
230 : 0 : ++SunkPreserveEnd;
231 : 0 : moveInstructionBefore(*call, *exit_pts[0], MSSAU, SE);
232 [ # # ]: 0 : for (unsigned i = 1; i < exit_pts.size(); i++) {
233 : : // Clone exit
234 : 0 : auto CI = CallInst::Create(call, {}, exit_pts[i]);
235 : 0 : createNewInstruction(CI, call, MSSAU);
236 : : }
237 : : }
238 [ + - ]: 36 : else if (callee == write_barrier_func ||
239 [ - + ]: 36 : callee == write_barrier_binding_func) {
240 : 0 : bool valid = true;
241 [ # # ]: 0 : for (std::size_t i = 0; i < call->arg_size(); i++) {
242 [ # # ]: 0 : if (!makeLoopInvariant(L, call->getArgOperand(i),
243 : : changed, preheader->getTerminator(),
244 : : MSSAU, SE)) {
245 : 0 : valid = false;
246 : 0 : break;
247 : : }
248 : : }
249 [ # # ]: 0 : if (valid) {
250 : 0 : ++HoistedWriteBarrier;
251 : 0 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
252 : 0 : changed = true;
253 : 0 : }
254 : : }
255 [ + + ]: 36 : else if (callee == alloc_obj_func) {
256 : 8 : jl_alloc::AllocUseInfo use_info;
257 : 8 : jl_alloc::CheckInst::Stack check_stack;
258 : 8 : jl_alloc::EscapeAnalysisRequiredArgs required{use_info, check_stack, *this, DL};
259 : 8 : jl_alloc::runEscapeAnalysis(call, required, jl_alloc::EscapeAnalysisOptionalArgs().with_valid_set(&L->getBlocksSet()));
260 [ - + - - ]: 8 : if (use_info.escaped || use_info.addrescaped) {
261 : 8 : continue;
262 : : }
263 : 0 : bool valid = true;
264 [ # # ]: 0 : for (std::size_t i = 0; i < call->arg_size(); i++) {
265 [ # # ]: 0 : if (!makeLoopInvariant(L, call->getArgOperand(i), changed,
266 : : preheader->getTerminator(), MSSAU, SE)) {
267 : 0 : valid = false;
268 : 0 : break;
269 : : }
270 : : }
271 [ # # ]: 0 : if (use_info.refstore) {
272 : : // We need to add write barriers to any stores
273 : : // that may start crossing generations
274 : 0 : continue;
275 : : }
276 [ # # ]: 0 : if (valid) {
277 : 0 : ++HoistedAllocation;
278 : 0 : moveInstructionBefore(*call, *preheader->getTerminator(), MSSAU, SE);
279 : 0 : changed = true;
280 : : }
281 : : }
282 : : }
283 : : }
284 [ - + - - ]: 4 : if (changed && SE) {
285 : 0 : SE->forgetLoopDispositions(L);
286 : : }
287 : : assert(!verifyFunction(*L->getHeader()->getParent(), &errs()));
288 : 4 : return changed;
289 : : }
290 : : };
291 : :
292 : 4 : bool JuliaLICMPassLegacy::runOnLoop(Loop *L, LPPassManager &LPM) {
293 : 4 : auto GetDT = [this]() -> DominatorTree & {
294 : 4 : return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
295 : 4 : };
296 : 4 : auto GetLI = [this]() -> LoopInfo & {
297 : 4 : return getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
298 : 4 : };
299 : 4 : auto GetMSSA = []() {
300 : 4 : return nullptr;
301 : : };
302 : 4 : auto GetSE = []() {
303 : 4 : return nullptr;
304 : : };
305 : 4 : auto juliaLICM = JuliaLICM(GetDT, GetLI, GetMSSA, GetSE);
306 : 4 : 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 : 4 : Pass *createJuliaLICMPass()
341 : : {
342 : 4 : 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 : }
|
