/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp

Bug Summary

File:	lib/Transforms/Scalar/LoopUnswitch.cpp
Location:	line 1109, column 18
Description:	Called C++ object pointer is null

Annotated Source Code

//===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//

// The LLVM Compiler Infrastructure

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//===----------------------------------------------------------------------===//

// This pass transforms loops that contain branches on loop-invariant conditions

// to have multiple loops. For example, it turns the left into the right code:

// for (...) if (lic)

// A for (...)

// if (lic) A; B; C

// B else

// C for (...)

// A; C

// This can increase the size of the code exponentially (doubling it every time

// a loop is unswitched) so we only unswitch if the resultant code will be

// smaller than a threshold.

// This pass expects LICM to be run before it to hoist invariant conditions out

// of the loop, to make the unswitching opportunity obvious.

//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/Analysis/AssumptionCache.h"

#include "llvm/Analysis/CodeMetrics.h"

#include "llvm/Analysis/InstructionSimplify.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/LoopPass.h"

#include "llvm/Analysis/ScalarEvolution.h"

#include "llvm/Analysis/TargetTransformInfo.h"

#include "llvm/IR/Constants.h"

#include "llvm/IR/DerivedTypes.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/Module.h"

#include "llvm/IR/MDBuilder.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/raw_ostream.h"

#include "llvm/Transforms/Utils/BasicBlockUtils.h"

#include "llvm/Transforms/Utils/Cloning.h"

#include "llvm/Transforms/Utils/Local.h"

#include <algorithm>

#include <map>

#include <set>

using namespace llvm;

#define DEBUG_TYPE"loop-unswitch" "loop-unswitch"

STATISTIC(NumBranches, "Number of branches unswitched")static llvm::Statistic NumBranches = { "loop-unswitch", "Number of branches unswitched"
, 0, 0 };

STATISTIC(NumSwitches, "Number of switches unswitched")static llvm::Statistic NumSwitches = { "loop-unswitch", "Number of switches unswitched"
, 0, 0 };

STATISTIC(NumSelects , "Number of selects unswitched")static llvm::Statistic NumSelects = { "loop-unswitch", "Number of selects unswitched"
, 0, 0 };

STATISTIC(NumTrivial , "Number of unswitches that are trivial")static llvm::Statistic NumTrivial = { "loop-unswitch", "Number of unswitches that are trivial"
, 0, 0 };

STATISTIC(NumSimplify, "Number of simplifications of unswitched code")static llvm::Statistic NumSimplify = { "loop-unswitch", "Number of simplifications of unswitched code"
, 0, 0 };

STATISTIC(TotalInsts, "Total number of instructions analyzed")static llvm::Statistic TotalInsts = { "loop-unswitch", "Total number of instructions analyzed"
, 0, 0 };

// The specific value of 100 here was chosen based only on intuition and a

// few specific examples.

static cl::opt<unsigned>

Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),

cl::init(100), cl::Hidden);

namespace {

class LUAnalysisCache {

typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >

UnswitchedValsMap;

typedef UnswitchedValsMap::iterator UnswitchedValsIt;

struct LoopProperties {

unsigned CanBeUnswitchedCount;

unsigned WasUnswitchedCount;

unsigned SizeEstimation;

UnswitchedValsMap UnswitchedVals;

};

// Here we use std::map instead of DenseMap, since we need to keep valid

// LoopProperties pointer for current loop for better performance.

typedef std::map<const Loop*, LoopProperties> LoopPropsMap;

typedef LoopPropsMap::iterator LoopPropsMapIt;

LoopPropsMap LoopsProperties;

UnswitchedValsMap *CurLoopInstructions;

LoopProperties *CurrentLoopProperties;

// A loop unswitching with an estimated cost above this threshold

// is not performed. MaxSize is turned into unswitching quota for

100

// the current loop, and reduced correspondingly, though note that

101

// the quota is returned by releaseMemory() when the loop has been

102

// processed, so that MaxSize will return to its previous

103

// value. So in most cases MaxSize will equal the Threshold flag

104

// when a new loop is processed. An exception to that is that

105

// MaxSize will have a smaller value while processing nested loops

106

// that were introduced due to loop unswitching of an outer loop.

107

108

// FIXME: The way that MaxSize works is subtle and depends on the

109

// pass manager processing loops and calling releaseMemory() in a

110

// specific order. It would be good to find a more straightforward

111

// way of doing what MaxSize does.

112

unsigned MaxSize;

113

114

public:

115

LUAnalysisCache()

116

: CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),

117

MaxSize(Threshold) {}

118

119

// Analyze loop. Check its size, calculate is it possible to unswitch

120

// it. Returns true if we can unswitch this loop.

121

bool countLoop(const Loop *L, const TargetTransformInfo &TTI,

122

AssumptionCache *AC);

123

124

// Clean all data related to given loop.

125

void forgetLoop(const Loop *L);

126

127

// Mark case value as unswitched.

128

// Since SI instruction can be partly unswitched, in order to avoid

129

// extra unswitching in cloned loops keep track all unswitched values.

130

void setUnswitched(const SwitchInst *SI, const Value *V);

131

132

// Check was this case value unswitched before or not.

133

bool isUnswitched(const SwitchInst *SI, const Value *V);

134

135

// Returns true if another unswitching could be done within the cost

136

// threshold.

137

bool CostAllowsUnswitching();

138

139

// Clone all loop-unswitch related loop properties.

140

// Redistribute unswitching quotas.

141

// Note, that new loop data is stored inside the VMap.

142

void cloneData(const Loop *NewLoop, const Loop *OldLoop,

143

const ValueToValueMapTy &VMap);

144

};

145

146

class LoopUnswitch : public LoopPass {

147

LoopInfo *LI; // Loop information

148

LPPassManager *LPM;

149

AssumptionCache *AC;

150

151

// LoopProcessWorklist - Used to check if second loop needs processing

152

// after RewriteLoopBodyWithConditionConstant rewrites first loop.

153

std::vector<Loop*> LoopProcessWorklist;

154

155

LUAnalysisCache BranchesInfo;

156

157

bool OptimizeForSize;

158

bool redoLoop;

159

160

Loop *currentLoop;

161

DominatorTree *DT;

162

BasicBlock *loopHeader;

163

BasicBlock *loopPreheader;

164

165

// LoopBlocks contains all of the basic blocks of the loop, including the

166

// preheader of the loop, the body of the loop, and the exit blocks of the

167

// loop, in that order.

168

std::vector<BasicBlock*> LoopBlocks;

169

// NewBlocks contained cloned copy of basic blocks from LoopBlocks.

170

std::vector<BasicBlock*> NewBlocks;

171

172

public:

173

static char ID; // Pass ID, replacement for typeid

174

explicit LoopUnswitch(bool Os = false) :

175

LoopPass(ID), OptimizeForSize(Os), redoLoop(false),

176

currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),

