Passes for Logging Stackdepth Info

[anniecherk]

Summary

These are two backend passes which log information that can be used to compute stack depth.

[anniecherk]

These are currently a work-in-progress; not ready for review yet.

[anniecherk]

This version includes two passes which run at the very back of the backend, just before codegen:

1. X86LogStackInfo: For every function, this pass logs the function name, stack size, function signature, and the direct & indirect calls made from this function.
2. X86LogStackInfoClasses: This module pass logs any identified struct types in the IR; these include class inheritance data, which can be used to track indirect function calls by function signature.

This version is implemented in the X86 backend. We plan to also support the AArch64 backend. The code in the two passes should run on other backends without modification, except for scheduling the passes to run in other backends. I'm not sure what the most correct way to implement this is, with the least amount of code duplication-- for instance, where in the source tree is the best place for the LogStackInfo passes? I'd appreciate hearing any opinions on this.

[mcgrathr]

I thought the plan was to produce JSON, not YAML.

llvm/lib/Target/X86/X86LogStackInfo.cpp

60

This looks like a really wrong way to generate the file name. String manipulation here is a big red flag.
Why is "." magical??
The file name you need to generate here is something based on the -o argument.

63

Opening the file afresh for each function seems really wrong. The file should be opened exactly one and the stream shared across all runs of the passes in a single translation unit. Besides the cleanliness and performance problems with reopening the file, this approach looks like it will always append to an existing file from a previous compilation, which is completely wrong.

llvm/lib/Target/X86/X86LogStackInfoClasses.cpp

38

The file-opening logic being repeated in two places is another big red flag.

[phosek]

Two high level comments:

1. All new files should have LLVM copyright header.
2. All files should be formatted according to the LLVM style guide (easiest way to achieve that is to run them through clang-format).

[anniecherk]

• Moved from Target/X86 to Codegen. These passes will now run on all backends.

• Fixed a logical bug to check whether a structType has a name before calling getStructName().

• Ran clang-format, clang-check & clang-tidy
  • Question: clang-format reformatted many lines of code that I did not write in a file that I modified. Should I revert these changes?

• Added LLVM copyright headers to new files

• Switched from manual string mangling to llvm's file extension updating function

[anniecherk]

Updated logging approach to log directly to the DiagnosticsOutputFile contained in the LLVMContext.

The main advantage of this approach is the creation, opening, and closing of the output file is already taken care of.
The disadvantage of this approach is other passes do not interact with the DiagnosticOutputFile directly, but instead write to to it using the DiagnosticInfo framework. The DiagnosticInfo framework currently does not support logging any data other than a single integer from Module passes, and does not support logging any data other than strings from Function passes. As an alternative implementation, I could create new DiagnosticInfo subclasses, but it's not clear whether that's the correct approach, and if it is, the details of the best way to do this.

If anyone has opinions on the correct way to do this, please voice them.

Minor update: the function pass now also logs whether that function has both default visibility and is externally visible. A function with those properties can be a root of the call graph.

[anniecherk]

Updated logic to not log callsites which are llvm intrinsics.

llvm/lib/Target/X86/CMakeLists.txt

