[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

42

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

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_REPLACECONSTANT_H
 #define LLVM_IR_REPLACECONSTANT_H
 
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instruction.h"
+#include <map>
+#include <vector>
 
 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 constant expression trees. Convert
+/// all reachable paths from contant expression operands of \p I to \p CE into
+/// corresponding instructions, insert them before \p I, update operands of \p I
+/// accordingly, and if required, return all such converted instructions at
+/// \p Insts.
+void convertConstantExprsToInstructions(
+    Instruction *I, ConstantExpr *CE,
+    SmallPtrSetImpl<Instruction *> *Insts = nullptr);
+
+/// The given instruction \p I contains constant expression CE within the
+/// constant expression trees of it`s constant expression operands, and
+/// \p CEPaths holds all the reachable paths (to CE) from such constant
+/// expression trees of \p I. Convert constant expressions within these paths
+/// into corresponding instructions, insert them before \p I, update operands of
+/// \p I accordingly, and if required, return all such converted instructions at
+/// \p Insts.
+void convertConstantExprsToInstructions(
+    Instruction *I,
+    std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
+    SmallPtrSetImpl<Instruction *> *Insts = nullptr);
+
+/// Given an instruction \p I which uses given constant expression \p CE as
+/// operand, either directly or nested within other constant expressions, return
+/// all reachable paths from the constant expression operands of \p I to \p CE,
+/// and return collected paths at \p CEPaths.
+void collectConstantExprPaths(
+    Instruction *I, ConstantExpr *CE,
+    std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths);
+
 } // 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) {
+  // Collect all reachable paths to CE from constant exprssion operands of I.
+  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
+  collectConstantExprPaths(I, CE, CEPaths);
+
+  // Convert all constant expressions to instructions which are collected at
+  // CEPaths.
+  convertConstantExprsToInstructions(I, CEPaths, Insts);
+}
+
+void convertConstantExprsToInstructions(
+    Instruction *I,
+    std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
+    SmallPtrSetImpl<Instruction *> *Insts) {
+  for (Use &U : I->operands()) {
+    // The operand U is either not a constant expression operand or the
+    // constant expression paths do not belong to U, ignore U.
+    if (!CEPaths.count(&U))
+      continue;
+
+    // If the instruction I is a PHI instruction, then fix the instruction
+    // insertion point to the entry of the incoming basic block for operand U.
+    auto *BI = I;
+    if (auto *Phi = dyn_cast<PHINode>(I)) {
+      BasicBlock *BB = Phi->getIncomingBlock(U);
+      BI = &(*(BB->getFirstInsertionPt()));
+    }
+
+    // Go through the paths associated with operand U, and convert all the
+    // constant expressions along all paths to corresponding instructions.
+    auto *II = I;
+    auto &Paths = CEPaths[&U];
+    SmallPtrSet<ConstantExpr *, 8> Visited;
+    for (auto &Path : Paths) {
+      for (auto *CE : Path) {
+        if (!Visited.insert(CE).second)
+          continue;
+        auto *NI = CE->getAsInstruction();
+        NI->insertBefore(BI);
+        II->replaceUsesOfWith(CE, NI);
+        CE->removeDeadConstantUsers();
+        BI = II = NI;
+        if (Insts)
+          Insts->insert(NI);
+      }
+    }
+  }
+}
+
+void collectConstantExprPaths(
+    Instruction *I, ConstantExpr *CE,
+    std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
+  for (Use &U : I->operands()) {
+    // If the operand U is not a constant expression operand, then ignore it.
+    auto *CE2 = dyn_cast<ConstantExpr>(U.get());
+    if (!CE2)
+      continue;
+
+    // Holds all reachable paths from CE2 to CE.
+    std::vector<std::vector<ConstantExpr *>> Paths;
+
+    // Collect all reachable paths from CE2 to CE.
+    std::vector<ConstantExpr *> Path{CE2};
+    std::vector<std::vector<ConstantExpr *>> Stack{Path};
+    while (!Stack.empty()) {
+      std::vector<ConstantExpr *> TPath = Stack.back();
+      Stack.pop_back();
+      auto *CE3 = TPath.back();
+
+      if (CE3 == CE) {
+        Paths.push_back(TPath);
+        continue;
+      }
+
+      for (auto &UU : CE3->operands()) {
+        if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
+          std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
+          NPath.push_back(CE4);
+          Stack.push_back(NPath);
+        }
+      }
+    }
+
+    // Associate all the collected paths with U, and save it.
+    if (!Paths.empty())
+      CEPaths[&U] = Paths;
+  }
+}
+
 } // namespace llvm