How to re-arragne LLVM GEP instructions?

Question

I have LLVM IR like below :

 for.body:                                         ; preds = %for.cond
  %add = add nsw i32 %i.0, 3
  %idxprom = sext i32 %add to i64
  %arrayidx = getelementptr inbounds i32, i32* %arr, i64 %idxprom
  %0 = load i32, i32* %arrayidx, align 4
  %add1 = add nsw i32 %sum1.0, %0
  %add2 = add nsw i32 %i.0, 2
  %idxprom3 = sext i32 %add2 to i64
  %arrayidx4 = getelementptr inbounds i32, i32* %arr, i64 %idxprom3
  %1 = load i32, i32* %arrayidx4, align 4
  %add5 = add nsw i32 %sum2.0, %1
  %add6 = add nsw i32 %i.0, 1
  %idxprom7 = sext i32 %add6 to i64
  %arrayidx8 = getelementptr inbounds i32, i32* %arr, i64 %idxprom7
  %2 = load i32, i32* %arrayidx8, align 4
  %add9 = add nsw i32 %sum3.0, %2
  %idxprom10 = sext i32 %i.0 to i64
  %arrayidx11 = getelementptr inbounds i32, i32* %arr, i64 %idxprom10
  %3 = load i32, i32* %arrayidx11, align 4
  %add12 = add nsw i32 %sum4.0, %3
  br label %for.inc

I want to re-arrang GEP instructions above. It should be arranged like below for this example :

  %arrayidx11 = getelementptr inbounds i32, i32* %arr, i64 %idxprom10
  %arrayidx8 = getelementptr inbounds i32, i32* %arr, i64 %idxprom7
  %arrayidx4 = getelementptr inbounds i32, i32* %arr, i64 %idxprom3
  %arrayidx = getelementptr inbounds i32, i32* %arr, i64 %idxprom

I know that even the uses of array access has to be moved after this arrangement. So I am trying to get use-chain for each GEP instruction using below code :

    // Get all the use chain instructions
    for (Value::use_iterator i = inst1->use_begin(),e = inst1->use_end(); i!=e;++i) {
      dyn_cast<Instruction>(*i)->dump();
    }

But I am getting only the declaration instruction with this code, I was expecting to get all the below instructions for %arrayidx4 :

  %arrayidx4 = getelementptr inbounds i32, i32* %arr, i64 %idxprom3
  %1 = load i32, i32* %arrayidx4, align 4

Please help me out here. Thanks in advance.

Answer 1

I don't really like this question, but I should be doing paperwork for my taxes today...

Your first task is to find the GEPs and sort them into the order you want. When doing this, you need a separate list. LLVM's BasicBlock class does provide a list, but as a general rule, never modify that list while you're iterating over it. That's permitted but too error-prone.

So at the start:

std::vector<GetElementPtr *> geps;
for(auto & i : block->getInstList())
    if(GetElementPtrInst * g = dyn_cast<GetElementPTrInst>(&i))
        geps.push_back(g);

You can use any container class, your project's code standard will probably suggest using either std::whatever or an LLVM class.

Next, sort geps into the order you prefer. I leave that part out.

After that, move each GEP to the latest permissible point in the block. Which point is that? Well, if the block was valid, then each GEP is already after the values it uses and before the instructions that use it, so moving it to a possibly later point while keeping it before its users will do.

for(auto g : geps) {
    Instruction * firstUser = nullptr;
    for(auto u : g->users()) {
        Instruction * i = dyn_cast<Instruction>(u);
        if(i &&
           i->getParent() == g->getParent() &&
           (!firstUser ||
            i->comesBefore(firstUser)))
              firstUser = i;
        }
    }
    if(firstUser)
        g->moveBefore(firstUser);
}

For each user, check that it is an instruction within the same basic block, and if it is so, check whether it's earlier in the block than the other users seen so far. Finally, move the GEP.

You may prefer a different approach. Several are possible. For example, you could reorder the GEPs after sorting them (using moveAfter() to move each GEP after the previous one) and then use a combination of users() and moveAfter() to make sure all users are after the instructions they use.

for(auto u : foo->users))) {
    Instruction * i = dyn_cast<Instruction>(u);
    if(i &&
       i->getParent() == foo->getParent() &&
       i->comesBefore(foo))
        i->moveAfter(foo);
}

Note again that this code never modifies the basic block's list while iterating over it. If you have any mysterious errors, check that first.