177

loopPreheader(nullptr) {

178

initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());

179

}

180

181

bool runOnLoop(Loop *L, LPPassManager &LPM) override;

182

bool processCurrentLoop();

183

184

/// This transformation requires natural loop information & requires that

185

/// loop preheaders be inserted into the CFG.

186

///

187

void getAnalysisUsage(AnalysisUsage &AU) const override {

188

AU.addRequired<AssumptionCacheTracker>();

189

AU.addRequiredID(LoopSimplifyID);

190

AU.addPreservedID(LoopSimplifyID);

191

AU.addRequired<LoopInfoWrapperPass>();

192

AU.addPreserved<LoopInfoWrapperPass>();

193

AU.addRequiredID(LCSSAID);

194

AU.addPreservedID(LCSSAID);

195

AU.addPreserved<DominatorTreeWrapperPass>();

196

AU.addPreserved<ScalarEvolution>();

197

AU.addRequired<TargetTransformInfoWrapperPass>();

198

}

199

200

private:

201

202

void releaseMemory() override {

203

BranchesInfo.forgetLoop(currentLoop);

204

}

205

206

void initLoopData() {

207

loopHeader = currentLoop->getHeader();

208

loopPreheader = currentLoop->getLoopPreheader();

209

}

210

211

/// Split all of the edges from inside the loop to their exit blocks.

212

/// Update the appropriate Phi nodes as we do so.

213

void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks);

214

215

bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,

216

TerminatorInst *TI = nullptr);

217

void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,

218

BasicBlock *ExitBlock, TerminatorInst *TI);

219

void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,

220

TerminatorInst *TI);

221

222

void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,

223

Constant *Val, bool isEqual);

224

225

void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,

226

BasicBlock *TrueDest,

227

BasicBlock *FalseDest,

228

Instruction *InsertPt,

229

TerminatorInst *TI);

230

231

void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);

232

bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = nullptr,

233

BasicBlock **LoopExit = nullptr);

234

235

};

236

}

237

238

// Analyze loop. Check its size, calculate is it possible to unswitch

239

// it. Returns true if we can unswitch this loop.

240

bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,

241

AssumptionCache *AC) {

242

243

LoopPropsMapIt PropsIt;

244

bool Inserted;

245

std::tie(PropsIt, Inserted) =

246

LoopsProperties.insert(std::make_pair(L, LoopProperties()));

247

248

LoopProperties &Props = PropsIt->second;

249

250

if (Inserted) {

251

// New loop.

252

253

// Limit the number of instructions to avoid causing significant code

254

// expansion, and the number of basic blocks, to avoid loops with

255

// large numbers of branches which cause loop unswitching to go crazy.

256

// This is a very ad-hoc heuristic.

257

258

SmallPtrSet<const Value *, 32> EphValues;

259

CodeMetrics::collectEphemeralValues(L, AC, EphValues);

260

261

// FIXME: This is overly conservative because it does not take into

262

// consideration code simplification opportunities and code that can

263

// be shared by the resultant unswitched loops.

264

CodeMetrics Metrics;

265

for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;

266

++I)

267

Metrics.analyzeBasicBlock(*I, TTI, EphValues);

268

269

Props.SizeEstimation = Metrics.NumInsts;

270

Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);

271

Props.WasUnswitchedCount = 0;

272

MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;

273

274

if (Metrics.notDuplicatable) {

275

DEBUG(dbgs() << "NOT unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< L->getHeader()->getName() << ", contents cannot be "
<< "duplicated!\n"; } } while (0)

276

<< L->getHeader()->getName() << ", contents cannot be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< L->getHeader()->getName() << ", contents cannot be "
<< "duplicated!\n"; } } while (0)

277

<< "duplicated!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< L->getHeader()->getName() << ", contents cannot be "
<< "duplicated!\n"; } } while (0);

278

return false;

279

}

280

}

281

282

// Be careful. This links are good only before new loop addition.

283

CurrentLoopProperties = &Props;

284

CurLoopInstructions = &Props.UnswitchedVals;

285

286

return true;

287

}

288

289

// Clean all data related to given loop.

290

void LUAnalysisCache::forgetLoop(const Loop *L) {

291

292

LoopPropsMapIt LIt = LoopsProperties.find(L);

293

294

if (LIt != LoopsProperties.end()) {

295

LoopProperties &Props = LIt->second;

296

MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *

297

Props.SizeEstimation;

298

LoopsProperties.erase(LIt);

299

}

300

301

CurrentLoopProperties = nullptr;

302

CurLoopInstructions = nullptr;

303

}

304

305

// Mark case value as unswitched.

306

// Since SI instruction can be partly unswitched, in order to avoid

307

// extra unswitching in cloned loops keep track all unswitched values.

308

void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {

309

(*CurLoopInstructions)[SI].insert(V);

310

}

311

312

// Check was this case value unswitched before or not.

313

bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {

314

return (*CurLoopInstructions)[SI].count(V);

315

}

316

317

bool LUAnalysisCache::CostAllowsUnswitching() {

318

return CurrentLoopProperties->CanBeUnswitchedCount > 0;

319

}

320

321

// Clone all loop-unswitch related loop properties.

322

// Redistribute unswitching quotas.

323

// Note, that new loop data is stored inside the VMap.

324

void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,

325

const ValueToValueMapTy &VMap) {

326

327

LoopProperties &NewLoopProps = LoopsProperties[NewLoop];

328

LoopProperties &OldLoopProps = *CurrentLoopProperties;

329

UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;

330

331

// Reallocate "can-be-unswitched quota"

332

333

--OldLoopProps.CanBeUnswitchedCount;

334

++OldLoopProps.WasUnswitchedCount;

335

NewLoopProps.WasUnswitchedCount = 0;

336

unsigned Quota = OldLoopProps.CanBeUnswitchedCount;

337

NewLoopProps.CanBeUnswitchedCount = Quota / 2;

338

OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;

339

340

NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;

341

342

// Clone unswitched values info:

343

// for new loop switches we clone info about values that was

344

// already unswitched and has redundant successors.

345

for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {

346

const SwitchInst *OldInst = I->first;

347

Value *NewI = VMap.lookup(OldInst);

348

const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);

349

assert(NewInst && "All instructions that are in SrcBB must be in VMap.")((NewInst && "All instructions that are in SrcBB must be in VMap."
) ? static_cast<void> (0) : __assert_fail ("NewInst && \"All instructions that are in SrcBB must be in VMap.\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 349, __PRETTY_FUNCTION__));

350

351

NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];

352

}

353

}

