[RFC] Assembly Code Super Optimiser

[SjoerdMeijer]

Summary

See RFC here: https://discourse.llvm.org/t/rfc-assembly-super-optimiser/71365

llvm/include/llvm/Support/SMTAPI.h

   /// Returns true if the sort is a boolean, calls isBooleanSortImpl().
   virtual bool isBooleanSort() const { return isBooleanSortImpl(); }
 
+  /// Returns true if the sort is an integer, calls isIntegerSortImpl().
+  virtual bool isIntegerSort() const { return isIntegerSortImpl(); }
+
   /// Returns the bitvector size, fails if the sort is not a bitvector
   /// Calls getBitvectorSortSizeImpl().
   virtual unsigned getBitvectorSortSize() const {

   /// Query the SMT solver and checks if a sort is boolean.
   virtual bool isBooleanSortImpl() const = 0;
 
+  /// Query the SMT solver and checks if a sort is integer.
+  virtual bool isIntegerSortImpl() const = 0;
+
   /// Query the SMT solver and returns the sort bit width.
   virtual unsigned getBitvectorSortSizeImpl() const = 0;
 

   virtual ~SMTSolver() = default;
 
   LLVM_DUMP_METHOD void dump() const;
+  LLVM_DUMP_METHOD void dumpOpt() const;
 
   // Returns an appropriate floating-point sort for the given bitwidth.
   SMTSortRef getFloatSort(unsigned BitWidth) {

   // Returns an appropriate bitvector sort for the given bitwidth.
   virtual SMTSortRef getBitvectorSort(const unsigned BitWidth) = 0;
 
+  // Returns an integer sort
+  virtual SMTSortRef getIntegerSort() = 0;
+
   // Returns a floating-point sort of width 16
   virtual SMTSortRef getFloat16Sort() = 0;
 

   /// Given a constraint, adds it to the solver
   virtual void addConstraint(const SMTExprRef &Exp) const = 0;
 
+  /// Given a constraint, adds it to the optimizing solver
+  virtual void addOptConstraint(const SMTExprRef &Exp) const = 0;
+
   /// Creates a bitvector addition operation
   virtual SMTExprRef mkBVAdd(const SMTExprRef &LHS, const SMTExprRef &RHS) = 0;
 

   /// Creates a bitvector signed greater-equal-than operation
   virtual SMTExprRef mkBVSge(const SMTExprRef &LHS, const SMTExprRef &RHS) = 0;
 
+  /// Creates an integer greater-than operation
+  virtual SMTExprRef mkIntGt(const SMTExprRef &LHS, const SMTExprRef &RHS) = 0;
+
+  /// Creates an integer less-than operation
+  virtual SMTExprRef mkIntLt(const SMTExprRef &LHS, const SMTExprRef &RHS) = 0;
+
+  /// Creates a binary integer add operation
+  virtual SMTExprRef mkIntBinAdd(const SMTExprRef &LHS, const SMTExprRef &RHS) = 0;
+
+
+  /// Creates a minimization operations, and check the model
+  virtual bool mkMinimizeAndCheck(const SMTExprRef &Exp) = 0;
+
+
   /// Creates a boolean not operation
   virtual SMTExprRef mkNot(const SMTExprRef &Exp) = 0;
 

   /// Constructs an SMTExprRef from an APSInt and its bit width
   virtual SMTExprRef mkBitvector(const llvm::APSInt Int, unsigned BitWidth) = 0;
 
+  /// Constructs an integer SMTExprRef from an int
+  virtual SMTExprRef mkInteger(int V) = 0;
+
   /// Given an expression, extract the value of this operand in the model.
   virtual bool getInterpretation(const SMTExprRef &Exp, llvm::APSInt &Int) = 0;
 

   virtual bool getInterpretation(const SMTExprRef &Exp,
                                  llvm::APFloat &Float) = 0;
 
+  /// Given an expression extract the value of this operand in the optimization model.
+  virtual bool getOptInterpretation(const SMTExprRef &Exp, llvm::APSInt &Int) = 0;
+
   /// Check if the constraints are satisfiable
   virtual std::optional<bool> check() const = 0;
 

   virtual bool isFPSupported() = 0;
 
   virtual void print(raw_ostream &OS) const = 0;
+  virtual void printOpt(raw_ostream &OS) const = 0;
 };
 
 /// Shared pointer for SMTSolvers.

llvm/lib/Support/Z3Solver.cpp

 public:
   Z3_context Context;
 
+  // The optimization context
+  Z3_optimize OptContext;
+
+
   Z3Context() {
     Context = Z3_mk_context_rc(Z3Config().Config);
+    OptContext = Z3_mk_optimize(Context);
+    Z3_optimize_inc_ref(Context, OptContext);
+
     // The error function is set here because the context is the first object
     // created by the backend
     Z3_set_error_handler(Context, Z3ErrorHandler);

     return (Z3_get_sort_kind(Context.Context, Sort) == Z3_BOOL_SORT);
   }
 
+  bool isIntegerSortImpl() const override {
+    return (Z3_get_sort_kind(Context.Context, Sort) == Z3_INT_SORT);
+  }
+
   unsigned getBitvectorSortSizeImpl() const override {
     return Z3_get_bv_sort_size(Context.Context, Sort);
   }

     Z3_solver_assert(Context.Context, Solver, toZ3Expr(*Exp).AST);
   }
 
+  void addOptConstraint(const SMTExprRef &Exp) const override {
+    Z3_optimize_assert(Context.Context, Context.OptContext, toZ3Expr(*Exp).AST);
+  }
+
   // Given an SMTSort, adds/retrives it from the cache and returns
   // an SMTSortRef to the SMTSort in the cache
   SMTSortRef newSortRef(const SMTSort &Sort) {

         Z3Sort(Context, Z3_mk_bv_sort(Context.Context, BitWidth)));
   }
 
+  SMTSortRef getIntegerSort() override {
+    return newSortRef(
+        Z3Sort(Context, Z3_mk_int_sort(Context.Context)));
+  }
+
+
   SMTSortRef getSort(const SMTExprRef &Exp) override {
     return newSortRef(
         Z3Sort(Context, Z3_get_sort(Context.Context, toZ3Expr(*Exp).AST)));

         Z3Expr(Context, Z3_mk_not(Context.Context, toZ3Expr(*Exp).AST)));
   }
 
