Index: llvm/include/llvm/Support/SMTAPI.h =================================================================== --- llvm/include/llvm/Support/SMTAPI.h +++ llvm/include/llvm/Support/SMTAPI.h @@ -37,6 +37,9 @@ /// 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 { @@ -86,6 +89,9 @@ /// 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; @@ -139,6 +145,7 @@ 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) { @@ -162,6 +169,9 @@ // 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; @@ -180,6 +190,9 @@ /// 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; @@ -249,6 +262,20 @@ /// 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; @@ -411,6 +438,9 @@ /// 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; @@ -418,6 +448,9 @@ 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 check() const = 0; @@ -434,6 +467,7 @@ virtual bool isFPSupported() = 0; virtual void print(raw_ostream &OS) const = 0; + virtual void printOpt(raw_ostream &OS) const = 0; }; /// Shared pointer for SMTSolvers. Index: llvm/lib/Support/Z3Solver.cpp =================================================================== --- llvm/lib/Support/Z3Solver.cpp +++ llvm/lib/Support/Z3Solver.cpp @@ -52,8 +52,15 @@ 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); @@ -118,6 +125,10 @@ 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); } @@ -289,6 +300,10 @@ 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) { @@ -312,6 +327,12 @@ 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))); @@ -348,6 +369,21 @@ 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, @@ -432,6 +468,17 @@ 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, @@ -725,6 +772,12 @@ : 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; @@ -839,6 +892,11 @@ return true; } + if (Sort->isIntegerSort()) { + Int = getBitvector(AST, Int.getBitWidth(), Int.isUnsigned()); + return true; + } + llvm_unreachable("Unsupported sort to integer!"); } @@ -870,6 +928,25 @@ 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 check() const override { Z3_lbool res = Z3_solver_check(Context.Context, Solver); if (res == Z3_L_TRUE) @@ -896,6 +973,11 @@ 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 @@ -916,3 +998,4 @@ 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()); } Index: llvm/test/tools/llvm-superasm/ARM/constraints1.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/constraints1.s @@ -0,0 +1,38 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/constraints2.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/constraints2.s @@ -0,0 +1,12 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/deps.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/deps.s @@ -0,0 +1,14 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/deps1.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/deps1.s @@ -0,0 +1,10 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/deps2.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/deps2.s @@ -0,0 +1,78 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/deps3.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/deps3.s @@ -0,0 +1,10 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/scheduling1.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/scheduling1.s @@ -0,0 +1,11 @@ +# 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 Index: llvm/test/tools/llvm-superasm/ARM/unsupported1.s =================================================================== --- /dev/null +++ llvm/test/tools/llvm-superasm/ARM/unsupported1.s @@ -0,0 +1,9 @@ +# 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 Index: llvm/tools/llvm-superasm/CMakeLists.txt =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/CMakeLists.txt @@ -0,0 +1,21 @@ +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}) Index: llvm/tools/llvm-superasm/ConstraintManager.h =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/ConstraintManager.h @@ -0,0 +1,40 @@ +//===-- 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 + +using namespace llvm; + +class DepGraph; +class DGNode; + +class ConstraintManager { + DepGraph *DG; + std::vector Symbols; + + mutable llvm::SMTSolverRef Solver = llvm::CreateZ3Solver(); + std::map Z3Var2Node; +public: + + ConstraintManager(DepGraph *DG) : DG(DG) { } + bool solve(); + bool createIntConstraints(); + void setNodeSchedInterpretations(); + void dumpModel() { dbgs() << "\nSolver model:\n\n"; Solver->dumpOpt(); } +}; + +#endif Index: llvm/tools/llvm-superasm/ConstraintManager.cpp =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/ConstraintManager.cpp @@ -0,0 +1,93 @@ +//===-- 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 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; +} Index: llvm/tools/llvm-superasm/DepGraph.h =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/DepGraph.h @@ -0,0 +1,148 @@ +//===-- 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 +#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 Nodes; + std::vector Edges; + + std::unique_ptr &MCII; + std::unique_ptr &STI; + MCInstPrinter *IP; + std::unique_ptr &MRI; + + DepGraph(formatted_raw_ostream &FOSRef, + std::unique_ptr &STI, + std::unique_ptr &MCII, MCInstPrinter *IP, + std::unique_ptr &MRI) : + FOSRef(FOSRef), MCII(MCII), STI(STI), IP(IP), MRI(MRI) {} + + void createEdges(); + bool createNodes(std::vector &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 Index: llvm/tools/llvm-superasm/DepGraph.cpp =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/DepGraph.cpp @@ -0,0 +1,192 @@ +//===-- 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 +#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 &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() << "\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; +} Index: llvm/tools/llvm-superasm/MCStreamerWrapper.h =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/MCStreamerWrapper.h @@ -0,0 +1,44 @@ +//===-- 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 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 {} +}; Index: llvm/tools/llvm-superasm/llvm-superasm.cpp =================================================================== --- /dev/null +++ llvm/tools/llvm-superasm/llvm-superasm.cpp @@ -0,0 +1,326 @@ +//===-- 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] +// -march +// -mcpu +// -o +// +// 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 InputFilename(cl::Positional, + cl::desc(""), + cl::cat(ToolOptions), cl::init("-")); + +static cl::opt OutputFilename("o", cl::desc("Output filename"), + cl::init("-"), cl::cat(ToolOptions), + cl::value_desc("filename")); + +static cl::opt + ArchName("march", + cl::desc("Target architecture. " + "See -version for available targets"), + cl::cat(ToolOptions)); + +static cl::opt + TripleName("mtriple", + cl::desc("Target triple. See -version for available targets"), + cl::cat(ToolOptions)); + +static cl::opt + 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 + 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 + OutputAsmVariant("output-asm-variant", + cl::desc("Syntax variant to use for output printing"), + cl::cat(ToolOptions), cl::init(-1)); + +static cl::opt + PrintDepGraph("print-dep-graph", cl::cat(ViewOptions), cl::init(false), + cl::desc("Print the dependency graph in Dot format")); + +static cl::opt + PrintSMTConstraints("print-smt-constraints", cl::cat(ViewOptions), + cl::init(false), + cl::desc("Print the scheduling constraints")); +cl::opt + PrintSolverModel("print-solver-model", cl::cat(ViewOptions), + cl::init(false), + cl::desc("Print the output of the SMT solver")); + +static cl::opt + 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 Parser(createMCAsmParser(SrcMgr, Ctx, Str, MAI)); + std::unique_ptr 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 GetOutputStream(StringRef Path, + sys::fs::OpenFlags Flags) { + std::error_code EC; + auto Out = std::make_unique(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> 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 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 MRI(TheTarget->createMCRegInfo(TripleName)); + assert(MRI && "Unable to create target register info!"); + + MCTargetOptions MCOptions = mc::InitMCTargetOptionsFromFlags(); + std::unique_ptr 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 MOFI( + TheTarget->createMCObjectFileInfo(Ctx, /*PIC=*/false)); + Ctx.setObjectFileInfo(MOFI.get()); + + std::unique_ptr MCII(TheTarget->createMCInstrInfo()); + assert(MCII && "Unable to create instruction info!"); + + std::unique_ptr 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 Out = GetOutputStream(OutputFilename, Flags); + if (!Out) + return 1; + + std::unique_ptr BOS; + raw_pwrite_stream *OS = &Out->os(); + MCStreamerWrapper Str(Ctx); + + // Set up the AsmStreamer. + std::unique_ptr CE; + + std::unique_ptr MAB( + TheTarget->createMCAsmBackend(*STI, *MRI, MCOptions)); + auto FOut = std::make_unique(*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; +}