LLVM  16.0.0git
ReplaceConstant.cpp
Go to the documentation of this file.
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 
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/IR/Constants.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/ValueMap.h"
19 
20 namespace llvm {
21 
24  // Collect all reachable paths to CE from constant exprssion operands of I.
25  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> CEPaths;
26  collectConstantExprPaths(I, CE, CEPaths);
27 
28  // Convert all constant expressions to instructions which are collected at
29  // CEPaths.
30  convertConstantExprsToInstructions(I, CEPaths, Insts);
31 }
32 
34  Instruction *I,
35  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
38 
39  for (Use &U : I->operands()) {
40  // The operand U is either not a constant expression operand or the
41  // constant expression paths do not belong to U, ignore U.
42  if (!CEPaths.count(&U))
43  continue;
44 
45  // If the instruction I is a PHI instruction, then fix the instruction
46  // insertion point to the entry of the incoming basic block for operand U.
47  auto *BI = I;
48  if (auto *Phi = dyn_cast<PHINode>(I)) {
49  BasicBlock *BB = Phi->getIncomingBlock(U);
50  BI = &(*(BB->getFirstInsertionPt()));
51  }
52 
53  // Go through all the paths associated with operand U, and convert all the
54  // constant expressions along all the paths to corresponding instructions.
55  auto *II = I;
56  auto &Paths = CEPaths[&U];
57  for (auto &Path : Paths) {
58  for (auto *CE : Path) {
59  // Instruction which is equivalent to CE.
60  Instruction *NI = nullptr;
61 
62  if (!Visited.count(CE)) {
63  // CE is encountered first time, convert it into a corresponding
64  // instruction NI, and appropriately insert NI before the parent
65  // instruction.
66  NI = CE->getAsInstruction(BI);
67 
68  // Mark CE as visited by mapping CE to NI.
69  Visited[CE] = NI;
70 
71  // If required collect NI.
72  if (Insts)
73  Insts->insert(NI);
74  } else {
75  // We had already encountered CE, the correponding instruction already
76  // exist, use it to replace CE.
77  NI = Visited[CE];
78  }
79 
80  assert(NI && "Expected an instruction corresponding to constant "
81  "expression.");
82 
83  // Replace all uses of constant expression CE by the corresponding
84  // instruction NI within the current parent instruction.
85  II->replaceUsesOfWith(CE, NI);
86  BI = II = NI;
87  }
88  }
89  }
90 
91  // Remove all converted constant expressions which are dead by now.
92  for (auto Item : Visited)
93  Item.first->removeDeadConstantUsers();
94 }
95 
98  std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths) {
99  for (Use &U : I->operands()) {
100  // If the operand U is not a constant expression operand, then ignore it.
101  auto *CE2 = dyn_cast<ConstantExpr>(U.get());
102  if (!CE2)
103  continue;
104 
105  // Holds all reachable paths from CE2 to CE.
106  std::vector<std::vector<ConstantExpr *>> Paths;
107 
108  // Collect all reachable paths from CE2 to CE.
109  std::vector<ConstantExpr *> Path{CE2};
110  std::vector<std::vector<ConstantExpr *>> Stack{Path};
111  while (!Stack.empty()) {
112  std::vector<ConstantExpr *> TPath = Stack.back();
113  Stack.pop_back();
114  auto *CE3 = TPath.back();
115 
116  if (CE3 == CE) {
117  Paths.push_back(TPath);
118  continue;
119  }
120 
121  for (auto &UU : CE3->operands()) {
122  if (auto *CE4 = dyn_cast<ConstantExpr>(UU.get())) {
123  std::vector<ConstantExpr *> NPath(TPath.begin(), TPath.end());
124  NPath.push_back(CE4);
125  Stack.push_back(NPath);
126  }
127  }
128  }
129 
130  // Associate all the collected paths with U, and save it.
131  if (!Paths.empty())
132  CEPaths[&U] = Paths;
133  }
134 }
135 
136 } // namespace llvm
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Constants.h
llvm::convertConstantExprsToInstructions
void convertConstantExprsToInstructions(Instruction *I, ConstantExpr *CE, SmallPtrSetImpl< Instruction * > *Insts=nullptr)
The given instruction I contains given constant expression CE as one of its operands,...
Definition: ReplaceConstant.cpp:22
llvm::Instruction
Definition: Instruction.h:42
SmallPtrSet.h
llvm::ValueMap::count
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: ValueMap.h:152
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
ValueMap.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:972
llvm::collectConstantExprPaths
void collectConstantExprPaths(Instruction *I, ConstantExpr *CE, std::map< Use *, std::vector< std::vector< ConstantExpr * >>> &CEPaths)
Given an instruction I which uses given constant expression CE as operand, either directly or nested ...
Definition: ReplaceConstant.cpp:96
Instructions.h
ReplaceConstant.h
llvm::SmallPtrSetImpl< Instruction * >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365