ControlFlowUtils.cpp Source File (original) (raw)

22#define DEBUG_TYPE "control-flow-hub"

24using namespace llvm;

38 "Only support branch terminator.");

39 auto *Branch = cast(BB->getTerminator());

40 auto *Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;

42 assert(Succ0 || Succ1);

44 if (Branch->isUnconditional()) {

45 assert(Succ0 == Branch->getSuccessor(0));

47 Branch->setSuccessor(0, FirstGuardBlock);

48 } else {

49 assert(!Succ1 || Succ1 == Branch->getSuccessor(1));

50 if (Succ0 && !Succ1) {

51 Branch->setSuccessor(0, FirstGuardBlock);

52 } else if (Succ1 && !Succ0) {

53 Branch->setSuccessor(1, FirstGuardBlock);

54 } else {

55 Branch->eraseFromParent();

57 }

58 }

60 return Condition;

61}

73 int I = 0;

74 for (int E = GuardBlocks.size() - 1; I != E; ++I) {

77 GuardBlocks[I]);

78 }

81 GuardBlocks[I]);

82}

95 FirstGuardBlock);

97 for (auto [BB, Succ0, Succ1] : Branches) {

99 Value *IncomingId = nullptr;

100 if (Succ0 && Succ1) {

101 auto Succ0Iter = find(Outgoing, Succ0);

102 auto Succ1Iter = find(Outgoing, Succ1);

104 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), Succ0Iter));

106 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), Succ1Iter));

107 IncomingId = SelectInst::Create(Condition, Id0, Id1, "target.bb.idx",

108 BB->getTerminator()->getIterator());

109 } else {

110

111 auto SuccIter = Succ0 ? find(Outgoing, Succ0) : find(Outgoing, Succ1);

112 IncomingId =

113 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), SuccIter));

114 }

115 Phi->addIncoming(IncomingId, BB);

116 }

117

118 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {

121 << "\n");

122 auto *Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,

123 ConstantInt::get(Int32Ty, I),

124 Out->getName() + ".predicate", GuardBlocks[I]);

125 GuardPredicates[Out] = Cmp;

126 }

127}

128

129

130

139

140

141

142 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {

145 << "\n");

146

147 auto *Phi =

150 GuardPredicates[Out] = Phi;

151 }

152

153 for (auto [BB, Succ0, Succ1] : Branches) {

155

156

157

158

159

160

161

162

163 bool OneSuccessorDone = false;

164 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {

166 PHINode *Phi = cast(GuardPredicates[Out]);

167 if (Out != Succ0 && Out != Succ1) {

168 Phi->addIncoming(BoolFalse, BB);

169 } else if (!Succ0 || !Succ1 || OneSuccessorDone) {

170

171

172 Phi->addIncoming(BoolTrue, BB);

173 } else {

174 assert(Succ0 && Succ1);

175 if (Out == Succ0) {

176 Phi->addIncoming(Condition, BB);

177 } else {

179 DeletionCandidates.push_back(Condition);

180 Phi->addIncoming(Inverted, BB);

181 }

182 OneSuccessorDone = true;

183 }

184 }

185 }

186}

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

206 std::optional MaxControlFlowBooleans) {

209

210 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I)

213

214

215

216

217

218

219 if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans)

221 DeletionCandidates);

222 else

224

226}

227

228

229

230

231

232

233

234

235

236

240 auto I = Out->begin();

241 while (I != Out->end() && isa(I)) {

242 auto *Phi = cast(I);

243 auto *NewPhi =

245 Phi->getName() + ".moved", FirstGuardBlock->begin());

246 bool AllUndef = true;

247 for (auto [BB, Succ0, Succ1] : Incoming) {

249 if (BB == Out) {

250 V = NewPhi;

251 } else if (Phi->getBasicBlockIndex(BB) != -1) {

252 V = Phi->removeIncomingValue(BB, false);

253 AllUndef &= isa(V);

254 }

255 NewPhi->addIncoming(V, BB);

256 }

257 assert(NewPhi->getNumIncomingValues() == Incoming.size());

258 Value *NewV = NewPhi;

259 if (AllUndef) {

260 NewPhi->eraseFromParent();

262 }

263 if (Phi->getNumOperands() == 0) {

264 Phi->replaceAllUsesWith(NewV);

265 I = Phi->eraseFromParent();

266 continue;

267 }

268 Phi->addIncoming(NewV, GuardBlock);

269 ++I;

270 }

271}

272

275 const StringRef Prefix, std::optional MaxControlFlowBooleans) {

276#ifndef NDEBUG

278#endif

280

281 for (auto [BB, Succ0, Succ1] : Branches) {

282#ifndef NDEBUG

283 assert(Incoming.insert(BB).second && "Duplicate entry for incoming block.");

284#endif

285 if (Succ0)

286 Outgoing.insert(Succ0);

287 if (Succ1)

288 Outgoing.insert(Succ1);

289 }

290

291 if (Outgoing.size() < 2)

292 return Outgoing.front();

293

295 if (DTU) {

296 for (auto [BB, Succ0, Succ1] : Branches) {

297 if (Succ0)

299 if (Succ1)

301 }

302 }

303

306 DeletionCandidates, Prefix, MaxControlFlowBooleans);

308

309

310 for (int I = 0, E = GuardBlocks.size(); I != E; ++I)

312

314

315 if (DTU) {

316 int NumGuards = GuardBlocks.size();

317

318 for (auto [BB, Succ0, Succ1] : Branches)

320

321 for (int I = 0; I != NumGuards - 1; ++I) {

325 }

326

327

329 Outgoing[NumGuards - 1]});

331 Outgoing[NumGuards]});

333 }

334

335 for (auto I : DeletionCandidates) {

336 if (I->use_empty())

337 if (auto *Inst = dyn_cast_or_null(I))

338 Inst->eraseFromParent();

339 }

340

341 return FirstGuardBlock;

342}

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

static void calcPredicateUsingBooleans(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates)

static void setupBranchForGuard(ArrayRef< BasicBlock * > GuardBlocks, ArrayRef< BasicBlock * > Outgoing, BBPredicates &GuardPredicates)

static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, ArrayRef< EdgeDescriptor > Incoming, BasicBlock *FirstGuardBlock)

static void calcPredicateUsingInteger(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, ArrayRef< BasicBlock * > GuardBlocks, BBPredicates &GuardPredicates)

static Value * redirectToHub(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1, BasicBlock *FirstGuardBlock)

static void convertToGuardPredicates(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans)

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

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallSet class.

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

const T & front() const

front - Get the first element.

size_t size() const

size - Get the array size.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

static ConstantInt * getTrue(LLVMContext &Context)

static ConstantInt * getFalse(LLVMContext &Context)

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

This is an important class for using LLVM in a threaded context.

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.

static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)

A vector that has set insertion semantics.

ArrayRef< value_type > getArrayRef() const

size_type size() const

Determine the number of elements in the SetVector.

const value_type & front() const

Return the first element of the SetVector.

const value_type & back() const

Return the last element of the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

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 IntegerType * getInt1Ty(LLVMContext &C)

static IntegerType * getInt32Ty(LLVMContext &C)

LLVM Value Representation.

StringRef getName() const

Return a constant reference to the value's name.

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

raw_ostream & dbgs()

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

Value * invertCondition(Value *Condition)

Invert the given true/false value, possibly reusing an existing copy.

BasicBlock * finalize(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)

SmallVector< BranchDescriptor > Branches

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...