354

355

char LoopUnswitch::ID = 0;

356

INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",static void* initializeLoopUnswitchPassOnce(PassRegistry &
Registry) {

357

false, false)static void* initializeLoopUnswitchPassOnce(PassRegistry &
Registry) {

358

INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);

359

INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);

360

INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry);

361

INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);

362

INITIALIZE_PASS_DEPENDENCY(LCSSA)initializeLCSSAPass(Registry);

363

INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",PassInfo *PI = new PassInfo("Unswitch loops", "loop-unswitch"
, & LoopUnswitch ::ID, PassInfo::NormalCtor_t(callDefaultCtor
< LoopUnswitch >), false, false); Registry.registerPass
(*PI, true); return PI; } void llvm::initializeLoopUnswitchPass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopUnswitchPassOnce(Registry
); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364, &initialized); initialized = 2; AnnotateIgnoreWritesEnd
("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364); } else { sys::cas_flag tmp = initialized; sys::MemoryFence
(); while (tmp != 2) { tmp = initialized; sys::MemoryFence();
} } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364, &initialized); }

364

false, false)PassInfo *PI = new PassInfo("Unswitch loops", "loop-unswitch"
, & LoopUnswitch ::ID, PassInfo::NormalCtor_t(callDefaultCtor
< LoopUnswitch >), false, false); Registry.registerPass
(*PI, true); return PI; } void llvm::initializeLoopUnswitchPass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopUnswitchPassOnce(Registry
); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364, &initialized); initialized = 2; AnnotateIgnoreWritesEnd
("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364); } else { sys::cas_flag tmp = initialized; sys::MemoryFence
(); while (tmp != 2) { tmp = initialized; sys::MemoryFence();
} } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 364, &initialized); }

365

366

Pass *llvm::createLoopUnswitchPass(bool Os) {

367

return new LoopUnswitch(Os);

368

}

369

370

/// FindLIVLoopCondition - Cond is a condition that occurs in L. If it is

371

/// invariant in the loop, or has an invariant piece, return the invariant.

372

/// Otherwise, return null.

373

static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {

374

375

// We started analyze new instruction, increment scanned instructions counter.

376

++TotalInsts;

377

378

// We can never unswitch on vector conditions.

379

if (Cond->getType()->isVectorTy())

380

return nullptr;

381

382

// Constants should be folded, not unswitched on!

383

if (isa<Constant>(Cond)) return nullptr;

384

385

// TODO: Handle: br (VARIANT|INVARIANT).

386

387

// Hoist simple values out.

388

if (L->makeLoopInvariant(Cond, Changed))

389

return Cond;

390

391

if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))

392

if (BO->getOpcode() == Instruction::And ||

393

BO->getOpcode() == Instruction::Or) {

394

// If either the left or right side is invariant, we can unswitch on this,

395

// which will cause the branch to go away in one loop and the condition to

396

// simplify in the other one.

397

if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))

398

return LHS;

399

if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))

400

return RHS;

401

}

402

403

return nullptr;

404

}

405

406

bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {

407

if (skipOptnoneFunction(L))

Taking false branch

→

408

return false;

409

410

AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(

411

*L->getHeader()->getParent());

412

LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

413

LPM = &LPM_Ref;

414

DominatorTreeWrapperPass *DTWP =

415

getAnalysisIfAvailable<DominatorTreeWrapperPass>();

416

DT = DTWP ? &DTWP->getDomTree() : nullptr;

←

Assuming 'DTWP' is non-null

→

←

'?' condition is true

→

417

currentLoop = L;

418

Function *F = currentLoop->getHeader()->getParent();

419

bool Changed = false;

420

do {

←

Loop condition is true. Execution continues on line 421

→

←

Loop condition is true. Execution continues on line 421

→

←

Loop condition is true. Execution continues on line 421

→

421

assert(currentLoop->isLCSSAForm(*DT))((currentLoop->isLCSSAForm(*DT)) ? static_cast<void>
(0) : __assert_fail ("currentLoop->isLCSSAForm(*DT)", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 421, __PRETTY_FUNCTION__));

422

redoLoop = false;

423

Changed |= processCurrentLoop();

←

Calling 'LoopUnswitch::processCurrentLoop'

→

424

} while(redoLoop);

425

426

if (Changed) {

427

// FIXME: Reconstruct dom info, because it is not preserved properly.

428

if (DT)

429

DT->recalculate(*F);

430

}

431

return Changed;

432

}

433

434

/// processCurrentLoop - Do actual work and unswitch loop if possible

435

/// and profitable.

436

bool LoopUnswitch::processCurrentLoop() {

437

bool Changed = false;

438

439

initLoopData();

440

441

// If LoopSimplify was unable to form a preheader, don't do any unswitching.

442

if (!loopPreheader)

←

Taking false branch

→

443

return false;

444

445

// Loops with indirectbr cannot be cloned.

446

if (!currentLoop->isSafeToClone())

←

Taking false branch

→

447

return false;

448

449

// Without dedicated exits, splitting the exit edge may fail.

450

if (!currentLoop->hasDedicatedExits())

←

Taking false branch

→

451

return false;

452

453

LLVMContext &Context = loopHeader->getContext();

454

455

// Probably we reach the quota of branches for this loop. If so

456

// stop unswitching.

457

if (!BranchesInfo.countLoop(

←

Taking false branch

→

458

currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(

459

*currentLoop->getHeader()->getParent()),

460

AC))

461

return false;

462

463

// Loop over all of the basic blocks in the loop. If we find an interior

464

// block that is branching on a loop-invariant condition, we can unswitch this

465

// loop.

466

for (Loop::block_iterator I = currentLoop->block_begin(),

←

Loop condition is true. Entering loop body

→

467

E = currentLoop->block_end(); I != E; ++I) {

468

TerminatorInst *TI = (*I)->getTerminator();

469

if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {

←

Taking false branch

→

470

// If this isn't branching on an invariant condition, we can't unswitch

471

// it.

472

if (BI->isConditional()) {

473

// See if this, or some part of it, is loop invariant. If so, we can

474

// unswitch on it if we desire.

475

Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),

476

currentLoop, Changed);

477

if (LoopCond &&

478

UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {

479

++NumBranches;

480

return true;

481

}

482

}

483

} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {

←

Taking false branch

→

484

Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),

485

currentLoop, Changed);

