SSAUpdaterBulk.cpp Source File (original) (raw)

22using namespace llvm;

24#define DEBUG_TYPE "ssaupdaterbulk"

33 return UserPN->getIncomingBlock(*U);

34 else

35 return User->getParent();

36}

41 unsigned Var = Rewrites.size();

42 LLVM_DEBUG(dbgs() << "SSAUpdater: Var=" << Var << ": initialized with Ty = "

43 << *Ty << ", Name = " << Name << "\n");

44 RewriteInfo RI(Name, Ty);

45 Rewrites.push_back(RI);

46 return Var;

47}

52 assert(Var < Rewrites.size() && "Variable not found!");

54 << ": added new available value " << *V << " in "

55 << BB->getName() << "\n");

56 Rewrites[Var].Defines.emplace_back(BB, V);

57}

62 assert(Var < Rewrites.size() && "Variable not found!");

63 LLVM_DEBUG(dbgs() << "SSAUpdater: Var=" << Var << ": added a use" << *U->get()

65 Rewrites[Var].Uses.push_back(U);

66}

70static void

79 UsingBlocks.end());

83 while (!LiveInBlockWorklist.empty()) {

88 if (!LiveInBlocks.insert(BB).second)

89 continue;

96 if (DefBlocks.count(P))

97 continue;

101 }

102 }

103}

104

109

110

111

115 for (RewriteInfo &R : Rewrites) {

117

118

119

120

121

122

124 LLVM_DEBUG(dbgs() << "SSAUpdater: rewriting " << R.Uses.size()

125 << " use(s)\n");

126

130

132 for (Use *U : R.Uses)

134

140

141

143

144 for (auto [BB, V] : R.Defines)

145 BBInfos[BB].LiveOutValue = V;

146

147

148 for (BasicBlock *FrontierBB : IDFBlocks) {

149 IRBuilder<> B(FrontierBB, FrontierBB->begin());

150 PHINode *PN = B.CreatePHI(R.Ty, 0, R.Name);

151 BBInfos[FrontierBB].LiveInValue = PN;

152 if (InsertedPHIs)

154 }

155

156

157

158 auto ComputeValue = [&](BasicBlock *BB, bool IsLiveOut) -> Value * {

160

161 if (IsLiveOut && BBInfo->LiveOutValue)

162 return BBInfo->LiveOutValue;

163

164 if (BBInfo->LiveInValue)

165 return BBInfo->LiveInValue;

166

168 Value *V = nullptr;

169

172 BBInfo = &BBInfos[BB];

173

174 if (BBInfo->LiveOutValue) {

175 V = BBInfo->LiveOutValue;

176 break;

177 }

178

179 if (BBInfo->LiveInValue) {

180 V = BBInfo->LiveInValue;

181 break;

182 }

183

184 Stack.emplace_back(BBInfo);

185 }

186

187 if (!V)

189

191

192

193 BBInfo->LiveInValue = V;

194

195 return V;

196 };

197

198

201 for (BasicBlock *Pred : PredCache.get(BB))

202 PHI->addIncoming(ComputeValue(Pred, true), Pred);

203 }

204

205

207 for (Use *U : R.Uses) {

208 if (!ProcessedUses.insert(U).second)

209 continue;

210

213 Value *V = ComputeValue(BB, BB != User->getParent());

214 Value *OldVal = U->get();

215 assert(OldVal && "Invalid use!");

216

219 LLVM_DEBUG(dbgs() << "SSAUpdater: replacing " << *OldVal << " with " << *V

220 << "\n");

221 U->set(V);

222 }

223 }

224}

225

226

227

228

229

230

235 PHI->replaceAllUsesWith(Simplified);

236 PHI->eraseFromParent();

237 PHI = nullptr;

238 }

239 }

240}

241

242#ifndef NDEBUG

243

244

245

246static bool

249 for (PHINode &PN : NewPHIs)

250 NewPHISet.insert(&PN);

252 for (Value *V : PHI.incoming_values()) {

254 if (IncPHI && IncPHI != &PHI && NewPHISet.contains(IncPHI))

255 return true;

256 }

257 }

258 return false;

259}

260#endif

261

263 if ( PHI .isIdenticalToWhenDefined(&ReplPHI))

264 return false;

265 PHI.replaceAllUsesWith(&ReplPHI);

