diff options
Diffstat (limited to 'llvm/pass.cpp')
| -rw-r--r-- | llvm/pass.cpp | 469 |
1 files changed, 469 insertions, 0 deletions
diff --git a/llvm/pass.cpp b/llvm/pass.cpp new file mode 100644 index 0000000..2872a98 --- /dev/null +++ b/llvm/pass.cpp @@ -0,0 +1,469 @@ +// 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<std::string> Instr("ztrace-instr", cl::init("lines,calls,vars,stores"), + cl::desc("What to instrument: lines,stores,loads,calls,vars")); +static cl::opt<std::string> 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<std::string> MemOnly("ztrace-mem", cl::desc("Globs: of those, the functions whose stores and loads are instrumented")); +static cl::opt<bool> 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<GlobPattern> Where, Memory; + std::vector<GlobalValue *> Used; + DenseSet<const DIType *> Defined; + DenseMap<const DIFile *, Constant *> Files; + + FunctionCallee callee(const char *Name, std::initializer_list<Type *> 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<StringRef> Words; + StringRef(Instr).split(Words, ',', -1, false); + for (StringRef W : Words) { + bool *Flag = StringSwitch<bool *>(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<DINamespace>(S) || isa<DICompositeType>(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<GlobPattern> &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<DIDerivedType>(T)) + T = D->getBaseType(); + if (auto *C = dyn_cast_or_null<DICompositeType>(T)) + T = C->getBaseType(); // an enum's integer + auto *B = dyn_cast_or_null<DIBasicType>(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<std::string()> 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<DIEnumerator>(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<DIDerivedType>(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<DIBasicType>(T)) + return letter(B) + utostr(B->getSizeInBits()); + if (auto *S = dyn_cast<DISubroutineType>(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<DIDerivedType>(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<DICompositeType>(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<DISubrange>(E)) { + // A flexible or variable-length array has no constant count: 0. + auto *N = dyn_cast_if_present<ConstantInt *>(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<Local> Locals; + SmallPtrSet<Value *, 8> 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<AllocaInst>(V); A && A->isStaticAlloca()) { + if (auto Size = A->getAllocationSize(DL)) + Locals.push_back({A, Size->getFixedValue(), R.getVariable()}); + } else if (auto *Arg = dyn_cast<Argument>(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<LifetimeIntrinsic>(U)) + Life->eraseFromParent(); + + // What was there before anything is inserted. + std::vector<Instruction *> 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<PHINode>(I) && !isa<AllocaInst>(I) && !I->isEHPad() && !I->isLifetimeStartOrEnd() && !isa<UncondBrInst>(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<ReturnInst>(I) || I == Tail)) { + Value *V = I == Tail ? nullptr : cast<ReturnInst>(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<StoreInst>(I); S && Stores) + Addr = S->getPointerOperand(), Size = i64(DL.getTypeStoreSize(S->getValueOperand()->getType())); + else if (auto *A = dyn_cast<AtomicRMWInst>(I); A && Stores) + Addr = A->getPointerOperand(), Size = i64(DL.getTypeStoreSize(A->getValOperand()->getType())); + else if (auto *X = dyn_cast<AtomicCmpXchgInst>(I); X && Stores) + Addr = X->getPointerOperand(), Size = i64(DL.getTypeStoreSize(X->getNewValOperand()->getType())); + else if (auto *Set = dyn_cast<MemIntrinsic>(I); Set && Stores) + Addr = Set->getRawDest(), Size = Set->getLength(); + else if (auto *L = dyn_cast<LoadInst>(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<AllocaInst>(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<Function *> 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<Constant *> Globals; + if (Vars) + for (GlobalVariable &G : M.globals()) { + SmallVector<DIGlobalVariableExpression *, 1> 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<ZtracePass> { + 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<PassBuilder::PipelineElement>) { + if (Name != "ztrace") + return false; + MPM.addPass(ZtracePass()); + return true; + }); + }}; +} |
