如何解决指针别名问题？

Question

不小心使用模板可能会导致膨胀。避免这种膨胀的一种方法是使用一个薄的类型安全模板来包装非类型安全的非模板代码。为此，包装器需要为非模板代码提供某种方式来访问它一无所知的内容。

例如，在数据结构中，包装器定义节点结构。不安全代码需要读取和写入节点，但必须通过包装器指定的某种接口间接执行此操作。

实现此接口的一种方法是用诸如函数指针和包装器确定的常量等详细信息填充结构（由不安全代码定义）。一种相关的常量是特定字段的偏移量（在某些结构内）。不安全代码可以使用该偏移量（以及一些指针算术）直接访问该字段。

不过，这会带来问题 - 随着优化器变得更加激进，这可能会导致指针别名问题。如果节点可以逃离库，则尤其如此。例如，可以从二叉树中提取节点并重新链接以形成链表。令人烦恼的是，另一个例子发生在单元测试时。

我目前有一个按照这些思路编写的容器库，目前它不会导致这些问题 - 但很快就会。它避免这些问题的原因是因为所有单元测试都应用于容器（而不是底层代码），并且因为节点永远不会逃逸容器。也就是说，节点始终以相同的指针算术方式访问，因此永远不会出现指针别名优化问题。

不幸的是，我很快将需要允许从容器中提取节点，并且我可能还需要对底层不安全代码进行单元测试。

我没有处理这个特定的库，而是从一个旧的二叉树库中提取了一个更简单的摘录，该库也遇到了同样的问题。在 VC++9 中它就可以工作。使用 MinGW GCC 4.4.0，调试构建可以工作，但发布构建失败。该问题是内联和优化器未能发现指针别名的混合问题。

需要明确的是 - 我不想在这里“WTF - GOTO！！！”或其他什么。问题是解决优化/指针问题。不过，如果您能找到一种方法来编写结构正确且不使用隐藏/伪装的 goto 来实现的 Tree_To_List ，我很感兴趣。

此外，还缺少一层基于模板的抽象（模板 c_Bin_Tree_Tool 并没有完成全部工作 - c_Tool 完成了包装，而是以每次使用的方式而不是以可重用的形式。这只是提取相关代码。

该代码的作用是通过逐一插入节点来创建不平衡二叉树，然后通过将树转换为列表（以某种方式已经是）来平衡该树，然后。 树都会转储到 stdio

之前和之后，

inline void* Ptr_Add  (void* p1, std::ptrdiff_t p2)  {  return (void*) (((std::ptrdiff_t) p1) + p2);  }

struct c_Bin_Tree_Closure
{
  typedef int (*c_Node_Comp) (void* p_Node1, void* p_Node2);

  c_Node_Comp    m_Node_Comp;
  std::ptrdiff_t m_Left, m_Right;
};

class c_BT_Policy_Closure
{
  private:
    const c_Bin_Tree_Closure* m_Closure;

  protected:
    void** Left_Of  (void* p)  {  return ((void**) Ptr_Add (p, m_Closure->m_Left ));  }
    void** Right_Of (void* p)  {  return ((void**) Ptr_Add (p, m_Closure->m_Right));  }

    int Compare_Node (void* p_Node1, void* p_Node2) const
    {
      return m_Closure->m_Node_Comp (p_Node1, p_Node2);
    }

  public:
    c_BT_Policy_Closure ()
    {
      m_Closure = 0;
    }

    void Set_Closure (const c_Bin_Tree_Closure& p_Closure)
    {
      m_Closure = &p_Closure;
    }
};

template<class tc_Policy>
class c_Bin_Tree_Tool : public tc_Policy
{
  public:
    c_Bin_Tree_Tool ()
    {
    }

    void *List_To_Tree (size_t p_Size, void* &p_List);
    void  Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size);
    void  Balance      (void* &p);
    void  Insert       (void* &p_Tree, void* p_Node);
};

