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 : :
5 : : #include <llvm-c/Core.h>
6 : : #include <llvm-c/Types.h>
7 : :
8 : : #include <llvm/ADT/SmallPtrSet.h>
9 : : #include <llvm/Analysis/CFG.h>
10 : : #include <llvm/IR/Value.h>
11 : : #include <llvm/IR/ValueMap.h>
12 : : #include <llvm/IR/Constants.h>
13 : : #include <llvm/IR/Dominators.h>
14 : : #include <llvm/IR/LegacyPassManager.h>
15 : : #include <llvm/IR/Function.h>
16 : : #include <llvm/IR/Instructions.h>
17 : : #include <llvm/IR/IntrinsicInst.h>
18 : : #include <llvm/IR/InstVisitor.h>
19 : : #include <llvm/IR/Module.h>
20 : : #include <llvm/IR/IRBuilder.h>
21 : : #include <llvm/IR/Verifier.h>
22 : : #include <llvm/Pass.h>
23 : : #include <llvm/Support/Debug.h>
24 : :
25 : : #include "codegen_shared.h"
26 : : #include "julia.h"
27 : : #include "passes.h"
28 : :
29 : : #define DEBUG_TYPE "propagate_julia_addrspaces"
30 : :
31 : : using namespace llvm;
32 : :
33 : : /* This pass performs propagation of addrspace information that is legal from
34 : : the frontend definition, but illegal by general IR semantics. In particular,
35 : : this includes:
36 : : - Changing the address space of a load/store if the base pointer is
37 : : in an untracked address space
38 : : - Commuting GEPs and addrspace casts
39 : :
40 : : This is most useful for removing superfluous casts that can inhibit LLVM
41 : : optimizations.
42 : : */
43 : :
44 : : struct PropagateJuliaAddrspacesVisitor : public InstVisitor<PropagateJuliaAddrspacesVisitor> {
45 : : DenseMap<Value *, Value *> LiftingMap;
46 : : SmallPtrSet<Value *, 4> Visited;
47 : : std::vector<Instruction *> ToDelete;
48 : : std::vector<std::pair<Instruction *, Instruction *>> ToInsert;
49 : :
50 : : public:
51 : : Value *LiftPointer(Value *V, Instruction *InsertPt=nullptr);
52 : : void visitMemop(Instruction &I, Type *T, unsigned OpIndex);
53 : : void visitLoadInst(LoadInst &LI);
54 : : void visitStoreInst(StoreInst &SI);
55 : : void visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI);
56 : : void visitAtomicRMWInst(AtomicRMWInst &SI);
57 : : void visitMemSetInst(MemSetInst &MI);
58 : : void visitMemTransferInst(MemTransferInst &MTI);
59 : :
60 : : private:
61 : : void PoisonValues(std::vector<Value *> &Worklist);
62 : : };
63 : :
64 : 2871390 : static unsigned getValueAddrSpace(Value *V) {
65 : 2871390 : return cast<PointerType>(V->getType())->getAddressSpace();
66 : : }
67 : :
68 : 20363800 : static bool isSpecialAS(unsigned AS) {
69 [ + + + - ]: 20363800 : return AddressSpace::FirstSpecial <= AS && AS <= AddressSpace::LastSpecial;
70 : : }
71 : :
72 : 58943500 : void PropagateJuliaAddrspacesVisitor::PoisonValues(std::vector<Value *> &Worklist) {
73 [ + + ]: 58943500 : while (!Worklist.empty()) {
74 : 57235300 : Value *CurrentV = Worklist.back();
75 : 57235300 : Worklist.pop_back();
76 [ + + ]: 119216000 : for (Value *User : CurrentV->users()) {
77 [ + + ]: 61980300 : if (Visited.count(User))
78 : 6453250 : continue;
79 : 55527100 : Visited.insert(CurrentV);
80 : 55527100 : Worklist.push_back(User);
81 : : }
82 : : }
83 : 1708190 : }
84 : :
85 : 6904980 : Value *PropagateJuliaAddrspacesVisitor::LiftPointer(Value *V, Instruction *InsertPt) {
86 : 13810000 : SmallVector<Value *, 4> Stack;
87 : 13810000 : std::vector<Value *> Worklist;
88 : 13810000 : std::set<Value *> LocalVisited;
89 : 6904980 : Worklist.push_back(V);
90 : : // Follow pointer casts back, see if we're based on a pointer in
91 : : // an untracked address space, in which case we're allowed to drop
92 : : // intermediate addrspace casts.
93 [ + + ]: 7047940 : while (!Worklist.empty()) {
94 : 7000460 : Value *CurrentV = Worklist.back();
95 : 7000460 : Worklist.pop_back();
96 [ + + ]: 7000460 : if (LocalVisited.count(CurrentV)) {
97 : 1057 : continue;
98 : : }
99 : : while (true) {
100 [ + + ]: 12632000 : if (auto *BCI = dyn_cast<BitCastInst>(CurrentV))
101 : 3423660 : CurrentV = BCI->getOperand(0);
102 [ + + ]: 9208370 : else if (auto *ACI = dyn_cast<AddrSpaceCastInst>(CurrentV)) {
103 : 1142580 : CurrentV = ACI->getOperand(0);
104 [ - + ]: 1142580 : if (!isSpecialAS(getValueAddrSpace(ACI)))
105 : 0 : break;
106 : : }
107 [ + + ]: 8065790 : else if (auto *GEP = dyn_cast<GetElementPtrInst>(CurrentV)) {
108 [ + + ]: 6193260 : if (LiftingMap.count(GEP)) {
109 : 19877 : CurrentV = LiftingMap[GEP];
110 : 19877 : break;
111 [ + + ]: 6173380 : } else if (Visited.count(GEP)) {
112 : 6857500 : return nullptr;
113 : : }
114 : 1049220 : Stack.push_back(GEP);
115 : 1049220 : LocalVisited.insert(GEP);
116 : 1049220 : CurrentV = GEP->getOperand(0);
117 [ + + ]: 1872530 : } else if (auto *Phi = dyn_cast<PHINode>(CurrentV)) {
118 [ + + ]: 62779 : if (LiftingMap.count(Phi)) {
119 : 4776 : break;
120 : : }
121 [ + + ]: 180064 : for (Value *Incoming : Phi->incoming_values()) {
122 : 122061 : Worklist.push_back(Incoming);
123 : : }
124 : 58003 : Stack.push_back(Phi);
125 : 58003 : LocalVisited.insert(Phi);
126 : 58003 : break;
127 [ + + ]: 1809750 : } else if (auto *Select = dyn_cast<SelectInst>(CurrentV)) {
128 [ + + ]: 52483 : if (LiftingMap.count(Select)) {
129 : 10169 : break;
130 [ + + ]: 42314 : } else if (Visited.count(Select)) {
131 : 25150 : return nullptr;
132 : : }
133 : : // Push one of the branches onto the worklist, continue with the other one
134 : : // directly
135 : 17164 : Worklist.push_back(Select->getOperand(2));
136 : 17164 : Stack.push_back(Select);
137 : 17164 : LocalVisited.insert(Select);
138 : 17164 : CurrentV = Select->getOperand(1);
139 [ + + ]: 1757270 : } else if (isa<ConstantPointerNull>(CurrentV)) {
140 : : // It's always legal to lift null pointers into any address space
141 : 28463 : break;
142 : : } else {
143 : : // Ok, we've reached a leaf - check if it is eligible for lifting
144 [ + - + + : 3457610 : if (!CurrentV->getType()->isPointerTy() ||
+ + ]
145 : 1728800 : isSpecialAS(getValueAddrSpace(CurrentV))) {
146 : : // If not, poison all (recursive) users of this value, to prevent
147 : : // looking at them again in future iterations.
148 : 1708190 : Worklist.clear();
149 : 1708190 : Worklist.push_back(CurrentV);
150 : 1708190 : Visited.insert(CurrentV);
151 : 1708190 : PoisonValues(Worklist);
152 : 1708190 : return nullptr;
153 : : }
154 : 20616 : break;
155 : : }
156 : 5632640 : }
157 : : }
158 : :
159 : : // Go through and insert lifted versions of all instructions on the list.
160 : 94960 : std::vector<Value *> ToRevisit;
161 [ + + ]: 101734 : for (Value *V : Stack) {
162 [ - + ]: 54254 : if (LiftingMap.count(V))
163 : 0 : continue;
164 [ + + + + : 54254 : if (isa<GetElementPtrInst>(V) || isa<PHINode>(V) || isa<SelectInst>(V)) {
+ - + - ]
165 : 54254 : Instruction *InstV = cast<Instruction>(V);
166 : 54254 : Instruction *NewV = InstV->clone();
167 : 54254 : ToInsert.push_back(std::make_pair(NewV, InstV));
168 : 54254 : Type *NewRetTy = PointerType::getWithSamePointeeType(cast<PointerType>(InstV->getType()), AddressSpace::Generic);
169 : 54254 : NewV->mutateType(NewRetTy);
170 : 54254 : LiftingMap[InstV] = NewV;
171 : 54254 : ToRevisit.push_back(NewV);
172 : : }
173 : : }
174 : :
175 : 131361 : auto CollapseCastsAndLift = [&](Value *CurrentV, Instruction *InsertPt) -> Value * {
176 : 131361 : PointerType *TargetType = PointerType::getWithSamePointeeType(cast<PointerType>(CurrentV->getType()), AddressSpace::Generic);
177 [ + + ]: 304350 : while (!LiftingMap.count(CurrentV)) {
178 [ + + ]: 214658 : if (isa<BitCastInst>(CurrentV))
179 : 103837 : CurrentV = cast<BitCastInst>(CurrentV)->getOperand(0);
180 [ + + ]: 110821 : else if (isa<AddrSpaceCastInst>(CurrentV))
181 : 69152 : CurrentV = cast<AddrSpaceCastInst>(CurrentV)->getOperand(0);
182 : : else
183 : 41669 : break;
184 : : }
185 [ + + ]: 131361 : if (isa<ConstantPointerNull>(CurrentV)) {
186 : 24222 : return ConstantPointerNull::get(TargetType);
187 : : }
188 [ + + ]: 107139 : if (LiftingMap.count(CurrentV))
189 : 89692 : CurrentV = LiftingMap[CurrentV];
190 [ + + ]: 107139 : if (CurrentV->getType() != TargetType) {
191 : 82575 : auto *BCI = new BitCastInst(CurrentV, TargetType);
192 : 82575 : ToInsert.push_back(std::make_pair(BCI, InsertPt));
193 : 82575 : CurrentV = BCI;
194 : : }
195 : 107139 : return CurrentV;
196 : 47480 : };
197 : :
198 : : // Now go through and update the operands
199 [ + + ]: 101734 : for (Value *V : ToRevisit) {
200 [ + + ]: 54254 : if (GetElementPtrInst *NewGEP = dyn_cast<GetElementPtrInst>(V)) {
201 : 27767 : NewGEP->setOperand(GetElementPtrInst::getPointerOperandIndex(),
202 : : CollapseCastsAndLift(NewGEP->getOperand(GetElementPtrInst::getPointerOperandIndex()),
203 : : NewGEP));
204 [ + + ]: 26487 : } else if (PHINode *NewPhi = dyn_cast<PHINode>(V)) {
205 [ + + ]: 42854 : for (size_t i = 0; i < NewPhi->getNumIncomingValues(); ++i) {
206 : 29616 : NewPhi->setIncomingValue(i, CollapseCastsAndLift(NewPhi->getIncomingValue(i),
207 : : NewPhi->getIncomingBlock(i)->getTerminator()));
208 : : }
209 [ + - ]: 13249 : } else if (SelectInst *NewSelect = dyn_cast<SelectInst>(V)) {
210 : 13249 : NewSelect->setOperand(1, CollapseCastsAndLift(NewSelect->getOperand(1), NewSelect));
211 : 13249 : NewSelect->setOperand(2, CollapseCastsAndLift(NewSelect->getOperand(2), NewSelect));
212 : : } else {
213 : : assert(false && "Shouldn't have reached here");
214 : : }
215 : : }
216 : :
217 : 47480 : return CollapseCastsAndLift(V, InsertPt);
218 : : }
219 : :
220 : 14977900 : void PropagateJuliaAddrspacesVisitor::visitMemop(Instruction &I, Type *T, unsigned OpIndex) {
221 : 14977900 : Value *Original = I.getOperand(OpIndex);
222 : 14977900 : unsigned AS = Original->getType()->getPointerAddressSpace();
223 [ + + ]: 14977900 : if (!isSpecialAS(AS))
224 : 8530320 : return;
225 : 6447600 : Value *Replacement = LiftPointer(Original, &I);
226 [ + + ]: 6447600 : if (!Replacement)
227 : 6412220 : return;
228 : 35379 : I.setOperand(OpIndex, Replacement);
229 : : }
230 : :
231 : 10193800 : void PropagateJuliaAddrspacesVisitor::visitLoadInst(LoadInst &LI) {
232 : 10193800 : visitMemop(LI, LI.getType(), LoadInst::getPointerOperandIndex());
233 : 10193800 : }
234 : :
235 : 4775440 : void PropagateJuliaAddrspacesVisitor::visitStoreInst(StoreInst &SI) {
236 : 4775440 : visitMemop(SI, SI.getValueOperand()->getType(), StoreInst::getPointerOperandIndex());
237 : 4775440 : }
238 : :
239 : 6019 : void PropagateJuliaAddrspacesVisitor::visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI) {
240 : 6019 : visitMemop(SI, SI.getNewValOperand()->getType(), AtomicCmpXchgInst::getPointerOperandIndex());
241 : 6019 : }
242 : :
243 : 2653 : void PropagateJuliaAddrspacesVisitor::visitAtomicRMWInst(AtomicRMWInst &SI) {
244 : 2653 : visitMemop(SI, SI.getType(), AtomicRMWInst::getPointerOperandIndex());
245 : 2653 : }
246 : :
247 : 2747 : void PropagateJuliaAddrspacesVisitor::visitMemSetInst(MemSetInst &MI) {
248 : 2747 : unsigned AS = MI.getDestAddressSpace();
249 [ + + ]: 2747 : if (!isSpecialAS(AS))
250 : 2741 : return;
251 : 6 : Value *Replacement = LiftPointer(MI.getRawDest());
252 [ + - ]: 6 : if (!Replacement)
253 : 6 : return;
254 : 0 : Function *TheFn = Intrinsic::getDeclaration(MI.getModule(), Intrinsic::memset,
255 : 0 : {Replacement->getType(), MI.getOperand(1)->getType()});
256 : 0 : MI.setCalledFunction(TheFn);
257 : 0 : MI.setArgOperand(0, Replacement);
258 : : }
259 : :
260 : 957881 : void PropagateJuliaAddrspacesVisitor::visitMemTransferInst(MemTransferInst &MTI) {
261 : 957881 : unsigned DestAS = MTI.getDestAddressSpace();
262 : 957881 : unsigned SrcAS = MTI.getSourceAddressSpace();
263 [ + + + + : 957881 : if (!isSpecialAS(DestAS) && !isSpecialAS(SrcAS))
+ + ]
264 : 563044 : return;
265 : 394837 : Value *Dest = MTI.getRawDest();
266 [ + + ]: 394837 : if (isSpecialAS(DestAS)) {
267 : 193652 : Value *Replacement = LiftPointer(Dest, &MTI);
268 [ + + ]: 193652 : if (Replacement)
269 : 2 : Dest = Replacement;
270 : : }
271 : 394837 : Value *Src = MTI.getRawSource();
272 [ + + ]: 394837 : if (isSpecialAS(SrcAS)) {
273 : 263719 : Value *Replacement = LiftPointer(Src, &MTI);
274 [ + + ]: 263719 : if (Replacement)
275 : 12099 : Src = Replacement;
276 : : }
277 [ + + + + : 394837 : if (Dest == MTI.getRawDest() && Src == MTI.getRawSource())
+ + ]
278 : 382736 : return;
279 : 12101 : Function *TheFn = Intrinsic::getDeclaration(MTI.getModule(), MTI.getIntrinsicID(),
280 : 12101 : {Dest->getType(), Src->getType(),
281 : 12101 : MTI.getOperand(2)->getType()});
282 : 12101 : MTI.setCalledFunction(TheFn);
283 : 12101 : MTI.setArgOperand(0, Dest);
284 : 12101 : MTI.setArgOperand(1, Src);
285 : : }
286 : :
287 : 614971 : bool propagateJuliaAddrspaces(Function &F) {
288 : 614971 : PropagateJuliaAddrspacesVisitor visitor;
289 : 614971 : visitor.visit(F);
290 [ + + ]: 751800 : for (auto it : visitor.ToInsert)
291 : 136829 : it.first->insertBefore(it.second);
292 [ - + ]: 614971 : for (Instruction *I : visitor.ToDelete)
293 : 0 : I->eraseFromParent();
294 : 614971 : visitor.ToInsert.clear();
295 : 614971 : visitor.ToDelete.clear();
296 : 614971 : visitor.LiftingMap.clear();
297 : 614971 : visitor.Visited.clear();
298 : 614971 : return true;
299 : : }
300 : :
301 : : struct PropagateJuliaAddrspacesLegacy : FunctionPass {
302 : : static char ID;
303 : :
304 : 574 : PropagateJuliaAddrspacesLegacy() : FunctionPass(ID) {}
305 : 614971 : bool runOnFunction(Function &F) override {
306 : 614971 : return propagateJuliaAddrspaces(F);
307 : : }
308 : : };
309 : :
310 : : char PropagateJuliaAddrspacesLegacy::ID = 0;
311 : : static RegisterPass<PropagateJuliaAddrspacesLegacy> X("PropagateJuliaAddrspaces", "Propagate (non-)rootedness information", false, false);
312 : :
313 : 574 : Pass *createPropagateJuliaAddrspaces() {
314 : 574 : return new PropagateJuliaAddrspacesLegacy();
315 : : }
316 : :
317 : 0 : PreservedAnalyses PropagateJuliaAddrspacesPass::run(Function &F, FunctionAnalysisManager &AM) {
318 [ # # ]: 0 : if (propagateJuliaAddrspaces(F)) {
319 : 0 : return PreservedAnalyses::allInSet<CFGAnalyses>();
320 : : } else {
321 : 0 : return PreservedAnalyses::all();
322 : : }
323 : : }
324 : :
325 : 0 : extern "C" JL_DLLEXPORT void LLVMExtraAddPropagateJuliaAddrspaces_impl(LLVMPassManagerRef PM)
326 : : {
327 : 0 : unwrap(PM)->add(createPropagateJuliaAddrspaces());
328 : 0 : }
|
