借用检查¶

1-DefUse¶

1.1-定义¶

类 DefUse 对单个的 Stmt 进行分析，内部定义了 Defs 和 Uses 两个数组，分别存储当前定义和使用的变量。

class DefUse : public clang::StmtVisitor<DefUse> {
  enum { None, Def, Use } Action;
  llvm::SmallVector<VarDecl *> defs;
  llvm::SmallVector<VarDecl *> uses;
public:
  DefUse(Stmt *S) {
    Action = None;
    Visit(S);
  }

2-Visit函数¶

Visit 函数的调用针对以下特定的几个语句进行解析：

BinaryOperator
BinAssign
CallExpr
DeclRefExpr
DeclStmt
MemberExpr
ReturnStmt
UnaryDeref
UnaryOperator

例如： BinaryOperator¶

通过 opcode 判断检查：

1>算数运算符
- BO_Mul (* 乘法)
- BO_Div (/ 除法)
- BO_Rem (% 取模)
- BO_Add (+ 加法)
- BO_Sub (- 减法)
- BO_Shl (<< 左移)
- BO_Shr (>> 右移)
2>位运算符
- BO_And (& 按位与)
- BO_Xor (^ 按位异或)
- BO_Or (| 按位或)
- BO_LAnd (&& 逻辑与)
- BO_LOr (|| 逻辑或)
3>关系运算符
- BO_LT (< 小于)
- BO_GT (> 大于)
- BO_LE (<= 小于等于)
- BO_GE (>= 大于等于)
- BO_EQ (== 等于)
- BO_NE (!= 不等于)
4>复合赋值运算符
- BO_MulAssign 乘法赋值（a *= b）
- BO_DivAssign 除法赋值（a /= b）
- BO_RemAssign 取模赋值（a %= b）
- BO_AddAssign 加法赋值（a += b）
- BO_SubAssign 减法赋值（a -= b）
- BO_ShlAssign 左移赋值（a <<= b）
- BO_ShrAssign 右移赋值（a >>= b）
- BO_AndAssign 按位与赋值（a &= b）
- BO_XorAssign 按位异或赋值（a ^= b）
- BO_OrAssign 按位或赋值（a |= b）

void DefUse::VisitBinaryOperator(BinaryOperator *BO) {
  auto Opcode = BO->getOpcode();
  if ((Opcode >= BO_Mul && Opcode <= BO_Shr) ||
      (Opcode >= BO_And && Opcode <= BO_LOr) ||
      (Opcode >= BO_LT && Opcode <= BO_NE)) {
    Action = Use;
    Visit(BO->getLHS());
    Visit(BO->getRHS());
  } else if (Opcode >= BO_MulAssign && Opcode <= BO_OrAssign) {
    Action = Def;
    Visit(BO->getLHS());
    Action = Use;
    Visit(BO->getLHS());
    Visit(BO->getRHS());
  }
}

Visit(xxx) 到最终的 DeclRefExpr 通过 Action 来判断存入相应的数组中

void DefUse::VisitDeclRefExpr(DeclRefExpr *DRE) {
  if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
    if (Action == Def) {
      defs.push_back(VD);
    } else if (Action == Use) {
      uses.push_back(VD);
    }
  }
}

2-Liveness¶

类 Liveness 计算每个程序点上的活跃变量集合

using LivenessFact = llvm::DenseSet<VarDecl *>;
llvm::DenseMap<const CFGBlock *, LivenessFact> liveness; //

liveness 用于保存基本块的所有活跃变量集合。

compute 函数迭代计算达到不动点停止

bool SetFrom(LivenessFact &Dest, const LivenessFact &Src) {
    if (Src.empty())
      return false;

    unsigned old = Dest.size();
    Dest.insert(Src.begin(), Src.end());
    return old != Dest.size();
}

void Liveness::Compute() {
  llvm::DenseSet<VarDecl *> fact;

  bool changed = true;
  while (changed) {
    changed = false;
    //自底向上
    for (const CFGBlock *B : env.cfg.const_nodes()) {
        fact.clear();

        for (auto succ : B->succs()) { // 将所有后继 block 中的活跃变量存入当前的集合中
            if (succ)
            SetFrom(fact, liveness[succ]);
        }
        for (CFGBlock::const_reverse_iterator it = Block->rbegin(),ei = Block->rend(); it != ei; ++it) {
            if (elem.getAs<CFGStmt>()) {
                S = elem.castAs<CFGStmt>().getStmt();
                // Get the def-use information of a given statement.
                DefUse DU(const_cast<Stmt *>(S));
                const llvm::SmallVector<VarDecl *> &defs = DU.getDefs();
                const llvm::SmallVector<VarDecl *> &uses = DU.getUses();

                // Anything we write to is no longer live.
                for (VarDecl *def : defs) {
                    fact.erase(def);
                }

                // Any variables we read from, we make live.
                for (VarDecl *use : uses) {
                    fact.insert(uses);
                }
            }
        }
        changed |= SetFrom(liveness[B], fact); // 达到不动点的条件
    }
  }
}

3-其他定义¶

3.1-class RegionName¶

区域的名称。每个 RegionName 对应一个 AST（抽象语法树）节点。

每个绑定区域（bound region）的名称为 'region 加上一个正整数，例如 'region_0、'region_1 等。绑定区域与函数中的变量或借用（borrow）/重新借用（reborrow）表达式相关。

自由区域（free region）的名称为 'region_r。自由区域与函数的返回点或调用者中的位置相关。

class RegionName {
public:
  std::string Name;
  constexpr static const char *const NamePrefix = "'region_";
  static unsigned Cnt;

3.2-class RegionVariable¶

一种索引机制，旨在简化计算和管理。每个RegionName与一个RegionVariable相关联，并且RegionVariable的索引从0开始递增。

struct RegionVariable {
  unsigned index;

3.3-class VarDefinition¶

表示程序中某个区域的生命周期。每个区域变量通常与一个具体的变量声明（VarDecl）或一个显式/隐式的借用表达式相关联。

struct VarDefinition {
  RegionName name;

  /// The current value of this region name. This is adjusted during region
  /// check by calls to `AddLivePoint`, and then finally adjusted further by
  /// the call to `Solve`.
  Region value;

  /// Capped region names should no longer have to grow as a result of
  /// inference. If they do wind up growing, we will report an error.
  bool capped; //指示一个区域变量是否已经被“封顶”。一旦封顶，该区域变量的活跃点集合将不再扩展，即不允许在后续的分析中添加更多的活跃点。

};

3.4- class Point¶

某个基本块内的具体节点（语句或指令）

struct Point {
  unsigned blockID;
  unsigned index; // 当前基本块中节点（语句或指令）的索引位置。

  /// 表示自由区域 'region_r 的结束块的标识符
  static const unsigned EndBlockID = -1u;
  static const unsigned EndIndex = -1u;

3.5- class Region¶

描述了一个区域变量（region variable）的作用域范围，这个作用域由控制流图（Control Flow Graph, CFG）中的一组点（points）组成。

struct Region {
  std::set<Point> points;

3.6- class Constraint¶

Constraint 表示一个生命周期约束，即：

sub（子区域变量）必须比 sup（父区域变量）存活更久（即 sub outlives sup）。

这个约束在控制流图（CFG）中的某个特定点（point）成立。

struct Constraint {
  RegionVariable sub;
  RegionVariable sup;
  Point point;

本文总阅读量次本站访客数人次