[IR] Add utility to convert constant expression operands (of an instruction) to instructions.

[hsmhsm]

Summary

In the situation where we need to replace a constant operand C from a constant expression CE
by an instruction NI, it not possible without converting CE itself into an instruction. This
utility helps to convert the given set of constant expression operands from an instruction I
into a corresponding set of instructions.

The current use-case for this utility is from the patches - https://reviews.llvm.org/D103225
and https://reviews.llvm.org/D103655.

[foad]

Given a constant expression tree that contains CE, you are converting the entire tree to instructions. That is overkill. You only need to convert the nodes on the path from CE to the root.

[rampitec]

llvm/lib/IR/ReplaceConstant.cpp

145

This loop is just

append_range(Stack, CE3->operands());

[rampitec]

llvm/lib/IR/ReplaceConstant.cpp

108

The loop below can be replaced with the initializer:

SmallPtrSet<Value *, 4> Operands2(CE->op_begin(), CE->op_end());

[rampitec]

llvm/lib/IR/ReplaceConstant.cpp

107

To address Jay's comment I think you can pass an original CE into this function and amend the if to only execute it if CE != ReplacedCE. It will then skip the operands of the expression being replaced itself. I.e.:

@@ -77,12 +77,13 @@ void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,

   // Convert constant expressions operands of I (from the set CEOperands) to
   // instructions.