486

unsigned NumCases = SI->getNumCases();

487

if (LoopCond && NumCases) {

488

// Find a value to unswitch on:

489

// FIXME: this should chose the most expensive case!

490

// FIXME: scan for a case with a non-critical edge?

491

Constant *UnswitchVal = nullptr;

492

493

// Do not process same value again and again.

494

// At this point we have some cases already unswitched and

495

// some not yet unswitched. Let's find the first not yet unswitched one.

496

for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();

497

i != e; ++i) {

498

Constant *UnswitchValCandidate = i.getCaseValue();

499

if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {

500

UnswitchVal = UnswitchValCandidate;

501

break;

502

}

503

}

504

505

if (!UnswitchVal)

506

continue;

507

508

if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {

509

++NumSwitches;

510

return true;

511

}

512

}

513

}

514

515

// Scan the instructions to check for unswitchable values.

516

for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();

←

Loop condition is true. Entering loop body

→

←

Loop condition is true. Entering loop body

→

←

Loop condition is true. Entering loop body

→

←

Loop condition is true. Entering loop body

→

517

BBI != E; ++BBI)

518

if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {

Taking false branch

Taking false branch

Taking false branch

Assuming 'SI' is non-null

→

←

Taking true branch

→

519

Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),

520

currentLoop, Changed);

521

if (LoopCond && UnswitchIfProfitable(LoopCond,

←

Calling 'LoopUnswitch::UnswitchIfProfitable'

→

522

ConstantInt::getTrue(Context))) {

523

++NumSelects;

524

return true;

525

}

526

}

527

}

528

return Changed;

529

}

530

531

/// isTrivialLoopExitBlock - Check to see if all paths from BB exit the

532

/// loop with no side effects (including infinite loops).

533

///

534

/// If true, we return true and set ExitBB to the block we

535

/// exit through.

536

///

537

static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,

538

BasicBlock *&ExitBB,

539

std::set<BasicBlock*> &Visited) {

540

if (!Visited.insert(BB).second) {

541

// Already visited. Without more analysis, this could indicate an infinite

542

// loop.

543

return false;

544

}

545

if (!L->contains(BB)) {

546

// Otherwise, this is a loop exit, this is fine so long as this is the

547

// first exit.

548

if (ExitBB) return false;

549

ExitBB = BB;

550

return true;

551

}

552

553

// Otherwise, this is an unvisited intra-loop node. Check all successors.

554

for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {

555

// Check to see if the successor is a trivial loop exit.

556

if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))

557

return false;

558

}

559

560

// Okay, everything after this looks good, check to make sure that this block

561

// doesn't include any side effects.

562

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)

563

if (I->mayHaveSideEffects())

564

return false;

565

566

return true;

567

}

568

569

/// isTrivialLoopExitBlock - Return true if the specified block unconditionally

570

/// leads to an exit from the specified loop, and has no side-effects in the

571

/// process. If so, return the block that is exited to, otherwise return null.

572

static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {

573

std::set<BasicBlock*> Visited;

574

Visited.insert(L->getHeader()); // Branches to header make infinite loops.

575

BasicBlock *ExitBB = nullptr;

576

if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))

577

return ExitBB;

578

return nullptr;

579

}

580

581

/// IsTrivialUnswitchCondition - Check to see if this unswitch condition is

582

/// trivial: that is, that the condition controls whether or not the loop does

583

/// anything at all. If this is a trivial condition, unswitching produces no

584

/// code duplications (equivalently, it produces a simpler loop and a new empty

585

/// loop, which gets deleted).

586

///

587

/// If this is a trivial condition, return true, otherwise return false. When

588

/// returning true, this sets Cond and Val to the condition that controls the

589

/// trivial condition: when Cond dynamically equals Val, the loop is known to

590

/// exit. Finally, this sets LoopExit to the BB that the loop exits to when

591

/// Cond == Val.

592

///

593

bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val,

594

BasicBlock **LoopExit) {

595

BasicBlock *Header = currentLoop->getHeader();

596

TerminatorInst *HeaderTerm = Header->getTerminator();

597

LLVMContext &Context = Header->getContext();

598

599

BasicBlock *LoopExitBB = nullptr;

600

if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) {

601

// If the header block doesn't end with a conditional branch on Cond, we

602

// can't handle it.

603

if (!BI->isConditional() || BI->getCondition() != Cond)

604

return false;

605

606

// Check to see if a successor of the branch is guaranteed to

607

// exit through a unique exit block without having any

608

// side-effects. If so, determine the value of Cond that causes it to do

609

// this.

610

if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,

611

BI->getSuccessor(0)))) {

612

if (Val) *Val = ConstantInt::getTrue(Context);

613

} else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,

614

BI->getSuccessor(1)))) {

615

if (Val) *Val = ConstantInt::getFalse(Context);

616

}

617

} else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) {

618

// If this isn't a switch on Cond, we can't handle it.

619

if (SI->getCondition() != Cond) return false;

620

621

// Check to see if a successor of the switch is guaranteed to go to the

622

// latch block or exit through a one exit block without having any

623

// side-effects. If so, determine the value of Cond that causes it to do

624

// this.

625

// Note that we can't trivially unswitch on the default case or

626

// on already unswitched cases.

627

for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();

628

i != e; ++i) {

629

BasicBlock *LoopExitCandidate;

630

if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop,

631

i.getCaseSuccessor()))) {

632

// Okay, we found a trivial case, remember the value that is trivial.

633

ConstantInt *CaseVal = i.getCaseValue();

634

635

// Check that it was not unswitched before, since already unswitched

636

// trivial vals are looks trivial too.

637

if (BranchesInfo.isUnswitched(SI, CaseVal))

638

continue;

639

LoopExitBB = LoopExitCandidate;

640

if (Val) *Val = CaseVal;

641

break;

642

}

643

}

644

}

645

646

// If we didn't find a single unique LoopExit block, or if the loop exit block

647

// contains phi nodes, this isn't trivial.

648

if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))

649

return false; // Can't handle this.

650

651

if (LoopExit) *LoopExit = LoopExitBB;

652

653

// We already know that nothing uses any scalar values defined inside of this

654

// loop. As such, we just have to check to see if this loop will execute any

655

// side-effecting instructions (e.g. stores, calls, volatile loads) in the

656

// part of the loop that the code *would* execute. We already checked the

657

// tail, check the header now.

658

for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)

659

if (I->mayHaveSideEffects())

660

return false;

661

return true;

662

}

663

664

/// UnswitchIfProfitable - We have found that we can unswitch currentLoop when

665

