Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : // This LLVM pass verifies invariants required for correct GC root placement.
4 : : // See the devdocs for a description of these invariants.
5 : :
6 : : #include "llvm-version.h"
7 : : #include "passes.h"
8 : :
9 : : #include <llvm-c/Core.h>
10 : : #include <llvm-c/Types.h>
11 : :
12 : : #include <llvm/ADT/BitVector.h>
13 : : #include <llvm/ADT/PostOrderIterator.h>
14 : : #include <llvm/Analysis/CFG.h>
15 : : #include <llvm/IR/Value.h>
16 : : #include <llvm/IR/Constants.h>
17 : : #include <llvm/IR/LegacyPassManager.h>
18 : : #include <llvm/IR/Dominators.h>
19 : : #include <llvm/IR/Function.h>
20 : : #include <llvm/IR/Instructions.h>
21 : : #include <llvm/IR/IntrinsicInst.h>
22 : : #include <llvm/IR/InstVisitor.h>
23 : : #include <llvm/IR/Module.h>
24 : : #include <llvm/IR/IRBuilder.h>
25 : : #include <llvm/IR/Verifier.h>
26 : : #include <llvm/Pass.h>
27 : : #include <llvm/Support/Debug.h>
28 : :
29 : : #include "codegen_shared.h"
30 : : #include "julia.h"
31 : :
32 : : #define DEBUG_TYPE "verify_gc_invariants"
33 : : #undef DEBUG
34 : :
35 : : using namespace llvm;
36 : :
37 : : struct GCInvariantVerifier : public InstVisitor<GCInvariantVerifier> {
38 : : bool Broken = false;
39 : : bool Strong;
40 : 276026 : GCInvariantVerifier(bool Strong = false) : Strong(Strong) {}
41 : :
42 : : private:
43 : 24074900 : void Check(bool Cond, const char *message, Value *Val) {
44 [ - + ]: 24074900 : if (!Cond) {
45 : 0 : dbgs() << message << "\n\t" << *Val << "\n";
46 : 0 : Broken = true;
47 : : }
48 : 24074900 : }
49 : :
50 : : public:
51 : : void visitAddrSpaceCastInst(AddrSpaceCastInst &I);
52 : : void visitLoadInst(LoadInst &LI);
53 : : void visitStoreInst(StoreInst &SI);
54 : : void visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI);
55 : : void visitAtomicRMWInst(AtomicRMWInst &SI);
56 : : void visitReturnInst(ReturnInst &RI);
57 : : void visitGetElementPtrInst(GetElementPtrInst &GEP);
58 : : void visitIntToPtrInst(IntToPtrInst &IPI);
59 : : void visitPtrToIntInst(PtrToIntInst &PII);
60 : : void visitCallInst(CallInst &CI);
61 : :
62 : : void checkStoreInst(Type *VTy, unsigned AS, Value &SI);
63 : : };
64 : :
65 : 3004870 : void GCInvariantVerifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) {
66 : 3004870 : unsigned FromAS = cast<PointerType>(I.getSrcTy())->getAddressSpace();
67 : 3004870 : unsigned ToAS = cast<PointerType>(I.getDestTy())->getAddressSpace();
68 [ + + ]: 3004870 : if (FromAS == 0)
69 : 1033040 : return;
70 [ + - + - ]: 1971830 : Check(ToAS != AddressSpace::Loaded && FromAS != AddressSpace::Loaded,
71 : : "Illegal address space cast involving loaded ptr", &I);
72 [ + + ]: 3943650 : Check(FromAS != AddressSpace::Tracked ||
73 [ + - + - ]: 3943650 : ToAS == AddressSpace::CalleeRooted ||
74 : : ToAS == AddressSpace::Derived,
75 : : "Illegal address space cast from tracked ptr", &I);
76 [ + - + - ]: 1971830 : Check(FromAS != AddressSpace::CalleeRooted &&
77 : : FromAS != AddressSpace::Derived,
78 : : "Illegal address space cast from decayed ptr", &I);
79 : : }
80 : :
81 : 1156020 : void GCInvariantVerifier::checkStoreInst(Type *VTy, unsigned AS, Value &SI) {
82 [ + + ]: 1156020 : if (VTy->isPointerTy()) {
83 : : /* We currently don't obey this for arguments. That's ok - they're
84 : : externally rooted. */
85 : 505022 : unsigned AS = cast<PointerType>(VTy)->getAddressSpace();
86 [ + - + - ]: 505022 : Check(AS != AddressSpace::CalleeRooted &&
87 : : AS != AddressSpace::Derived,
88 : : "Illegal store of decayed value", &SI);
89 : : }
90 : 1156020 : Check(AS != AddressSpace::CalleeRooted,
91 : : "Illegal store to callee rooted value", &SI);
92 : 1156020 : }
93 : :
94 : 1153920 : void GCInvariantVerifier::visitStoreInst(StoreInst &SI) {
95 : 1153920 : Type *VTy = SI.getValueOperand()->getType();
96 : 1153920 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
97 : 1153920 : }
98 : :
99 : 2004 : void GCInvariantVerifier::visitAtomicRMWInst(AtomicRMWInst &SI) {
100 : 2004 : Type *VTy = SI.getValOperand()->getType();
101 : 2004 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
102 : 2004 : }
103 : :
104 : 88 : void GCInvariantVerifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI) {
105 : 88 : Type *VTy = SI.getNewValOperand()->getType();
106 : 88 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
107 : 88 : }
108 : :
109 : 7696720 : void GCInvariantVerifier::visitLoadInst(LoadInst &LI) {
110 : 7696720 : Type *Ty = LI.getType();
111 [ + + ]: 7696720 : if (Ty->isPointerTy()) {
112 : 6478100 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
113 [ + - + - ]: 6478100 : Check(AS != AddressSpace::CalleeRooted &&
114 : : AS != AddressSpace::Derived,
115 : : "Illegal load of gc relevant value", &LI);
116 : : }
117 : 7696720 : Ty = LI.getPointerOperand()->getType();
118 [ + - ]: 7696720 : if (Ty->isPointerTy()) {
119 : 7696720 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
120 : 7696720 : Check(AS != AddressSpace::CalleeRooted,
121 : : "Illegal load of callee rooted value", &LI);
122 : : }
123 : 7696720 : }
124 : :
125 : 6900310 : static bool isSpecialAS(unsigned AS) {
126 [ + + + - ]: 6900310 : return AddressSpace::FirstSpecial <= AS && AS <= AddressSpace::LastSpecial;
127 : : }
128 : :
129 : 311112 : void GCInvariantVerifier::visitReturnInst(ReturnInst &RI) {
130 [ + + ]: 311112 : if (!RI.getReturnValue())
131 : 39648 : return;
132 : 271464 : Type *RTy = RI.getReturnValue()->getType();
133 [ + + ]: 271464 : if (!RTy->isPointerTy())
134 : 57993 : return;
135 : 213471 : unsigned AS = cast<PointerType>(RTy)->getAddressSpace();
136 [ + - + - ]: 213471 : Check(!isSpecialAS(AS) || AS == AddressSpace::Tracked,
137 : : "Only gc tracked values may be directly returned", &RI);
138 : : }
139 : :
140 : 6575160 : void GCInvariantVerifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
141 : 6575160 : Type *Ty = GEP.getType();
142 [ - + ]: 6575160 : if (!Ty->isPointerTy())
143 : 0 : return;
144 : 6575160 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
145 [ + + ]: 6575160 : if (!isSpecialAS(AS))
146 : 4924950 : return;
147 : : /* We're actually ok with GEPs here, as long as they don't feed into any
148 : : uses. Upstream is currently still debating whether CAST(GEP) == GEP(CAST).
149 : : In the frontend, we always perform CAST(GEP), so while we can enforce
150 : : this invariant when we run directly after the frontend (Strong == 1),
151 : : the optimizer will introduce the other form. Thus, we need to allow it
152 : : while upstream hasn't decided whether the optimizer is allowed to
153 : : introduce these.
154 : : */
155 [ + + ]: 1650210 : if (Strong) {
156 : 827240 : Check(AS != AddressSpace::Tracked,
157 : : "GC tracked values may not appear in GEP expressions."
158 : : " You may have to decay the value first", &GEP);
159 : : }
160 : : }
161 : :
162 : 3240150 : void GCInvariantVerifier::visitCallInst(CallInst &CI) {
163 : 3240150 : Function *Callee = CI.getCalledFunction();
164 [ + + + + : 6039230 : if (Callee && (Callee->getName() == "julia.call" ||
+ + ]
165 [ + + ]: 6039230 : Callee->getName() == "julia.call2")) {
166 : 267351 : bool First = true;
167 [ + + ]: 1438480 : for (Value *Arg : CI.args()) {
168 : 1171120 : Type *Ty = Arg->getType();
169 [ + - + + : 1171120 : Check(Ty->isPointerTy() && cast<PointerType>(Ty)->getAddressSpace() == (First ? 0 : AddressSpace::Tracked),
+ - ]
170 : : "Invalid derived pointer in jlcall", &CI);
171 : 1171120 : First = false;
172 : : }
173 : : }
174 : 3240150 : }
175 : :
176 : : /* These next two are caught by the regular verifier on LLVM 5.0+, but we
177 : : may want to run this on earlier LLVM versions. */
178 : 2416 : void GCInvariantVerifier::visitIntToPtrInst(IntToPtrInst &IPI) {
179 : 2416 : Check(!isSpecialAS(IPI.getAddressSpace()),
180 : : "Illegal inttoptr", &IPI);
181 : 2416 : }
182 : :
183 : 109266 : void GCInvariantVerifier::visitPtrToIntInst(PtrToIntInst &PII) {
184 : 109266 : Check(!isSpecialAS(PII.getPointerAddressSpace()),
185 : : "Illegal inttoptr", &PII);
186 : 109266 : }
187 : :
188 : 0 : PreservedAnalyses GCInvariantVerifierPass::run(Function &F, FunctionAnalysisManager &AM) {
189 : 0 : GCInvariantVerifier GIV(Strong);
190 : 0 : GIV.visit(F);
191 [ # # ]: 0 : if (GIV.Broken) {
192 : 0 : abort();
193 : : }
194 : 0 : return PreservedAnalyses::all();
195 : : }
196 : :
197 : : struct GCInvariantVerifierLegacy : public FunctionPass {
198 : : static char ID;
199 : : bool Strong;
200 : 34 : GCInvariantVerifierLegacy(bool Strong=false) : FunctionPass(ID), Strong(Strong) {}
201 : :
202 : : public:
203 : 34 : void getAnalysisUsage(AnalysisUsage &AU) const override {
204 : 34 : FunctionPass::getAnalysisUsage(AU);
205 : 34 : AU.setPreservesAll();
206 : 34 : }
207 : :
208 : 276026 : bool runOnFunction(Function &F) override {
209 : 276026 : GCInvariantVerifier GIV(Strong);
210 : 276026 : GIV.visit(F);
211 [ - + ]: 276026 : if (GIV.Broken) {
212 : 0 : abort();
213 : : }
214 : 276026 : return false;
215 : : }
216 : : };
217 : :
218 : : char GCInvariantVerifierLegacy::ID = 0;
219 : : static RegisterPass<GCInvariantVerifierLegacy> X("GCInvariantVerifier", "GC Invariant Verification Pass", false, false);
220 : :
221 : 34 : Pass *createGCInvariantVerifierPass(bool Strong) {
222 : 34 : return new GCInvariantVerifierLegacy(Strong);
223 : : }
224 : :
225 : 0 : extern "C" JL_DLLEXPORT void LLVMExtraAddGCInvariantVerifierPass_impl(LLVMPassManagerRef PM, LLVMBool Strong)
226 : : {
227 : 0 : unwrap(PM)->add(createGCInvariantVerifierPass(Strong));
228 : 0 : }
|
