// ztrace-pass.so: an LLVM pass plugin that instruments a program for // animation. Each inserted call hands the runtime (src/instr/rt.zig) what a // viewer needs, so nothing parses DWARF at view time: // // lines __zt_line(file, line, column) before each new source line of a block // stores __zt_store(addr, size) after each store, memset, memcpy // loads __zt_load(addr, size) after each load; neither for the // compiler's own temporaries // calls __zt_enter(name, type, sp, site) at function entry // __zt_exit(name, value, size) before each return // vars __zt_var(addr, size, name, type, arg) per named local, after __zt_enter; // a record in section ztrace_vars per global // // file, name and type are texts: pointers to records in section ztrace_strs // (id, length, text), one per text in the program, the linker folding the // copies of other translation units. The runtime numbers them from 1 and // emits each as a `string` before the first event: an id is a byte or two // in a recording. Type descriptions follow the grammar in // src/instr/types.zig; the description of a named type has its id fixed // here, a hash of the name, so a viewer finds it from the name. // // clang -g -fpass-plugin=ztrace-pass.so -Xclang -load -Xclang ztrace-pass.so \ // -mllvm -ztrace-instr=lines,calls,vars,stores \ // -mllvm -ztrace-only='sqlite3Btree*,*/pager.c' -mllvm -ztrace-mem='*Insert*' // opt -load-pass-plugin=ztrace-pass.so -passes=ztrace // // It runs before optimization by default: every local still has an address // and a debug record that says so, every source store exists, lines come in // source order; the optimizer then keeps what the calls made observable. // -ztrace-late runs it after: the stores, loads and lines of the code that // really runs, and only the variables the optimizer left in memory. #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/BinaryFormat/Dwarf.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DebugProgramInstruction.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/Passes/PassBuilder.h" #include "llvm/Plugins/PassPlugin.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/GlobPattern.h" #include "llvm/Support/Path.h" #include "llvm/Transforms/Utils/ModuleUtils.h" using namespace llvm; static cl::opt Instr("ztrace-instr", cl::init("lines,calls,vars,stores"), cl::desc("What to instrument: lines,stores,loads,calls,vars")); static cl::opt Only("ztrace-only", cl::desc("Globs: instrument only the functions and globals whose name, " "source path or source file name matches one")); static cl::opt MemOnly("ztrace-mem", cl::desc("Globs: of those, the functions whose stores and loads are instrumented")); static cl::opt Late("ztrace-late", cl::desc("Instrument after optimization")); namespace { uint64_t hash(StringRef S) { uint64_t H = 0xcbf29ce484222325; for (unsigned char C : S) H = (H ^ C) * 0x100000001b3; return H; } struct Instrumenter { Module &M; LLVMContext &Ctx = M.getContext(); const DataLayout &DL = M.getDataLayout(); Type *Void = Type::getVoidTy(Ctx), *Ptr = PointerType::getUnqual(Ctx); IntegerType *I32 = Type::getInt32Ty(Ctx), *I64 = Type::getInt64Ty(Ctx); bool Lines = false, Stores = false, Loads = false, Calls = false, Vars = false; std::vector Where, Memory; std::vector Used; DenseSet Defined; DenseMap Files; FunctionCallee callee(const char *Name, std::initializer_list Params) { return M.getOrInsertFunction(Name, FunctionType::get(Void, Params, false)); } ConstantInt *i64(uint64_t V) { return ConstantInt::get(I64, V); } Instrumenter(Module &M) : M(M) { SmallVector Words; StringRef(Instr).split(Words, ',', -1, false); for (StringRef W : Words) { bool *Flag = StringSwitch(W).Case("lines", &Lines).Case("stores", &Stores).Case("loads", &Loads).Case("calls", &Calls).Case("vars", &Vars).Default(nullptr); if (!Flag) reportFatalUsageError(Twine("-ztrace-instr: '") + W + "' is none of lines,stores,loads,calls,vars"); *Flag = true; } for (auto [Text, Globs] : {std::pair(StringRef(Only), &Where), std::pair(StringRef(MemOnly), &Memory)}) { Words.clear(); Text.split(Words, ',', -1, false); for (StringRef W : Words) { auto G = GlobPattern::create(W); if (!G) reportFatalUsageError(Twine("ztrace: glob '") + W + "': " + toString(G.takeError())); Globs->push_back(*G); } } } // Names. // The record the runtime turns into a `string` event: id, length, text, // padded to 8 bytes. One per name in the program: the linker folds the // rest. Id 0 is the runtime's to number. Constant *record(const Twine &Name, uint64_t Id, StringRef Text) { if (GlobalVariable *G = M.getNamedGlobal(Name.str())) return G; std::string Bytes(16 + alignTo(Text.size(), 8), '\0'); uint64_t Len = Text.size(); memcpy(&Bytes[0], &Id, 8); memcpy(&Bytes[8], &Len, 8); memcpy(&Bytes[16], Text.data(), Len); Constant *Init = ConstantDataArray::getString(Ctx, Bytes, false); auto *G = new GlobalVariable(M, Init->getType(), false, GlobalValue::LinkOnceODRLinkage, Init, Name); G->setSection("ztrace_strs"); G->setAlignment(Align(8)); G->setVisibility(GlobalValue::HiddenVisibility); G->setComdat(M.getOrInsertComdat(G->getName())); Used.push_back(G); return G; } Constant *str(StringRef Text) { return record("__zt_s_" + utohexstr(hash(Text)), 0, Text); } static std::string path(const DIFile *F) { SmallString<256> P(F->getFilename()); if (!sys::path::is_absolute(P)) { P = F->getDirectory(); sys::path::append(P, F->getFilename()); } sys::path::remove_dots(P, true); return std::string(P); } // C++: the namespaces and classes a name sits in. static std::string qualified(const DIScope *S, StringRef Name) { std::string Out(Name); for (; S && (isa(S) || isa(S)); S = S->getScope()) Out = (S->getName().empty() ? "(anonymous)" : S->getName().str()) + "::" + Out; return Out; } // No list selects everything; a list, what has a name (as written, or as // linked) or a source file (its path, or its last part) matching one glob. static bool selected(std::vector &Globs, StringRef Name, StringRef Linked, const DIFile *File) { std::string Path = File ? path(File) : ""; for (GlobPattern &G : Globs) if (G.match(Name) || G.match(Linked) || G.match(Path) || G.match(sys::path::filename(Path))) return true; return Globs.empty(); } // Type descriptions: the grammar of src/instr/types.zig. static std::string opaque(const DIType *T) { return "x" + utostr(T->getSizeInBits()); } static char letter(const DIType *T) { while (auto *D = dyn_cast_or_null(T)) T = D->getBaseType(); if (auto *C = dyn_cast_or_null(T)) T = C->getBaseType(); // an enum's integer auto *B = dyn_cast_or_null(T); switch (B ? B->getEncoding() : 0) { case dwarf::DW_ATE_boolean: return 'b'; case dwarf::DW_ATE_float: return 'f'; case dwarf::DW_ATE_signed: return 'i'; case dwarf::DW_ATE_unsigned: return 'u'; case dwarf::DW_ATE_signed_char: return B->getName() == "char" ? 'c' : 'i'; case dwarf::DW_ATE_unsigned_char: return B->getName() == "char" ? 'c' : 'u'; case dwarf::DW_ATE_UTF: case dwarf::DW_ATE_ASCII: return 'c'; default: return 'x'; } } // A named type is written as its name. Its description is a text of its // own, under an id no numbered text has (the top bit) that follows from // the name: `defId` in types.zig. It is marked defined before its body is // described, so a struct that points to itself ends. std::string named(const DIType *T, std::string Name, bool HasBody, function_ref Body) { if (HasBody && Defined.insert(T).second) { uint64_t Id = hash("=" + Name) | 1ull << 63; record("__zt_d_" + utohexstr(Id), Id, Body()); } return "`" + Name + "`"; } std::string record(const DICompositeType *C) { if (C->getTag() == dwarf::DW_TAG_enumeration_type) { std::string Out = "enum(" + (C->getBaseType() ? type(C->getBaseType()) : "u" + utostr(C->getSizeInBits())) + "){"; for (DINode *E : C->getElements()) if (auto *V = dyn_cast(E)) Out += V->getName().str() + "=" + toString(V->getValue(), 10, !V->isUnsigned()) + ";"; return Out + "}"; } std::string Out = (C->getTag() == dwarf::DW_TAG_union_type ? "union(" : "struct(") + utostr(C->getSizeInBits() / 8) + "){"; for (DINode *E : C->getElements()) { auto *F = dyn_cast(E); if (!F || F->isStaticMember() || (F->getTag() != dwarf::DW_TAG_member && F->getTag() != dwarf::DW_TAG_inheritance)) continue; for (char Ch : F->getName()) Out += isAlnum(Ch) || Ch == '$' ? Ch : '_'; uint64_t At = F->getOffsetInBits(); Out += "@" + utostr(At / 8); if (F->isBitField()) Out += "." + utostr(At % 8) + ":" + letter(F->getBaseType()) + utostr(F->getSizeInBits()); else Out += ":" + type(F->getBaseType()); Out += ";"; } return Out + "}"; } std::string type(const DIType *T) { if (!T) return "void"; if (auto *B = dyn_cast(T)) return letter(B) + utostr(B->getSizeInBits()); if (auto *S = dyn_cast(T)) { DITypeArray Types = S->getTypeArray(); std::string Out = "fn("; for (unsigned I = 1; I < Types.size(); ++I) Out += (I > 1 ? "," : "") + (Types[I] ? type(Types[I]) : "..."); return Out + ")" + type(Types.size() ? Types[0] : nullptr); } if (auto *D = dyn_cast(T)) { switch (D->getTag()) { case dwarf::DW_TAG_pointer_type: case dwarf::DW_TAG_reference_type: case dwarf::DW_TAG_rvalue_reference_type: return "*" + type(D->getBaseType()); case dwarf::DW_TAG_typedef: return named(D, qualified(D->getScope(), D->getName()), true, [&] { return type(D->getBaseType()); }); case dwarf::DW_TAG_ptr_to_member_type: return opaque(D); default: // const, volatile, restrict, atomic return type(D->getBaseType()); } } if (auto *C = dyn_cast(T)) { unsigned Tag = C->getTag(); if (Tag == dwarf::DW_TAG_array_type && !C->isVector()) { std::string Out; for (DINode *E : C->getElements()) if (auto *R = dyn_cast(E)) { // A flexible or variable-length array has no constant count: 0. auto *N = dyn_cast_if_present(R->getCount()); Out += "[" + utostr(N && N->getSExtValue() > 0 ? N->getZExtValue() : 0) + "]"; } return Out + type(C->getBaseType()); } bool Struct = Tag == dwarf::DW_TAG_structure_type || Tag == dwarf::DW_TAG_class_type; if (Struct || Tag == dwarf::DW_TAG_union_type || Tag == dwarf::DW_TAG_enumeration_type) { if (C->getName().empty()) return record(C); // shortcut: two different types with one name (file-local structs in // two C files) share a definition; add the declaring file to the name // when a target has them. return named(C, (Struct ? "struct " : Tag == dwarf::DW_TAG_union_type ? "union " : "enum ") + qualified(C->getScope(), C->getName()), !C->isForwardDecl(), [&] { return record(C); }); } } return opaque(T); } // Code. void instrument(Function &F) { DISubprogram *SP = F.getSubprogram(); BasicBlock &Entry = F.getEntryBlock(); std::string FName = qualified(SP->getScope(), SP->getName()); bool Mem = selected(Memory, FName, F.getName(), SP->getFile()); // The named locals that live in memory: the first debug record that // gives a static alloca or a by-value argument as a variable's address. // That is #dbg_declare at -O0, and #dbg_assign from -O1 on, where clang // turns the one into the other before any plugin runs. struct Local { Value *Addr; uint64_t Size; DILocalVariable *Var; }; std::vector Locals; SmallPtrSet Named; for (BasicBlock &BB : F) for (Instruction &I : BB) for (DbgVariableRecord &R : filterDbgVars(I.getDbgRecordRange())) { if (!R.isDbgDeclare() && !R.isDbgAssign()) continue; Value *V = R.getAddress(); if (!V || !Named.insert(V).second || !Vars || (R.isDbgAssign() ? R.getAddressExpression() : R.getExpression())->getNumElements()) continue; if (auto *A = dyn_cast(V); A && A->isStaticAlloca()) { if (auto Size = A->getAllocationSize(DL)) Locals.push_back({A, Size->getFixedValue(), R.getVariable()}); } else if (auto *Arg = dyn_cast(V); Arg && Arg->hasByValAttr()) { Locals.push_back({Arg, DL.getTypeAllocSize(Arg->getParamByValType()).getFixedValue(), R.getVariable()}); } } // Declared for the whole call, so two of them must not share a stack // slot: without its lifetime markers a slot is never reused. for (Local &L : Locals) for (User *U : make_early_inc_range(L.Addr->users())) if (auto *Life = dyn_cast(U)) Life->eraseFromParent(); // What was there before anything is inserted. std::vector Body; for (BasicBlock &BB : F) for (Instruction &I : BB) Body.push_back(&I); IRBuilder<> B(&Entry, Entry.getFirstNonPHIOrDbgOrAlloca()); B.SetCurrentDebugLocation(DILocation::get(Ctx, SP->getScopeLine(), 0, SP)); Constant *Name = Calls ? str(FName) : nullptr; if (Calls) { Value *Sp = B.CreateIntrinsic(Intrinsic::addressofreturnaddress, {Ptr}, {}); Value *Site = B.CreateIntrinsic(Intrinsic::returnaddress, {Ptr}, {ConstantInt::get(I32, 0)}); B.CreateCall(callee("__zt_enter", {Ptr, Ptr, Ptr, Ptr}), {Name, str(type(SP->getType())), Sp, Site}); } for (Local &L : Locals) B.CreateCall(callee("__zt_var", {Ptr, I64, Ptr, Ptr, I32}), {L.Addr, i64(L.Size), str(L.Var->getName()), str(type(L.Var->getType())), ConstantInt::get(I32, L.Var->getArg())}); const BasicBlock *Block = nullptr; const DIFile *File = nullptr; unsigned Line = 0; for (Instruction *I : Body) { // Nothing may come between a musttail call and its return: the call // is where this function ends. CallInst *Tail = I->getParent()->getTerminatingMustTailCall(); if (Tail && I != Tail && Tail->comesBefore(I)) continue; B.SetInsertPoint(I); // A line event where a block reaches a line it was not on. A block // always says where it is: a loop comes back to the same line. Jumps // do no work of their own (the closing brace of a loop body). if (I->getParent() != Block) { Block = I->getParent(); Line = 0; } const DebugLoc &Loc = I->getDebugLoc(); if (Lines && Loc && Loc.getLine() && !isa(I) && !isa(I) && !I->isEHPad() && !I->isLifetimeStartOrEnd() && !isa(I) && (Loc.getLine() != Line || Loc->getFile() != File)) { Line = Loc.getLine(); File = Loc->getFile(); auto [At, New] = Files.try_emplace(File); if (New) At->second = str(path(File)); B.CreateCall(callee("__zt_line", {Ptr, I32, I32}), {At->second, ConstantInt::get(I32, Line), ConstantInt::get(I32, Loc.getCol())}); } if (Calls && (isa(I) || I == Tail)) { Value *V = I == Tail ? nullptr : cast(I)->getReturnValue(); Type *T = V ? V->getType() : Void; unsigned Bits = T->isPointerTy() ? 64 : T->isIntegerTy() || T->isFloatTy() || T->isDoubleTy() ? T->getPrimitiveSizeInBits().getFixedValue() : 0; if (Bits == 0 || Bits > 64) V = i64(0), Bits = 0; // void, or an aggregate: no value else if (T->isPointerTy()) V = B.CreatePtrToInt(V, I64); else V = B.CreateZExt(B.CreateBitCast(V, IntegerType::get(Ctx, Bits)), I64); B.CreateCall(callee("__zt_exit", {Ptr, I64, I32}), {Name, V, ConstantInt::get(I32, (Bits + 7) / 8)}); } Value *Addr = nullptr, *Size = nullptr; const char *Hook = "__zt_store"; if (auto *S = dyn_cast(I); S && Stores) Addr = S->getPointerOperand(), Size = i64(DL.getTypeStoreSize(S->getValueOperand()->getType())); else if (auto *A = dyn_cast(I); A && Stores) Addr = A->getPointerOperand(), Size = i64(DL.getTypeStoreSize(A->getValOperand()->getType())); else if (auto *X = dyn_cast(I); X && Stores) Addr = X->getPointerOperand(), Size = i64(DL.getTypeStoreSize(X->getNewValOperand()->getType())); else if (auto *Set = dyn_cast(I); Set && Stores) Addr = Set->getRawDest(), Size = Set->getLength(); else if (auto *L = dyn_cast(I); L && Loads) Addr = L->getPointerOperand(), Size = i64(DL.getTypeStoreSize(L->getType())), Hook = "__zt_load"; // Not the stack slots the compiler made for itself (a return value on // its way out, a temporary): nothing names them, so nothing draws them. Value *Object = Addr ? getUnderlyingObject(Addr) : nullptr; if (Addr && Mem && (!isa(Object) || Named.count(Object))) { // After it: the runtime reads the bytes the store left. B.SetInsertPoint(I->getNextNode()); B.SetCurrentDebugLocation(Loc); B.CreateCall(callee(Hook, {Ptr, I64}), {Addr, B.CreateZExtOrTrunc(Size, I64)}); } } } bool run() { std::vector Functions; for (Function &F : M) { DISubprogram *SP = F.getSubprogram(); if (!F.isDeclaration() && SP && !F.hasAvailableExternallyLinkage() && !F.hasFnAttribute(Attribute::Naked) && !F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation) && selected(Where, qualified(SP->getScope(), SP->getName()), F.getName(), SP->getFile())) Functions.push_back(&F); } // The globals with debug info: {address, size, name, type} each, for the // runtime to declare and snapshot at startup. std::vector Globals; if (Vars) for (GlobalVariable &G : M.globals()) { SmallVector Info; G.getDebugInfo(Info); if (G.isDeclaration() || G.hasAvailableExternallyLinkage() || G.isThreadLocal() || Info.empty()) continue; DIGlobalVariable *V = Info[0]->getVariable(); std::string Name = qualified(V->getScope(), V->getName()); if (selected(Where, Name, G.getName(), V->getFile())) Globals.push_back(ConstantStruct::getAnon({&G, i64(DL.getTypeAllocSize(G.getValueType())), str(Name), str(type(V->getType()))})); } for (Function *F : Functions) instrument(*F); for (Constant *Init : Globals) { auto *G = new GlobalVariable(M, Init->getType(), true, GlobalValue::PrivateLinkage, Init, "__zt_v"); G->setSection("ztrace_vars"); G->setAlignment(Align(8)); Used.push_back(G); } // Used: nothing refers to these records but the section's bounds. appendToUsed(M, Used); return !Used.empty() || !Functions.empty(); } }; struct ZtracePass : PassInfoMixin { PreservedAnalyses run(Module &M, ModuleAnalysisManager &) { return Instrumenter(M).run() ? PreservedAnalyses::none() : PreservedAnalyses::all(); } // Also for the optnone functions of -O0. static bool isRequired() { return true; } }; } // namespace extern "C" LLVM_ATTRIBUTE_WEAK PassPluginLibraryInfo llvmGetPassPluginInfo() { return {LLVM_PLUGIN_API_VERSION, "ztrace", "0.1", [](PassBuilder &PB) { PB.registerPipelineStartEPCallback([](ModulePassManager &MPM, OptimizationLevel) { if (!Late) MPM.addPass(ZtracePass()); }); PB.registerOptimizerLastEPCallback([](ModulePassManager &MPM, OptimizationLevel, ThinOrFullLTOPhase) { if (Late) MPM.addPass(ZtracePass()); }); PB.registerPipelineParsingCallback([](StringRef Name, ModulePassManager &MPM, ArrayRef) { if (Name != "ztrace") return false; MPM.addPass(ZtracePass()); return true; }); }}; }