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 : 1381430 : GCInvariantVerifier(bool Strong = false) : Strong(Strong) {}
41 : :
42 : : private:
43 : 80252700 : void Check(bool Cond, const char *message, Value *Val) {
44 [ - + ]: 80252700 : if (!Cond) {
45 : 0 : dbgs() << message << "\n\t" << *Val << "\n";
46 : 0 : Broken = true;
47 : : }
48 : 80252700 : }
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 : 10375400 : void GCInvariantVerifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) {
66 : 10375400 : unsigned FromAS = cast<PointerType>(I.getSrcTy())->getAddressSpace();
67 : 10375400 : unsigned ToAS = cast<PointerType>(I.getDestTy())->getAddressSpace();
68 [ + + ]: 10375400 : if (FromAS == 0)
69 : 1583420 : return;
70 [ + - + - ]: 8791970 : Check(ToAS != AddressSpace::Loaded && FromAS != AddressSpace::Loaded,
71 : : "Illegal address space cast involving loaded ptr", &I);
72 [ + + ]: 17583900 : Check(FromAS != AddressSpace::Tracked ||
73 [ + - + - ]: 17583900 : ToAS == AddressSpace::CalleeRooted ||
74 : : ToAS == AddressSpace::Derived,
75 : : "Illegal address space cast from tracked ptr", &I);
76 [ + - + - ]: 8791970 : Check(FromAS != AddressSpace::CalleeRooted &&
77 : : FromAS != AddressSpace::Derived,
78 : : "Illegal address space cast from decayed ptr", &I);
79 : : }
80 : :
81 : 9645150 : void GCInvariantVerifier::checkStoreInst(Type *VTy, unsigned AS, Value &SI) {
82 [ + + ]: 9645150 : if (VTy->isPointerTy()) {
83 : : /* We currently don't obey this for arguments. That's ok - they're
84 : : externally rooted. */
85 : 1985100 : unsigned AS = cast<PointerType>(VTy)->getAddressSpace();
86 [ + - + - ]: 1985100 : Check(AS != AddressSpace::CalleeRooted &&
87 : : AS != AddressSpace::Derived,
88 : : "Illegal store of decayed value", &SI);
89 : : }
90 : 9645150 : Check(AS != AddressSpace::CalleeRooted,
91 : : "Illegal store to callee rooted value", &SI);
92 : 9645150 : }
93 : :
94 : 9626750 : void GCInvariantVerifier::visitStoreInst(StoreInst &SI) {
95 : 9626750 : Type *VTy = SI.getValueOperand()->getType();
96 : 9626750 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
97 : 9626750 : }
98 : :
99 : 6303 : void GCInvariantVerifier::visitAtomicRMWInst(AtomicRMWInst &SI) {
100 : 6303 : Type *VTy = SI.getValOperand()->getType();
101 : 6303 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
102 : 6303 : }
103 : :
104 : 12099 : void GCInvariantVerifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &SI) {
105 : 12099 : Type *VTy = SI.getNewValOperand()->getType();
106 : 12099 : checkStoreInst(VTy, SI.getPointerAddressSpace(), SI);
107 : 12099 : }
108 : :
109 : 19520000 : void GCInvariantVerifier::visitLoadInst(LoadInst &LI) {
110 : 19520000 : Type *Ty = LI.getType();
111 [ + + ]: 19520000 : if (Ty->isPointerTy()) {
112 : 9210560 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
113 [ + - + - ]: 9210560 : Check(AS != AddressSpace::CalleeRooted &&
114 : : AS != AddressSpace::Derived,
115 : : "Illegal load of gc relevant value", &LI);
116 : : }
117 : 19520000 : Ty = LI.getPointerOperand()->getType();
118 [ + - ]: 19520000 : if (Ty->isPointerTy()) {
119 : 19520000 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
120 : 19520000 : Check(AS != AddressSpace::CalleeRooted,
121 : : "Illegal load of callee rooted value", &LI);
122 : : }
123 : 19520000 : }
124 : :
125 : 21462100 : static bool isSpecialAS(unsigned AS) {
126 [ + + + - ]: 21462100 : return AddressSpace::FirstSpecial <= AS && AS <= AddressSpace::LastSpecial;
127 : : }
128 : :
129 : 1423120 : void GCInvariantVerifier::visitReturnInst(ReturnInst &RI) {
130 [ + + ]: 1423120 : if (!RI.getReturnValue())
131 : 186178 : return;
132 : 1236940 : Type *RTy = RI.getReturnValue()->getType();
133 [ + + ]: 1236940 : if (!RTy->isPointerTy())
134 : 226228 : return;
135 : 1010710 : unsigned AS = cast<PointerType>(RTy)->getAddressSpace();
136 [ + + + - ]: 1010710 : Check(!isSpecialAS(AS) || AS == AddressSpace::Tracked,
137 : : "Only gc tracked values may be directly returned", &RI);
138 : : }
139 : :
140 : 20131900 : void GCInvariantVerifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
141 : 20131900 : Type *Ty = GEP.getType();
142 [ + + ]: 20131900 : if (!Ty->isPointerTy())
143 : 121 : return;
144 : 20131800 : unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
145 [ + + ]: 20131800 : if (!isSpecialAS(AS))
146 : 10130300 : 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 [ + + ]: 10001400 : if (Strong) {
156 : 7011200 : 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 : 17487900 : void GCInvariantVerifier::visitCallInst(CallInst &CI) {
163 : 17487900 : Function *Callee = CI.getCalledFunction();
164 [ + + + + : 33246500 : if (Callee && (Callee->getName() == "julia.call" ||
+ + ]
165 [ + + ]: 33246500 : Callee->getName() == "julia.call2")) {
166 : 1149260 : bool First = true;
167 [ + + ]: 6323680 : for (Value *Arg : CI.args()) {
168 : 5174420 : Type *Ty = Arg->getType();
169 [ + - + + : 5174420 : Check(Ty->isPointerTy() && cast<PointerType>(Ty)->getAddressSpace() == (First ? 0 : AddressSpace::Tracked),
+ - ]
170 : : "Invalid derived pointer in jlcall", &CI);
171 : 5174420 : First = false;
172 : : }
173 : : }
174 : 17487900 : }
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 : 15018 : void GCInvariantVerifier::visitIntToPtrInst(IntToPtrInst &IPI) {
179 : 15018 : Check(!isSpecialAS(IPI.getAddressSpace()),
180 : : "Illegal inttoptr", &IPI);
181 : 15018 : }
182 : :
183 : 304627 : void GCInvariantVerifier::visitPtrToIntInst(PtrToIntInst &PII) {
184 : 304627 : Check(!isSpecialAS(PII.getPointerAddressSpace()),
185 : : "Illegal inttoptr", &PII);
186 : 304627 : }
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 : 2104 : GCInvariantVerifierLegacy(bool Strong=false) : FunctionPass(ID), Strong(Strong) {}
201 : :
202 : : public:
203 : 2104 : void getAnalysisUsage(AnalysisUsage &AU) const override {
204 : 2104 : FunctionPass::getAnalysisUsage(AU);
205 : 2104 : AU.setPreservesAll();
206 : 2104 : }
207 : :
208 : 1381430 : bool runOnFunction(Function &F) override {
209 : 1381430 : GCInvariantVerifier GIV(Strong);
210 : 1381430 : GIV.visit(F);
211 [ - + ]: 1381430 : if (GIV.Broken) {
212 : 0 : abort();
213 : : }
214 : 1381430 : return false;
215 : : }
216 : : };
217 : :
218 : : char GCInvariantVerifierLegacy::ID = 0;
219 : : static RegisterPass<GCInvariantVerifierLegacy> X("GCInvariantVerifier", "GC Invariant Verification Pass", false, false);
220 : :
221 : 2104 : Pass *createGCInvariantVerifierPass(bool Strong) {
222 : 2104 : 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 : }
|
