if (!node->GetType()->IsBits()) {

return "?";

}

return query_engine.ToString(node);

std::cout << absl::StreamFormat("Entry function (%s) node count: %d nodes\n",

f->name(), f->node_count());

std::vector<Op> ops;

absl::flat_hash_map<Op, int64_t> op_count;

for (Node* node : f->nodes()) {

if (!op_count.contains(node->op())) {

ops.push_back(node->op());

}

op_count[node->op()] += 1;

}

std::sort(ops.begin(), ops.end(),

[&](Op a, Op b) { return op_count.at(a) > op_count.at(b); });

std::cout << "Breakdown by op of all nodes in the graph:" << '\n';

for (Op op : ops) {

std::cout << absl::StreamFormat(" %15s : %5d (%5.2f%%)\n", OpToString(op),

op_count.at(op),

100.0 * op_count.at(op) / f->node_count());

}

Package* package, const OptimizationPassOptions& pass_options) {

std::unique_ptr<OptimizationCompoundPass> pipeline =

CreateOptimizationPassPipeline();

absl::Time start = absl::Now();

PassResults pass_results;

OptimizationContext context;

XLS_RETURN_IF_ERROR(

pipeline->Run(package, pass_options, &pass_results, context).status());

absl::Duration total_time = absl::Now() - start;

std::cout << absl::StreamFormat("Optimization time: %dms\n",

DurationToMs(total_time));

std::cout << absl::StreamFormat("Dynamic pass count: %d\n",

pass_results.total_invocations());

// Print table(s) of pass metrics.

std::cout << SummarizePassPipelineMetrics(pass_results.ToProto(),

/*show_all_changed_passes=*/false);

return absl::OkStatus();

FunctionBase* f, const QueryEngine& query_engine,

const synthesis::SynthesizedDelayDiffByStage& delay_diff) {

const std::vector<CriticalPathEntry>& critical_path =

delay_diff.total_diff.critical_path;

int64_t total_delay =

critical_path.empty() ? 0 : critical_path.front().path_delay_ps;

std::cout << absl::StrFormat("Critical path delay: %dps\n", total_delay);

std::cout << absl::StrFormat("Critical path entry count: %d\n",

critical_path.size());

absl::flat_hash_map<Op, std::pair<int64_t, int64_t>> op_to_sum;

std::cout << "Critical path:" << '\n';

std::cout << SynthesizedDelayDiffToString(

delay_diff.total_diff, [&query_engine](Node* n) -> std::string {

if (absl::GetFlag(FLAGS_show_known_bits)) {

return absl::StrFormat(

" %s <= [%s]\n", KnownBitString(n, query_engine),

absl::StrJoin(

n->operands(), ", ", [&](std::string* out, Node* n) {

absl::StrAppend(out, KnownBitString(n, query_engine));

}));

}

return "";

});

for (const CriticalPathEntry& entry : critical_path) {

// Make a note of the sums.

auto& tally = op_to_sum[entry.node->op()];

tally.first += entry.node_delay_ps;

tally.second += 1;

}

std::cout << absl::StrFormat("Contribution by op (total %dps):\n",

total_delay);

std::vector<Op> ops(kAllOps.begin(), kAllOps.end());

std::sort(ops.begin(), ops.end(), [&](Op lhs, Op rhs) {

return op_to_sum[lhs].first > op_to_sum[rhs].first;

});

for (Op op : ops) {

if (op_to_sum[op].second == 0) {

continue;

}

std::cout << absl::StreamFormat(

" %20s: %4d (%5.2f%%, %4d nodes, %5.1f avg)\n", OpToString(op),

op_to_sum[op].first,

static_cast<double>(op_to_sum[op].first) / total_delay * 100.0,

op_to_sum[op].second,

static_cast<double>(op_to_sum[op].first) / op_to_sum[op].second);

}

std::cout << "\nOverall delay: "

<< synthesis::SynthesizedDelayDiffToStringHeaderWithPercent(

delay_diff.total_diff)

<< "\nTotal synthesized stage weight diff: "

<< absl::StrFormat("%.2f", delay_diff.total_stage_percent_diff_abs)

<< "\nMax synthesized stage weight diff: "

<< absl::StrFormat("%.2f", delay_diff.max_stage_percent_diff_abs)

<< "\n";

return absl::OkStatus();

const DelayEstimator& delay_estimator) {

int64_t total_delay = 0;

for (Node* node : f->nodes()) {

XLS_ASSIGN_OR_RETURN(int64_t op_delay,

delay_estimator.GetOperationDelayInPs(node));

total_delay += op_delay;

}

std::cout << absl::StrFormat("Total delay: %dps\n", total_delay);

return absl::OkStatus();

const AreaEstimator& area_estimator) {

int64_t total_area = 0;

for (Node* node : f->nodes()) {

XLS_ASSIGN_OR_RETURN(double op_area,

area_estimator.GetOperationAreaInSquareMicrons(node));

total_area += op_area;

}

std::cout << absl::StrFormat("Total area: %.4f um2\n", total_area);

return absl::OkStatus();

FunctionBase* f, const PipelineSchedule& schedule,

const DelayEstimator& delay_estimator) {

std::vector<int64_t> delay_per_stage(schedule.length() + 1);

// The delay from the beginning of the stage at which each node completes.

absl::flat_hash_map<Node*, int64_t> completion_time;

XLS_ASSIGN_OR_RETURN(std::vector<Node*> sorted_nodes, TopoSort(f));

for (Node* node : sorted_nodes) {

if (IsUntimed(node)) {

completion_time[node] = 0;

continue;

}

int64_t start_time = 0;

for (Node* operand : node->operands()) {

if (IsUntimed(operand)) {

continue;

}

if (schedule.cycle(operand) == schedule.cycle(node)) {

start_time = std::max(start_time, completion_time[operand]);

}

}

XLS_ASSIGN_OR_RETURN(int64_t node_delay,

delay_estimator.GetOperationDelayInPs(node));

completion_time[node] = start_time + node_delay;

delay_per_stage[schedule.cycle(node)] =

std::max(delay_per_stage[schedule.cycle(node)], completion_time[node]);

}

return delay_per_stage;

const PipelineSchedule& schedule,

const BddQueryEngine& bdd_query_engine,

const DelayEstimator& delay_estimator,

std::optional<int64_t> clock_period_ps) {

int64_t total_flops = 0;

int64_t total_duplicates = 0;

int64_t total_constants = 0;

std::vector<int64_t> flops_per_stage(schedule.length());

std::vector<int64_t> duplicates_per_stage(schedule.length());

std::vector<int64_t> constants_per_stage(schedule.length());

XLS_ASSIGN_OR_RETURN(absl::flat_hash_set<Node*> dead_after_synthesis,

GetDeadAfterSynthesisNodes(f));

for (int64_t i = 0; i < schedule.length(); ++i) {

absl::flat_hash_map<BddNodeIndex, std::pair<Node*, int64_t>> bdd_nodes;

for (Node* node : schedule.GetLiveOutOfCycle(i)) {

if (!dead_after_synthesis.contains(node) &&

(f->HasImplicitUse(node) ||

absl::c_any_of(node->users(), [&](Node* user) {

return schedule.cycle(user) > i &&

dead_after_synthesis.contains(user);

}))) {

flops_per_stage[i] += node->GetType()->GetFlatBitCount();

}

if (node->GetType()->IsBits()) {

for (int64_t bit_index = 0; bit_index < node->BitCountOrDie();

++bit_index) {

TreeBitLocation location(node, bit_index);

if (std::optional<bool> known_value =

bdd_query_engine.KnownValue(location);

known_value.has_value()) {

VLOG(1) << absl::StreamFormat("%s:%d in stage %d is known %s",

node->GetName(), bit_index, i,

*known_value ? "zero" : "one");

constants_per_stage[i]++;

total_constants++;

} else if (BddNodeIndex bdd_node =

*bdd_query_engine.GetBddNode(location);

bdd_nodes.contains(bdd_node)) {

VLOG(1) << absl::StreamFormat(

"%s:%d in stage %d duplicate of %s:%d", node->GetName(),

bit_index, i, bdd_nodes.at(bdd_node).first->GetName(),

bdd_nodes.at(bdd_node).second);

duplicates_per_stage[i]++;

total_duplicates++;

} else {

bdd_nodes[bdd_node] = {node, bit_index};

}

}

}

}

total_flops += flops_per_stage[i];

}

XLS_ASSIGN_OR_RETURN(std::vector<int64_t> delay_per_stage,

GetDelayPerStageInPs(f, schedule, delay_estimator));

// TODO(tedhong) 2023-03-06 - Add functionality to report I/O flop count.

std::cout << "Pipeline:\n";

for (int64_t i = 0; i < schedule.length(); ++i) {

std::string stage_str = absl::StrFormat(

" [Stage %2d] flops: %4d (%4d dups, %4d constant)\n", i,

flops_per_stage[i], duplicates_per_stage[i], constants_per_stage[i]);

// Horizontally offset the information about the logic in the stage from

// the information about stage registers to make it easier to scan the

// information vertically without register and logic info intermixing.

std::cout << std::string(stage_str.size(), ' ');

std::cout << absl::StreamFormat("nodes: %4d, delay: %4dps\n",

schedule.nodes_in_cycle(i).size(),

delay_per_stage[i]);

if (i + 1 != schedule.length()) {

std::cout << stage_str;

}

}

std::cout << absl::StreamFormat(

"Total pipeline flops: %d (%d dups, %4d constant)\n", total_flops,

total_duplicates, total_constants);

if (clock_period_ps.has_value()) {

int64_t min_slack = std::numeric_limits<int64_t>::max();

for (int64_t stage_delay : delay_per_stage) {

min_slack = std::min(min_slack, *clock_period_ps - stage_delay);

}

std::cout << absl::StreamFormat("Min stage slack: %d\n", min_slack);

}

return absl::OkStatus();

const DelayEstimator& delay_estimator,

std::optional<int64_t> clock_period_ps) {

if (package_schedule.GetSchedules().size() == 1) {

// With multiple schedules there may be multiple minimum clock periods.

// However, a consumer of the output of this utility expects a single value

// for this metric. The core underlying problem is that we should have a

// single minimum clock period across multiple FunctionBases (procs) rather

// than minimizing on a per-FunctionBase basis.

const PipelineSchedule& schedule =

package_schedule.GetSchedules().begin()->second;

if (schedule.min_clock_period_ps().has_value()) {

std::cout << absl::StreamFormat("Min clock period ps: %d\n",

*schedule.min_clock_period_ps());

}

}

for (auto& [function_base, schedule] : package_schedule.GetSchedules()) {

std::cout << "\n\nFunction: " << function_base->name() << "\n";

// NB query engines are associated with a specific function, so we need to

// create a new one for each function.

BddQueryEngine query_engine(BddQueryEngine::kDefaultPathLimit);

XLS_RETURN_IF_ERROR(query_engine.Populate(function_base).status());

XLS_RETURN_IF_ERROR(PrintScheduleInfo(function_base, schedule, query_engine,

delay_estimator, clock_period_ps));

}

return absl::OkStatus();

XLS_RET_CHECK(p != nullptr);

int64_t total_flops = 0;

for (StateElement* state_element : p->StateElements()) {

total_flops += state_element->type()->GetFlatBitCount();

}

return absl::StrFormat("Total state flops: %d\n", total_flops);

int64_t duration_ms) {

// To avoid including absl::Now() calls in the time measurement, first

// estimate how many calls it will take for `duration_ms` milliseconds to

// elapse. This is done my running until `duration_ms / 10` milliseconds have

// elapsed with absl::Now() in the loop.

int64_t call_count = 0;

absl::Time start_estimate = absl::Now();

while (DurationToMs(absl::Now() - start_estimate) < duration_ms / 10) {

f();

++call_count;

}

// Then run 10x the estimated call count to get close to `duration_ms` total

// run time.

absl::Time start_actual = absl::Now();

for (int64_t i = 0; i < call_count * 10; ++i) {

f();

}

int64_t elapsed_ms = DurationToMs(absl::Now() - start_actual);

return elapsed_ms == 0 ? 0.0f : (1000.0 * call_count) / elapsed_ms;

FunctionBase* function, int64_t input_count,

absl::Span<ParamNode* const> params, Rng& rng_engine) {

std::vector<std::vector<Value>> arg_set(input_count);

for (std::vector<Value>& args : arg_set) {

args.reserve(params.size());

for (Node* param : params) {

args.push_back(RandomValue(param->GetType(), rng_engine));

}

}

return arg_set;

const std::vector<std::vector<Value>>& arg_set,

absl::Span<Type* const> params, JitRuntime* runtime) {

std::vector<std::vector<std::vector<uint8_t>>> arg_buffers;

std::vector<std::vector<uint8_t*>> arg_pointers;

for (const std::vector<Value>& args : arg_set) {

std::vector<std::vector<uint8_t>> buffers;

std::vector<uint8_t*> pointers;

buffers.reserve(args.size());

pointers.reserve(args.size());

for (int64_t i = 0; i < args.size(); ++i) {

buffers.push_back(

std::vector<uint8_t>(runtime->ShouldAllocateForAlignment(

runtime->GetTypeByteSize(params[i]),

runtime->GetTypeAlignment(params[i])),

0));

pointers.push_back(runtime

->AsAligned(absl::MakeSpan(buffers.back()),

runtime->GetTypeAlignment(params[i]))

.data());

CHECK_NE(pointers.back(), nullptr);

}

arg_buffers.push_back(std::move(buffers));

arg_pointers.push_back(pointers);

XLS_RETURN_IF_ERROR(runtime->PackArgs(args, params, arg_pointers.back()));

}

return JitArguments{std::move(arg_buffers), std::move(arg_pointers)};

std::string_view description,

Rng& rng_engine) {

absl::Time start_jit_compile = absl::Now();

XLS_ASSIGN_OR_RETURN(std::unique_ptr<FunctionJit> jit,

FunctionJit::Create(function));

std::cout << absl::StreamFormat(

"JIT compile time (%s): %dms\n", description,

DurationToMs(absl::Now() - start_jit_compile));

const int64_t kInputCount = 100;

auto arg_set =

GetRandomParams(function, kInputCount, function->params(), rng_engine);

// To avoid being dominated by xls::Value conversion to native

// format, preconvert the arguments.

XLS_ASSIGN_OR_RETURN(

JitArguments jit_args,

ConvertToJitArguments(arg_set, function->GetType()->parameters(),

jit->runtime()));

auto [jit_arg_buffers, jit_arg_pointers] = std::move(jit_args);

// The JIT is much faster so run many times.

InterpreterEvents events;

std::vector<uint8_t> result_buffer(jit->runtime()->ShouldAllocateForAlignment(

jit->GetReturnTypeSize(), jit->GetReturnTypeAlignment()));

absl::Span<uint8_t> result_aligned = jit->runtime()->AsAligned(

absl::MakeSpan(result_buffer), jit->GetReturnTypeAlignment());

XLS_ASSIGN_OR_RETURN(

float jit_run_rate,

CountRate(

[&]() -> absl::Status {

for (int64_t i = 0; i < kJitRunMultiplier; ++i) {

for (const std::vector<uint8_t*>& pointers : jit_arg_pointers) {

CHECK_OK(jit->RunWithViews(pointers, result_aligned, &events));

}

}

return absl::OkStatus();

},

kRunDurationMs));

std::cout << absl::StreamFormat(

"JIT run time (%s): %d Kcalls/s\n", description,

static_cast<int64_t>(kInputCount * jit_run_rate));

XLS_ASSIGN_OR_RETURN(

float interpreter_run_rate,

CountRate(

[&]() -> absl::Status {

for (const std::vector<Value>& args : arg_set) {

CHECK_OK(InterpretFunction(function, args).status());

}

return absl::OkStatus();

},

kRunDurationMs));

std::cout << absl::StreamFormat(

"Interpreter run time (%s): %d calls/s\n", description,

static_cast<int64_t>(kInputCount * interpreter_run_rate));

return absl::OkStatus();

std::string_view description,

Rng& rng_engine) {

absl::Time start_jit_compile = absl::Now();

XLS_ASSIGN_OR_RETURN(std::unique_ptr<BlockJit> jit, BlockJit::Create(block));

std::cout << absl::StreamFormat(

"JIT compile time (%s): %dms\n", description,

DurationToMs(absl::Now() - start_jit_compile));

const int64_t kInputCount = 100;

std::vector<std::vector<Value>> arg_set =

GetRandomParams(block, kInputCount, block->GetInputPorts(), rng_engine);

std::vector<absl::flat_hash_map<std::string, Value>> port_set;

port_set.reserve(arg_set.size());

absl::c_transform(arg_set, std::back_inserter(port_set),

[&](const std::vector<Value>& ports) {

absl::flat_hash_map<std::string, Value> out;

out.reserve(ports.size());

for (int i = 0; i < ports.size(); ++i) {

out[block->GetInputPorts()[i]->name()] = ports[i];

}

return out;

});

// To avoid being dominated by xls::Value conversion to native

// format, preconvert the arguments.

std::vector<Type*> input_types;

input_types.reserve(block->GetInputPorts().size());

absl::c_transform(block->GetInputPorts(), std::back_inserter(input_types),

[](InputPort* v) { return v->GetType(); });

XLS_ASSIGN_OR_RETURN(

auto jit_args,

ConvertToJitArguments(arg_set, input_types, jit->runtime()));

auto [jit_arg_buffers, jit_arg_pointers] = std::move(jit_args);

// The JIT is much faster so run many times.

auto jit_continuation = jit->NewContinuation(

BlockEvaluator::OutputPortSampleTime::kAtLastPosEdgeClock);

XLS_ASSIGN_OR_RETURN(

float jit_run_rate,

CountRate(

[&]() -> absl::Status {

for (int64_t i = 0; i < kJitRunMultiplier; ++i) {

for (const std::vector<uint8_t*>& pointers : jit_arg_pointers) {

CHECK_OK(jit_continuation->SetInputPorts(pointers));

CHECK_OK(jit->RunOneCycle(*jit_continuation));

}

}

return absl::OkStatus();

},

kRunDurationMs));

std::cout << absl::StreamFormat(

"JIT run time (%s): %d Kcalls/s\n", description,

static_cast<int64_t>(kInputCount * jit_run_rate));

XLS_ASSIGN_OR_RETURN(std::unique_ptr<BlockContinuation> continuation,

kInterpreterBlockEvaluator.NewContinuation(block));

XLS_ASSIGN_OR_RETURN(

float interpreter_run_rate,

CountRate(

[&]() -> absl::Status {

for (const absl::flat_hash_map<std::string, Value>& ports :

port_set) {

CHECK_OK(continuation->RunOneCycle(ports));

}

return absl::OkStatus();

},

kRunDurationMs));

std::cout << absl::StreamFormat(

"Interpreter run time (%s): %d calls/s\n", description,

static_cast<int64_t>(kInputCount * interpreter_run_rate));

return absl::OkStatus();

Rng& rng_engine) {

absl::Time start_jit_compile = absl::Now();

// Technically the creation cost to get the data layout is amortized over all

// the procs in the elaboration.

XLS_ASSIGN_OR_RETURN(std::unique_ptr<OrcJit> layout_source, OrcJit::Create());

XLS_ASSIGN_OR_RETURN(auto data_layout, layout_source->CreateDataLayout());

XLS_ASSIGN_OR_RETURN(

std::unique_ptr<JitChannelQueueManager> queue_manager,

JitChannelQueueManager::CreateThreadSafe(

proc->package(), std::make_unique<JitRuntime>(data_layout)));

XLS_ASSIGN_OR_RETURN(

std::unique_ptr<ProcJit> jit,

ProcJit::Create(proc, &queue_manager->runtime(), queue_manager.get()));

std::cout << absl::StreamFormat(

"JIT compile time (%s): %dms\n", description,

DurationToMs(absl::Now() - start_jit_compile));

// TODO(meheff): 2022/5/16 Run the proc as well.

return absl::OkStatus();

std::string_view description) {

std::minstd_rand rng_engine;

if (function_base->IsFunction()) {

Function* function = function_base->AsFunctionOrDie();

return RunFunctionInterpreterAndJit(function, description, rng_engine);

}

if (function_base->IsBlock()) {

Block* block = function_base->AsBlockOrDie();

return RunBlockInterpreterAndJit(block, description, rng_engine);

}

XLS_RET_CHECK(function_base->IsProc());

Proc* proc = function_base->AsProcOrDie();

return RunProcInterpreterAndJit(proc, description, rng_engine);

FunctionBase* f, std::optional<int64_t> effective_clock_period_ps,

const DelayEstimator& delay_estimator, const AreaEstimator* area_estimator,

const QueryEngine& query_engine, PackageSchedule* package_schedule,

synthesis::Synthesizer* synthesizer) {

XLS_ASSIGN_OR_RETURN(

std::vector<CriticalPathEntry> critical_path,

AnalyzeCriticalPath(f, effective_clock_period_ps, delay_estimator));

synthesis::SynthesizedDelayDiffByStage delay_diff;

if (synthesizer) {

if (package_schedule) {

XLS_ASSIGN_OR_RETURN(

delay_diff, CreateDelayDiffByStage(

f, package_schedule->GetSchedules().begin()->second,

delay_estimator, synthesizer));

delay_diff.total_diff.critical_path = std::move(critical_path);

} else {

XLS_ASSIGN_OR_RETURN(

delay_diff.total_diff,

SynthesizeAndGetDelayDiff(f, critical_path, synthesizer));

}

} else {

delay_diff.total_diff.critical_path = std::move(critical_path);

}

XLS_RETURN_IF_ERROR(PrintCriticalPath(f, query_engine, delay_diff));

XLS_RETURN_IF_ERROR(PrintTotalDelay(f, delay_estimator));

if (area_estimator != nullptr) {

XLS_RETURN_IF_ERROR(PrintTotalArea(f, *area_estimator));

}

return absl::OkStatus();

f->IsProc() ? ProcInfo(f->AsProcOrDie()) : "");