266 PHI.eraseFromParent();

267 return true;

268}

269

273

274

275

277 for (auto I = BB->phis().begin(); I != FirstExistingPN; ++I) {

278 for (auto J = std::next(I); J != FirstExistingPN;) {

280 }

281 }

282

283

285 auto I = BB->phis().begin();

286 assert(I != FirstExistingPN);

287 do {

289 } while (I != FirstExistingPN);

290 if (BB->phis().begin() == FirstExistingPN)

292 }

294}

295

300 ++BBs[PHI->getParent()];

301 }

302

303 for (auto [BB, NumNewPHIs] : BBs) {

304 auto FirstExistingPN = std::next(BB->phis().begin(), NumNewPHIs);

306 }

307}

308

312 if (PHIs.empty())

313 return;

314

317}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This defines the Use class.

static StringRef getName(Value *V)

static BasicBlock * getUserBB(Use *U)

Helper function for finding a block which should have a value for the given user.

Definition SSAUpdaterBulk.cpp:29

bool EliminateNewDuplicatePHINodes(BasicBlock *BB, BasicBlock::phi_iterator FirstExistingPN)

Definition SSAUpdaterBulk.cpp:270

static void simplifyPass(MutableArrayRef< PHINode * > Worklist, const DataLayout &DL)

Definition SSAUpdaterBulk.cpp:231

static void deduplicatePass(ArrayRef< PHINode * > Worklist)

Definition SSAUpdaterBulk.cpp:296

static bool PHIAreRefEachOther(const iterator_range< BasicBlock::phi_iterator > NewPHIs)

Definition SSAUpdaterBulk.cpp:247

static void ComputeLiveInBlocks(const SmallPtrSetImpl< BasicBlock * > &UsingBlocks, const SmallPtrSetImpl< BasicBlock * > &DefBlocks, SmallPtrSetImpl< BasicBlock * > &LiveInBlocks, PredIteratorCache &PredCache)

Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.

Definition SSAUpdaterBulk.cpp:71

static bool replaceIfIdentical(PHINode &PHI, PHINode &ReplPHI)

Definition SSAUpdaterBulk.cpp:262

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

phi_iterator_impl<> phi_iterator

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Instruction & front() const

A parsed version of the target data layout string in and methods for querying it.

void reserve(size_type NumEntries)

Grow the densemap so that it can contain at least NumEntries items before resizing again.

DomTreeNodeBase * getIDom() const

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)

Calculate iterated dominance frontiers.

void setLiveInBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)

Give the IDF calculator the set of blocks in which the value is live on entry to the block.

void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)

Give the IDF calculator the set of blocks in which the value is defined.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.

ArrayRef< BasicBlock * > get(BasicBlock *BB)

LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)

Add a new variable to the SSA rewriter.

Definition SSAUpdaterBulk.cpp:40

LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)

Indicate that a rewritten value is available in the specified block with the specified value.

Definition SSAUpdaterBulk.cpp:51

LLVM_ABI void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.

Definition SSAUpdaterBulk.cpp:112

LLVM_ABI void AddUse(unsigned Var, Use *U)

Record a use of the symbolic value.

Definition SSAUpdaterBulk.cpp:61

LLVM_ABI_FOR_TEST void RewriteAndOptimizeAllUses(DominatorTree &DT)

Rewrite all uses and simplify the inserted PHI nodes.

Definition SSAUpdaterBulk.cpp:309

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

bool contains(ConstPtrType Ptr) const

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

The instances of the Type class are immutable: once they are created, they are never changed.

static LLVM_ABI UndefValue * get(Type *T)

Static factory methods - Return an 'undef' object of the specified type.

A Use represents the edge between a Value definition and its users.

static LLVM_ABI void ValueIsRAUWd(Value *Old, Value *New)

LLVM Value Representation.

bool hasValueHandle() const

Return true if there is a value handle associated with this value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

A range adaptor for a pair of iterators.

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

constexpr from_range_t from_range

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

auto make_first_range(ContainerTy &&c)

Given a container of pairs, return a range over the first elements.

IDFCalculator< false > ForwardIDFCalculator

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

Definition SSAUpdaterBulk.cpp:105

Value * LiveOutValue

Definition SSAUpdaterBulk.cpp:107

Value * LiveInValue

Definition SSAUpdaterBulk.cpp:106