ControlFlowUtils.cpp Source File (original) (raw)

22#define DEBUG_TYPE "control-flow-hub"

24using namespace llvm;

38 "Only support branch terminator.");

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");

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) {

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();

243 auto *NewPhi =

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

246 bool AllUndef = true;

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

249 if (Phi->getBasicBlockIndex(BB) != -1) {

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

251 if (BB == Out) {

252 V = NewPhi;

253 }

255 }

256

257 NewPhi->addIncoming(V, BB);

258 }

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

260 Value *NewV = NewPhi;

261 if (AllUndef) {

262 NewPhi->eraseFromParent();

264 }

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

266 Phi->replaceAllUsesWith(NewV);

267 I = Phi->eraseFromParent();

268 continue;

269 }

270 Phi->addIncoming(NewV, GuardBlock);

271 ++I;

272 }

273}

274

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

278#ifndef NDEBUG

280#endif

282

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

284#ifndef NDEBUG

287 "Duplicate entry for incoming block.");

288#endif

289 if (Succ0)

290 Outgoing.insert(Succ0);

291 if (Succ1)

292 Outgoing.insert(Succ1);

293 }

294

295 if (Outgoing.size() < 2)

296 return {Outgoing.front(), false};

297

299 if (DTU) {

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

301 if (Succ0)

303 if (Succ1)

305 }

306 }

307

310 DeletionCandidates, Prefix, MaxControlFlowBooleans);

312

313

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

316

318

319 if (DTU) {

320 int NumGuards = GuardBlocks.size();

321

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

324

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

329 }

330

331

333 Outgoing[NumGuards - 1]});

335 Outgoing[NumGuards]});

337 }

338

339 for (auto I : DeletionCandidates) {

340 if (I->use_empty())

342 Inst->eraseFromParent();

343 }

344

345 return {FirstGuardBlock, true};

346}

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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)

Definition ControlFlowUtils.cpp:131

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

Definition ControlFlowUtils.cpp:68

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

Definition ControlFlowUtils.cpp:237

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

Definition ControlFlowUtils.cpp:86

DenseMap< BasicBlock *, Instruction * > BBPredicates

Definition ControlFlowUtils.cpp:26

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

Definition ControlFlowUtils.cpp:35

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

Definition ControlFlowUtils.cpp:202

ControlFlowHub::BranchDescriptor EdgeDescriptor

Definition ControlFlowUtils.cpp:27

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

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 LLVM_ABI CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Construct a compare instruction, given the opcode, the predicate and the two operands.

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

static LLVM_ABI 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 LLVM_ABI 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, const 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.

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

static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)

LLVM Value Representation.

LLVM_ABI 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.

FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

decltype(auto) cast(const From &Val)

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

LLVM_ABI Value * invertCondition(Value *Condition)

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

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

Return the unified loop exit block and a flag indicating if the CFG was changed at all.

Definition ControlFlowUtils.cpp:275

SmallVector< BranchDescriptor > Branches

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