XLS_ASSIGN_OR_RETURN(

verilog::CodegenResult codegen_result,

Codegen(package.get(), scheduling_options_flags_proto,

codegen_flags_proto, delay_model_flag_passed,

codegen_flags_proto.generator() == GENERATOR_KIND_PIPELINE

? &package_schedule

: nullptr));

std::cout << absl::StreamFormat(

"Codegen time: %dms\n",

PassPipelineDuration(codegen_result.pass_pipeline_metrics) /

absl::Milliseconds(1));

std::cout << absl::StreamFormat(

"Lines of Verilog: %d\n",

std::vector<std::string>(

absl::StrSplit(codegen_result.verilog_text, '\n'))

.size());

// Print out state information for procs.

std::cout << proc_info;

if (absl::GetFlag(FLAGS_run_evaluators)) {

XLS_RETURN_IF_ERROR(

RunInterpreterAndJit(package->blocks()[0].get(), "block"));

}

}

return absl::OkStatus();

}

} // namespace

} // namespace xls

int main(int argc, char** argv) {

std::vector<std::string_view> positional_arguments =

xls::InitXls(kUsage, argc, argv);

if (positional_arguments.empty() || positional_arguments[0].empty()) {

LOG(QFATAL) << "Expected path argument with IR: " << argv[0]

<< " <ir_path>";