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 : 32 : static unsigned getValueAddrSpace(Value *V) {
65 : 32 : return cast<PointerType>(V->getType())->getAddressSpace();
66 : : }
67 : :
68 : 124 : static bool isSpecialAS(unsigned AS) {
69 [ + + + - ]: 124 : return AddressSpace::FirstSpecial <= AS && AS <= AddressSpace::LastSpecial;
70 : : }
71 : :
72 : 254 : void PropagateJuliaAddrspacesVisitor::PoisonValues(std::vector<Value *> &Worklist) {
73 [ + + ]: 254 : while (!Worklist.empty()) {
74 : 230 : Value *CurrentV = Worklist.back();
75 : 230 : Worklist.pop_back();
76 [ + + ]: 488 : for (Value *User : CurrentV->users()) {
77 [ + + ]: 258 : if (Visited.count(User))
78 : 52 : continue;
79 : 206 : Visited.insert(CurrentV);
80 : 206 : Worklist.push_back(User);
81 : : }
82 : : }
83 : 24 : }
84 : :
85 : 28 : Value *PropagateJuliaAddrspacesVisitor::LiftPointer(Value *V, Instruction *InsertPt) {
86 : 56 : SmallVector<Value *, 4> Stack;
87 : 56 : std::vector<Value *> Worklist;
88 : 56 : std::set<Value *> LocalVisited;
89 : 28 : 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 [ + - ]: 28 : while (!Worklist.empty()) {
94 : 28 : Value *CurrentV = Worklist.back();
95 : 28 : Worklist.pop_back();
96 [ - + ]: 28 : if (LocalVisited.count(CurrentV)) {
97 : 0 : continue;
98 : : }
99 : : while (true) {
100 [ + + ]: 52 : if (auto *BCI = dyn_cast<BitCastInst>(CurrentV))
101 : 16 : CurrentV = BCI->getOperand(0);
102 [ + + ]: 36 : else if (auto *ACI = dyn_cast<AddrSpaceCastInst>(CurrentV)) {
103 : 8 : CurrentV = ACI->getOperand(0);
104 [ - + ]: 8 : if (!isSpecialAS(getValueAddrSpace(ACI)))
105 : 0 : break;
106 : : }
107 [ + + ]: 28 : else if (auto *GEP = dyn_cast<GetElementPtrInst>(CurrentV)) {
108 [ - + ]: 4 : if (LiftingMap.count(GEP)) {
109 : 0 : CurrentV = LiftingMap[GEP];
110 : 0 : break;
111 [ + - ]: 4 : } else if (Visited.count(GEP)) {
112 : 28 : return nullptr;
113 : : }
114 : 0 : Stack.push_back(GEP);
115 : 0 : LocalVisited.insert(GEP);
116 : 0 : CurrentV = GEP->getOperand(0);
117 [ - + ]: 24 : } else if (auto *Phi = dyn_cast<PHINode>(CurrentV)) {
118 [ # # ]: 0 : if (LiftingMap.count(Phi)) {
119 : 0 : break;
120 : : }
121 [ # # ]: 0 : for (Value *Incoming : Phi->incoming_values()) {
122 : 0 : Worklist.push_back(Incoming);
123 : : }
124 : 0 : Stack.push_back(Phi);
125 : 0 : LocalVisited.insert(Phi);
126 : 0 : break;
127 [ - + ]: 24 : } else if (auto *Select = dyn_cast<SelectInst>(CurrentV)) {
128 [ # # ]: 0 : if (LiftingMap.count(Select)) {
129 : 0 : break;
130 [ # # ]: 0 : } else if (Visited.count(Select)) {
131 : 0 : return nullptr;
132 : : }
133 : : // Push one of the branches onto the worklist, continue with the other one
134 : : // directly
135 : 0 : Worklist.push_back(Select->getOperand(2));
136 : 0 : Stack.push_back(Select);
137 : 0 : LocalVisited.insert(Select);
138 : 0 : CurrentV = Select->getOperand(1);
139 [ - + ]: 24 : } else if (isa<ConstantPointerNull>(CurrentV)) {
140 : : // It's always legal to lift null pointers into any address space
141 : 0 : break;
142 : : } else {
143 : : // Ok, we've reached a leaf - check if it is eligible for lifting
144 [ + - + - : 48 : if (!CurrentV->getType()->isPointerTy() ||
+ - ]
145 : 24 : isSpecialAS(getValueAddrSpace(CurrentV))) {
146 : : // If not, poison all (recursive) users of this value, to prevent
147 : : // looking at them again in future iterations.
148 : 24 : Worklist.clear();
149 : 24 : Worklist.push_back(CurrentV);
150 : 24 : Visited.insert(CurrentV);
151 : 24 : PoisonValues(Worklist);
152 : 24 : return nullptr;
153 : : }
154 : 0 : break;
155 : : }
156 : 24 : }
157 : : }
158 : :
159 : : // Go through and insert lifted versions of all instructions on the list.
160 : 0 : std::vector<Value *> ToRevisit;
161 [ # # ]: 0 : for (Value *V : Stack) {
162 [ # # ]: 0 : if (LiftingMap.count(V))
163 : 0 : continue;
164 [ # # # # : 0 : if (isa<GetElementPtrInst>(V) || isa<PHINode>(V) || isa<SelectInst>(V)) {
# # # # ]
165 : 0 : Instruction *InstV = cast<Instruction>(V);
166 : 0 : Instruction *NewV = InstV->clone();
167 : 0 : ToInsert.push_back(std::make_pair(NewV, InstV));
168 : 0 : Type *NewRetTy = PointerType::getWithSamePointeeType(cast<PointerType>(InstV->getType()), AddressSpace::Generic);
169 : 0 : NewV->mutateType(NewRetTy);
170 : 0 : LiftingMap[InstV] = NewV;
171 : 0 : ToRevisit.push_back(NewV);
172 : : }
173 : : }
174 : :
175 : 0 : auto CollapseCastsAndLift = [&](Value *CurrentV, Instruction *InsertPt) -> Value * {
176 : 0 : PointerType *TargetType = PointerType::getWithSamePointeeType(cast<PointerType>(CurrentV->getType()), AddressSpace::Generic);
177 [ # # ]: 0 : while (!LiftingMap.count(CurrentV)) {
178 [ # # ]: 0 : if (isa<BitCastInst>(CurrentV))
179 : 0 : CurrentV = cast<BitCastInst>(CurrentV)->getOperand(0);
180 [ # # ]: 0 : else if (isa<AddrSpaceCastInst>(CurrentV))
181 : 0 : CurrentV = cast<AddrSpaceCastInst>(CurrentV)->getOperand(0);
182 : : else
183 : 0 : break;
184 : : }
185 [ # # ]: 0 : if (isa<ConstantPointerNull>(CurrentV)) {
186 : 0 : return ConstantPointerNull::get(TargetType);
187 : : }
188 [ # # ]: 0 : if (LiftingMap.count(CurrentV))
189 : 0 : CurrentV = LiftingMap[CurrentV];
190 [ # # ]: 0 : if (CurrentV->getType() != TargetType) {
191 : 0 : auto *BCI = new BitCastInst(CurrentV, TargetType);
192 : 0 : ToInsert.push_back(std::make_pair(BCI, InsertPt));
193 : 0 : CurrentV = BCI;
194 : : }
195 : 0 : return CurrentV;
196 : 0 : };
197 : :
198 : : // Now go through and update the operands
199 [ # # ]: 0 : for (Value *V : ToRevisit) {
200 [ # # ]: 0 : if (GetElementPtrInst *NewGEP = dyn_cast<GetElementPtrInst>(V)) {
201 : 0 : NewGEP->setOperand(GetElementPtrInst::getPointerOperandIndex(),
202 : : CollapseCastsAndLift(NewGEP->getOperand(GetElementPtrInst::getPointerOperandIndex()),
203 : : NewGEP));
204 [ # # ]: 0 : } else if (PHINode *NewPhi = dyn_cast<PHINode>(V)) {
205 [ # # ]: 0 : for (size_t i = 0; i < NewPhi->getNumIncomingValues(); ++i) {
206 : 0 : NewPhi->setIncomingValue(i, CollapseCastsAndLift(NewPhi->getIncomingValue(i),
207 : : NewPhi->getIncomingBlock(i)->getTerminator()));
208 : : }
209 [ # # ]: 0 : } else if (SelectInst *NewSelect = dyn_cast<SelectInst>(V)) {
210 : 0 : NewSelect->setOperand(1, CollapseCastsAndLift(NewSelect->getOperand(1), NewSelect));
211 : 0 : NewSelect->setOperand(2, CollapseCastsAndLift(NewSelect->getOperand(2), NewSelect));
212 : : } else {
213 : : assert(false && "Shouldn't have reached here");
214 : : }
215 : : }
216 : :
217 : 0 : return CollapseCastsAndLift(V, InsertPt);
218 : : }
219 : :
220 : 92 : void PropagateJuliaAddrspacesVisitor::visitMemop(Instruction &I, Type *T, unsigned OpIndex) {
221 : 92 : Value *Original = I.getOperand(OpIndex);
222 : 92 : unsigned AS = Original->getType()->getPointerAddressSpace();
223 [ + + ]: 92 : if (!isSpecialAS(AS))
224 : 64 : return;
225 : 28 : Value *Replacement = LiftPointer(Original, &I);
226 [ + - ]: 28 : if (!Replacement)
227 : 28 : return;
228 : 0 : I.setOperand(OpIndex, Replacement);
229 : : }
230 : :
231 : 56 : void PropagateJuliaAddrspacesVisitor::visitLoadInst(LoadInst &LI) {
232 : 56 : visitMemop(LI, LI.getType(), LoadInst::getPointerOperandIndex());
233 : 56 : }
234 : :
235 : 36 : void PropagateJuliaAddrspacesVisitor::visitStoreInst(StoreInst &SI) {
236 : 36 : visitMemop(SI, SI.getValueOperand()->getType(), StoreInst::getPointerOperandIndex());
237 : 36 : }
238 : :
239 : 0 : void PropagateJuliaAddrspacesVisitor::visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI) {
240 : 0 : visitMemop(SI, SI.getNewValOperand()->getType(), AtomicCmpXchgInst::getPointerOperandIndex());
241 : 0 : }
242 : :
243 : 0 : void PropagateJuliaAddrspacesVisitor::visitAtomicRMWInst(AtomicRMWInst &SI) {
244 : 0 : visitMemop(SI, SI.getType(), AtomicRMWInst::getPointerOperandIndex());
245 : 0 : }
246 : :
247 : 0 : void PropagateJuliaAddrspacesVisitor::visitMemSetInst(MemSetInst &MI) {
248 : 0 : unsigned AS = MI.getDestAddressSpace();
249 [ # # ]: 0 : if (!isSpecialAS(AS))
250 : 0 : return;
251 : 0 : Value *Replacement = LiftPointer(MI.getRawDest());
252 [ # # ]: 0 : if (!Replacement)
253 : 0 : 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 : 0 : void PropagateJuliaAddrspacesVisitor::visitMemTransferInst(MemTransferInst &MTI) {
261 : 0 : unsigned DestAS = MTI.getDestAddressSpace();
262 : 0 : unsigned SrcAS = MTI.getSourceAddressSpace();
263 [ # # # # : 0 : if (!isSpecialAS(DestAS) && !isSpecialAS(SrcAS))
# # ]
264 : 0 : return;
265 : 0 : Value *Dest = MTI.getRawDest();
266 [ # # ]: 0 : if (isSpecialAS(DestAS)) {
267 : 0 : Value *Replacement = LiftPointer(Dest, &MTI);
268 [ # # ]: 0 : if (Replacement)
269 : 0 : Dest = Replacement;
270 : : }
271 : 0 : Value *Src = MTI.getRawSource();
272 [ # # ]: 0 : if (isSpecialAS(SrcAS)) {
273 : 0 : Value *Replacement = LiftPointer(Src, &MTI);
274 [ # # ]: 0 : if (Replacement)
275 : 0 : Src = Replacement;
276 : : }
277 [ # # # # : 0 : if (Dest == MTI.getRawDest() && Src == MTI.getRawSource())
# # ]
278 : 0 : return;
279 : 0 : Function *TheFn = Intrinsic::getDeclaration(MTI.getModule(), MTI.getIntrinsicID(),
280 : 0 : {Dest->getType(), Src->getType(),
281 : 0 : MTI.getOperand(2)->getType()});
282 : 0 : MTI.setCalledFunction(TheFn);
283 : 0 : MTI.setArgOperand(0, Dest);
284 : 0 : MTI.setArgOperand(1, Src);
285 : : }
286 : :
287 : 10 : bool propagateJuliaAddrspaces(Function &F) {
288 : 10 : PropagateJuliaAddrspacesVisitor visitor;
289 : 10 : visitor.visit(F);
290 [ - + ]: 10 : for (auto it : visitor.ToInsert)
291 : 0 : it.first->insertBefore(it.second);
292 [ - + ]: 10 : for (Instruction *I : visitor.ToDelete)
293 : 0 : I->eraseFromParent();
294 : 10 : visitor.ToInsert.clear();
295 : 10 : visitor.ToDelete.clear();
296 : 10 : visitor.LiftingMap.clear();
297 : 10 : visitor.Visited.clear();
298 : 10 : return true;
299 : : }
300 : :
301 : : struct PropagateJuliaAddrspacesLegacy : FunctionPass {
302 : : static char ID;
303 : :
304 : 2 : PropagateJuliaAddrspacesLegacy() : FunctionPass(ID) {}
305 : 10 : bool runOnFunction(Function &F) override {
306 : 10 : 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 : 2 : Pass *createPropagateJuliaAddrspaces() {
314 : 2 : 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 : }
|
