llvm/lib/IR/ReplaceConstant.cpp

   1 //===- ReplaceConstant.cpp - Replace LLVM constant expression--------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements a utility function for replacing LLVM constant
  10 // expressions by instructions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/IR/ReplaceConstant.h"
  15 #include "llvm/IR/IRBuilder.h"
  16 #include "llvm/IR/Instructions.h"
  17 #include "llvm/IR/NoFolder.h"
  18
  19 namespace llvm {
  20 // Replace a constant expression by instructions with equivalent operations at
  21 // a specified location.
  22 Instruction *createReplacementInstr(ConstantExpr *CE, Instruction *Instr) {
  23   auto *CEInstr = CE->getAsInstruction();
  24   CEInstr->insertBefore(Instr);
  25   return CEInstr;
  26 }
  27
  28 void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE,
  29                                         SmallPtrSetImpl<Instruction *> *Insts) {
  30   // Collect all reachable paths to CE from constant exprssion operands of I.
  31   std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
  32   collectConstantExprPaths(I, CE, CEPaths);
  33
  34   // Convert all constant expressions to instructions which are collected at
  35   // CEPaths.
  36   convertConstantExprsToInstructions(I, CEPaths, Insts);
  37 }
  38
  39 void convertConstantExprsToInstructions(
  40     Instruction *I,
  41     std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
  42     SmallPtrSetImpl<Instruction *> *Insts) {
  43   SmallPtrSet<ConstantExpr *, 8> Visited;
  44   for (Use &U : I->operands()) {
  45     // The operand U is either not a constant expression operand or the
  46     // constant expression paths do not belong to U, ignore U.
  47     if (!CEPaths.count(&U))
  48       continue;
  49
  50     // If the instruction I is a PHI instruction, then fix the instruction
  51     // insertion point to the entry of the incoming basic block for operand U.
  52     auto *BI = I;
  53     if (auto *Phi = dyn_cast<PHINode>(I)) {
  54       BasicBlock *BB = Phi->getIncomingBlock(U);
  55       BI = &(*(BB->getFirstInsertionPt()));
  56     }
  57
  58     // Go through the paths associated with operand U, and convert all the
  59     // constant expressions along all paths to corresponding instructions.
  60     auto *II = I;
  61     auto &Paths = CEPaths[&U];
  62     for (auto &Path : Paths) {
  63       for (auto *CE : Path) {
  64         if (!Visited.insert(CE).second)
  65           continue;
  66         auto *NI = CE->getAsInstruction();
  67         NI->insertBefore(BI);
  68         II->replaceUsesOfWith(CE, NI);
  69         CE->removeDeadConstantUsers();
  70         BI = II = NI;
  71         if (Insts)
  72           Insts->insert(NI);
  73       }
  74     }
  75   }
  76 }
  77
  78 void collectConstantExprPaths(
  79     Instruction *I, ConstantExpr *CE,
  80     std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
  81   for (Use &U : I->operands()) {
  82     // If the operand U is not a constant expression operand, then ignore it.
  83     auto *CE2 = dyn_cast<ConstantExpr>(U.get());
  84     if (!CE2)
  85       continue;
  86
  87     // Holds all reachable paths from CE2 to CE.
  88     std::vector<std::vector<ConstantExpr *>> Paths;
  89
  90     // Collect all reachable paths from CE2 to CE.
  91     std::vector<ConstantExpr *> Path{CE2};
  92     std::vector<std::vector<ConstantExpr *>> Stack{Path};
  93     while (!Stack.empty()) {
  94       std::vector<ConstantExpr *> TPath = Stack.back();
  95       Stack.pop_back();
  96       auto *CE3 = TPath.back();
  97
  98       if (CE3 == CE) {
  99         Paths.push_back(TPath);
 100         continue;
 101       }
 102
 103       for (auto &UU : CE3->operands()) {
 104         if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
 105           std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
 106           NPath.push_back(CE4);
 107           Stack.push_back(NPath);
 108         }
 109       }
 110     }
 111
 112     // Associate all the collected paths with U, and save it.
 113     if (!Paths.empty())
 114       CEPaths[&U] = Paths;
 115   }
 116 }
 117
 118 } // namespace llvm