/// LoopCond == Val to simplify the loop. If we decide that this is profitable,

666

/// unswitch the loop, reprocess the pieces, then return true.

667

bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,

668

TerminatorInst *TI) {

669

Function *F = loopHeader->getParent();

670

Constant *CondVal = nullptr;

671

BasicBlock *ExitBlock = nullptr;

672

673

if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {

←

Value assigned to field 'DT'

→

←

Taking true branch

→

674

// If the condition is trivial, always unswitch. There is no code growth

675

// for this case.

676

UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock, TI);

←

Calling 'LoopUnswitch::UnswitchTrivialCondition'

→

677

return true;

678

}

679

680

// Check to see if it would be profitable to unswitch current loop.

681

if (!BranchesInfo.CostAllowsUnswitching()) {

682

DEBUG(dbgs() << "NOT unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName() << " at non-trivial condition '"
<< *Val << "' == " << *LoopCond << "\n"
<< ". Cost too high.\n"; } } while (0)

683

<< currentLoop->getHeader()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName() << " at non-trivial condition '"
<< *Val << "' == " << *LoopCond << "\n"
<< ". Cost too high.\n"; } } while (0)

684

<< " at non-trivial condition '" << *Valdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName() << " at non-trivial condition '"
<< *Val << "' == " << *LoopCond << "\n"
<< ". Cost too high.\n"; } } while (0)

685

<< "' == " << *LoopCond << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName() << " at non-trivial condition '"
<< *Val << "' == " << *LoopCond << "\n"
<< ". Cost too high.\n"; } } while (0)

686

<< ". Cost too high.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName() << " at non-trivial condition '"
<< *Val << "' == " << *LoopCond << "\n"
<< ". Cost too high.\n"; } } while (0);

687

return false;

688

}

689

690

// Do not do non-trivial unswitch while optimizing for size.

691

if (OptimizeForSize || F->hasFnAttribute(Attribute::OptimizeForSize))

692

return false;

693

694

UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI);

695

return true;

696

}

697

698

/// CloneLoop - Recursively clone the specified loop and all of its children,

699

/// mapping the blocks with the specified map.

700

static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,

701

LoopInfo *LI, LPPassManager *LPM) {

702

Loop *New = new Loop();

703

LPM->insertLoop(New, PL);

704

705

// Add all of the blocks in L to the new loop.

706

for (Loop::block_iterator I = L->block_begin(), E = L->block_end();

707

I != E; ++I)

708

if (LI->getLoopFor(*I) == L)

709

New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);

710

711

// Add all of the subloops to the new loop.

712

for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)

713

CloneLoop(*I, New, VM, LI, LPM);

714

715

return New;

716

}

717

718

static void copyMetadata(Instruction *DstInst, const Instruction *SrcInst,

719

bool Swapped) {

720

if (!SrcInst || !SrcInst->hasMetadata())

721

return;

722

723

SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;

724

SrcInst->getAllMetadata(MDs);

725

for (auto &MD : MDs) {

726

switch (MD.first) {

727

default:

728

break;

729

case LLVMContext::MD_prof:

730

if (Swapped && MD.second->getNumOperands() == 3 &&

731

isa<MDString>(MD.second->getOperand(0))) {

732

MDString *MDName = cast<MDString>(MD.second->getOperand(0));

733

if (MDName->getString() == "branch_weights") {

734

auto *ValT = cast_or_null<ConstantAsMetadata>(

735

MD.second->getOperand(1))->getValue();

736

auto *ValF = cast_or_null<ConstantAsMetadata>(

737

MD.second->getOperand(2))->getValue();

738

assert(ValT && ValF && "Invalid Operands of branch_weights")((ValT && ValF && "Invalid Operands of branch_weights"
) ? static_cast<void> (0) : __assert_fail ("ValT && ValF && \"Invalid Operands of branch_weights\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 738, __PRETTY_FUNCTION__));

739

auto NewMD =

740

MDBuilder(DstInst->getParent()->getContext())

741

.createBranchWeights(cast<ConstantInt>(ValF)->getZExtValue(),

742

cast<ConstantInt>(ValT)->getZExtValue());

743

MD.second = NewMD;

744

}

745

}

746

// fallthrough.

747

case LLVMContext::MD_dbg:

748

DstInst->setMetadata(MD.first, MD.second);

749

}

750

}

751

}

752

753

/// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values

754

/// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the

755

/// code immediately before InsertPt.

756

void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,

757

BasicBlock *TrueDest,

758

BasicBlock *FalseDest,

759

Instruction *InsertPt,

760

TerminatorInst *TI) {

761

// Insert a conditional branch on LIC to the two preheaders. The original

762

// code is the true version and the new code is the false version.

763

Value *BranchVal = LIC;

764

bool Swapped = false;

765

if (!isa<ConstantInt>(Val) ||

766

Val->getType() != Type::getInt1Ty(LIC->getContext()))

767

BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val);

768

else if (Val != ConstantInt::getTrue(Val->getContext())) {

769

// We want to enter the new loop when the condition is true.

770

std::swap(TrueDest, FalseDest);

771

Swapped = true;

772

}

773

774

// Insert the new branch.

775

BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);

776

copyMetadata(BI, TI, Swapped);

777

778

// If either edge is critical, split it. This helps preserve LoopSimplify

779

// form for enclosing loops.

780

auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();

781

SplitCriticalEdge(BI, 0, Options);

782

SplitCriticalEdge(BI, 1, Options);

783

}

784

785

/// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable

786

/// condition in it (a cond branch from its header block to its latch block,

787

/// where the path through the loop that doesn't execute its body has no

788

/// side-effects), unswitch it. This doesn't involve any code duplication, just

789

/// moving the conditional branch outside of the loop and updating loop info.

790

void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,

791

BasicBlock *ExitBlock,

792

TerminatorInst *TI) {

793

DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << L
->getHeader()->getParent()->getName() << " on cond: "
<< *Val << " == " << *Cond << "\n"; }
} while (0)

794

<< loopHeader->getName() << " [" << L->getBlocks().size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << L
->getHeader()->getParent()->getName() << " on cond: "
<< *Val << " == " << *Cond << "\n"; }
} while (0)

795

<< " blocks] in Function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << L
->getHeader()->getParent()->getName() << " on cond: "
<< *Val << " == " << *Cond << "\n"; }
} while (0)

796

<< L->getHeader()->getParent()->getName() << " on cond: " << *Valdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << L
->getHeader()->getParent()->getName() << " on cond: "
<< *Val << " == " << *Cond << "\n"; }
} while (0)

797

