MC: Disassembled CFG reconstruction.

This patch builds on some existing code to do CFG reconstruction from
a disassembled binary:
- MCModule represents the binary, and has a list of MCAtoms.
- MCAtom represents either disassembled instructions (MCTextAtom), or
  contiguous data (MCDataAtom), and covers a specific range of addresses.
- MCBasicBlock and MCFunction form the reconstructed CFG. An MCBB is
  backed by an MCTextAtom, and has the usual successors/predecessors.
- MCObjectDisassembler creates a module from an ObjectFile using a
  disassembler. It first builds an atom for each section. It can also
  construct the CFG, and this splits the text atoms into basic blocks.

MCModule and MCAtom were only sketched out; MCFunction and MCBB were
implemented under the experimental "-cfg" llvm-objdump -macho option.
This cleans them up for further use; llvm-objdump -d -cfg now generates
graphviz files for each function found in the binary.

In the future, MCObjectDisassembler may be the right place to do
"intelligent" disassembly: for example, handling constant islands is just
a matter of splitting the atom, using information that may be available
in the ObjectFile. Also, better initial atom formation than just using
sections is possible using symbols (and things like Mach-O's
function_starts load command).

This brings two minor regressions in llvm-objdump -macho -cfg:
- The printing of a relocation's referenced symbol.
- An annotation on loop BBs, i.e., which are their own successor.

Relocation printing is replaced by the MCSymbolizer; the basic CFG
annotation will be superseded by more related functionality.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182628 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 71 insertions, 22 deletions

diff --git a/include/llvm/MC/MCModule.h b/include/llvm/MC/MCModule.h
index 755fa02..02f8ca0 100644
--- a/include/llvm/MC/MCModule.h
+++ b/include/llvm/MC/MCModule.h
@@ -15,44 +15,93 @@
 #ifndef LLVM_MC_MCMODULE_H
 #define LLVM_MC_MCMODULE_H
 
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IntervalMap.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/DataTypes.h"
+#include <vector>
 
 namespace llvm {
 
 class MCAtom;
+class MCDataAtom;
+class MCFunction;
+class MCObjectDisassembler;
+class MCTextAtom;
 
-/// MCModule - This class represent a completely disassembled object file or
-/// executable.  It comprises a list of MCAtom's, and a branch target table.
-/// Each atom represents a contiguous range of either instructions or data.
+/// \brief A completely disassembled object file or executable.
+/// It comprises a list of MCAtom's, each representing a contiguous range of
+/// either instructions or data.
+/// An MCModule is created using MCObjectDisassembler::buildModule.
 class MCModule {
-  /// AtomAllocationTracker - An MCModule owns its component MCAtom's, so it
-  /// must track them in order to ensure they are properly freed as atoms are
-  /// merged or otherwise manipulated.
-  SmallPtrSet<MCAtom*, 8> AtomAllocationTracker;
+  /// \name Atom tracking
+  /// @{
 
-  /// OffsetMap - Efficiently maps offset ranges to MCAtom's.
-  IntervalMap<uint64_t, MCAtom*> OffsetMap;
-
-  /// BranchTargetMap - Maps offsets that are determined to be branches and
-  /// can be statically resolved to their target offsets.
-  DenseMap<uint64_t, MCAtom*> BranchTargetMap;
+  /// \brief Atoms in this module, sorted by begin address.
+  /// FIXME: This doesn't handle overlapping atoms (which happen when a basic
+  /// block starts in the middle of an instruction of another basic block.)
+  typedef std::vector<MCAtom*> AtomListTy;
+  AtomListTy Atoms;
 
   friend class MCAtom;
-
-  /// remap - Update the interval mapping for an MCAtom.
+  /// \brief Remap \p Atom to the given range, and update its Begin/End fields.
+  /// \param Atom An atom belonging to this module.
+  /// An atom should always use this method to update its bounds, because this
+  /// enables the owning MCModule to keep track of its atoms.
   void remap(MCAtom *Atom, uint64_t NewBegin, uint64_t NewEnd);
 
+  /// \brief Insert an atom in the module, using its Begin and End addresses.
+  void map(MCAtom *NewAtom);
+  /// @}
+
+  /// \name Function tracking
+  /// @{
+  typedef std::vector<MCFunction*> FunctionListTy;
+  FunctionListTy Functions;
+  /// @}
+
+  MCModule           (const MCModule &) LLVM_DELETED_FUNCTION;
+  MCModule& operator=(const MCModule &) LLVM_DELETED_FUNCTION;
+
+  // MCObjectDisassembler creates MCModules.
+  friend class MCObjectDisassembler;
+  MCModule() : Atoms() { }
+
 public:
-  MCModule(IntervalMap<uint64_t, MCAtom*>::Allocator &A) : OffsetMap(A) { }
+  ~MCModule();
 
-  /// createAtom - Creates a new MCAtom covering the specified offset range.
-  MCAtom *createAtom(MCAtom::AtomType Type, uint64_t Begin, uint64_t End);
+  /// \name Create a new MCAtom covering the specified offset range.
+  /// @{
+  MCTextAtom *createTextAtom(uint64_t Begin, uint64_t End);
+  MCDataAtom *createDataAtom(uint64_t Begin, uint64_t End);
+  /// @}
+
+  /// \name Access to the owned atom list, ordered by begin address.
+  /// @{
+  const MCAtom *findAtomContaining(uint64_t Addr) const;
+        MCAtom *findAtomContaining(uint64_t Addr);
+
+  typedef AtomListTy::const_iterator const_atom_iterator;
+  typedef AtomListTy::      iterator       atom_iterator;
+  const_atom_iterator atom_begin() const { return Atoms.begin(); }
+        atom_iterator atom_begin()       { return Atoms.begin(); }
+  const_atom_iterator atom_end()   const { return Atoms.end(); }
+        atom_iterator atom_end()         { return Atoms.end(); }
+  /// @}
+
+  /// \name Create a new MCFunction.
+  MCFunction *createFunction(const StringRef &Name);
+
+  /// \name Access to the owned function list.
+  /// @{
+  typedef FunctionListTy::const_iterator const_func_iterator;
+  typedef FunctionListTy::      iterator       func_iterator;
+  const_func_iterator func_begin() const { return Functions.begin(); }
+        func_iterator func_begin()       { return Functions.begin(); }
+  const_func_iterator func_end()   const { return Functions.end(); }
+        func_iterator func_end()         { return Functions.end(); }
+  /// @}
 };
 
 }
 
 #endif
-