+  bool mkMinimizeAndCheck(const SMTExprRef &Exp) override {
+    auto Min = Z3_optimize_minimize(Context.Context, Context.OptContext, toZ3Expr(*Exp).AST);
+    (void) Min;
+    auto Res = Z3_optimize_check(Context.Context, Context.OptContext, 0, nullptr);
+    return Res == Z3_L_TRUE;
+  }
+
+  SMTExprRef mkIntBinAdd(const SMTExprRef &LHS, const SMTExprRef &RHS) override {
+    auto E1 = toZ3Expr(*LHS).AST;
+    auto E2 = toZ3Expr(*RHS).AST;
+    Z3_ast const args[] = {E1, E2};
+    return newExprRef(
+        Z3Expr(Context, Z3_mk_add(Context.Context, 2, args)));
+  }
+
   SMTExprRef mkBVAdd(const SMTExprRef &LHS, const SMTExprRef &RHS) override {
     return newExprRef(
         Z3Expr(Context, Z3_mk_bvadd(Context.Context, toZ3Expr(*LHS).AST,

                                     toZ3Expr(*RHS).AST)));
   }
 
+  SMTExprRef mkIntGt(const SMTExprRef &LHS, const SMTExprRef &RHS) override {
+    return newExprRef(
+        Z3Expr(Context, Z3_mk_gt(Context.Context, toZ3Expr(*LHS).AST,
+                                    toZ3Expr(*RHS).AST)));
+  }
+  SMTExprRef mkIntLt(const SMTExprRef &LHS, const SMTExprRef &RHS) override {
+    return newExprRef(
+        Z3Expr(Context, Z3_mk_lt(Context.Context, toZ3Expr(*LHS).AST,
+                                    toZ3Expr(*RHS).AST)));
+  }
+
   SMTExprRef mkBVSlt(const SMTExprRef &LHS, const SMTExprRef &RHS) override {
     return newExprRef(
         Z3Expr(Context, Z3_mk_bvslt(Context.Context, toZ3Expr(*LHS).AST,

                                         : Z3_mk_false(Context.Context)));
   }
 
+  SMTExprRef mkInteger(int V) override {
+    auto Sort = Z3_mk_int_sort(Context.Context);
+      return newExprRef(Z3Expr(
+          Context, Z3_mk_int(Context.Context, V, Sort)));
+  }
+
   SMTExprRef mkBitvector(const llvm::APSInt Int, unsigned BitWidth) override {
     const Z3_sort Z3Sort = toZ3Sort(*getBitvectorSort(BitWidth)).Sort;
 

       return true;
     }
 
+    if (Sort->isIntegerSort()) {
+      Int = getBitvector(AST, Int.getBitWidth(), Int.isUnsigned());
+      return true;
+    }
+
     llvm_unreachable("Unsupported sort to integer!");
   }
 

     return toAPFloat(Sort, Assign, Float, true);
   }
 
+  bool getOptInterpretation(const SMTExprRef &Exp, llvm::APSInt &Int) override {
+    auto OptModel = Z3_optimize_get_model(Context.Context, Context.OptContext);
+
+    Z3_func_decl Func = Z3_get_app_decl(
+        Context.Context, Z3_to_app(Context.Context, toZ3Expr(*Exp).AST));
+
+    if (Z3_model_has_interp(Context.Context, OptModel, Func) != Z3_L_TRUE)
+      return false;
+
+    SMTExprRef Assign = newExprRef(
+        Z3Expr(Context,
+               Z3_model_get_const_interp(Context.Context, OptModel, Func)));
+
+    SMTSortRef Sort = getSort(Assign);
+    toAPSInt(Sort, Assign, Int, true);
+    return true;
+  }
+
+
   std::optional<bool> check() const override {
     Z3_lbool res = Z3_solver_check(Context.Context, Solver);
     if (res == Z3_L_TRUE)

   void print(raw_ostream &OS) const override {
     OS << Z3_solver_to_string(Context.Context, Solver);
   }
+
+  void printOpt(raw_ostream &OS) const override {
+    auto OptModel = Z3_optimize_get_model(Context.Context, Context.OptContext);
+    OS << Z3_model_to_string(Context.Context, OptModel);
+  }
 }; // end class Z3Solver
 
 } // end anonymous namespace

 LLVM_DUMP_METHOD void SMTSort::dump() const { print(llvm::errs()); }
 LLVM_DUMP_METHOD void SMTExpr::dump() const { print(llvm::errs()); }
 LLVM_DUMP_METHOD void SMTSolver::dump() const { print(llvm::errs()); }
+LLVM_DUMP_METHOD void SMTSolver::dumpOpt() const { printOpt(llvm::errs()); }

llvm/test/tools/llvm-superasm/ARM/constraints1.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-smt-constraints < %s 2> %t
+# RUN: cat %t | FileCheck %s --check-prefix=CONSTRAINTS
+# RUN: z3 -model %t | FileCheck %s --check-prefix=Z3
+
+
+# CONSTRAINTS:       (declare-const N0 Int)
+# CONSTRAINTS-NEXT:  (assert (> N0 0))
+# CONSTRAINTS-NEXT:  (declare-const N1 Int)
+# CONSTRAINTS-NEXT:  (assert (> N1 0))
+# CONSTRAINTS-NEXT:  (declare-const N2 Int)
+# CONSTRAINTS-NEXT:  (assert (> N2 0))
+# CONSTRAINTS-NEXT:  (declare-const N3 Int)
+# CONSTRAINTS-NEXT:  (assert (> N3 0))
+# CONSTRAINTS-NEXT:  (assert (not (or (= N0 N1) (= N0 N2) (= N0 N3) )))
+# CONSTRAINTS-NEXT:  (assert (not (or (= N1 N0) (= N1 N2) (= N1 N3) )))
+# CONSTRAINTS-NEXT:  (assert (not (or (= N2 N0) (= N2 N1) (= N2 N3) )))
+# CONSTRAINTS-NEXT:  (assert (not (or (= N3 N0) (= N3 N1) (= N3 N2) )))
+# CONSTRAINTS-NEXT:  (assert (< (+ N0 2) N1))
+# CONSTRAINTS-NEXT:  (assert (< (+ N0 2) N1))
+# CONSTRAINTS-NEXT:  (minimize (+ N0 N1 N2 N3 ))
+# CONSTRAINTS-NEXT:  (check-sat)
+
+# Z3:       sat
+# Z3-NEXT:  (
+# Z3-NEXT:    (define-fun N1 () Int
+# Z3-NEXT:      4)
+# Z3-NEXT:    (define-fun N0 () Int
+# Z3-NEXT:      1)
+# Z3-NEXT:    (define-fun N2 () Int
+# Z3-NEXT:      3)
+# Z3-NEXT:    (define-fun N3 () Int
+# Z3-NEXT:      2)
+# Z3-NEXT:  )
+
+mul r1, r2, r3
+mul r5, r1, r1
+add r4, r2, r3
+sub r6, r2, #1