<< " == " << *Cond << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << L
->getHeader()->getParent()->getName() << " on cond: "
<< *Val << " == " << *Cond << "\n"; }
} while (0);

798

799

// First step, split the preheader, so that we know that there is a safe place

800

// to insert the conditional branch. We will change loopPreheader to have a

801

// conditional branch on Cond.

802

BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);

803

804

// Now that we have a place to insert the conditional branch, create a place

805

// to branch to: this is the exit block out of the loop that we should

806

// short-circuit to.

807

808

// Split this block now, so that the loop maintains its exit block, and so

809

// that the jump from the preheader can execute the contents of the exit block

810

// without actually branching to it (the exit block should be dominated by the

811

// loop header, not the preheader).

812

assert(!L->contains(ExitBlock) && "Exit block is in the loop?")((!L->contains(ExitBlock) && "Exit block is in the loop?"
) ? static_cast<void> (0) : __assert_fail ("!L->contains(ExitBlock) && \"Exit block is in the loop?\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 812, __PRETTY_FUNCTION__));

813

BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), DT, LI);

814

815

// Okay, now we have a position to branch from and a position to branch to,

816

// insert the new conditional branch.

817

EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,

818

loopPreheader->getTerminator(), TI);

819

LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);

820

loopPreheader->getTerminator()->eraseFromParent();

821

822

// We need to reprocess this loop, it could be unswitched again.

823

redoLoop = true;

824

825

// Now that we know that the loop is never entered when this condition is a

826

// particular value, rewrite the loop with this info. We know that this will

827

// at least eliminate the old branch.

828

RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);

←

Calling 'LoopUnswitch::RewriteLoopBodyWithConditionConstant'

→

829

++NumTrivial;

830

}

831

832

/// SplitExitEdges - Split all of the edges from inside the loop to their exit

833

/// blocks. Update the appropriate Phi nodes as we do so.

834

void LoopUnswitch::SplitExitEdges(Loop *L,

835

const SmallVectorImpl<BasicBlock *> &ExitBlocks){

836

837

for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {

838

BasicBlock *ExitBlock = ExitBlocks[i];

839

SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),

840

pred_end(ExitBlock));

841

842

// Although SplitBlockPredecessors doesn't preserve loop-simplify in

843

// general, if we call it on all predecessors of all exits then it does.

844

SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa",

845

/*AliasAnalysis*/ nullptr, DT, LI,

846

/*PreserveLCSSA*/ true);

847

}

848

}

849

850

/// UnswitchNontrivialCondition - We determined that the loop is profitable

851

/// to unswitch when LIC equal Val. Split it into loop versions and test the

852

/// condition outside of either loop. Return the loops created as Out1/Out2.

853

void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,

854

Loop *L, TerminatorInst *TI) {

855

Function *F = loopHeader->getParent();

856

DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << F
->getName() << " when '" << *Val << "' == "
<< *LIC << "\n"; } } while (0)

857

<< loopHeader->getName() << " [" << L->getBlocks().size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << F
->getName() << " when '" << *Val << "' == "
<< *LIC << "\n"; } } while (0)

858

<< " blocks] in Function " << F->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << F
->getName() << " when '" << *Val << "' == "
<< *LIC << "\n"; } } while (0)

859

<< " when '" << *Val << "' == " << *LIC << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %"
<< loopHeader->getName() << " [" << L->
getBlocks().size() << " blocks] in Function " << F
->getName() << " when '" << *Val << "' == "
<< *LIC << "\n"; } } while (0);

860

861

if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())

862

SE->forgetLoop(L);

863

864

LoopBlocks.clear();

865

NewBlocks.clear();

866

867

// First step, split the preheader and exit blocks, and add these blocks to

868

// the LoopBlocks list.

869

BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);

870

LoopBlocks.push_back(NewPreheader);

871

872

// We want the loop to come after the preheader, but before the exit blocks.

873

LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());

874

875

SmallVector<BasicBlock*, 8> ExitBlocks;

876

L->getUniqueExitBlocks(ExitBlocks);

877

878

// Split all of the edges from inside the loop to their exit blocks. Update

879

// the appropriate Phi nodes as we do so.

880

SplitExitEdges(L, ExitBlocks);

881

882

// The exit blocks may have been changed due to edge splitting, recompute.

883

ExitBlocks.clear();

884

L->getUniqueExitBlocks(ExitBlocks);

885

886

// Add exit blocks to the loop blocks.

887

LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());

888

889

// Next step, clone all of the basic blocks that make up the loop (including

890

// the loop preheader and exit blocks), keeping track of the mapping between

891

// the instructions and blocks.

892

NewBlocks.reserve(LoopBlocks.size());

893

ValueToValueMapTy VMap;

894

for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {

895

BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);

896

897

NewBlocks.push_back(NewBB);

898

VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping.

899

LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);

900

}

901

902

// Splice the newly inserted blocks into the function right before the

903

// original preheader.

904

F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(),

905

NewBlocks[0], F->end());

906

907

// FIXME: We could register any cloned assumptions instead of clearing the

908

// whole function's cache.

909

AC->clear();

910

911

// Now we create the new Loop object for the versioned loop.

912

Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);

913

914

// Recalculate unswitching quota, inherit simplified switches info for NewBB,

915

// Probably clone more loop-unswitch related loop properties.

916

BranchesInfo.cloneData(NewLoop, L, VMap);

917

918

Loop *ParentLoop = L->getParentLoop();

919

if (ParentLoop) {

920

// Make sure to add the cloned preheader and exit blocks to the parent loop

921

// as well.

922

ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);

923

}

924

925

for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {

926

BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);

927

// The new exit block should be in the same loop as the old one.

928

if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))

929

ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);

930

931

assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&((NewExit->getTerminator()->getNumSuccessors() == 1 &&
"Exit block should have been split to have one successor!") ?
static_cast<void> (0) : __assert_fail ("NewExit->getTerminator()->getNumSuccessors() == 1 && \"Exit block should have been split to have one successor!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 932, __PRETTY_FUNCTION__))

932

"Exit block should have been split to have one successor!")((NewExit->getTerminator()->getNumSuccessors() == 1 &&
"Exit block should have been split to have one successor!") ?
static_cast<void> (0) : __assert_fail ("NewExit->getTerminator()->getNumSuccessors() == 1 && \"Exit block should have been split to have one successor!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 932, __PRETTY_FUNCTION__));

933

BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);

934

935

// If the successor of the exit block had PHI nodes, add an entry for

936

// NewExit.

937

for (BasicBlock::iterator I = ExitSucc->begin();

938

PHINode *PN = dyn_cast<PHINode>(I); ++I) {

939

Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);

940

ValueToValueMapTy::iterator It = VMap.find(V);

941

if (It != VMap.end()) V = It->second;

942

PN->addIncoming(V, NewExit);

943

}

944

945

if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {

946

PHINode *PN = PHINode::Create(LPad->getType(), 0, "",

947

ExitSucc->getFirstInsertionPt());

948

949

for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);

950

I != E; ++I) {

951

BasicBlock *BB = *I;

952

LandingPadInst *LPI = BB->getLandingPadInst();

953

LPI->replaceAllUsesWith(PN);

954

PN->addIncoming(LPI, BB);

955

}

