SSAUpdater.cpp Source File (original) (raw)

32#include

33#include

35using namespace llvm;

37#define DEBUG_TYPE "ssaupdater"

43}

46 : InsertedPHIs(NewPHI) {}

50}

53 if (!AV)

55 else

57 ProtoType = Ty;

58 ProtoName = std::string(Name);

59}

63}

67}

70 assert(ProtoType && "Need to initialize SSAUpdater");

71 assert(ProtoType == V->getType() &&

72 "All rewritten values must have the same type");

74}

78 unsigned PHINumValues = PHI->getNumIncomingValues();

79 if (PHINumValues != ValueMapping.size())

80 return false;

83 for (unsigned i = 0, e = PHINumValues; i != e; ++i)

84 if (ValueMapping[PHI->getIncomingBlock(i)] !=

85 PHI->getIncomingValue(i)) {

86 return false;

87 }

89 return true;

90}

93 Value *Res = GetValueAtEndOfBlockInternal(BB);

94 return Res;

95}

102

103

104

106 Value *SingularValue = nullptr;

107

108

109

110

111 if (PHINode *SomePhi = dyn_cast(BB->begin())) {

112 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {

113 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);

115 PredValues.push_back(std::make_pair(PredBB, PredVal));

116

117

118 if (i == 0)

119 SingularValue = PredVal;

120 else if (PredVal != SingularValue)

121 SingularValue = nullptr;

122 }

123 } else {

124 bool isFirstPred = true;

127 PredValues.push_back(std::make_pair(PredBB, PredVal));

128

129

130 if (isFirstPred) {

131 SingularValue = PredVal;

132 isFirstPred = false;

133 } else if (PredVal != SingularValue)

134 SingularValue = nullptr;

135 }

136 }

137

138

139 if (PredValues.empty())

141

142

143 if (SingularValue)

144 return SingularValue;

145

146

147

148 if (isa(BB->begin())) {

150 PredValues.end());

153 return &SomePHI;

154 }

155 }

156

157

161

162

163 for (const auto &PredValue : PredValues)

164 InsertedPHI->addIncoming(PredValue.second, PredValue.first);

165

166

167

171 return V;

172 }

173

174

177 DL = I->getDebugLoc();

179

180

181 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);

182

183 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");

184 return InsertedPHI;

185}

186

189

191 if (PHINode *UserPN = dyn_cast(User))

193 else

195

196 U.set(V);

197}

198

203 for (auto &DbgValue : DbgValues) {

204 if (DbgValue->getParent() == I->getParent())

205 continue;

207 }

208 for (auto &DVR : DbgVariableRecords) {

209 if (DVR->getParent() == I->getParent())

210 continue;

211 UpdateDebugValue(I, DVR);

212 }

213}

214

217 for (auto &DbgValue : DbgValues) {

219 }

220}

221

224 for (auto &DVR : DbgVariableRecords) {

225 UpdateDebugValue(I, DVR);

226 }

227}

228

233 DbgValue->replaceVariableLocationOp(I, NewVal);

234 } else

236}

237

243 } else

245}

246

249

251 if (PHINode *UserPN = dyn_cast(User))

253 else

255

256 U.set(V);

257}

258

259namespace llvm {

260

261template<>

263public:

268

271

272 class PHI_iterator {

273 private:

275 unsigned idx;

276

277 public:

279 : PHI(P), idx(0) {}

281 : PHI(P), idx(PHI->getNumIncomingValues()) {}

282

283 PHI_iterator &operator++() { ++idx; return *this; }

284 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }

286

289 };

290

293 return PHI_iterator(PHI, true);

294 }

295

296

297

300

301

302

303 if (PHINode *SomePhi = dyn_cast(BB->begin()))

305 else

307 }

308

309

310

313 }

314

315

316

320 PHINode::Create(Updater->ProtoType, NumPreds, Updater->ProtoName);

321 PHI->insertBefore(BB->begin());

322 return PHI;

323 }

324

325

326

328 PHI->addIncoming(Val, Pred);

329 }

330

331

333 return dyn_cast(Val);

334 }

335

336

337

339 PHINode *PHI = ValueIsPHI(Val, Updater);

340 if (PHI && PHI->getNumIncomingValues() == 0)

341 return PHI;

342 return nullptr;

343 }

344

345

346

348 return PHI;

349 }

350};

351

352}

353

354

355

356

357Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {

359 if (Value *V = AvailableVals[BB])

360 return V;

361

363 return Impl.GetValue(BB);

364}

365

366

367

368

369

373 if (Insts.empty()) return;

374

375 const Value *SomeVal;

376 if (const LoadInst *LI = dyn_cast(Insts[0]))

377 SomeVal = LI;

378 else

379 SomeVal = cast(Insts[0])->getOperand(0);

380

381 if (BaseName.empty())

382 BaseName = SomeVal->getName();

384}

385

387

388

389

391

393 UsesByBlock[User->getParent()].push_back(User);

394

395

396

397

400

404

405

406 if (BlockUses.empty()) continue;

407

408

409

410 if (BlockUses.size() == 1) {

411

415 } else if (auto *AI = dyn_cast(User)) {

416

418 } else {

419

421 }

422 BlockUses.clear();

423 continue;

424 }

425

426

427 bool HasStore = false;

429 if (isa(I) || isa(I)) {

430 HasStore = true;

431 break;

432 }

433 }

434

435

