Значения LLVM LoopPass, используемые вне цикла - PullRequest
Новая
       7

Значения LLVM LoopPass, используемые вне цикла

0 голосов
/ 27 июня 2018

Я пишу 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
}

Ясно, что должен быть способ сделать это, верно? Спасибо!

Ответы [ 2 ]

0 голосов
/ 27 июня 2018

Проблема в вашем состоянии выхода. Вы запрашиваете использование, но затем сравниваете с количеством блоков, в которых используется значение.

Таким образом, если значение используется дважды в одном и том же базовом блоке, количество использований равно 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;
}
0 голосов
/ 27 июня 2018

Вот как я это решил, хотя это выглядит слишком сложно: 

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;
}
...