set(sources
   X86FixupLEAs.cpp
   X86AvoidStoreForwardingBlocks.cpp
   X86FixupSetCC.cpp
   X86FlagsCopyLowering.cpp
   X86FloatingPoint.cpp
   X86FrameLowering.cpp
   X86InstructionSelector.cpp
   X86ISelDAGToDAG.cpp
+  X86LogStackInfo.cpp
+  X86LogStackInfoClasses.cpp
   X86ISelLowering.cpp
   X86IndirectBranchTracking.cpp
   X86InterleavedAccess.cpp
   X86InstrFMA3Info.cpp
   X86InstrInfo.cpp
   X86EvexToVex.cpp
   X86LegalizerInfo.cpp
   X86MCInstLower.cpp

llvm/lib/Target/X86/X86.h

 class ImmutablePass;
 class InstructionSelector;
 class ModulePass;
 class PassRegistry;
 class X86RegisterBankInfo;
 class X86Subtarget;
 class X86TargetMachine;
 
+// This pass logs information about the stack (stack size, function signature,
+// direct & indirect calls) to a yaml file with the same name as the module.
+FunctionPass *createX86LogStackInfo();
+void initializeX86LogStackInfoPass(PassRegistry &);
+
+// This pass logs information from the IR of how classes are related. This supplements
+// the information that X86LogStackInfo logs, making it possible to analyze
+// indirect function calls based on their signatures.
+ModulePass *createX86LogStackInfoClasses();
+void initializeX86LogStackInfoClassesPass(PassRegistry &);
+
 /// This pass converts a legalized DAG into a X86-specific DAG, ready for
 /// instruction scheduling.
 FunctionPass *createX86ISelDag(X86TargetMachine &TM,
                                CodeGenOpt::Level OptLevel);
 
 /// This pass initializes a global base register for PIC on x86-32.
 FunctionPass *createX86GlobalBaseRegPass();
 

llvm/lib/Target/X86/X86LogStackInfo.h

+#include "llvm/Support/YAMLTraits.h"
+
+struct TypeSignature {
+   std::string returnType;
+   std::vector<std::string> argTypes;
+};
+
+template <>
+struct llvm::yaml::MappingTraits<TypeSignature> {
+ static void mapping(IO &io, TypeSignature &info) {
+   io.mapRequired("returnType", info.returnType);
+   io.mapOptional("argTypes",   info.argTypes);
+ }
+};
+
+LLVM_YAML_IS_SEQUENCE_VECTOR(TypeSignature)
+
+struct ClassInfo {
+    std::string FName;
+    std::vector<std::string> IsA;
+};
+
+LLVM_YAML_IS_SEQUENCE_VECTOR(ClassInfo)
+
+ template <>
+ struct llvm::yaml::MappingTraits<ClassInfo> {
+   static void mapping(IO &io, ClassInfo &info) {
+     io.mapRequired("fname", info.FName);
+     io.mapRequired("isa",   info.IsA);
+   }
+ };
+
+ struct StackInfo {
+     std::string FName;
+     TypeSignature Signature;
+     int StackSize;
+     std::vector<std::string> DirectCalls;
+     std::vector<TypeSignature> IndirectCallSigs;
+ };
+
+ template <>
+ struct llvm::yaml::MappingTraits<StackInfo> {
+   static void mapping(IO &io, StackInfo &info) {
+     io.mapRequired("fname",            info.FName);
+     io.mapRequired("signature",        info.Signature);
+     io.mapRequired("stackSize",        info.StackSize);
+     io.mapRequired("directCalls",      info.DirectCalls);
+     io.mapRequired("indirectCallSigs", info.IndirectCallSigs);
+   }
+ };

llvm/lib/Target/X86/X86LogStackInfo.cpp

+#include "X86.h"
+#include "X86LogStackInfo.h"
+#include "X86MachineFunctionInfo.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/YAMLTraits.h"
+#include "llvm/Support/raw_ostream.h"
+#include <string>
+
+extern llvm::cl::opt<bool> GenerateStackAnalysis;
+
+using namespace llvm;
+
+#define X86_LOGSTACKINFO_PASS_NAME "X86 Log Stack Frame"
+
+namespace {
+class X86LogStackInfo : public MachineFunctionPass {
+    public:
+      static char ID;
+
+      X86LogStackInfo() : MachineFunctionPass(ID) {
+        initializeX86LogStackInfoPass(*PassRegistry::getPassRegistry());
+      }
+
+      bool runOnMachineFunction(MachineFunction &MF) override;
+
+      StringRef getPassName() const override
+      { return X86_LOGSTACKINFO_PASS_NAME; }
+}; //end class
+
+char X86LogStackInfo::ID = 0;
+
+// Function to format the type signature
+TypeSignature getSignature(FunctionType* FuncType){
+    TypeSignature Sig;
+    std::string OutputString;
+    llvm::raw_string_ostream SOS(OutputString);
+    FuncType->getReturnType()->print(SOS);
+    SOS.str();
+    Sig.returnType = OutputString;
+
+    std::vector<std::string> argTypes;
+    for(Type* argType : FuncType->params()){
+        OutputString = ""; //reset the string used in the buffer
+        argType->print(SOS);
+        argTypes.push_back(SOS.str());
+    }
+    Sig.argTypes = argTypes;
+    return Sig;
+}
+
+bool X86LogStackInfo::runOnMachineFunction(MachineFunction &MF) {
+    if(GenerateStackAnalysis){
+        std::string OutputFilename = MF.getMMI().getModule()->getName().split(".").first.str() + ".yaml";
+        std::error_code OK;
+        std::error_code OutErrorInfo;
+        llvm::raw_fd_ostream OS(OutputFilename, OutErrorInfo, llvm::sys::fs::F_Append);
+        if (OutErrorInfo != OK)
+          llvm::errs() << "Error opening yaml file: " << OutErrorInfo.message() << "\n";
+
+        StackInfo Info;
+        std::vector<std::string> DirectCalls;
+        std::vector<TypeSignature> IndirectCallSigs;
+        Info.FName =  MF.getName();
+        Info.StackSize = MF.getFrameInfo().getStackSize();
+        Function *F = const_cast<Function*>(&(MF.getFunction()));
+        Info.Signature = getSignature(F->getFunctionType());
+        for (BasicBlock &BB : *F){
+          for (Instruction &I : BB) {
+            if (auto CS = CallSite(&I)) {
+              if(CS.isIndirectCall())
+                  IndirectCallSigs.push_back(getSignature(CS.getFunctionType()));
+              else
+                  DirectCalls.push_back(CS.getCalledFunction()->getName());
+        }}}
+        Info.IndirectCallSigs = IndirectCallSigs;
+        Info.DirectCalls = DirectCalls;
+        llvm::yaml::Output yout(OS);
+        yout << Info;
+        OS.close();
+  } // end if
+  return false;
+} //end runOnMachineFunction
+}  // end anonymous namespace
+
+INITIALIZE_PASS(X86LogStackInfo, "x86-logStackFrames-printer",
+                X86_LOGSTACKINFO_PASS_NAME,
+                true, // is CFG only?
+                true  // is analysis?
+)
+
+namespace llvm {
+FunctionPass *createX86LogStackInfo() { return new X86LogStackInfo(); }
+}

llvm/lib/Target/X86/X86LogStackInfoClasses.cpp

+#include "X86.h"
+#include "X86LogStackInfo.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/YAMLTraits.h"
+#include "llvm/Support/raw_ostream.h"
+#include <string>
+#include <vector>
+
+using namespace llvm;
+
+llvm::cl::opt<bool>
+GenerateStackAnalysis("gen-stack-depth-info",
+               cl::desc("Generate data necessary for stack depth analysis"),
+               cl::value_desc(""));
+
+#define X86_LOGSTACKINFOCLASSES_PASS_NAME "LOG CALL GRAPH MODULE PASS"
+
+namespace {
+class X86LogStackInfoClasses : public ModulePass {
+ public:
+  static char ID;
+
+  X86LogStackInfoClasses() : ModulePass(ID) {
+    initializeX86LogStackInfoClassesPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnModule(Module& M) override;
+
+  StringRef getPassName() const override { return X86_LOGSTACKINFOCLASSES_PASS_NAME; }
+};
+
+char X86LogStackInfoClasses::ID = 0;
+
+bool X86LogStackInfoClasses::runOnModule(Module& M){
+    if(GenerateStackAnalysis){
+        std::string OutputFilename = M.getName().split(".").first.str() + ".yaml";
+        std::error_code OK;
+        std::error_code OutErrorInfo;
+        llvm::raw_fd_ostream OS(OutputFilename, OutErrorInfo, llvm::sys::fs::F_Append);
+        if (OutErrorInfo != OK)
+          llvm::errs() << "Error opening yaml file: " << OutErrorInfo.message() << "\n";
+
+        std::vector<ClassInfo> AllClassData;
+        for(StructType* s: M.getIdentifiedStructTypes()){
+            ClassInfo CI;
+            CI.FName = s->getName();
+            std::vector<std::string> IsA;
+            for(Type* t: s->elements()){
+                if(t->isStructTy())
+                    IsA.push_back(t->getStructName());
+            }
+            if (!IsA.empty()){
+                CI.IsA = IsA;
+                AllClassData.push_back(CI);
+            }
+        }
+        llvm::yaml::Output yout(OS);
+        yout << AllClassData;
+        OS.close();
+    } // end if
+    return false;
+} //end of runOnModule
+}  // end anonymous namespace
+
+INITIALIZE_PASS(X86LogStackInfoClasses, "x86-logstackinfoclasses",
+                X86_LOGSTACKINFOCLASSES_PASS_NAME,
+                true, // is CFG only?
+                true  // is analysis?
+)
+
+namespace llvm {
+ModulePass *createX86LogStackInfoClasses() { return new X86LogStackInfoClasses(); }
+}

llvm/lib/Target/X86/X86TargetMachine.cpp

extern "C" void LLVMInitializeX86Target() {
   initializeFixupLEAPassPass(PR);
   initializeShadowCallStackPass(PR);
   initializeX86CallFrameOptimizationPass(PR);
   initializeX86CmovConverterPassPass(PR);
   initializeX86ExecutionDomainFixPass(PR);
   initializeX86DomainReassignmentPass(PR);
   initializeX86AvoidSFBPassPass(PR);
   initializeX86FlagsCopyLoweringPassPass(PR);
+
+  initializeX86LogStackInfoPass(PR);
+  initializeX86LogStackInfoClassesPass(PR);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.isOSBinFormatMachO()) {
     if (TT.getArch() == Triple::x86_64)
       return llvm::make_unique<X86_64MachoTargetObjectFile>();
     return llvm::make_unique<TargetLoweringObjectFileMachO>();
   }

 void X86PassConfig::addPreEmitPass2() {
   addPass(createX86RetpolineThunksPass());
   // Verify basic block incoming and outgoing cfa offset and register values and
   // correct CFA calculation rule where needed by inserting appropriate CFI
   // instructions.
   const Triple &TT = TM->getTargetTriple();
   if (!TT.isOSDarwin() && !TT.isOSWindows())
     addPass(createCFIInstrInserter());
+
+  addPass(createX86LogStackInfo());
+  addPass(createX86LogStackInfoClasses());
 }