llvm/test/tools/llvm-superasm/ARM/constraints2.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-solver-model < %s 2> %t
+
+# CHECK:       Solver Model:
+# CHECK:       N1 -> 3
+# CHECK-NEXT:  N0 -> 1
+# CHECK-NEXT:  N2 -> 4
+# CHECK-NEXT:  N3 -> 2
+
+mul r1, r2, r3
+mul r5, r1, r1
+add r4, r2, r3
+sub r6, r2, #1

llvm/test/tools/llvm-superasm/ARM/deps.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-dep-graph < %s 2>&1 | FileCheck %s
+
+#CHECK:       digraph deps {
+#CHECK-NEXT:  N0 [label = "   add.w   r1, r2, r3"];
+#CHECK-NEXT:  N1 [label = "   add.w   r4, r2, r1"];
+#CHECK-NEXT:  N2 [label = "   add.w   r1, r2, r3"];
+#CHECK-NEXT:  N0 -> N1 [label = "R1:true"];
+#CHECK-NEXT:  N0 -> N2 [label = "R1:output"];
+#CHECK-NEXT:  N1 -> N2 [label = "R1:anti"];
+#CHECK-NEXT:  }
+
+add r1, r2, r3
+add r4, r2, r1
+add r1, r2, r3

llvm/test/tools/llvm-superasm/ARM/deps1.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-dep-graph < %s 2>&1 | FileCheck %s
+
+# CHECK:       digraph deps {
+# CHECK-NEXT:    N0 [label = "   mul     r3, r1, r2"];
+# CHECK-NEXT:    N1 [label = "   add.w   r2, r5, r6"];
+# CHECK-NEXT:    N0 -> N1 [label = "R2:anti"];
+# CHECK-NEXT:  }
+
+mul r3,r1,r2
+add r2,r5,r6