-  convertConstantExprsToInstructions(I, CEOperands, Insts);
+  convertConstantExprsToInstructions(I, CEOperands, Insts, CE);
 }

 void convertConstantExprsToInstructions(Instruction *I,
                                         SmallPtrSetImpl<Value *> &Operands,
-                                        SmallPtrSetImpl<Instruction *> &Insts) {
+                                        SmallPtrSetImpl<Instruction *> &Insts,
+                                        ConstantExpr *C) {
   for (Use &U : I->operands()) {
     auto *V = U.get();

@@ -104,11 +105,9 @@ void convertConstantExprsToInstructions(Instruction *I,
     I->replaceUsesOfWith(CE, NI);
     Insts.insert(NI);

-    if (CE->getNumOperands()) {
+    if (C != CE && CE->getNumOperands()) {
      SmallPtrSet<Value *, 4> Operands2;
      for (Use &UU : CE->operands())
        Operands2.insert(UU.get());
-      convertConstantExprsToInstructions(NI, Operands2, Insts);
+      convertConstantExprsToInstructions(NI, Operands2, Insts, C);
     }

     CE->removeDeadConstantUsers();

Note there are never recursive constant expressions.

[rampitec]

llvm/include/llvm/IR/ReplaceConstant.h

40

I would make Insts operand optional pointer. For instance I do not need it in D103655.

[rampitec]

llvm/lib/IR/ReplaceConstant.cpp

130

I think Visited is not needed. There can be no recursive CE.

[hsmhsm]

In D103661#2798554, @foad wrote:

Given a constant expression tree that contains CE, you are converting the entire tree to instructions. That is overkill. You only need to convert the nodes on the path from CE to the root.

Fixed it. Place take a look at latest submitted code.

llvm/lib/IR/ReplaceConstant.cpp

107

This will some extent reduces the unnecessary CE to I conversion. But, does not fully handle what @foad is suggesting. Consider below tree.

               I0
               |
              CE1
            /     \
         CE2      CE3
        /   \        \
     CE4    CE4      CE5
     /  \      \
  CE6   CE6    CE7
   /      \
CE8       CE9

Assuminng that, we need to convert CE4 into instructions, we only need to touch CEs in the two paths - (1) CE1, CE2, CE4 and (2) CE1, CE2, CE4. So result would be something like below.

I4_2 (CE7)
I4_1 (CE6, CE6)
I2 (I4_1, I4_2)
I1 (I2,  CE3)
I0 (I1)

But, the above code that you are suggesting here will convert every sub-tree except sub-trees starting from CE4.

Let's see what to do about it.

[hsmhsm]

Fixed few review comments by @rampitec.

[hsmhsm]

llvm/lib/IR/ReplaceConstant.cpp

107

The above tree is incorrect, please read it as below.

          I0
          |
         CE1
       /     \
    CE2      CE3
   /   \        \
CE4    CE4      CE5
   \      \
   CE7    CE7

and the CE to I conversion as below:

I4 (CE7)
I2 (I4, I4)
I1 (I2,  CE3)
I0 (I1)

[hsmhsm]

Make sure that only required constant expressions are converted into instructions.

[hsmhsm]

Replace llvm data structures by std c++ data structures, since passing complicated and nested
llvm data structures as a reference parameter of a function is very complicated.

[hsmhsm]

Remove braces around single line IF statements.

[rampitec]

Thanks! It makes it now I believe. D103655 has @timestwo() which exploits partial conversion change. LGTM.

llvm/include/llvm/IR/ReplaceConstant.h

 #include "llvm/IR/Instruction.h"
 
 namespace llvm {
 
 /// Create a replacement instruction for constant expression \p CE and insert
 /// it before \p Instr.
 Instruction *createReplacementInstr(ConstantExpr *CE, Instruction *Instr);
 
+/// The given instruction \p I contains given constant expression \p CE as one
+/// of its operands, possibly nested within other constant expressions. Convert
+/// all such constant expression operands into corresponding instructions,
+/// insert them before \p I, update operands of \p I accordingly, and return all
+/// such converted instructions at \p Insts.
+void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
+                                        SmallPtrSetImpl<Instruction *> &Insts);
+
+/// Given an instruction \p I and its operands \p Operands, convert all the
+/// constant expression operands from \p Operands into corresponding
+/// instructions, insert them before \p I, update operands of \p I accordingly,
+/// and return all such converted instructions at \p Insts.
+void convertConstantExprsToInstructions(Instruction *I,
+                                        SmallPtrSetImpl<Value *> &Operands,
+                                        SmallPtrSetImpl<Instruction *> &Insts);
+
+/// Given an instruction \p I which uses given constant expression \p CE as
+/// operand, either directly or nested within other constant expressions, return
+/// all such constant expression operands of \p I which contain \p CE.
+SmallPtrSet<Value *, 4> getConstantExprOperands(Instruction *I,
+                                                ConstantExpr *CE);
+
 } // end namespace llvm
 
 #endif // LLVM_IR_REPLACECONSTANT_H

llvm/lib/IR/ReplaceConstant.cpp

Instruction *createReplacementInstr(ConstantExpr *CE, Instruction *Instr) {
   case Instruction::AddrSpaceCast:
     return dyn_cast<Instruction>(
         Builder.CreateCast((Instruction::CastOps)OpCode, CE->getOperand(0),
                            CE->getType(), CE->getName()));
   default:
     llvm_unreachable("Unhandled constant expression!\n");
   }
 }
+
+void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
+                                        SmallPtrSetImpl<Instruction *> &Insts) {
+  // Get all operands of I which use CE as operand either directly or nested
+  // within other constant expressions.
+  SmallPtrSet<Value *, 4> CEOperands = getConstantExprOperands(I, CE);
+
+  // Convert constant expressions operands of I (from the set CEOperands) to
+  // instructions.
+  convertConstantExprsToInstructions(I, CEOperands, Insts);
+}
+
+void convertConstantExprsToInstructions(Instruction *I,
+                                        SmallPtrSetImpl<Value *> &Operands,
+                                        SmallPtrSetImpl<Instruction *> &Insts) {
+  for (Use &U : I->operands()) {
+    auto *V = U.get();
+
+    if (!Operands.contains(V))
+      continue;
+
+    auto *CE = dyn_cast<ConstantExpr>(V);
+    if (!CE)
+      continue;
+
+    auto *BI = I;
+    if (auto *Phi = dyn_cast<PHINode>(I)) {
+      BasicBlock *BB = Phi->getIncomingBlock(U);
+      BI = &(*(BB->getFirstInsertionPt()));
+    }
+
+    auto *NI = CE->getAsInstruction();
+    NI->insertBefore(BI);
+    I->replaceUsesOfWith(CE, NI);
+    Insts.insert(NI);
+
+    if (CE->getNumOperands()) {
+      SmallPtrSet<Value *, 4> Operands2;
+      for (Use &UU : CE->operands())
+        Operands2.insert(UU.get());
+      convertConstantExprsToInstructions(NI, Operands2, Insts);
+    }
+
+    CE->removeDeadConstantUsers();
+  }
+}
+
+// Return all the constant expression operands of I which contain CE.
+SmallPtrSet<Value *, 4> getConstantExprOperands(Instruction *I,
+                                                ConstantExpr *CE) {
+  SmallPtrSet<Value *, 4> CEOperands;
+
+  for (Use &U : I->operands()) {
+    auto *CE2 = dyn_cast<ConstantExpr>(U.get());
+    if (!CE2)
+      continue;
+
+    if (CE2 != CE) {
+      SmallVector<Value *, 8> Stack;
+      SmallPtrSet<Value *, 8> Visited;
+
+      Stack.push_back(CE2);
+
+      while (!Stack.empty()) {
+        Value *V = Stack.pop_back_val();
+
+        if (!Visited.insert(V).second)
+          continue;
+
+        if (auto *CE3 = dyn_cast<ConstantExpr>(V)) {
+          if (CE3 == CE) {
+            CEOperands.insert(U.get());
+            break;
+          }
+          for (Use &UU : CE3->operands())
+            Stack.push_back(UU.get());
+        }
+      }
+    } else {
+      CEOperands.insert(U.get());
+    }
+  }
+
+  return CEOperands;
+}
+
 } // namespace llvm