- 关键改动
熵最小化：用 Z3 的 Optimize 对象，把 Σ w(b)·h(b) 设成 minimize 目标。
Memory DAG：用 LLVM 自带的 MemorySSA 取真·别名信息，只给实际可能 alias 的 Load/Store 插边，避免过度串行。
diff --git a/llvm/lib/CodeGen/EntropyScheduler.cpp b/llvm/lib/CodeGen/EntropyScheduler.cpp
index 9a8b1c4..c3fe2e2 100644
--- a/llvm/lib/CodeGen/EntropyScheduler.cpp
+++ b/llvm/lib/CodeGen/EntropyScheduler.cpp
@@ -2,6 +2,8 @@
include "llvm/Analysis/MemorySSA.h"
include "llvm/CodeGen/MachineScheduler.h"
include "llvm/Support/Debug.h"
+#include "z3++.h"
+
using namespace llvm;
using namespace z3;
@@ -64,21 +66,27 @@ static void buildDependencies(const MachineBasicBlock &MBB,
SmallVectorImpl> &Edges,
const MachineLoopInfo &MLI,
const MemorySSA &MSSA) {
- DenseMap Idx;
- unsigned Pos = 0;
- for (const MachineInstr &MI : MBB)
- Idx[&MI] = Pos++;
+
// 数据依赖
for (const MachineInstr &MI : MBB) {
for (const MachineOperand &MO : MI.operands()) {
if (MO.isReg() && MO.isUse()) {if (const MachineInstr *Def = MO.getReg().isVirtual() ? MRI.getVRegDef(MO.getReg()) : nullptr)
- Edges.emplace_back(getInstrIndex(Def), getInstrIndex(&MI));
- Edges.emplace_back(Idx.lookup(Def), Idx.lookup(&MI));
}
}
}
// Memory DAG：只给 alias 的 pair 插边
- for (const MachineInstr &A : MBB) {
- for (const MachineInstr &B : MBB) {
- if (&A != &B && MSSA.isAlias(&A, &B))
- Edges.emplace_back(getInstrIndex(&A), getInstrIndex(&B));
- for (auto It1 = MBB.begin(), E = MBB.end(); It1 != E; ++It1) {
- for (auto It2 = std::next(It1); It2 != E; ++It2) {
- if (MSSA.isAlias(&It1, &It2))
- Edges.emplace_back(Idx.lookup(&It1), Idx.lookup(&It2));
}
}
}
@@ -88,13 +96,14 @@ bool EntropyScheduler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
SmallVector> Edges;
buildDependencies(MBB, Edges, MLI, MSSA);
- context ctx;
- solver s(ctx);
- context c;
- optimize opt(c);
- solver s(c);
unsigned N = Instrs.size();
- std::vector pos(N);
- std::vector pos(N);
for (unsigned i = 0; i < N; ++i)
- pos[i] = ctx.int_const(("p" + Twine(i)).str().c_str());
pos[i] = c.int_const(("p" + Twine(i)).str().c_str());
// 唯一 & 范围
for (unsigned i = 0; i < N; ++i) {
@@ -105,12 +114,29 @@ bool EntropyScheduler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
for (auto [u, v] : Edges)
s.add(pos[u] < pos[v]);
- if (s.check() == sat) {
- model m = s.get_model();
- SmallVector Order(N);
- for (unsigned i = 0; i < N; ++i)
- Order[m.get_const_interp(pos[i]).get_numeral_int()] = i;
- applySchedule(MBB, Order);
- // 熵目标：minimize Σ -p log p
- expr total = c.int_val(0);
- for (unsigned i = 0; i < N; ++i)
- total = total + pos[i]; // dummy, 占位
+ - // 简化为：把相同 opcode 尽量连续 => 最小化熵
- std::map> buckets;
- for (unsigned i = 0; i < N; ++i)
- buckets[Instrs[i]->getOpcode()].push_back(pos[i]);
- expr entropy = c.int_val(0);
- for (auto &[opc, vars] : buckets) {
- for (size_t k = 1; k < vars.size(); ++k)
- entropy = entropy + (vars[k] - vars[k-1] - 1);
} - opt.add(s.assertions());
- opt.minimize(entropy);
+ - if (opt.check() == sat) {
- model m = opt.get_model();
- SmallVector NewIdx(N);
- for (unsigned i = 0; i < N; ++i)
- NewIdx[m.eval(pos[i]).get_numeral_int()] = i;
- applySchedule(MBB, NewIdx);
- }
return false;
}
- 一键验证
bash打补丁 & 重编
curl -L https://gist.githubusercontent.com/yourname/entropy_dag_min.patch | git apply
ninja -C build clang
测
build/bin/clang -O3 -mllvm -enable-entropy-sched -mllvm -debug-only=entropy-sched \
n-body.c -o n-body-ent-dag
perf stat -e energy-pkg ./n-body-ent-dag 50000000
预期结果
崩溃 = 0（Memory DAG 正确）
能量差异有望拉到 2–3 %（DAG 让 load/store 并行度更高，熵目标让同 opcode 成簇，解码缓存命中率↑）。
如果还是 <1%，那就说明“熵-密度”这招在 OoO 核上确实鸡肋，可以安心弃坑了。
————————————————版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/Yyf1234561234633/article/details/150268163