956

}

957

}

958

959

// Rewrite the code to refer to itself.

960

for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)

961

for (BasicBlock::iterator I = NewBlocks[i]->begin(),

962

E = NewBlocks[i]->end(); I != E; ++I)

963

RemapInstruction(I, VMap,RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);

964

965

// Rewrite the original preheader to select between versions of the loop.

966

BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());

967

assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&((OldBR->isUnconditional() && OldBR->getSuccessor
(0) == LoopBlocks[0] && "Preheader splitting did not work correctly!"
) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && \"Preheader splitting did not work correctly!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 968, __PRETTY_FUNCTION__))

968

"Preheader splitting did not work correctly!")((OldBR->isUnconditional() && OldBR->getSuccessor
(0) == LoopBlocks[0] && "Preheader splitting did not work correctly!"
) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && \"Preheader splitting did not work correctly!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 968, __PRETTY_FUNCTION__));

969

970

// Emit the new branch that selects between the two versions of this loop.

971

EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,

972

TI);

973

LPM->deleteSimpleAnalysisValue(OldBR, L);

974

OldBR->eraseFromParent();

975

976

LoopProcessWorklist.push_back(NewLoop);

977

redoLoop = true;

978

979

// Keep a WeakVH holding onto LIC. If the first call to RewriteLoopBody

980

// deletes the instruction (for example by simplifying a PHI that feeds into

981

// the condition that we're unswitching on), we don't rewrite the second

982

// iteration.

983

WeakVH LICHandle(LIC);

984

985

// Now we rewrite the original code to know that the condition is true and the

986

// new code to know that the condition is false.

987

RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);

988

989

// It's possible that simplifying one loop could cause the other to be

990

// changed to another value or a constant. If its a constant, don't simplify

991

// it.

992

if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&

993

LICHandle && !isa<Constant>(LICHandle))

994

RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);

995

}

996

997

/// RemoveFromWorklist - Remove all instances of I from the worklist vector

998

/// specified.

999

static void RemoveFromWorklist(Instruction *I,

1000

std::vector<Instruction*> &Worklist) {

1001

1002

Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),

1003

Worklist.end());

1004

}

1005

1006

/// ReplaceUsesOfWith - When we find that I really equals V, remove I from the

1007

/// program, replacing all uses with V and update the worklist.

1008

static void ReplaceUsesOfWith(Instruction *I, Value *V,

1009

std::vector<Instruction*> &Worklist,

1010

Loop *L, LPPassManager *LPM) {

1011

DEBUG(dbgs() << "Replace with '" << *V << "': " << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "Replace with '" <<
*V << "': " << *I; } } while (0);

1012

1013

// Add uses to the worklist, which may be dead now.

1014

for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)

1015

if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))

1016

Worklist.push_back(Use);

1017

1018

// Add users to the worklist which may be simplified now.

1019

for (User *U : I->users())

1020

Worklist.push_back(cast<Instruction>(U));

1021

LPM->deleteSimpleAnalysisValue(I, L);

1022

RemoveFromWorklist(I, Worklist);

1023

I->replaceAllUsesWith(V);

1024

I->eraseFromParent();

1025

++NumSimplify;

1026

}

1027

1028

// RewriteLoopBodyWithConditionConstant - We know either that the value LIC has

1029

// the value specified by Val in the specified loop, or we know it does NOT have

1030

// that value. Rewrite any uses of LIC or of properties correlated to it.

1031

void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,

1032

Constant *Val,

1033

bool IsEqual) {

1034

assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?")((!isa<Constant>(LIC) && "Why are we unswitching on a constant?"
) ? static_cast<void> (0) : __assert_fail ("!isa<Constant>(LIC) && \"Why are we unswitching on a constant?\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 1034, __PRETTY_FUNCTION__));

1035

1036

// FIXME: Support correlated properties, like:

1037

// for (...)

1038

// if (li1 < li2)

1039

// ...

1040

// if (li1 > li2)

1041

// ...

1042

1043

// FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,

1044

// selects, switches.

1045

std::vector<Instruction*> Worklist;

1046

LLVMContext &Context = Val->getContext();

1047

1048

// If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC

1049

// in the loop with the appropriate one directly.

1050

if (IsEqual || (isa<ConstantInt>(Val) &&

1051

Val->getType()->isIntegerTy(1))) {

1052

Value *Replacement;

1053

if (IsEqual)

1054

Replacement = Val;

1055

else

1056

Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),

1057

!cast<ConstantInt>(Val)->getZExtValue());

1058

1059

for (User *U : LIC->users()) {

1060

Instruction *UI = dyn_cast<Instruction>(U);

1061

if (!UI || !L->contains(UI))

1062

continue;

1063

Worklist.push_back(UI);

1064

}

1065

1066

for (std::vector<Instruction*>::iterator UI = Worklist.begin(),

1067

UE = Worklist.end(); UI != UE; ++UI)

1068

(*UI)->replaceUsesOfWith(LIC, Replacement);

1069

1070

SimplifyCode(Worklist, L);

1071

return;

1072

}

1073

1074

// Otherwise, we don't know the precise value of LIC, but we do know that it

1075

// is certainly NOT "Val". As such, simplify any uses in the loop that we

1076

// can. This case occurs when we unswitch switch statements.

1077

for (User *U : LIC->users()) {

1078

Instruction *UI = dyn_cast<Instruction>(U);

1079

if (!UI || !L->contains(UI))

←

Assuming 'UI' is non-null

Taking false branch

Assuming 'UI' is non-null

→

←

Taking false branch

→

1080

continue;

1081

1082

Worklist.push_back(UI);

1083

1084

// TODO: We could do other simplifications, for example, turning

1085

// 'icmp eq LIC, Val' -> false.

1086

1087

// If we know that LIC is not Val, use this info to simplify code.

1088

SwitchInst *SI = dyn_cast<SwitchInst>(UI);

1089

if (!SI || !isa<ConstantInt>(Val)) continue;

←

Assuming 'SI' is non-null

Taking false branch

Assuming 'SI' is non-null

→

←

Taking false branch

→

1090

1091

SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val));

