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/ADT/SetVector.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/Instructions.h"
18
19using namespace llvm;
20
21static bool isExpandableUser(User *U) {
22 return isa<ConstantExpr>(Val: U) || isa<ConstantAggregate>(Val: U);
23}
24
25static void expandUser(BasicBlock::iterator InsertPt, Constant *C,
26 SmallVector<Instruction *, 4> &NewInsts) {
27 NewInsts.clear();
28 if (auto *CE = dyn_cast<ConstantExpr>(Val: C)) {
29 Instruction *ConstInst = CE->getAsInstruction();
30 ConstInst->insertBefore(BB&: *InsertPt->getParent(), InsertPos: InsertPt);
31 NewInsts.push_back(Elt: ConstInst);
32 } else if (isa<ConstantStruct>(Val: C) || isa<ConstantArray>(Val: C)) {
33 Value *V = PoisonValue::get(T: C->getType());
34 for (auto [Idx, Op] : enumerate(First: C->operands())) {
35 V = InsertValueInst::Create(Agg: V, Val: Op, Idxs: Idx, NameStr: "", InsertBefore: InsertPt);
36 NewInsts.push_back(Elt: cast<Instruction>(Val: V));
37 }
38 } else if (isa<ConstantVector>(Val: C)) {
39 Type *IdxTy = Type::getInt32Ty(C&: C->getContext());
40 Value *V = PoisonValue::get(T: C->getType());
41 for (auto [Idx, Op] : enumerate(First: C->operands())) {
42 V = InsertElementInst::Create(Vec: V, NewElt: Op, Idx: ConstantInt::get(Ty: IdxTy, V: Idx), NameStr: "",
43 InsertBefore: InsertPt);
44 NewInsts.push_back(Elt: cast<Instruction>(Val: V));
45 }
46 } else {
47 llvm_unreachable("Not an expandable user");
48 }
49}
50
51bool llvm::convertUsersOfConstantsToInstructions(ArrayRef<Constant *> Consts,
52 Function *RestrictToFunc,
53 bool RemoveDeadConstants,
54 bool IncludeSelf) {
55 // Find all expandable direct users of Consts.
56 SmallVector<Constant *> Stack;
57 for (Constant *C : Consts) {
58 assert(!isa<ConstantData>(C) &&
59 "should not be expanding trivial constant users");
60
61 if (IncludeSelf) {
62 assert(isExpandableUser(C) && "One of the constants is not expandable");
63 Stack.push_back(Elt: C);
64 } else {
65 for (User *U : C->users())
66 if (isExpandableUser(U))
67 Stack.push_back(Elt: cast<Constant>(Val: U));
68 }
69 }
70
71 // Include transitive users.
72 SetVector<Constant *> ExpandableUsers;
73 while (!Stack.empty()) {
74 Constant *C = Stack.pop_back_val();
75 if (!ExpandableUsers.insert(X: C))
76 continue;
77
78 for (auto *Nested : C->users())
79 if (isExpandableUser(U: Nested))
80 Stack.push_back(Elt: cast<Constant>(Val: Nested));
81 }
82
83 // Find all instructions that use any of the expandable users
84 SetVector<Instruction *> InstructionWorklist;
85 for (Constant *C : ExpandableUsers)
86 for (User *U : C->users())
87 if (auto *I = dyn_cast<Instruction>(Val: U))
88 if (!RestrictToFunc || I->getFunction() == RestrictToFunc)
89 InstructionWorklist.insert(X: I);
90
91 // Replace those expandable operands with instructions
92 bool Changed = false;
93 // We need to cache the instructions we've already expanded to avoid expanding
94 // the same constant multiple times in the same basic block, which is
95 // problematic when the same constant is used in a phi node multiple times.
96 DenseMap<std::pair<Constant *, BasicBlock *>, SmallVector<Instruction *, 4>>
97 ConstantToInstructionMap;
98 while (!InstructionWorklist.empty()) {
99 Instruction *I = InstructionWorklist.pop_back_val();
100 DebugLoc Loc = I->getDebugLoc();
101 for (Use &U : I->operands()) {
102 BasicBlock::iterator BI = I->getIterator();
103 if (auto *Phi = dyn_cast<PHINode>(Val: I)) {
104 BasicBlock *BB = Phi->getIncomingBlock(U);
105 BI = BB->getFirstInsertionPt();
106 assert(BI != BB->end() && "Unexpected empty basic block");
107 }
108
109 if (auto *C = dyn_cast<Constant>(Val: U.get())) {
110 if (ExpandableUsers.contains(key: C)) {
111 Changed = true;
112 SmallVector<Instruction *, 4> &NewInsts =
113 ConstantToInstructionMap[std::make_pair(x&: C, y: BI->getParent())];
114 // If the cached instruction is after the insertion point, we need to
115 // create a new one. We can't simply move the cached instruction
116 // because its operands (also expanded instructions) might not
117 // dominate the new position.
118 if (NewInsts.empty() || BI->comesBefore(Other: NewInsts.front()))
119 expandUser(InsertPt: BI, C, NewInsts);
120 for (auto *NI : NewInsts)
121 NI->setDebugLoc(Loc);
122 InstructionWorklist.insert_range(R&: NewInsts);
123 U.set(NewInsts.back());
124 }
125 }
126 }
127 }
128
129 if (RemoveDeadConstants)
130 for (Constant *C : Consts)
131 C->removeDeadConstantUsers();
132
133 return Changed;
134}
135