template<class tc_Policy>
void* c_Bin_Tree_Tool<tc_Policy>::List_To_Tree (size_t p_Size, void* &p_List)
{
  if (p_Size == 0)  return 0;

  size_t l_Size = p_Size / 2;
  void*  l_Ptr  = List_To_Tree (l_Size, p_List);

  void* l_This = p_List;
  p_List = *tc_Policy::Right_Of (l_This);

  *tc_Policy::Left_Of (l_This) = l_Ptr;

  l_Size = p_Size - (l_Size + 1);
  *tc_Policy::Right_Of (l_This) = List_To_Tree (l_Size, p_List);

  return l_This;
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size)
{
  //  Use left links as prev links and right links as next links

  void*  l_Start    = 0;         //  first-item-in-list pointer
  void*  l_Prev     = 0;         //  previous node in list
  void** l_Prev_Ptr = &l_Start;  //  points to the next (ie right) pointer for the next node.
  void*  l_Pos      = p_Root;
  void*  l_Next;
  void*  l_Parent   = 0;
  size_t l_Count    = 0;

  p_Last = 0;

  TOP_OF_LOOP:
    l_Next = *tc_Policy::Left_Of (l_Pos);

    if (l_Next != 0)
    {
      *tc_Policy::Left_Of (l_Pos) = l_Parent;  //  So we can find our way back up the tree
      l_Parent = l_Pos;
      l_Pos    = l_Next;
      goto TOP_OF_LOOP;
    }

  AFTER_STEP_PARENT:
    l_Next = *tc_Policy::Right_Of (l_Pos);

    *tc_Policy::Left_Of (l_Pos) = l_Prev;

    p_Last      = l_Pos;
    l_Prev      = l_Pos;
    *l_Prev_Ptr = l_Pos;
    l_Prev_Ptr  = tc_Policy::Right_Of (l_Pos);
    l_Count++;

    if (l_Next != 0)
    {
      l_Pos = l_Next;
      goto TOP_OF_LOOP;
    }

    if (l_Parent != 0)
    {
      l_Pos    = l_Parent;
      l_Parent = *tc_Policy::Left_Of (l_Pos);
      goto AFTER_STEP_PARENT;
    }

  *l_Prev_Ptr = 0;
  p_First     = l_Start;
  p_Size      = l_Count;
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Balance (void* &p)
{
  void   *l_First, *l_Last;
  size_t l_Count;

  Tree_To_List (p, l_First, l_Last, l_Count);
  p = List_To_Tree (l_Count, l_First);
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Insert (void* &p_Tree, void* p_Node)
{
  void** l_Tree = &p_Tree;

  while (*l_Tree != 0)
  {
    int l_Compare = tc_Policy::Compare_Node (*l_Tree, p_Node);
    l_Tree = ((l_Compare < 0) ? tc_Policy::Right_Of (*l_Tree) : tc_Policy::Left_Of (*l_Tree));
  }

  *l_Tree = p_Node;
  *tc_Policy::Right_Of (p_Node) = 0;
  *tc_Policy::Left_Of  (p_Node) = 0;
};

。

#include <iostream>

#include "bintree.h"

struct c_Node
{
  c_Node *m_Left, *m_Right;
  int    m_Data;
};

c_Node g_Node0001 = { 0, 0,  1 };  c_Node g_Node0002 = { 0, 0,  2 };
c_Node g_Node0003 = { 0, 0,  3 };  c_Node g_Node0004 = { 0, 0,  4 };
c_Node g_Node0005 = { 0, 0,  5 };  c_Node g_Node0006 = { 0, 0,  6 };
c_Node g_Node0007 = { 0, 0,  7 };  c_Node g_Node0008 = { 0, 0,  8 };
c_Node g_Node0009 = { 0, 0,  9 };  c_Node g_Node0010 = { 0, 0, 10 };

int Node_Compare (void* p1, void* p2)
{
  return (((c_Node*) p1)->m_Data - ((c_Node*) p2)->m_Data);
}

c_Bin_Tree_Closure  g_Closure =
{
  (c_Bin_Tree_Closure::c_Node_Comp) Node_Compare,
  offsetof (c_Node, m_Left ),  offsetof (c_Node, m_Right)
};

class c_Tool : public c_Bin_Tree_Tool<c_BT_Policy_Closure>
{
  protected:
    typedef c_Bin_Tree_Tool<c_BT_Policy_Closure> c_Base;
  public:
    c_Tool ()  {  Set_Closure (g_Closure);  }
    void Insert  (c_Node* &p_Tree, c_Node* p_Node)  {  c_Base::Insert ((void*&) p_Tree, p_Node);  }
    void Balance (c_Node* &p)  {  c_Base::Balance ((void*&) p);  }
};

void BT_Dump (size_t p_Depth, c_Node* p_Node)
{
  if (p_Node != 0)
  {
    BT_Dump (p_Depth + 1, p_Node->m_Left);
    for (size_t i = 0; i < p_Depth; i++)  std::cout << " .";
    std::cout << " " << p_Node->m_Data << std::endl;
    BT_Dump (p_Depth + 1, p_Node->m_Right);
  }
}

int main (int argc, char* argv[])
{
  c_Tool  l_Tool;
  c_Node *l_Root = 0;

  l_Tool.Insert (l_Root, &g_Node0001);
  l_Tool.Insert (l_Root, &g_Node0002);
  l_Tool.Insert (l_Root, &g_Node0003);
  l_Tool.Insert (l_Root, &g_Node0004);
  l_Tool.Insert (l_Root, &g_Node0005);
  l_Tool.Insert (l_Root, &g_Node0006);
  l_Tool.Insert (l_Root, &g_Node0007);
  l_Tool.Insert (l_Root, &g_Node0008);
  l_Tool.Insert (l_Root, &g_Node0009);
  l_Tool.Insert (l_Root, &g_Node0010);

  BT_Dump (0, l_Root);  std::cout << "----------" << std::endl;

  l_Tool.Balance (l_Root);
  BT_Dump (0, l_Root);

  return 0;
}

将列表转换回树。在平衡 是...

 1
 . 2
 . . 3
 . . . 4
 . . . . 5
 . . . . . 6
 . . . . . . 7
 . . . . . . . 8
 . . . . . . . . 9
 . . . . . . . . . 10
----------
 . . . 1
 . . 2
 . 3
 . . . 4
 . . 5
 6
 . . . 7
 . . 8
 . 9
 . . 10

实际发生了什么（MinGW GCC 4.4.0，优化版本构建）...

 1
 . 2
 . . 3
 . . . 4
 . . . . 5
 . . . . . 6
 . . . . . . 7
 . . . . . . . 8
 . . . . . . . . 9
 . . . . . . . . . 10
----------
 1

据我所知，Balance 操作运行正确，但 BT_Dump 函数无法看到 的所有更改m_Left 和 m_Right 字段

编辑这是错误的 - 否则为什么我将节点 1 视为新根，我猜这就是当您过度依赖时会发生的情况。记得几个月前进行的一项调查。

编辑 实际上，节点 1 作为根是一个问题，但由于它是旧根 - 好吧，最好忽略这个“问题是什么”的东西并找出你自己的理论;-)

代码中存在许多未定义标准的问题。我认为最大的问题是节点结构中的链接是 c_Node*，但由于不安全代码对 c_Node 一无所知，因此它以 void* 的形式访问它们（通过指针算术）。

一种修复方法是让不安全代码通过 getter 和 setter 函数指针进行所有读取和写入，避免所有指针算术并确保对 c_Node 实例的所有访问都是通过 c_Node* 指针完成的。更好的是 - 接口成为一个具有 getter/setter 方法等的类。在完整的二叉树库中，我有替代策略类来执行此操作，尽管说实话，当问题出现时我真正的解决方案是将所有代码放入一个“垃圾”文件夹，因为我很少使用它，并且无论如何应该使用增强侵入式列表。

然而，这仍然留下了另一个更复杂和大量使用的容器库，它不会消失。我想我将不得不进行非常痛苦的重构来摆脱 offsetof 和指针算术的东西，但是......

C++ 规则到底是什么 - 何时允许编译器无法识别可能的指针别名？上面的二叉树代码是否可以重写，以便它仍然使用指针算术，仍然允许在库内部和外部访问/修改节点，并且不受此优化问题的影响？

Answer 1

你关掉警告了吗？您应该得到一些“取消引用类型双关指针违反严格别名”，因为这正是您在 (void**) Ptr_Add(... 处所做的事情。

编译器可以自由地假设指向不同类型的指针不会别名（有一些execpitions），并且会生成将指针的目标缓存在寄存器中的优化代码，为了避免这种情况，您必须使用联合来在不同的指针类型之间进行转换。 onlinedocs/gcc/Optimize-Options.html#Optimize-Options" rel="nofollow noreferrer">http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options：

特别是，假定一种类型的对象永远不会与不同类型的对象驻留在同一地址，除非类型几乎相同。例如，unsigned int 可以为 int 起别名，但不能为 void* 或 double 起别名。字符类型可以是任何其他类型的别名。

特别注意这样的代码：

 union a_union {
        整数我；
        双 d；
      };

     int f() {
        联合a_联合t；
        td = 3.0；
        返回ti；
      }

从不同的工会成员那里读取内容而不是最近写信给的成员的做法（称为“类型双关”）很常见。即使使用 -fstrict-aliasing，也允许类型双关，前提是通过联合类型访问内存。因此，上面的代码将按预期工作。请参阅结构联合枚举和位字段实现。但是，此代码可能不会：

<前><代码> int f() {
联合a_联合t；
int* ip；
td = 3.0；
ip = &ti;
返回*ip；
}

类似地，通过获取地址、转换结果指针和取消引用结果进行访问具有未定义的行为，即使转换使用联合类型，例如：

<前><代码> int f() {
双 d = 3.0；
return ((union a_union *) &d)->i;
}

-fstrict-aliasing 选项在级别 -O2 启用，-O3，-Os。

在你的情况下，你可以使用类似的东西

union {
    void** ret_ptr;
    ptrdiff_t in_ptr;
}

，但 ptr_add 中的代码看起来很糟糕；-)

或者只是使用“fno-strict-aliasing”禁用这个特定的优化。不过最好修复你的代码;-)

Answer 2

不小心使用模板可能会导致膨胀。但你完全没有抓住重点。

• 模板使用时会导致膨胀
  粗心地，不仔细地。
• 运行时错误的数量
  模板所避免的内容是巨大的。
• 模板化代码的速度远
  大于非模板代码。
• 除非在嵌入式系统上运行，否则可执行文件的大小绝对微不足道。
• STL 提供了一个映射容器（它是一个二叉搜索树）供您使用。

你根本就没有好好思考这个问题。模板提供的优势远远超过可执行文件的几 kb 大小。

还值得注意的是，该代码在 Visual Studio 2010 上按预期工作。