1092

// Default case is live for multiple values.

1093

if (DeadCase == SI->case_default()) continue;

Taking false branch

Taking false branch

1094

1095

// Found a dead case value. Don't remove PHI nodes in the

1096

// successor if they become single-entry, those PHI nodes may

1097

// be in the Users list.

1098

1099

BasicBlock *Switch = SI->getParent();

1100

BasicBlock *SISucc = DeadCase.getCaseSuccessor();

1101

BasicBlock *Latch = L->getLoopLatch();

1102

1103

BranchesInfo.setUnswitched(SI, Val);

1104

1105

if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.

Taking false branch

Taking false branch

1106

// If the DeadCase successor dominates the loop latch, then the

1107

// transformation isn't safe since it will delete the sole predecessor edge

1108

// to the latch.

1109

if (Latch && DT->dominates(SISucc, Latch))

←

Called C++ object pointer is null

1110

continue;

1111

1112

// FIXME: This is a hack. We need to keep the successor around

1113

// and hooked up so as to preserve the loop structure, because

1114

// trying to update it is complicated. So instead we preserve the

1115

// loop structure and put the block on a dead code path.

1116

SplitEdge(Switch, SISucc, DT, LI);

1117

// Compute the successors instead of relying on the return value

1118

// of SplitEdge, since it may have split the switch successor

1119

// after PHI nodes.

1120

BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();

1121

BasicBlock *OldSISucc = *succ_begin(NewSISucc);

1122

// Create an "unreachable" destination.

1123

BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",

1124

Switch->getParent(),

1125

OldSISucc);

1126

new UnreachableInst(Context, Abort);

1127

// Force the new case destination to branch to the "unreachable"

1128

// block while maintaining a (dead) CFG edge to the old block.

1129

NewSISucc->getTerminator()->eraseFromParent();

1130

BranchInst::Create(Abort, OldSISucc,

1131

ConstantInt::getTrue(Context), NewSISucc);

1132

// Release the PHI operands for this edge.

1133

for (BasicBlock::iterator II = NewSISucc->begin();

←

Loop condition is false. Execution continues on line 1141

→

1134

PHINode *PN = dyn_cast<PHINode>(II); ++II)

1135

PN->setIncomingValue(PN->getBasicBlockIndex(Switch),

1136

UndefValue::get(PN->getType()));

1137

// Tell the domtree about the new block. We don't fully update the

1138

// domtree here -- instead we force it to do a full recomputation

1139

// after the pass is complete -- but we do need to inform it of

1140

// new blocks.

1141

if (DT)

←

Assuming pointer value is null

→

←

Taking false branch

→

1142

DT->addNewBlock(Abort, NewSISucc);

1143

}

1144

1145

SimplifyCode(Worklist, L);

1146

}

1147

1148

/// SimplifyCode - Okay, now that we have simplified some instructions in the

1149

/// loop, walk over it and constant prop, dce, and fold control flow where

1150

/// possible. Note that this is effectively a very simple loop-structure-aware

1151

/// optimizer. During processing of this loop, L could very well be deleted, so

1152

/// it must not be used.

1153

///

1154

/// FIXME: When the loop optimizer is more mature, separate this out to a new

1155

/// pass.

1156

///

1157

void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {

1158

const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();

1159

while (!Worklist.empty()) {

1160

Instruction *I = Worklist.back();

1161

Worklist.pop_back();

1162

1163

// Simple DCE.

1164

if (isInstructionTriviallyDead(I)) {

1165

DEBUG(dbgs() << "Remove dead instruction '" << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "Remove dead instruction '"
<< *I; } } while (0);

1166

1167

// Add uses to the worklist, which may be dead now.

1168

for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)

1169

if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))

1170

Worklist.push_back(Use);

1171

LPM->deleteSimpleAnalysisValue(I, L);

1172

RemoveFromWorklist(I, Worklist);

1173

I->eraseFromParent();

1174

++NumSimplify;

1175

continue;

1176

}

1177

1178

// See if instruction simplification can hack this up. This is common for

1179

// things like "select false, X, Y" after unswitching made the condition be

1180

// 'false'. TODO: update the domtree properly so we can pass it here.

1181

if (Value *V = SimplifyInstruction(I, DL))

1182

if (LI->replacementPreservesLCSSAForm(I, V)) {

1183

ReplaceUsesOfWith(I, V, Worklist, L, LPM);

1184

continue;

1185

}

1186

1187

// Special case hacks that appear commonly in unswitched code.

1188

if (BranchInst *BI = dyn_cast<BranchInst>(I)) {

1189

if (BI->isUnconditional()) {

1190

// If BI's parent is the only pred of the successor, fold the two blocks

1191

// together.

1192

BasicBlock *Pred = BI->getParent();

1193

BasicBlock *Succ = BI->getSuccessor(0);

1194

BasicBlock *SinglePred = Succ->getSinglePredecessor();

1195

if (!SinglePred) continue; // Nothing to do.

1196

assert(SinglePred == Pred && "CFG broken")((SinglePred == Pred && "CFG broken") ? static_cast<
void> (0) : __assert_fail ("SinglePred == Pred && \"CFG broken\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Transforms/Scalar/LoopUnswitch.cpp"
, 1196, __PRETTY_FUNCTION__));

1197

1198

DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "Merging blocks: " <<
Pred->getName() << " <- " << Succ->getName
() << "\n"; } } while (0)

1199

<< Succ->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unswitch")) { dbgs() << "Merging blocks: " <<
Pred->getName() << " <- " << Succ->getName
() << "\n"; } } while (0);

1200

1201

// Resolve any single entry PHI nodes in Succ.

1202

while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))

1203

ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);

1204

1205

// If Succ has any successors with PHI nodes, update them to have

1206

// entries coming from Pred instead of Succ.

1207

Succ->replaceAllUsesWith(Pred);

1208

1209

// Move all of the successor contents from Succ to Pred.

1210

Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),

1211

Succ->end());

1212

LPM->deleteSimpleAnalysisValue(BI, L);

1213

BI->eraseFromParent();

1214

RemoveFromWorklist(BI, Worklist);

1215

1216

// Remove Succ from the loop tree.

1217

LI->removeBlock(Succ);

1218

LPM->deleteSimpleAnalysisValue(Succ, L);

1219

Succ->eraseFromParent();

1220

++NumSimplify;

1221

continue;

1222

}

1223

1224

continue;

1225

}

1226

}

1227

}