循环外使用的 LLVM LoopPass 值

Question

我正在编写一个 LLVM LoopPass，其中我需要知道 哪些值在循环外使用。为此，我有这个代码：

virtual bool runOnLoop(Loop *loop, LPPassManager &LPM)
{
    for (auto it = loop->block_begin(); it != loop->block_end(); it++)
    {
        for (auto inst = (*it)->begin(); inst != (*it)->end(); inst++)
        {
            if (Is_Used_Outside_This_loop(loop,(Instruction *) inst))
            {
                errs() << inst->getName().str();
                errs() << " is used outside the loop\n";
            }
        }
    }
    // ...
}

内部函数一开始看起来是对的，但是下面的*.ll文件，它给出了 %tmp5 的错误分类，因为它 使用了两次 在循环的基本块内。

bool Is_Used_Outside_This_loop(Loop *loop, Value *v)
{
    int n=0;
    int numUses = v->getNumUses();
    for (auto it = loop->block_begin(); it != loop->block_end(); it++)
    {
        if (v->isUsedInBasicBlock(*it))
        {
            n++;
        }
    }
    if (n == numUses) return false;
    else              return true;
}

下面的*.ll代码说明%tmp5被使用了两次在循环的基本块内。当我仔细搜索 API 时，我找不到类似 Value::numUsesInBasicBlock( ... )

的内容

; Function Attrs: nounwind uwtable
define internal void @foo(i8* %s) #0 {
entry:
  %s.addr = alloca i8*, align 8
  %c = alloca i8, align 1
  store i8* %s, i8** %s.addr, align 8
  store i8 0, i8* %c, align 1
  br label %while.cond

while.cond:    ; preds = %while.body, %entry
  %tmp = load i8*, i8** %s.addr, align 8
  %tmp1 = load i8, i8* %tmp, align 1
  %conv = sext i8 %tmp1 to i32
  %cmp = icmp eq i32 %conv, 97
  br i1 %cmp, label %lor.end, label %lor.rhs

lor.rhs:    ; preds = %while.cond
  %tmp2 = load i8*, i8** %s.addr, align 8
  %tmp3 = load i8, i8* %tmp2, align 1
  %conv2 = sext i8 %tmp3 to i32
  %cmp3 = icmp eq i32 %conv2, 98
  br label %lor.end

lor.end:; preds = %lor.rhs, %while.cond
  %tmp4 = phi i1 [ true, %while.cond ], [ %cmp3, %lor.rhs ]
  br i1 %tmp4, label %while.body, label %while.end

while.body:    ; preds = %lor.end
  %tmp5 = load i8*, i8** %s.addr, align 8
  %incdec.ptr = getelementptr inbounds i8, i8* %tmp5, i32 1
  store i8* %incdec.ptr, i8** %s.addr, align 8
  %tmp6 = load i8, i8* %tmp5, align 1
  store i8 %tmp6, i8* %c, align 1
  br label %while.cond

while.end:    ; preds = %lor.end
  %tmp7 = load i8*, i8** %s.addr, align 8
  %tmp8 = load i8, i8* %tmp7, align 1
  %conv5 = sext i8 %tmp8 to i32
  %cmp6 = icmp eq i32 %conv5, 99
  br i1 %cmp6, label %if.then, label %if.end

if.then:    ; preds = %while.end
  %tmp9 = load i8*, i8** %s.addr, align 8
  %incdec.ptr8 = getelementptr inbounds i8, i8* %tmp9, i32 1
  store i8* %incdec.ptr8, i8** %s.addr, align 8
  br label %if.end

if.end:    ; preds = %if.then, %while.end
  ret void
}

显然，一定有办法做到这一点，对吧？谢谢！

Answer 1

下面是我的解决方法，虽然它看起来过于复杂：

virtual bool runOnLoop(Loop *loop, LPPassManager &LPM)
{
    for (auto it = loop->block_begin(); it != loop->block_end(); it++)
    {
        for (auto inst = (*it)->begin(); inst != (*it)->end(); inst++)
        {
            int n=0;
            for (auto use = inst->use_begin(); use != inst->use_end(); use++)
            {
                Instruction *i = (Instruction *) use->getUser();
                if (BasicBlockBelongsToLoop(i->getParent(),loop))
                {
                    n++;
                }
            }
            assert(n <= inst->getNumUses());
            if (n < inst->getNumUses())
            {
                errs() << inst->getName().str();
                errs() << " is used outside the loop\n";
            }
        }
    }
    // ...

我在API中也找不到，如何检查一个基本块是否属于一个循环，所以我不得不编写自己的 BasicBlockBelongsToLoop，这里是：

bool BasicBlockBelongsToLoop(BasicBlock *BB, Loop *loop)
{
    for (auto it = loop->block_begin(); it != loop->block_end(); it++)
    {
        if (BB == (*it))
        {
            return true;
        }
    }
    return false;
}

Answer 2

问题是你的退出条件。您要求使用，但随后与使用该值的块数进行比较。

因此，如果该值在同一个基本块中使用两次，则使用次数为 2，并且使用该值的基本块的 n 计数器仅递增一次，因此 n 和 numUses.

也许一个更简洁的方法来做你想做的事情是：

void FindUsesNotIn(
  llvm::SmallPtrSetImpl<llvm::BasicBlock *> &Blocks,
  llvm::SmallPtrSetImpl<llvm::Value *> &OutUses) {
  for(const auto &b : Blocks)
    for(auto &i : *b)
      for(const auto &u : i.users()) {
        auto *userInst = llvm::dyn_cast<llvm::Instruction>(u);

        if(userInst && !Blocks.count(userInst->getParent())) {
          OutUses.insert(&i);
          break;
        }
      }
}

然后在 runOnLoop 方法中有这样的东西：

virtual bool runOnLoop(llvm::Loop *loop, llvm::LPPassManager &LPM) {
  llvm::SmallPtrSet<llvm::BasicBlock*, 10> loopBlocks(loop->block_begin(), loop->block_end());
  llvm::SmallPtrSet<llvm::Value *, 10> outs;

  FindUsesNotIn(loopBlocks, outs);

  for(const auto *e : outs)
    llvm::dbgs() << *e << '\n';

  return false;
}

循环外使用的 LLVM LoopPass 值

LLVM LoopPass values used outside the loop

llvm

llvm-ir