llvm/test/tools/llvm-superasm/ARM/deps2.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-dep-graph < %s 2>&1 | FileCheck %s
+
+# CHECK:       digraph deps {
+# CHECK-NEXT:  N0 [label = "   vldrw.u32       q0, [r0]"];
+# CHECK-NEXT:  N1 [label = "   vldrw.u32       q1, [r0, #16]"];
+# CHECK-NEXT:  N2 [label = "   vldrw.u32       q2, [r0, #32]"];
+# CHECK-NEXT:  N3 [label = "   vldrw.u32       q7, [r1], #16"];
+# CHECK-NEXT:  N4 [label = "   vmulh.u32       q0, q0, q7"];
+# CHECK-NEXT:  N5 [label = "   vmulh.u32       q1, q1, q7"];
+# CHECK-NEXT:  N6 [label = "   vmulh.u32       q2, q2, q7"];
+# CHECK-NEXT:  N7 [label = "   vadd.i32        q0, q0, q0"];
+# CHECK-NEXT:  N8 [label = "   vadd.i32        q0, q0, q7"];
+# CHECK-NEXT:  N9 [label = "   vadd.i32        q1, q1, q1"];
+# CHECK-NEXT:  N10 [label = "  vadd.i32        q1, q1, q7"];
+# CHECK-NEXT:  N11 [label = "  vadd.i32        q2, q2, q2"];
+# CHECK-NEXT:  N12 [label = "  vadd.i32        q2, q2, q7"];
+# CHECK-NEXT:  N13 [label = "  vstrw.32        q1, [r0, #16]"];
+# CHECK-NEXT:  N14 [label = "  vstrw.32        q2, [r0, #32]"];
+# CHECK-NEXT:  N15 [label = "  vstrw.32        q0, [r0], #48"];
+# CHECK-NEXT:  N0 -> N4 [label = "Q0:output"];
+# CHECK-NEXT:  N0 -> N4 [label = "Q0:true"];
+# CHECK-NEXT:  N1 -> N5 [label = "Q1:output"];
+# CHECK-NEXT:  N1 -> N5 [label = "Q1:true"];
+# CHECK-NEXT:  N2 -> N6 [label = "Q2:output"];
+# CHECK-NEXT:  N2 -> N6 [label = "Q2:true"];
+# CHECK-NEXT:  N3 -> N4 [label = "Q7:true"];
+# CHECK-NEXT:  N3 -> N5 [label = "Q7:true"];
+# CHECK-NEXT:  N3 -> N6 [label = "Q7:true"];
+# CHECK-NEXT:  N3 -> N8 [label = "Q7:true"];
+# CHECK-NEXT:  N3 -> N10 [label = "Q7:true"];
+# CHECK-NEXT:  N3 -> N12 [label = "Q7:true"];
+# CHECK-NEXT:  N4 -> N7 [label = "Q0:output"];
+# CHECK-NEXT:  N4 -> N7 [label = "Q0:true"];
+# CHECK-NEXT:  N4 -> N7 [label = "Q0:true"];
+# CHECK-NEXT:  N4 -> N7 [label = "Q0:anti"];
+# CHECK-NEXT:  N5 -> N9 [label = "Q1:output"];
+# CHECK-NEXT:  N5 -> N9 [label = "Q1:true"];
+# CHECK-NEXT:  N5 -> N9 [label = "Q1:true"];
+# CHECK-NEXT:  N5 -> N9 [label = "Q1:anti"];
+# CHECK-NEXT:  N6 -> N11 [label = "Q2:output"];
+# CHECK-NEXT:  N6 -> N11 [label = "Q2:true"];
+# CHECK-NEXT:  N6 -> N11 [label = "Q2:true"];
+# CHECK-NEXT:  N6 -> N11 [label = "Q2:anti"];
+# CHECK-NEXT:  N7 -> N8 [label = "Q0:output"];
+# CHECK-NEXT:  N7 -> N8 [label = "Q0:true"];
+# CHECK-NEXT:  N7 -> N8 [label = "Q0:anti"];
+# CHECK-NEXT:  N7 -> N8 [label = "Q0:anti"];
+# CHECK-NEXT:  N8 -> N15 [label = "Q0:true"];
+# CHECK-NEXT:  N9 -> N10 [label = "Q1:output"];
+# CHECK-NEXT:  N9 -> N10 [label = "Q1:true"];
+# CHECK-NEXT:  N9 -> N10 [label = "Q1:anti"];
+# CHECK-NEXT:  N9 -> N10 [label = "Q1:anti"];
+# CHECK-NEXT:  N10 -> N13 [label = "Q1:true"];
+# CHECK-NEXT:  N11 -> N12 [label = "Q2:output"];
+# CHECK-NEXT:  N11 -> N12 [label = "Q2:true"];
+# CHECK-NEXT:  N11 -> N12 [label = "Q2:anti"];
+# CHECK-NEXT:  N11 -> N12 [label = "Q2:anti"];
+# CHECK-NEXT:  N12 -> N14 [label = "Q2:true"];
+# CHECK-NEXT:  N13 -> N15 [label = "R0:anti"];
+# CHECK-NEXT:  N14 -> N15 [label = "R0:anti"];
+# CHECK-NEXT:  }
+
+vldrw.u32 q0, [r0]
+vldrw.u32 q1, [r0, #16]
+vldrw.u32 q2, [r0, #32]
+vldrw.u32 q7, [r1], #16
+vmulh.u32 q0, q0, q7
+vmulh.u32 q1, q1, q7
+vmulh.u32 q2, q2, q7
+vadd.u32 q0, q0, q0
+vadd.u32 q0, q0, q7
+vadd.u32 q1, q1, q1
+vadd.u32 q1, q1, q7
+vadd.u32 q2, q2, q2
+vadd.u32 q2, q2, q7
+vstrw.u32 q1, [r0, #16]
+vstrw.u32 q2, [r0, #32]
+vstrw.u32 q0, [r0], #48

llvm/test/tools/llvm-superasm/ARM/deps3.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-dep-graph < %s 2>&1 | FileCheck %s
+
+# CHECK: digraph deps {
+# CHECK-NEXT:  N0 [label = "   vstrw.32        q2, [r0, #32]"];
+# CHECK-NEXT:  N1 [label = "   vstrw.32        q0, [r0], #48"];
+# CHECK-NEXT:  N0 -> N1 [label = "R0:anti"];
+# CHECK-NEXT:  }
+
+vstrw.32        q2, [r0, #32]
+vstrw.32        q0, [r0], #48

llvm/test/tools/llvm-superasm/ARM/scheduling1.s

+# RUN: llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 < %s 2> %t
+
+# CHECK:            mul     r1, r2, r3
+# CHECK-NEXT:       sub.w   r6, r2, #1
+# CHECK-NEXT:       add.w   r4, r2, r3
+# CHECK-NEXT:       mul     r5, r1, r1
+
+mul r1, r2, r3
+mul r5, r1, r1
+add r4, r2, r3
+sub r6, r2, #1

llvm/test/tools/llvm-superasm/ARM/unsupported1.s

+# RUN: not llvm-superasm -mtriple=thumbv8.1-m.main-none-none-eabi -mcpu=cortex-m55 -print-dep-graph < %s 2>&1 | FileCheck %s
+
+# CHECK:  error: branch instructions are not yet supported:
+# CHECK:          b       LOOP
+# CHECK:  error: cannot optimise this input.
+
+LOOP:
+  add r1, r2, r3
+b LOOP

llvm/tools/llvm-superasm/CMakeLists.txt

+include_directories(include)
+
+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmParsers
+  AllTargetsDescs
+  AllTargetsDisassemblers
+  AllTargetsInfos
+  MCA
+  MC
+  MCParser
+  Support
+  TargetParser
+  )
+
+add_llvm_tool(llvm-superasm
+  llvm-superasm.cpp
+  DepGraph.cpp
+  ConstraintManager.cpp
+  )
+
+set(LLVM_SUPERASM_SOURCE_DIR ${CURRENT_SOURCE_DIR})

llvm/tools/llvm-superasm/ConstraintManager.h

+//===-- ConstraintManager.h - Assembly Super Optimiser ---------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  TODO
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_SUPERASM_CONSTRAINT_MANAGER
+#define  LLVM_TOOLS_SUPERASM_CONSTRAINT_MANAGER
+
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/SMTAPI.h"
+#include <map>
+
+using namespace llvm;
+
+class DepGraph;
+class DGNode;
+
+class ConstraintManager {
+  DepGraph *DG;
+  std::vector<SMTExprRef> Symbols;
+
+  mutable llvm::SMTSolverRef Solver = llvm::CreateZ3Solver();
+  std::map<SMTExprRef, DGNode*> Z3Var2Node;
+public:
+
+  ConstraintManager(DepGraph *DG) : DG(DG) { }
+  bool solve();
+  bool createIntConstraints();
+  void setNodeSchedInterpretations();
+  void dumpModel() { dbgs() << "\nSolver model:\n\n"; Solver->dumpOpt(); }
+};
+
+#endif

llvm/tools/llvm-superasm/ConstraintManager.cpp

+//===-- ConstraintManager.cpp - Assembly Super Optimiser -------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  TODO
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "llvm-superasm"
+
+#include "ConstraintManager.h"
+#include "DepGraph.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+extern cl::opt<bool>  PrintSolverModel;
+
+bool ConstraintManager::createIntConstraints() {
+  LLVM_DEBUG(dbgs() << "Creating Z3 constraints:\n\n");
+  for (auto *N : DG->Nodes) {
+    auto Sym = Solver->mkSymbol(N->getName().c_str(),
+                                Solver->getIntegerSort());
+    N->setZ3SchedVar(Sym);
+    Z3Var2Node.insert({Sym, N});
+
+    Symbols.push_back(Sym);
+    auto Zero = Solver->mkInteger(0);
+    auto GT = Solver->mkIntGt(Sym, Zero);
+    LLVM_DEBUG(dbgs() << "Adding constraint: "; GT->dump(); dbgs() << "\n");
+    Solver->addOptConstraint(GT);
+  }
+
+  // All variables should get distinct values.
+  for (unsigned i = 0; i < DG->Nodes.size(); ++i) {
+    for (unsigned j = 0; j < DG->Nodes.size(); ++j) {
+      if (i == j)
+        continue;
+
+      auto Eq = Solver->mkEqual(Symbols[i], Symbols[j]);
+      auto Not = Solver->mkNot(Eq);
+      Solver->addOptConstraint(Not);
+      LLVM_DEBUG(dbgs() << "Adding constraint: "; Not->dump(); dbgs() << "\n");
+    }
+  }
+
+  // Add the scheduling constraints.
+  for (auto E : DG->Edges) {
+    unsigned ID1 = E.Src->getID();
+    unsigned ID2 = E.Dst->getID();
+
+    auto Lat = Solver->mkInteger(E.Src->getLatency());
+    auto Add = Solver->mkIntBinAdd(Symbols[ID1], Lat);
+    auto LT = Solver->mkIntLt(Add, Symbols[ID2]);
+    LLVM_DEBUG(dbgs() << "Adding sched constraint: "; LT->dump(); dbgs() << "\n");
+    Solver->addOptConstraint(LT);
+  }
+
+  if (!DG->Nodes.size())
+    return false;
+  if (DG->Nodes.size() == 1)
+    return Solver->mkMinimizeAndCheck(Symbols[0]);
+
+  auto Add = Solver->mkIntBinAdd(Symbols[0], Symbols[1]);
+  for (unsigned i = 2; i < DG->Nodes.size(); ++i)
+    Add = Solver->mkIntBinAdd(Add, Symbols[i]);
+
+  LLVM_DEBUG(dbgs() << "Constraint to minimize: "; Add->dump(); dbgs() << "\n");
+  return Solver->mkMinimizeAndCheck(Add);
+}
+
+void ConstraintManager::setNodeSchedInterpretations() {
+  for (auto S : Symbols) {
+    APSInt I(32);
+    bool Tmp = Solver->getOptInterpretation(S, I);
+    (void) Tmp;
+    auto Find = Z3Var2Node.find(S);
+    Find->second->setZ3SchedVarInterp(I.getExtValue());
+  }
+}
+
+bool ConstraintManager::solve() {
+  if (!createIntConstraints())
+    return false;
+
+  setNodeSchedInterpretations();
+  return true;
+}

llvm/tools/llvm-superasm/DepGraph.h

+//===-- DepGraph.h - Assembly Super Optimiser ------------------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  TODO
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_SUPER_ASM_H
+#define LLVM_TOOLS_SUPER_ASM_H
+
+#include <vector>
+#include "ConstraintManager.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
+
+using namespace llvm;
+
+class DepGraph;
+
+class DGNode {
+  MCInstrDesc MCDesc;
+  unsigned ID;
+  int Latency;
+
+  SMTExprRef Z3SchedVar;
+  int64_t Z3SchedVarInterpretation;
+
+public:
+  DepGraph *DG;
+  MCInst Ins;
+
+  DGNode(MCInst I, DepGraph *DG, unsigned ID);
+
+  unsigned getNumDefs() { return MCDesc.getNumDefs(); }
+  unsigned getPosDef() { return getNumDefs() - 1; }
+  std::string getName() { return "N" + std::to_string(ID); }
+  bool isSupportedIns(const MCRegisterInfo &MRI);
+  void setLatency(int L) { Latency = L; }
+  int getLatency() { return Latency; }
+  unsigned getID() { return ID; }
+  unsigned getSchedClass() { return MCDesc.getSchedClass(); }
+  void setZ3SchedVar(SMTExprRef V) { Z3SchedVar = V ; }
+  void setZ3SchedVarInterp(unsigned V) { Z3SchedVarInterpretation = V ; }
+  unsigned getZ3SchedVarInterp() { return Z3SchedVarInterpretation; }
+
+  bool isValidReg(int OpIdx) {
+    return Ins.getOperand(OpIdx).isValid() && Ins.getOperand(OpIdx).isReg()
+      && Ins.getOperand(OpIdx).getReg();
+  }
+
+  bool isWriteReg(unsigned OpIdx) {
+    if (!getNumDefs())
+      return false;
+    return OpIdx < getNumDefs();
+  }
+
+  void dumpMCInst();
+  void dumpMCInstNL();
+  void dumpOperandInfo();
+  void dumpOperandInfo(int OpIdx);
+
+  void dumpDotty() {
+    dbgs() << getName() << " [label = \"";
+    dumpMCInst();
+    dbgs() << "\"];\n";
+  }
+};
+
+enum class EdgeType { AntiDep, TrueDep, OutputDep };
+
+class DGEdge {
+public:
+  DGNode *Src;
+  DGNode *Dst;
+  EdgeType DepType;
+  unsigned SrcOpIdx;
+
+  DGEdge(DGNode *S, DGNode *D, EdgeType E, unsigned I)
+    : Src(S), Dst(D), DepType(E), SrcOpIdx(I) {}
+
+  void dumpDotty() {
+    dbgs() << Src->getName();
+    dbgs() << " -> ";
+    dbgs() << Dst->getName();
+    dbgs() << " [label = \"";
+    Src->dumpOperandInfo(SrcOpIdx);
+    dbgs() << ":";
+    if (DepType == EdgeType::AntiDep)
+      dbgs() << "anti";
+    else if (DepType == EdgeType::TrueDep)
+      dbgs() << "true";
+    else
+      dbgs() << "output";
+    dbgs() << "\"];\n";
+
+  }
+};
+
+class DepGraph {
+  formatted_raw_ostream &FOSRef;
+
+public:
+  std::vector<DGNode*> Nodes;
+  std::vector<DGEdge> Edges;
+
+  std::unique_ptr<MCInstrInfo> &MCII;
+  std::unique_ptr<MCSubtargetInfo> &STI;
+  MCInstPrinter *IP;
+  std::unique_ptr<MCRegisterInfo> &MRI;
+
+  DepGraph(formatted_raw_ostream &FOSRef,
+           std::unique_ptr<MCSubtargetInfo> &STI,
+           std::unique_ptr<MCInstrInfo> &MCII, MCInstPrinter *IP,
+           std::unique_ptr<MCRegisterInfo> &MRI) :
+      FOSRef(FOSRef), MCII(MCII), STI(STI), IP(IP), MRI(MRI) {}
+
+  void createEdges();
+  bool createNodes(std::vector<MCInst> &Insts);
+
+  void dumpDotty() {
+    dbgs() << "\ndigraph deps {\n";
+    for (auto *N : Nodes)
+      N->dumpDotty();
+    for (auto E : Edges)
+      E.dumpDotty();
+    dbgs() << "}\n";
+  }
+
+  void dumpSMTConstraints();
+  void scheduleNodes();
+  void printNodes();
+
+  void printNodeAddrs() {
+    for (auto *N : Nodes) {
+      dbgs() << "Node: " << N << "\n";
+    }
+  }
+};
+
+#endif

llvm/tools/llvm-superasm/DepGraph.cpp

+//===-- DepGraph.cpp - Assembly Super Optimiser ----------------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  TODO
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "llvm-superasm"
+
+#include "DepGraph.h"
+#include <algorithm>
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSchedule.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Support/WithColor.h"
+
+bool DepGraph::createNodes(std::vector<MCInst> &Insts) {
+  unsigned ID = 0;
+  const MCSchedModel &SM = STI->getSchedModel();
+  for (auto I : Insts) {
+    DGNode *N = new DGNode(I, this, ID++);
+    if (!N->isSupportedIns(*MRI))
+      return false;
+    Nodes.push_back(N);
+
+    unsigned SchedClassID = N->getSchedClass();
+    const MCSchedClassDesc &SCDesc = *SM.getSchedClassDesc(SchedClassID);
+    int Latency = MCSchedModel::computeInstrLatency(*STI, SCDesc);
+    LLVM_DEBUG(dbgs() << "Created node " << N->getID() << ", Latency = "
+               << Latency << "\n");
+    N->setLatency(Latency);
+  }
+  return true;
+}
+
+void DepGraph::dumpSMTConstraints() {
+  LLVM_DEBUG(dbgs() << "\nSMT constraints:\n\n");
+  // Add all variables.
+  for (auto *N: Nodes) {
+    dbgs() << "(declare-const " << N->getName() << " Int)\n";
+    dbgs() << "(assert (> " << N->getName() << " 0))\n";
+  }
+
+  // All variables should get distinct values.
+  for (unsigned i = 0; i < Nodes.size(); ++i) {
+    dbgs() << "(assert (not (or ";
+    for (unsigned j = 0; j < Nodes.size(); ++j) {
+      if (i == j)
+        continue;
+      dbgs() << "(= " << Nodes[i]->getName() << " " << Nodes[j]->getName() << ") ";
+    }
+    dbgs() << ")))\n";
+  }
+
+  // Add the scheduling constraints.
+  for (auto E : Edges) {
+    dbgs() << "(assert (< ";
+    if (E.DepType == EdgeType::TrueDep) {
+      dbgs() << "(+ " << E.Src->getName() << " " << E.Src->getLatency() << ") "
+        << E.Dst->getName() ;
+      dbgs() << "))\n";
+    } else {
+      dbgs() << E.Src->getName() << " " << E.Dst->getName() << "))\n";
+    }
+  }
+
+  // Add the constraint to minimise the schedule
+  dbgs() << "(minimize (+ ";
+  for (auto *N: Nodes)
+    dbgs() << N->getName() << " ";
+  dbgs() << "))\n";
+
+  dbgs() << "(check-sat)\n";
+  dbgs() << "\n";
+}
+
+void DepGraph::createEdges() {
+  LLVM_DEBUG(dbgs() << "Analysing " << Nodes.size() << " nodes.\n");
+  for (unsigned i = 0; i < Nodes.size(); i++) {
+    LLVM_DEBUG(dbgs() << "\n== Analysing instruction: "; Nodes[i]->dumpMCInstNL());
+    auto I = Nodes[i]->Ins;
+    bool FoundOutputDep = false;
+    for (unsigned j=i+1; j < Nodes.size() ; j++) {
+      LLVM_DEBUG(dbgs() << "Looking at: "; Nodes[j]->dumpMCInstNL());
+      auto J = Nodes[j]->Ins;
+      for (unsigned IOpIdx = 0; IOpIdx < I.getNumOperands(); IOpIdx++) {
+        if (!Nodes[i]->isValidReg(IOpIdx))
+          continue;
+        for (unsigned JOpIdx = 0; JOpIdx < J.getNumOperands(); JOpIdx++) {
+          if (!Nodes[j]->isValidReg(JOpIdx))
+            continue;
+          LLVM_DEBUG(dbgs() << "Comparing: ";
+                     Nodes[i]->dumpOperandInfo(IOpIdx);
+                     dbgs() << " == "; Nodes[j]->dumpOperandInfo(JOpIdx);
+                     dbgs() << "\n");
+          if (I.getOperand(IOpIdx).getReg() != J.getOperand(JOpIdx).getReg())
+            continue;
+          int IWrite = Nodes[i]->isWriteReg(IOpIdx);
+          int JWrite = Nodes[j]->isWriteReg(JOpIdx);
+
+          if (IWrite && JWrite) {
+            LLVM_DEBUG(dbgs() << "Found an output dependency in: ";
+                       Nodes[j]->dumpMCInstNL());
+            Edges.push_back(DGEdge(Nodes[i], Nodes[j], EdgeType::OutputDep,
+                                   IOpIdx));
+            FoundOutputDep = true;
+          } else if (IWrite && !JWrite) {
+            LLVM_DEBUG(dbgs() << "Found a true dependency in: ";
+                       Nodes[j]->dumpMCInstNL());
+            Edges.push_back(DGEdge(Nodes[i], Nodes[j], EdgeType::TrueDep,
+                                   IOpIdx));
+          } else if (!IWrite && JWrite) {
+            LLVM_DEBUG(dbgs() << "Found an anti dependency in: ";
+                       Nodes[j]->dumpMCInstNL());
+            Edges.push_back(DGEdge(Nodes[i], Nodes[j], EdgeType::AntiDep,
+                                   IOpIdx));
+            FoundOutputDep = true;
+          }
+        }
+      }
+      if (FoundOutputDep)
+        break;
+    }
+  }
+}
+
+static bool compareSchedVarInterp(DGNode *LHS, DGNode *RHS) {
+  return LHS->getZ3SchedVarInterp() < RHS->getZ3SchedVarInterp();
+}
+
+void DepGraph::scheduleNodes() {
+  std::sort(Nodes.begin(), Nodes.end(), compareSchedVarInterp);
+}
+
+void DepGraph::printNodes() {
+  dbgs() << "\n";
+  for (auto *N : Nodes) {
+    // FIXME
+    IP->printInst(&N->Ins, 0, "", *N->DG->STI, dbgs());
+    dbgs() << "\n";
+  }
+}
+
+void DGNode::dumpMCInst() {
+  DG->IP->printInst(&Ins, 0, "", *DG->STI, dbgs());
+}
+void DGNode::dumpMCInstNL() {
+  DG->IP->printInst(&Ins, 0, "", *DG->STI, dbgs());
+  dbgs() << "\n";
+}
+
+void DGNode::dumpOperandInfo(int OpIdx) {
+    dbgs() <<
+      DG->MRI->getName(Ins.getOperand(OpIdx).getReg());
+}
+
+void DGNode::dumpOperandInfo() {
+  dbgs() << "Number of operands: " << MCDesc.getNumOperands() << "\n";
+  dbgs() << "Number of defs: " << MCDesc.getNumDefs() << "\n";
+  dbgs() << "Def reg name: ";
+  if (!getNumDefs())
+    dbgs() << "<none>\n";
+  else
+    dbgs() <<
+      DG->MRI->getName(Ins.getOperand(getPosDef()).getReg()) <<  "\n";
+}
+
+DGNode::DGNode(MCInst I, DepGraph *D, unsigned Num) {
+  Ins = I;
+  DG = D;
+  MCDesc = DG->MCII->get(I.getOpcode());
+  ID = Num;
+}
+
+bool DGNode::isSupportedIns(const MCRegisterInfo &MRI) {
+  if (MCDesc.mayAffectControlFlow(Ins, MRI)) {
+    WithColor::error() << "branch instructions are not yet supported:\n";
+    dumpMCInstNL();
+    return false;
+  }
+  if (MCDesc.isBarrier()) {
+    WithColor::error() << "function calls are not yet supported:\n";
+    dumpMCInstNL();
+    return false;
+  }
+  return true;
+}

llvm/tools/llvm-superasm/MCStreamerWrapper.h

+//===-- MCStreamerWrapper.h - Assembly Super Optimiser ---------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// TODO
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/MC/MCStreamer.h"
+
+using namespace llvm;
+
+class MCStreamerWrapper final : public MCStreamer {
+public:
+  std::vector<MCInst> Insts;
+
+  MCStreamerWrapper(MCContext &Context)
+      : MCStreamer(Context) {}
+
+  // We only want to intercept the emission of new instructions.
+  void emitInstruction(const MCInst &Inst,
+                       const MCSubtargetInfo & /* unused */) override {
+    Insts.push_back(Inst);
+  }
+
+  bool emitSymbolAttribute(MCSymbol *Symbol, MCSymbolAttr Attribute) override {
+    return true;
+  }
+
+  void emitCommonSymbol(MCSymbol *Symbol, uint64_t Size,
+                        Align ByteAlignment) override {}
+  void emitZerofill(MCSection *Section, MCSymbol *Symbol = nullptr,
+                    uint64_t Size = 0, Align ByteAlignment = Align(1),
+                    SMLoc Loc = SMLoc()) override {}
+  void emitGPRel32Value(const MCExpr *Value) override {}
+  void beginCOFFSymbolDef(const MCSymbol *Symbol) override {}
+  void emitCOFFSymbolStorageClass(int StorageClass) override {}
+  void emitCOFFSymbolType(int Type) override {}
+  void endCOFFSymbolDef() override {}
+};

llvm/tools/llvm-superasm/llvm-superasm.cpp

+//===-- llvm-superasm.cpp - Assembly Super Optimiser -----------*- C++ -* -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//   llvm-superasm [options] <file-name>
+//      -march <type>
+//      -mcpu <cpu>
+//      -o <file>
+//
+// The target defaults to the host target.
+// The cpu defaults to the 'native' host cpu.
+// The output defaults to standard output.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ConstraintManager.h"
+#include "DepGraph.h"
+#include "MCStreamerWrapper.h"
+#include "llvm/MC/MCAsmBackend.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCCodeEmitter.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCStreamer.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/MC/MCTargetOptionsCommandFlags.h"
+#include "llvm/MC/TargetRegistry.h"
+#include "llvm/MC/MCParser/MCAsmLexer.h"
+#include "llvm/MC/MCParser/MCAsmParser.h"
+#include "llvm/MC/MCParser/MCTargetAsmParser.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Support/WithColor.h"
+#include "llvm/TargetParser/Host.h"
+
+using namespace llvm;
+
+static mc::RegisterMCTargetOptionsFlags MOF;
+
+static cl::OptionCategory ToolOptions("Tool Options");
+static cl::OptionCategory ViewOptions("View Options");
+static cl::OptionCategory MCCategory("MC Options");
+
+static cl::opt<std::string> InputFilename(cl::Positional,
+                                          cl::desc("<input file>"),
+                                          cl::cat(ToolOptions), cl::init("-"));
+
+static cl::opt<std::string> OutputFilename("o", cl::desc("Output filename"),
+                                           cl::init("-"), cl::cat(ToolOptions),
+                                           cl::value_desc("filename"));
+
+static cl::opt<std::string>
+    ArchName("march",
+             cl::desc("Target architecture. "
+                      "See -version for available targets"),
+             cl::cat(ToolOptions));
+
+static cl::opt<std::string>
+    TripleName("mtriple",
+               cl::desc("Target triple. See -version for available targets"),
+               cl::cat(ToolOptions));
+
+static cl::opt<std::string>
+    MCPU("mcpu",
+         cl::desc("Target a specific cpu type (-mcpu=help for details)"),
+         cl::value_desc("cpu-name"), cl::cat(ToolOptions), cl::init("native"));
+
+static cl::list<std::string>
+    MATTRS("mattr", cl::CommaSeparated,
+           cl::desc("Target specific attributes (-mattr=help for details)"),
+           cl::value_desc("a1,+a2,-a3,..."), cl::cat(ToolOptions));
+
+static cl::opt<int>
+    OutputAsmVariant("output-asm-variant",
+                     cl::desc("Syntax variant to use for output printing"),
+                     cl::cat(ToolOptions), cl::init(-1));
+
+static cl::opt<bool>
+    PrintDepGraph("print-dep-graph", cl::cat(ViewOptions), cl::init(false),
+                  cl::desc("Print the dependency graph in Dot format"));
+
+static cl::opt<bool>
+    PrintSMTConstraints("print-smt-constraints", cl::cat(ViewOptions),
+                        cl::init(false),
+                        cl::desc("Print the scheduling constraints"));
+cl::opt<bool>
+    PrintSolverModel("print-solver-model", cl::cat(ViewOptions),
+                        cl::init(false),
+                        cl::desc("Print the output of the SMT solver"));
+
+static cl::opt<bool>
+    ShowInstOperands("show-inst-operands",
+                     cl::desc("Show instructions operands as parsed"),
+                     cl::cat(MCCategory));
+
+namespace {
+
+const Target *getTarget(const char *ProgName) {
+  if (TripleName.empty())
+    TripleName = Triple::normalize(sys::getDefaultTargetTriple());
+  Triple TheTriple(TripleName);
+
+  // Get the target specific parser.
+  std::string Error;
+  const Target *TheTarget =
+      TargetRegistry::lookupTarget(ArchName, TheTriple, Error);
+  if (!TheTarget) {
+    errs() << ProgName << ": " << Error;
+    return nullptr;
+  }
+
+  // Update TripleName with the updated triple from the target lookup.
+  TripleName = TheTriple.str();
+
+  // Return the found target.
+  return TheTarget;
+}
+
+} // end of anonymous namespace
+
+static int ParseInput(const char *ProgName, const Target *TheTarget,
+                      SourceMgr &SrcMgr, MCContext &Ctx, MCStreamerWrapper &Str,
+                      MCAsmInfo &MAI, MCSubtargetInfo &STI,
+                      MCInstrInfo &MCII, MCTargetOptions const &MCOptions) {
+
+  std::unique_ptr<MCAsmParser> Parser(createMCAsmParser(SrcMgr, Ctx, Str, MAI));
+  std::unique_ptr<MCTargetAsmParser> TAP(
+      TheTarget->createMCAsmParser(STI, *Parser, MCII, MCOptions));
+
+  if (!TAP) {
+    WithColor::error(errs(), ProgName)
+        << "this target does not support assembly parsing.\n";
+    return 1;
+  }
+
+  Parser->setShowParsedOperands(ShowInstOperands);
+  Parser->setTargetParser(*TAP);
+  int Res = Parser->Run(false/*NoInitialTextSection*/);
+  return Res;
+}
+
+static std::unique_ptr<ToolOutputFile> GetOutputStream(StringRef Path,
+    sys::fs::OpenFlags Flags) {
+  std::error_code EC;
+  auto Out = std::make_unique<ToolOutputFile>(Path, EC, Flags);
+  if (EC) {
+    WithColor::error() << EC.message() << '\n';
+    return nullptr;
+  }
+
+  return Out;
+}
+
+int main(int argc, char **argv) {
+  InitLLVM X(argc, argv);
+
+  // Initialize targets and assembly parsers.
+  InitializeAllTargetInfos();
+  InitializeAllTargetMCs();
+  InitializeAllAsmParsers();
+
+  // Register the Target and CPU printer for --version.
+  cl::AddExtraVersionPrinter(sys::printDefaultTargetAndDetectedCPU);
+
+  // Enable printing of available targets when flag --version is specified.
+  cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
+
+  cl::HideUnrelatedOptions({&ToolOptions, &ViewOptions, &MCCategory});
+
+  // Parse flags and initialize target options.
+  cl::ParseCommandLineOptions(argc, argv,
+                              "llvm machine code performance analyzer.\n");
+
+  // Get the target from the triple. If a triple is not specified, then select
+  // the default triple for the host. If the triple doesn't correspond to any
+  // registered target, then exit with an error message.
+  const char *ProgName = argv[0];
+  const Target *TheTarget = getTarget(ProgName);
+  if (!TheTarget)
+    return 1;
+
+  // GetTarget() may replaced TripleName with a default triple.
+  // For safety, reconstruct the Triple object.
+  Triple TheTriple(TripleName);
+
+  ErrorOr<std::unique_ptr<MemoryBuffer>> BufferPtr =
+      MemoryBuffer::getFileOrSTDIN(InputFilename);
+  if (std::error_code EC = BufferPtr.getError()) {
+    WithColor::error() << InputFilename << ": " << EC.message() << '\n';
+    return 1;
+  }
+
+  if (MCPU == "native")
+    MCPU = std::string(llvm::sys::getHostCPUName());
+
+  // Package up features to be passed to target/subtarget
+  std::string FeaturesStr;
+  if (MATTRS.size()) {
+    SubtargetFeatures Features;
+    for (std::string &MAttr : MATTRS)
+      Features.AddFeature(MAttr);
+    FeaturesStr = Features.getString();
+  }
+
+  std::unique_ptr<MCSubtargetInfo> STI(
+      TheTarget->createMCSubtargetInfo(TripleName, MCPU, FeaturesStr));
+  assert(STI && "Unable to create subtarget info!");
+  if (!STI->isCPUStringValid(MCPU))
+    return 1;
+
+  if (!STI->getSchedModel().hasInstrSchedModel()) {
+    WithColor::error()
+        << "unable to find instruction-level scheduling information for"
+        << " target triple '" << TheTriple.normalize() << "' and cpu '" << MCPU
+        << "'.\n";
+
+    if (STI->getSchedModel().InstrItineraries)
+      WithColor::note()
+          << "cpu '" << MCPU << "' provides itineraries. However, "
+          << "instruction itineraries are currently unsupported.\n";
+    return 1;
+  }
+
+  std::unique_ptr<MCRegisterInfo> MRI(TheTarget->createMCRegInfo(TripleName));
+  assert(MRI && "Unable to create target register info!");
+
+  MCTargetOptions MCOptions = mc::InitMCTargetOptionsFromFlags();
+  std::unique_ptr<MCAsmInfo> MAI(
+      TheTarget->createMCAsmInfo(*MRI, TripleName, MCOptions));
+  assert(MAI && "Unable to create target asm info!");
+
+  SourceMgr SrcMgr;
+
+  // Tell SrcMgr about this buffer, which is what the parser will pick up.
+  SrcMgr.AddNewSourceBuffer(std::move(*BufferPtr), SMLoc());
+
+  MCContext Ctx(TheTriple, MAI.get(), MRI.get(), STI.get(), &SrcMgr);
+  std::unique_ptr<MCObjectFileInfo> MOFI(
+      TheTarget->createMCObjectFileInfo(Ctx, /*PIC=*/false));
+  Ctx.setObjectFileInfo(MOFI.get());
+
+  std::unique_ptr<MCInstrInfo> MCII(TheTarget->createMCInstrInfo());
+  assert(MCII && "Unable to create instruction info!");
+
+  std::unique_ptr<MCInstrAnalysis> MCIA(
+      TheTarget->createMCInstrAnalysis(MCII.get()));
+
+  // Need to initialize an MCInstPrinter as it is
+  // required for initializing the MCTargetStreamer
+  // which needs to happen within the CRG.parseAnalysisRegions() call below.
+  // Without an MCTargetStreamer, certain assembly directives can trigger a
+  // segfault. (For example, the .cv_fpo_proc directive on x86 will segfault if
+  // we don't initialize the MCTargetStreamer.)
+  unsigned IPtempOutputAsmVariant =
+      OutputAsmVariant == -1 ? 0 : OutputAsmVariant;
+
+  MCInstPrinter *IP = TheTarget->createMCInstPrinter(
+      Triple(TripleName), IPtempOutputAsmVariant, *MAI, *MCII, *MRI);
+
+  if (!IP) {
+    WithColor::error()
+        << "unable to create instruction printer for target triple '"
+        << TheTriple.normalize() << "' with assembly variant "
+        << IPtempOutputAsmVariant << ".\n";
+    return 1;
+  }
+
+  sys::fs::OpenFlags Flags = sys::fs::OF_TextWithCRLF;
+  std::unique_ptr<ToolOutputFile> Out = GetOutputStream(OutputFilename, Flags);
+  if (!Out)
+    return 1;
+
+  std::unique_ptr<buffer_ostream> BOS;
+  raw_pwrite_stream *OS = &Out->os();
+  MCStreamerWrapper Str(Ctx);
+
+   // Set up the AsmStreamer.
+  std::unique_ptr<MCCodeEmitter> CE;
+
+  std::unique_ptr<MCAsmBackend> MAB(
+      TheTarget->createMCAsmBackend(*STI, *MRI, MCOptions));
+  auto FOut = std::make_unique<formatted_raw_ostream>(*OS);
+
+  formatted_raw_ostream FOSRef(*OS);
+  TheTarget->createAsmTargetStreamer(Str, FOSRef, IP,
+                                    /*IsVerboseAsm=*/true);
+
+  DepGraph DG(FOSRef, STI, MCII, IP, MRI);
+  ParseInput(ProgName, TheTarget, SrcMgr, Ctx, Str, *MAI, *STI, *MCII, MCOptions);
+
+  if (!DG.createNodes(Str.Insts)) {
+    WithColor::error() << "cannot optimise this input.\n";
+    return 1;
+  }
+
+  DG.createEdges();
+  if (PrintDepGraph)
+    DG.dumpDotty();
+  if (PrintSMTConstraints)
+    DG.dumpSMTConstraints();
+
+  ConstraintManager CM(&DG);
+  if (!CM.solve())
+    return 1;
+
+  if (PrintSolverModel)
+    CM.dumpModel();
+
+  DG.scheduleNodes();
+  DG.printNodes();
+  return 0;
+}