Tagged Pointer
c++ edaTagged Pointer是一个经典的时间优化技术,通过巧妙利用内存对齐特性，在零额外内存开销下避免堆分配。
基础原理
为了防止未对齐访问,编译器会插入填充0以根据类型的对齐要求对齐值，分配内存对齐到8字节(在64位系统上是16字节)，指针地址以000结尾 。可以利用这些未使用的低位来指示这不是真实指针,然后将对象数据直接存储在这个"非指针"的剩余部分中,而不是单独的内存分配。
1Top Bottom
2▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮▮000
3 ^^^
4 可用于存储标记
简单实现:存储小整数
以一个能将小整数直接编码进指针的系统为例:
1#include <stdint.h>
2#include <stdbool.h>
3
4// 标记位定义
5#define TAG_MASK 0x7 // 低3位掩码: 0b111
6#define TAG_INT 0x1 // 整数标记: 0b001
7#define TAG_PTR 0x0 // 指针标记: 0b000
8
9// 类型判断
10static inline bool is_tagged_int(uintptr_t value) {
11 return (value & TAG_MASK) == TAG_INT;
12}
13
14static inline bool is_pointer(uintptr_t value) {
15 return (value & TAG_MASK) == TAG_PTR;
16}
17
18// 整数编码:左移3位后设置标记
19static inline uintptr_t encode_int(int64_t num) {
20 return (num << 3) | TAG_INT;
21}
22
23// 整数解码:去除标记后右移
24static inline int64_t decode_int(uintptr_t tagged) {
25 return (int64_t)tagged >> 3; // 算术右移保留符号
26}
27
28// 指针编码:确保低3位为0
29static inline uintptr_t encode_ptr(void* ptr) {
30 uintptr_t addr = (uintptr_t)ptr;
31 // 断言指针已对齐
32 assert((addr & TAG_MASK) == 0);
33 return addr | TAG_PTR;
34}
35
36// 指针解码:清除标记位
37static inline void* decode_ptr(uintptr_t tagged) {
38 return (void*)(tagged & ~TAG_MASK);
39}
使用示例
1// 示例:实现简单的动态类型值
2typedef uintptr_t Value;
3
4// 创建整数值
5Value create_number(int64_t num) {
6 // 小整数:直接编码
7 if (num >= -(1LL << 60) && num < (1LL << 60)) {
8 return encode_int(num);
9 }
10 // 大整数:堆分配
11 int64_t* heap_num = malloc(sizeof(int64_t));
12 *heap_num = num;
13 return encode_ptr(heap_num);
14}
15
16// 整数加法
17Value add_numbers(Value a, Value b) {
18 int64_t a_val, b_val;
19
20 // 提取值a
21 if (is_tagged_int(a)) {
22 a_val = decode_int(a);
23 } else {
24 int64_t* ptr = decode_ptr(a);
25 a_val = *ptr;
26 }
27
28 // 提取值b
29 if (is_tagged_int(b)) {
30 b_val = decode_int(b);
31 } else {
32 int64_t* ptr = decode_ptr(b);
33 b_val = *ptr;
34 }
35
36 return create_number(a_val + b_val);
37}
38
39// 使用示例
40int main() {
41 Value num1 = create_number(42); // Tagged pointer
42 Value num2 = create_number(58); // Tagged pointer
43 Value sum = add_numbers(num1, num2); // 结果:100
44
45 printf("Result: %lld\n", decode_int(sum)); // 输出: 100
46 return 0;
47}
经典应用场景:And-Inverter Graph (AIG)
AIG是由二输入AND门和反相器组成的多级逻辑网络,用于表示二进制顺序逻辑电路。在数字电路设计中,任何布尔逻辑都可以用AND和NOT门表示。如果不使用Tagged Pointer,AIG节点结构可能是这样:
1// 传统实现:每条边需要单独存储反相信息
2typedef struct AigEdge_ {
3 AigNode *node; // 8字节
4 unsigned int complement : 1; // 反相标记
5} AigEdge;
6
7typedef struct AigNode_ {
8 unsigned int id;
9 AigEdge *fanin0; // 指向输入边0 (16字节对象)
10 AigEdge *fanin1; // 指向输入边1 (16字节对象)
11} AigNode;
每个AigEdge占用16字节(8字节指针 + 对齐填充)
每个AND门需要2个fanin,额外32字节仅用于存储边信息
ABC项目是加州大学伯克利分校开发的开源逻辑综合与验证工具，在其核心数据结构AIG的实现中，节点对象Aig_Obj_t使用tagged pointer优化，利用最低1位存储complement(反相)标记。在大规模电路网表中，这种优化的收益是显著的。
1struct Aig_Obj_t_ {
2 // ===== Tagged Fanin指针 =====
3 Aig_Obj_t *pFanin0; // 输入端0
4 Aig_Obj_t *pFanin1; // 输入端1
5
6 unsigned int Type : 3;
7 unsigned int fPhase : 1;
8 unsigned int fMarkA : 1;
9 unsigned int fMarkB : 1;
10 unsigned int nRefs : 26;
11
12 unsigned Level : 24;
13 unsigned nCuts : 8;
14
15 int TravId;
16 int Id;
17
18 union {
19 void * pData;
20 int iData;
21 float dData;
22 };
23};
核心Tagged Pointer操作:
1// 检查边是否为反相 (检查最低位)
2#define Aig_IsComplement(p) \
3 (((int)((ABC_PTRUINT_T)(p) & 01)))
4
5// 获取真实节点指针 (清除最低位)
6#define Aig_Regular(p) \
7 ((Aig_Obj_t *)((ABC_PTRUINT_T)(p) & ~01))
8
9// 获取非反相版本
10#define Aig_Not(p) \
11 ((Aig_Obj_t *)((ABC_PTRUINT_T)(p) ^ 01))
12
13// 带条件的反相
14#define Aig_NotCond(p,c) \
15 ((Aig_Obj_t *)((ABC_PTRUINT_T)(p) ^ (c)))
16
17// ===== 读取fanin操作 =====
18
19// 获取fanin0的真实节点指针
20static inline Aig_Obj_t* Aig_ObjFanin0(Aig_Obj_t* pObj) {
21 return Aig_Regular(pObj->pFanin0);
22}
23
24// 获取fanin1的真实节点指针
25static inline Aig_Obj_t* Aig_ObjFanin1(Aig_Obj_t* pObj) {
26 return Aig_Regular(pObj->pFanin1);
27}
28
29// 检查fanin0是否反相
30static inline int Aig_ObjFaninC0(Aig_Obj_t* pObj) {
31 return Aig_IsComplement(pObj->pFanin0);
32}
33
34// 检查fanin1是否反相
35static inline int Aig_ObjFaninC1(Aig_Obj_t* pObj) {
36 return Aig_IsComplement(pObj->pFanin1);
37}
38
39// ===== 构造操作 =====
40
41// 创建AND门 (根据条件设置反相标记)
42Aig_Obj_t* Aig_And(Aig_Man_t* p,
43 Aig_Obj_t* p0, // fanin0 (可能已tagged)
44 Aig_Obj_t* p1) { // fanin1 (可能已tagged)
45 Aig_Obj_t* pNode = Aig_TableLookup(p, p0, p1);
46 if (pNode) return pNode;
47
48 // 创建新节点
49 pNode = Aig_ManCreateNode(p);
50 pNode->pFanin0 = p0; // 直接存储tagged pointer
51 pNode->pFanin1 = p1;
52 pNode->Type = AIG_OBJ_AND;
53
54 return pNode;
55}
56
57// 创建反相边: NOT(p) = AND(p, 1) 的特殊表示
58Aig_Obj_t* Aig_Not_Func(Aig_Obj_t* p) {
59 return Aig_Not(p); // 翻转最低位
60}
实际使用示例
- 构造简单逻辑电路
1// 构造电路: out = NOT(AND(a, NOT(b))) 即 a NAND b
2void build_nand_circuit(Aig_Man_t* pMan) {
3 // 创建输入端口
4 Aig_Obj_t* pA = Aig_ObjCreateCi(pMan); // 输入a
5 Aig_Obj_t* pB = Aig_ObjCreateCi(pMan); // 输入b
6
7 // 创建 NOT(b) - 只是翻转指针的最低位!
8 Aig_Obj_t* pNotB = Aig_Not(pB);
9
10 // 创建 AND(a, NOT(b))
11 Aig_Obj_t* pAnd = Aig_And(pMan, pA, pNotB);
12
13 // 创建 NOT(AND(...))
14 Aig_Obj_t* pNand = Aig_Not(pAnd);
15
16 // 创建输出端口
17 Aig_ObjCreateCo(pMan, pNand);
18}
- 遍历电路拓扑
1// 递归计算节点逻辑值
2int Aig_ObjEvaluate(Aig_Obj_t* pObj, int* pInputVals) {
3 // 常量节点
4 if (Aig_ObjIsConst1(pObj)) {
5 return 1;
6 }
7
8 // 输入节点
9 if (Aig_ObjIsCi(pObj)) {
10 return pInputVals[Aig_ObjCioId(pObj)];
11 }
12
13 // AND节点:需要处理fanin的complement标记
14 assert(Aig_ObjIsAnd(pObj));
15
16 // 1. 获取真实的fanin节点指针
17 Aig_Obj_t* pFanin0 = Aig_ObjFanin0(pObj);
18 Aig_Obj_t* pFanin1 = Aig_ObjFanin1(pObj);
19
20 // 2. 递归计算fanin的值
21 int val0 = Aig_ObjEvaluate(pFanin0, pInputVals);
22 int val1 = Aig_ObjEvaluate(pFanin1, pInputVals);
23
24 // 3. 根据complement标记进行反相
25 if (Aig_ObjFaninC0(pObj)) val0 = !val0;
26 if (Aig_ObjFaninC1(pObj)) val1 = !val1;
27
28 // 4. 返回AND结果
29 return val0 & val1;
30}