436 if (!HasStore) {

438 LiveInLoads.push_back(cast(I));

439 BlockUses.clear();

440 continue;

441 }

442

443

444

446 BlockUses.begin(), BlockUses.end(),

448

449

450

451

452

453

454 Value *StoredValue = nullptr;

456 if (LoadInst *L = dyn_cast(I)) {

457

458

459 if (StoredValue) {

461 L->replaceAllUsesWith(StoredValue);

462 ReplacedLoads[L] = StoredValue;

463 } else {

465 }

466 continue;

467 }

468

469 if (StoreInst *SI = dyn_cast(I)) {

471

472

473 StoredValue = SI->getOperand(0);

474 } else if (auto *AI = dyn_cast(I)) {

475

476

478 }

479 }

480

481

482 assert(StoredValue && "Already checked that there is a store in block");

484 BlockUses.clear();

485 }

486

487

488

489 for (LoadInst *ALoad : LiveInLoads) {

492

493

495 ALoad->replaceAllUsesWith(NewVal);

496 ReplacedLoads[ALoad] = NewVal;

497 }

498

499

501

502

503

506 continue;

507

508

509

510

511

513 Value *NewVal = ReplacedLoads[User];

514 assert(NewVal && "not a replaced load?");

515

516

517

518

520 while (RLI != ReplacedLoads.end()) {

521 NewVal = RLI->second;

522 RLI = ReplacedLoads.find(NewVal);

523 }

524

527 }

528

530 User->eraseFromParent();

531 }

532}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This defines the Use class.

static AvailableValsTy & getAvailableVals(void *AV)

DenseMap< MachineBasicBlock *, Register > AvailableValsTy

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

static AvailableValsTy & getAvailableVals(void *AV)

static bool IsEquivalentPHI(PHINode *PHI, SmallDenseMap< BasicBlock *, Value *, 8 > &ValueMapping)

This file defines the SmallVector class.

Class recording the (high level) value of a variable.

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

bool empty() const

empty - Check if the array is empty.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

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

const Instruction * getFirstNonPHI() const

Returns a pointer to the first instruction in this block that is not a PHINode instruction.

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

const BasicBlock * getParent() const

This represents the llvm.dbg.value instruction.

Record of a variable value-assignment, aka a non instruction representation of the dbg....

void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

void insertBefore(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified instruction.

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

An instruction for reading from memory.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static PoisonValue * get(Type *T)

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

Value * getIncomingValue()

BasicBlock * getIncomingBlock()

PHI_iterator(PHINode *P, bool)

PHI_iterator & operator++()

bool operator!=(const PHI_iterator &x) const

bool operator==(const PHI_iterator &x) const

static BlkSucc_iterator BlkSucc_end(BlkT *BB)

static BlkSucc_iterator BlkSucc_begin(BlkT *BB)

static void FindPredecessorBlocks(BasicBlock *BB, SmallVectorImpl< BasicBlock * > *Preds)

FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds vector, set Info->NumPreds,...

static Value * CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, SSAUpdater *Updater)

CreateEmptyPHI - Create a new PHI instruction in the specified block.

static PHINode * ValueIsNewPHI(Value *Val, SSAUpdater *Updater)

ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source operands, i....

static PHI_iterator PHI_begin(PhiT *PHI)

static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred)

AddPHIOperand - Add the specified value as an operand of the PHI for the specified predecessor block.

static Value * GetPHIValue(PHINode *PHI)

GetPHIValue - For the specified PHI instruction, return the value that it defines.

static Value * GetPoisonVal(BasicBlock *BB, SSAUpdater *Updater)

GetPoisonVal - Get a poison value of the same type as the value being handled.

static PHI_iterator PHI_end(PhiT *PHI)

static PHINode * ValueIsPHI(Value *Val, SSAUpdater *Updater)

ValueIsPHI - Check if a value is a PHI.

Helper class for SSA formation on a set of values defined in multiple blocks.

void RewriteUse(Use &U)

Rewrite a use of the symbolic value.

void RewriteUseAfterInsertions(Use &U)

Rewrite a use like RewriteUse but handling in-block definitions.

Value * FindValueForBlock(BasicBlock *BB) const

Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.

void Initialize(Type *Ty, StringRef Name)

Reset this object to get ready for a new set of SSA updates with type 'Ty'.

Value * GetValueInMiddleOfBlock(BasicBlock *BB)

Construct SSA form, materializing a value that is live in the middle of the specified block.

SSAUpdater(SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

If InsertedPHIs is specified, it will be filled in with all PHI Nodes created by rewriting.

void UpdateDebugValues(Instruction *I)

Rewrite debug value intrinsics to conform to a new SSA form.

bool HasValueForBlock(BasicBlock *BB) const

Return true if the SSAUpdater already has a value for the specified block.

Value * GetValueAtEndOfBlock(BasicBlock *BB)

Construct SSA form, materializing a value that is live at the end of the specified block.

void AddAvailableValue(BasicBlock *BB, Value *V)

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

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.

An instruction for storing to memory.

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

constexpr bool empty() const

empty - Check if the string is empty.

TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...

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

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

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

StringRef getName() const

Return a constant reference to the value's name.

This is an optimization pass for GlobalISel generic memory operations.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)

Finds the llvm.dbg.value intrinsics describing a value.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

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

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

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

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

SuccIterator< Instruction, BasicBlock > succ_iterator

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

auto predecessors(const MachineBasicBlock *BB)