Skip to content

Commit fe799c9

Browse files
jdoerfertjdoerfert
committed
[MustExecute] Forward iterate over conditional branches
Summary: If a conditional branch is encountered we can try to find a join block where the execution is known to continue. This means finding a suitable block, e.g., the immediate post dominator of the conditional branch, and proofing control will always reach that block. This patch implements different techniques that work with and without provided analysis. Reviewers: uenoku, sstefan1, hfinkel Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68933
1 parent 4138fc9 commit fe799c9

File tree

4 files changed

+556
-16
lines changed

4 files changed

+556
-16
lines changed

‎llvm/include/llvm/Analysis/MustExecute.h

Lines changed: 29 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,8 +33,13 @@
3333

3434
namespace llvm {
3535

36+
namespace {
37+
template <typename T> using GetterTy = std::function<T *(const Function &F)>;
38+
}
39+
3640
class Instruction;
3741
class DominatorTree;
42+
class PostDominatorTree;
3843
class Loop;
3944

4045
/// Captures loop safety information.
@@ -374,8 +379,14 @@ struct MustBeExecutedContextExplorer {
374379
/// \param ExploreInterBlock Flag to indicate if instructions in blocks
375380
/// other than the parent of PP should be
376381
/// explored.
377-
MustBeExecutedContextExplorer(bool ExploreInterBlock)
378-
: ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
382+
MustBeExecutedContextExplorer(
383+
bool ExploreInterBlock,
384+
GetterTy<const LoopInfo> LIGetter =
385+
[](const Function &) { return nullptr; },
386+
GetterTy<const PostDominatorTree> PDTGetter =
387+
[](const Function &) { return nullptr; })
388+
: ExploreInterBlock(ExploreInterBlock), LIGetter(LIGetter),
389+
PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
379390

380391
/// Clean up the dynamically allocated iterators.
381392
~MustBeExecutedContextExplorer() {
@@ -454,13 +465,29 @@ struct MustBeExecutedContextExplorer {
454465
getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
455466
const Instruction *PP);
456467

468+
/// Find the next join point from \p InitBB in forward direction.
469+
const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB);
470+
457471
/// Parameter that limit the performed exploration. See the constructor for
458472
/// their meaning.
459473
///{
460474
const bool ExploreInterBlock;
461475
///}
462476

463477
private:
478+
/// Getters for common CFG analyses: LoopInfo, DominatorTree, and
479+
/// PostDominatorTree.
480+
///{
481+
GetterTy<const LoopInfo> LIGetter;
482+
GetterTy<const PostDominatorTree> PDTGetter;
483+
///}
484+
485+
/// Map to cache isGuaranteedToTransferExecutionToSuccessor results.
486+
DenseMap<const BasicBlock *, Optional<bool>> BlockTransferMap;
487+
488+
/// Map to cache containsIrreducibleCFG results.
489+
DenseMap<const Function*, Optional<bool>> IrreducibleControlMap;
490+
464491
/// Map from instructions to associated must be executed iterators.
465492
DenseMap<const Instruction *, MustBeExecutedIterator *>
466493
InstructionIteratorMap;

‎llvm/lib/Analysis/MustExecute.cpp

Lines changed: 187 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
#include "llvm/Analysis/LoopInfo.h"
1414
#include "llvm/Analysis/Passes.h"
1515
#include "llvm/Analysis/ValueTracking.h"
16+
#include "llvm/Analysis/PostDominators.h"
1617
#include "llvm/IR/AssemblyAnnotationWriter.h"
1718
#include "llvm/IR/DataLayout.h"
1819
#include "llvm/IR/InstIterator.h"
@@ -353,7 +354,19 @@ ModulePass *llvm::createMustBeExecutedContextPrinter() {
353354
}
354355

355356
bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
356-
MustBeExecutedContextExplorer Explorer(true);
357+
// We provide non-PM analysis here because the old PM doesn't like to query
358+
// function passes from a module pass. Given that this is a printer, we don't
359+
// care much about memory leaks.
360+
GetterTy<LoopInfo> LIGetter = [this](const Function &F) {
361+
DominatorTree *DT = new DominatorTree(const_cast<Function &>(F));
362+
LoopInfo *LI = new LoopInfo(*DT);
363+
return LI;
364+
};
365+
GetterTy<PostDominatorTree> PDTGetter = [this](const Function &F) {
366+
PostDominatorTree *PDT = new PostDominatorTree(const_cast<Function &>(F));
367+
return PDT;
368+
};
369+
MustBeExecutedContextExplorer Explorer(true, LIGetter, PDTGetter);
357370
for (Function &F : M) {
358371
for (Instruction &I : instructions(F)) {
359372
dbgs() << "-- Explore context of: " << I << "\n";
@@ -443,6 +456,173 @@ bool MustExecutePrinter::runOnFunction(Function &F) {
443456
return false;
444457
}
445458

459+
/// Return true if \p L might be an endless loop.
460+
static bool maybeEndlessLoop(const Loop &L) {
461+
if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
462+
return false;
463+
// TODO: Actually try to prove it is not.
464+
// TODO: If maybeEndlessLoop is going to be expensive, cache it.
465+
return true;
466+
}
467+
468+
static bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
469+
if (!LI)
470+
return false;
471+
using RPOTraversal = ReversePostOrderTraversal<const Function *>;
472+
RPOTraversal FuncRPOT(&F);
473+
return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
474+
const LoopInfo>(FuncRPOT, *LI);
475+
}
476+
477+
/// Lookup \p Key in \p Map and return the result, potentially after
478+
/// initializing the optional through \p Fn(\p args).
479+
template <typename K, typename V, typename FnTy, typename... ArgsTy>
480+
static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
481+
FnTy &&Fn, ArgsTy&&... args) {
482+
Optional<V> &OptVal = Map[Key];
483+
if (!OptVal.hasValue())
484+
OptVal = Fn(std::forward<ArgsTy>(args)...);
485+
return OptVal.getValue();
486+
}
487+
488+
const BasicBlock *
489+
MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
490+
const LoopInfo *LI = LIGetter(*InitBB->getParent());
491+
const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
492+
493+
LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
494+
<< (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
495+
496+
const Function &F = *InitBB->getParent();
497+
const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
498+
const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
499+
bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
500+
(L && !maybeEndlessLoop(*L))) &&
501+
F.doesNotThrow();
502+
LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
503+
<< (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
504+
<< "\n");
505+
506+
// Determine the adjacent blocks in the given direction but exclude (self)
507+
// loops under certain circumstances.
508+
SmallVector<const BasicBlock *, 8> Worklist;
509+
for (const BasicBlock *SuccBB : successors(InitBB)) {
510+
bool IsLatch = SuccBB == HeaderBB;
511+
// Loop latches are ignored in forward propagation if the loop cannot be
512+
// endless and may not throw: control has to go somewhere.
513+
if (!WillReturnAndNoThrow || !IsLatch)
514+
Worklist.push_back(SuccBB);
515+
}
516+
LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
517+
518+
// If there are no other adjacent blocks, there is no join point.
519+
if (Worklist.empty())
520+
return nullptr;
521+
522+
// If there is one adjacent block, it is the join point.
523+
if (Worklist.size() == 1)
524+
return Worklist[0];
525+
526+
// Try to determine a join block through the help of the post-dominance
527+
// tree. If no tree was provided, we perform simple pattern matching for one
528+
// block conditionals and one block loops only.
529+
const BasicBlock *JoinBB = nullptr;
530+
if (PDT)
531+
if (const auto *InitNode = PDT->getNode(InitBB))
532+
if (const auto *IDomNode = InitNode->getIDom())
533+
JoinBB = IDomNode->getBlock();
534+
535+
if (!JoinBB && Worklist.size() == 2) {
536+
const BasicBlock *Succ0 = Worklist[0];
537+
const BasicBlock *Succ1 = Worklist[1];
538+
const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
539+
const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
540+
if (Succ0UniqueSucc == InitBB) {
541+
// InitBB -> Succ0 -> InitBB
542+
// InitBB -> Succ1 = JoinBB
543+
JoinBB = Succ1;
544+
} else if (Succ1UniqueSucc == InitBB) {
545+
// InitBB -> Succ1 -> InitBB
546+
// InitBB -> Succ0 = JoinBB
547+
JoinBB = Succ0;
548+
} else if (Succ0 == Succ1UniqueSucc) {
549+
// InitBB -> Succ0 = JoinBB
550+
// InitBB -> Succ1 -> Succ0 = JoinBB
551+
JoinBB = Succ0;
552+
} else if (Succ1 == Succ0UniqueSucc) {
553+
// InitBB -> Succ0 -> Succ1 = JoinBB
554+
// InitBB -> Succ1 = JoinBB
555+
JoinBB = Succ1;
556+
} else if (Succ0UniqueSucc == Succ1UniqueSucc) {
557+
// InitBB -> Succ0 -> JoinBB
558+
// InitBB -> Succ1 -> JoinBB
559+
JoinBB = Succ0UniqueSucc;
560+
}
561+
}
562+
563+
if (!JoinBB && L)
564+
JoinBB = L->getUniqueExitBlock();
565+
566+
if (!JoinBB)
567+
return nullptr;
568+
569+
LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
570+
571+
// In forward direction we check if control will for sure reach JoinBB from
572+
// InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
573+
// are: infinite loops and instructions that do not necessarily transfer
574+
// execution to their successor. To check for them we traverse the CFG from
575+
// the adjacent blocks to the JoinBB, looking at all intermediate blocks.
576+
577+
// If we know the function is "will-return" and "no-throw" there is no need
578+
// for futher checks.
579+
if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
580+
581+
auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
582+
return isGuaranteedToTransferExecutionToSuccessor(BB);
583+
};
584+
585+
SmallPtrSet<const BasicBlock *, 16> Visited;
586+
while (!Worklist.empty()) {
587+
const BasicBlock *ToBB = Worklist.pop_back_val();
588+
if (ToBB == JoinBB)
589+
continue;
590+
591+
// Make sure all loops in-between are finite.
592+
if (!Visited.insert(ToBB).second) {
593+
if (!F.hasFnAttribute(Attribute::WillReturn)) {
594+
if (!LI)
595+
return nullptr;
596+
597+
bool MayContainIrreducibleControl = getOrCreateCachedOptional(
598+
&F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
599+
if (MayContainIrreducibleControl)
600+
return nullptr;
601+
602+
const Loop *L = LI->getLoopFor(ToBB);
603+
if (L && maybeEndlessLoop(*L))
604+
return nullptr;
605+
}
606+
607+
continue;
608+
}
609+
610+
// Make sure the block has no instructions that could stop control
611+
// transfer.
612+
bool TransfersExecution = getOrCreateCachedOptional(
613+
ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
614+
if (!TransfersExecution)
615+
return nullptr;
616+
617+
for (const BasicBlock *AdjacentBB : successors(ToBB))
618+
Worklist.push_back(AdjacentBB);
619+
}
620+
}
621+
622+
LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
623+
return JoinBB;
624+
}
625+
446626
const Instruction *
447627
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
448628
MustBeExecutedIterator &It, const Instruction *PP) {
@@ -490,6 +670,12 @@ MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
490670
return &PP->getSuccessor(0)->front();
491671
}
492672

673+
// Multiple successors mean we need to find the join point where control flow
674+
// converges again. We use the findForwardJoinPoint helper function with
675+
// information about the function and helper analyses, if available.
676+
if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
677+
return &JoinBB->front();
678+
493679
LLVM_DEBUG(dbgs() << "\tNo join point found\n");
494680
return nullptr;
495681
}

0 commit comments

Comments
 (0)