Skip to content

Commit a5b10b4

Browse files
author
Johannes Doerfert
committedAug 23, 2019
[MustExec] Add a generic "must-be-executed-context" explorer
Given an instruction I, the MustBeExecutedContextExplorer allows to easily traverse instructions that are guaranteed to be executed whenever I is. For now, these instruction have to be statically "after" I, in the same or different basic blocks. This patch also adds a pass which prints the must-be-executed-context for each instruction in a module. It is used to test the MustBeExecutedContextExplorer, for now on the examples given in the class comment of the MustBeExecutedIterator. Differential Revision: https://reviews.llvm.org/D65186 llvm-svn: 369765
1 parent 344eee9 commit a5b10b4

File tree

7 files changed

+693
-2
lines changed

7 files changed

+693
-2
lines changed
 

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

Lines changed: 283 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,10 +7,17 @@
77
//===----------------------------------------------------------------------===//
88
/// \file
99
/// Contains a collection of routines for determining if a given instruction is
10-
/// guaranteed to execute if a given point in control flow is reached. The most
10+
/// guaranteed to execute if a given point in control flow is reached. The most
1111
/// common example is an instruction within a loop being provably executed if we
1212
/// branch to the header of it's containing loop.
1313
///
14+
/// There are two interfaces available to determine if an instruction is
15+
/// executed once a given point in the control flow is reached:
16+
/// 1) A loop-centric one derived from LoopSafetyInfo.
17+
/// 2) A "must be executed context"-based one implemented in the
18+
/// MustBeExecutedContextExplorer.
19+
/// Please refer to the class comments for more information.
20+
///
1421
//===----------------------------------------------------------------------===//
1522

1623
#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
@@ -164,6 +171,280 @@ class ICFLoopSafetyInfo: public LoopSafetyInfo {
164171
virtual ~ICFLoopSafetyInfo() {};
165172
};
166173

167-
}
174+
struct MustBeExecutedContextExplorer;
175+
176+
/// Must be executed iterators visit stretches of instructions that are
177+
/// guaranteed to be executed together, potentially with other instruction
178+
/// executed in-between.
179+
///
180+
/// Given the following code, and assuming all statements are single
181+
/// instructions which transfer execution to the successor (see
182+
/// isGuaranteedToTransferExecutionToSuccessor), there are two possible
183+
/// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
184+
/// and E. If we start at C or D, we will visit all instructions A-E.
185+
///
186+
/// \code
187+
/// A;
188+
/// B;
189+
/// if (...) {
190+
/// C;
191+
/// D;
192+
/// }
193+
/// E;
194+
/// \endcode
195+
///
196+
///
197+
/// Below is the example extneded with instructions F and G. Now we assume F
198+
/// might not transfer execution to it's successor G. As a result we get the
199+
/// following visit sets:
200+
///
201+
/// Start Instruction | Visit Set
202+
/// A | A, B, E, F
203+
/// B | A, B, E, F
204+
/// C | A, B, C, D, E, F
205+
/// D | A, B, C, D, E, F
206+
/// E | A, B, E, F
207+
/// F | A, B, E, F
208+
/// G | A, B, E, F, G
209+
///
210+
///
211+
/// \code
212+
/// A;
213+
/// B;
214+
/// if (...) {
215+
/// C;
216+
/// D;
217+
/// }
218+
/// E;
219+
/// F; // Might not transfer execution to its successor G.
220+
/// G;
221+
/// \endcode
222+
///
223+
///
224+
/// A more complex example involving conditionals, loops, break, and continue
225+
/// is shown below. We again assume all instructions will transmit control to
226+
/// the successor and we assume we can prove the inner loop to be finite. We
227+
/// omit non-trivial branch conditions as the exploration is oblivious to them.
228+
/// Constant branches are assumed to be unconditional in the CFG. The resulting
229+
/// visist sets are shown in the table below.
230+
///
231+
/// \code
232+
/// A;
233+
/// while (true) {
234+
/// B;
235+
/// if (...)
236+
/// C;
237+
/// if (...)
238+
/// continue;
239+
/// D;
240+
/// if (...)
241+
/// break;
242+
/// do {
243+
/// if (...)
244+
/// continue;
245+
/// E;
246+
/// } while (...);
247+
/// F;
248+
/// }
249+
/// G;
250+
/// \endcode
251+
///
252+
/// Start Instruction | Visit Set
253+
/// A | A, B
254+
/// B | A, B
255+
/// C | A, B, C
256+
/// D | A, B, D
257+
/// E | A, B, D, E, F
258+
/// F | A, B, D, F
259+
/// G | A, B, D, G
260+
///
261+
///
262+
/// Note that the examples show optimal visist sets but not necessarily the ones
263+
/// derived by the explorer depending on the available CFG analyses (see
264+
/// MustBeExecutedContextExplorer). Also note that we, depending on the options,
265+
/// the visit set can contain instructions from other functions.
266+
struct MustBeExecutedIterator {
267+
/// Type declarations that make his class an input iterator.
268+
///{
269+
typedef const Instruction *value_type;
270+
typedef std::ptrdiff_t difference_type;
271+
typedef const Instruction **pointer;
272+
typedef const Instruction *&reference;
273+
typedef std::input_iterator_tag iterator_category;
274+
///}
275+
276+
using ExplorerTy = MustBeExecutedContextExplorer;
277+
278+
MustBeExecutedIterator(const MustBeExecutedIterator &Other)
279+
: Visited(Other.Visited), Explorer(Other.Explorer),
280+
CurInst(Other.CurInst) {}
281+
282+
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
283+
: Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
284+
CurInst(Other.CurInst) {}
285+
286+
MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
287+
if (this != &Other) {
288+
std::swap(Visited, Other.Visited);
289+
std::swap(CurInst, Other.CurInst);
290+
}
291+
return *this;
292+
}
293+
294+
~MustBeExecutedIterator() {}
295+
296+
/// Pre- and post-increment operators.
297+
///{
298+
MustBeExecutedIterator &operator++() {
299+
CurInst = advance();
300+
return *this;
301+
}
302+
303+
MustBeExecutedIterator operator++(int) {
304+
MustBeExecutedIterator tmp(*this);
305+
operator++();
306+
return tmp;
307+
}
308+
///}
309+
310+
/// Equality and inequality operators. Note that we ignore the history here.
311+
///{
312+
bool operator==(const MustBeExecutedIterator &Other) const {
313+
return CurInst == Other.CurInst;
314+
}
315+
316+
bool operator!=(const MustBeExecutedIterator &Other) const {
317+
return !(*this == Other);
318+
}
319+
///}
320+
321+
/// Return the underlying instruction.
322+
const Instruction *&operator*() { return CurInst; }
323+
const Instruction *getCurrentInst() const { return CurInst; }
324+
325+
/// Return true if \p I was encountered by this iterator already.
326+
bool count(const Instruction *I) const { return Visited.count(I); }
327+
328+
private:
329+
using VisitedSetTy = DenseSet<const Instruction *>;
330+
331+
/// Private constructors.
332+
MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
333+
334+
/// Reset the iterator to its initial state pointing at \p I.
335+
void reset(const Instruction *I);
336+
337+
/// Try to advance one of the underlying positions (Head or Tail).
338+
///
339+
/// \return The next instruction in the must be executed context, or nullptr
340+
/// if none was found.
341+
const Instruction *advance();
342+
343+
/// A set to track the visited instructions in order to deal with endless
344+
/// loops and recursion.
345+
VisitedSetTy Visited;
346+
347+
/// A reference to the explorer that created this iterator.
348+
ExplorerTy &Explorer;
349+
350+
/// The instruction we are currently exposing to the user. There is always an
351+
/// instruction that we know is executed with the given program point,
352+
/// initially the program point itself.
353+
const Instruction *CurInst;
354+
355+
friend struct MustBeExecutedContextExplorer;
356+
};
357+
358+
/// A "must be executed context" for a given program point PP is the set of
359+
/// instructions, potentially before and after PP, that are executed always when
360+
/// PP is reached. The MustBeExecutedContextExplorer an interface to explore
361+
/// "must be executed contexts" in a module through the use of
362+
/// MustBeExecutedIterator.
363+
///
364+
/// The explorer exposes "must be executed iterators" that traverse the must be
365+
/// executed context. There is little information sharing between iterators as
366+
/// the expected use case involves few iterators for "far apart" instructions.
367+
/// If that changes, we should consider caching more intermediate results.
368+
struct MustBeExecutedContextExplorer {
369+
370+
/// In the description of the parameters we use PP to denote a program point
371+
/// for which the must be executed context is explored, or put differently,
372+
/// for which the MustBeExecutedIterator is created.
373+
///
374+
/// \param ExploreInterBlock Flag to indicate if instructions in blocks
375+
/// other than the parent of PP should be
376+
/// explored.
377+
MustBeExecutedContextExplorer(bool ExploreInterBlock)
378+
: ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
379+
380+
/// Clean up the dynamically allocated iterators.
381+
~MustBeExecutedContextExplorer() {
382+
DeleteContainerSeconds(InstructionIteratorMap);
383+
}
384+
385+
/// Iterator-based interface. \see MustBeExecutedIterator.
386+
///{
387+
using iterator = MustBeExecutedIterator;
388+
using const_iterator = const MustBeExecutedIterator;
389+
390+
/// Return an iterator to explore the context around \p PP.
391+
iterator &begin(const Instruction *PP) {
392+
auto *&It = InstructionIteratorMap[PP];
393+
if (!It)
394+
It = new iterator(*this, PP);
395+
return *It;
396+
}
397+
398+
/// Return an iterator to explore the cached context around \p PP.
399+
const_iterator &begin(const Instruction *PP) const {
400+
return *InstructionIteratorMap.lookup(PP);
401+
}
402+
403+
/// Return an universal end iterator.
404+
///{
405+
iterator &end() { return EndIterator; }
406+
iterator &end(const Instruction *) { return EndIterator; }
407+
408+
const_iterator &end() const { return EndIterator; }
409+
const_iterator &end(const Instruction *) const { return EndIterator; }
410+
///}
411+
412+
/// Return an iterator range to explore the context around \p PP.
413+
llvm::iterator_range<iterator> range(const Instruction *PP) {
414+
return llvm::make_range(begin(PP), end(PP));
415+
}
416+
417+
/// Return an iterator range to explore the cached context around \p PP.
418+
llvm::iterator_range<const_iterator> range(const Instruction *PP) const {
419+
return llvm::make_range(begin(PP), end(PP));
420+
}
421+
///}
422+
423+
/// Return the next instruction that is guaranteed to be executed after \p PP.
424+
///
425+
/// \param It The iterator that is used to traverse the must be
426+
/// executed context.
427+
/// \param PP The program point for which the next instruction
428+
/// that is guaranteed to execute is determined.
429+
const Instruction *
430+
getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
431+
const Instruction *PP);
432+
433+
/// Parameter that limit the performed exploration. See the constructor for
434+
/// their meaning.
435+
///{
436+
const bool ExploreInterBlock;
437+
///}
438+
439+
private:
440+
/// Map from instructions to associated must be executed iterators.
441+
DenseMap<const Instruction *, MustBeExecutedIterator *>
442+
InstructionIteratorMap;
443+
444+
/// A unique end iterator.
445+
MustBeExecutedIterator EndIterator;
446+
};
447+
448+
} // namespace llvm
168449

169450
#endif

‎llvm/include/llvm/Analysis/Passes.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,13 @@ namespace llvm {
103103
//
104104
FunctionPass *createMustExecutePrinter();
105105

106+
//===--------------------------------------------------------------------===//
107+
//
108+
// createMustBeExecutedContextPrinter - This pass prints information about which
109+
// instructions are guaranteed to execute together (run with -analyze).
110+
//
111+
ModulePass *createMustBeExecutedContextPrinter();
112+
106113
}
107114

108115
#endif

‎llvm/include/llvm/InitializePasses.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -289,6 +289,7 @@ void initializeMetaRenamerPass(PassRegistry&);
289289
void initializeModuleDebugInfoPrinterPass(PassRegistry&);
290290
void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&);
291291
void initializeMustExecutePrinterPass(PassRegistry&);
292+
void initializeMustBeExecutedContextPrinterPass(PassRegistry&);
292293
void initializeNameAnonGlobalLegacyPassPass(PassRegistry&);
293294
void initializeNaryReassociateLegacyPassPass(PassRegistry&);
294295
void initializeNewGVNLegacyPassPass(PassRegistry&);

‎llvm/include/llvm/LinkAllPasses.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -219,6 +219,7 @@ namespace {
219219
(void) llvm::createStraightLineStrengthReducePass();
220220
(void) llvm::createMemDerefPrinter();
221221
(void) llvm::createMustExecutePrinter();
222+
(void) llvm::createMustBeExecutedContextPrinter();
222223
(void) llvm::createFloat2IntPass();
223224
(void) llvm::createEliminateAvailableExternallyPass();
224225
(void) llvm::createScalarizeMaskedMemIntrinPass();

‎llvm/lib/Analysis/Analysis.cpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
6565
initializeModuleDebugInfoPrinterPass(Registry);
6666
initializeModuleSummaryIndexWrapperPassPass(Registry);
6767
initializeMustExecutePrinterPass(Registry);
68+
initializeMustBeExecutedContextPrinterPass(Registry);
6869
initializeObjCARCAAWrapperPassPass(Registry);
6970
initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
7071
initializePhiValuesWrapperPassPass(Registry);

‎llvm/lib/Analysis/MustExecute.cpp

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@
77
//===----------------------------------------------------------------------===//
88

99
#include "llvm/Analysis/MustExecute.h"
10+
#include "llvm/ADT/PostOrderIterator.h"
11+
#include "llvm/Analysis/CFG.h"
1012
#include "llvm/Analysis/InstructionSimplify.h"
1113
#include "llvm/Analysis/LoopInfo.h"
1214
#include "llvm/Analysis/Passes.h"
@@ -19,8 +21,11 @@
1921
#include "llvm/Support/ErrorHandling.h"
2022
#include "llvm/Support/FormattedStream.h"
2123
#include "llvm/Support/raw_ostream.h"
24+
2225
using namespace llvm;
2326

27+
#define DEBUG_TYPE "must-execute"
28+
2429
const DenseMap<BasicBlock *, ColorVector> &
2530
LoopSafetyInfo::getBlockColors() const {
2631
return BlockColors;
@@ -306,6 +311,17 @@ namespace {
306311
}
307312
bool runOnFunction(Function &F) override;
308313
};
314+
struct MustBeExecutedContextPrinter : public ModulePass {
315+
static char ID;
316+
317+
MustBeExecutedContextPrinter() : ModulePass(ID) {
318+
initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry());
319+
}
320+
void getAnalysisUsage(AnalysisUsage &AU) const override {
321+
AU.setPreservesAll();
322+
}
323+
bool runOnModule(Module &M) override;
324+
};
309325
}
310326

311327
char MustExecutePrinter::ID = 0;
@@ -320,6 +336,36 @@ FunctionPass *llvm::createMustExecutePrinter() {
320336
return new MustExecutePrinter();
321337
}
322338

339+
char MustBeExecutedContextPrinter::ID = 0;
340+
INITIALIZE_PASS_BEGIN(
341+
MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
342+
"print the must-be-executed-contexed for all instructions", false, true)
343+
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
344+
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
345+
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
346+
INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
347+
"print-must-be-executed-contexts",
348+
"print the must-be-executed-contexed for all instructions",
349+
false, true)
350+
351+
ModulePass *llvm::createMustBeExecutedContextPrinter() {
352+
return new MustBeExecutedContextPrinter();
353+
}
354+
355+
bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
356+
MustBeExecutedContextExplorer Explorer(true);
357+
for (Function &F : M) {
358+
for (Instruction &I : instructions(F)) {
359+
dbgs() << "-- Explore context of: " << I << "\n";
360+
for (const Instruction *CI : Explorer.range(&I))
361+
dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
362+
<< "\n";
363+
}
364+
}
365+
366+
return false;
367+
}
368+
323369
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
324370
// TODO: merge these two routines. For the moment, we display the best
325371
// result obtained by *either* implementation. This is a bit unfair since no
@@ -396,3 +442,75 @@ bool MustExecutePrinter::runOnFunction(Function &F) {
396442

397443
return false;
398444
}
445+
446+
const Instruction *
447+
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
448+
MustBeExecutedIterator &It, const Instruction *PP) {
449+
if (!PP)
450+
return PP;
451+
LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
452+
453+
// If we explore only inside a given basic block we stop at terminators.
454+
if (!ExploreInterBlock && PP->isTerminator()) {
455+
LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
456+
return nullptr;
457+
}
458+
459+
// If we do not traverse the call graph we check if we can make progress in
460+
// the current function. First, check if the instruction is guaranteed to
461+
// transfer execution to the successor.
462+
bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
463+
if (!TransfersExecution)
464+
return nullptr;
465+
466+
// If this is not a terminator we know that there is a single instruction
467+
// after this one that is executed next if control is transfered. If not,
468+
// we can try to go back to a call site we entered earlier. If none exists, we
469+
// do not know any instruction that has to be executd next.
470+
if (!PP->isTerminator()) {
471+
const Instruction *NextPP = PP->getNextNode();
472+
LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
473+
return NextPP;
474+
}
475+
476+
// Finally, we have to handle terminators, trivial ones first.
477+
assert(PP->isTerminator() && "Expected a terminator!");
478+
479+
// A terminator without a successor is not handled yet.
480+
if (PP->getNumSuccessors() == 0) {
481+
LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
482+
return nullptr;
483+
}
484+
485+
// A terminator with a single successor, we will continue at the beginning of
486+
// that one.
487+
if (PP->getNumSuccessors() == 1) {
488+
LLVM_DEBUG(
489+
dbgs() << "\tUnconditional terminator, continue with successor\n");
490+
return &PP->getSuccessor(0)->front();
491+
}
492+
493+
LLVM_DEBUG(dbgs() << "\tNo join point found\n");
494+
return nullptr;
495+
}
496+
497+
MustBeExecutedIterator::MustBeExecutedIterator(
498+
MustBeExecutedContextExplorer &Explorer, const Instruction *I)
499+
: Explorer(Explorer), CurInst(I) {
500+
reset(I);
501+
}
502+
503+
void MustBeExecutedIterator::reset(const Instruction *I) {
504+
CurInst = I;
505+
Visited.clear();
506+
Visited.insert(I);
507+
}
508+
509+
const Instruction *MustBeExecutedIterator::advance() {
510+
assert(CurInst && "Cannot advance an end iterator!");
511+
const Instruction *Next =
512+
Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
513+
if (Next && !Visited.insert(Next).second)
514+
Next = nullptr;
515+
return Next;
516+
}

‎llvm/test/Analysis/MustExecute/must_be_executed_context.ll

Lines changed: 282 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,282 @@
1+
; RUN: opt -print-mustexecute -analyze 2>&1 < %s | FileCheck %s --check-prefix=ME
2+
; RUN: opt -print-must-be-executed-contexts -analyze 2>&1 < %s | FileCheck %s --check-prefix=MBEC
3+
;
4+
; void simple_conditional(int c) {
5+
; A();
6+
; B();
7+
; if (c) {
8+
; C();
9+
; D();
10+
; }
11+
; E();
12+
; F();
13+
; G();
14+
; }
15+
;
16+
; Best result:
17+
; Start Instruction | Visit Set
18+
; A | A, B, E, F
19+
; B | A, B, E, F
20+
; C | A, B, C, D, E, F
21+
; D | A, B, C, D, E, F
22+
; E | A, B, E, F
23+
; F | A, B, E, F
24+
; G | A, B, E, F, G
25+
;
26+
; FIXME: We miss the B -> E and backward exploration.
27+
;
28+
; There are no loops so print-mustexec will not do anything.
29+
; ME-NOT: mustexec
30+
;
31+
define void @simple_conditional(i32 %arg) {
32+
bb:
33+
call void @A()
34+
; MBEC: -- Explore context of: call void @A()
35+
; MBEC-NEXT: [F: simple_conditional] call void @A()
36+
; MBEC-NEXT: [F: simple_conditional] call void @B()
37+
; MBEC-NEXT: [F: simple_conditional] %tmp = icmp eq i32 %arg, 0
38+
; MBEC-NEXT: [F: simple_conditional] br i1 %tmp, label %bb2, label %bb1
39+
; MBEC-NOT: call
40+
41+
call void @B()
42+
; MBEC: -- Explore context of: call void @B()
43+
; MBEC-NEXT: [F: simple_conditional] call void @B()
44+
; MBEC-NEXT: [F: simple_conditional] %tmp = icmp eq i32 %arg, 0
45+
; MBEC-NEXT: [F: simple_conditional] br i1 %tmp, label %bb2, label %bb1
46+
; MBEC-NOT: call
47+
; MBEC: -- Explore context of: %tmp
48+
49+
%tmp = icmp eq i32 %arg, 0
50+
br i1 %tmp, label %bb2, label %bb1
51+
52+
bb1: ; preds = %bb
53+
call void @C()
54+
; MBEC: -- Explore context of: call void @C()
55+
; MBEC-NEXT: [F: simple_conditional] call void @C()
56+
; MBEC-NEXT: [F: simple_conditional] call void @D()
57+
; MBEC-NEXT: [F: simple_conditional] br label %bb2
58+
; MBEC-NEXT: [F: simple_conditional] call void @E()
59+
; MBEC-NEXT: [F: simple_conditional] call void @F()
60+
; MBEC-NOT: call
61+
62+
call void @D()
63+
; MBEC: -- Explore context of: call void @D()
64+
; MBEC-NEXT: [F: simple_conditional] call void @D()
65+
; MBEC-NEXT: [F: simple_conditional] br label %bb2
66+
; MBEC-NEXT: [F: simple_conditional] call void @E()
67+
; MBEC-NEXT: [F: simple_conditional] call void @F()
68+
; MBEC-NOT: call
69+
; MBEC: -- Explore context of: br
70+
71+
br label %bb2
72+
73+
bb2: ; preds = %bb, %bb1
74+
call void @E()
75+
; MBEC: -- Explore context of: call void @E()
76+
; MBEC-NEXT: [F: simple_conditional] call void @E()
77+
; MBEC-NEXT: [F: simple_conditional] call void @F()
78+
; MBEC-NOT: call
79+
80+
call void @F() ; might not return!
81+
; MBEC: -- Explore context of: call void @F()
82+
; MBEC-NEXT: [F: simple_conditional] call void @F()
83+
; MBEC-NOT: call
84+
85+
call void @G()
86+
; MBEC: -- Explore context of: call void @G()
87+
; MBEC-NEXT: [F: simple_conditional] call void @G()
88+
; MBEC-NEXT: [F: simple_conditional] ret void
89+
; MBEC-NOT: call
90+
; MBEC: -- Explore context of: ret
91+
92+
ret void
93+
}
94+
95+
96+
; void complex_loops_and_control(int c, int d) {
97+
; A();
98+
; while (1) {
99+
; B();
100+
; if (++c == d)
101+
; C();
102+
; if (++c == d)
103+
; continue;
104+
; D();
105+
; if (++c == d)
106+
; break;
107+
; do {
108+
; if (++c == d)
109+
; continue;
110+
; E();
111+
; } while (++c == d);
112+
; F();
113+
; }
114+
; G();
115+
; }
116+
;
117+
; Best result:
118+
; Start Instruction | Visit Set
119+
; A | A, B
120+
; B | A, B
121+
; C | A, B, C
122+
; D | A, B, D
123+
; E | A, B, D, E, F
124+
; F | A, B, D, F
125+
; G | A, B, D, G
126+
;
127+
;
128+
; ME: define void @complex_loops_and_control
129+
define void @complex_loops_and_control(i32 %arg, i32 %arg1) {
130+
bb:
131+
call void @A()
132+
; ME: call void @A()
133+
; ME-NOT: mustexec
134+
; ME-NEXT: br
135+
; MBEC: -- Explore context of: call void @A()
136+
; MBEC-NEXT: [F: complex_loops_and_control] call void @A()
137+
; MBEC-NEXT: [F: complex_loops_and_control] br label %bb2
138+
; MBEC-NEXT: [F: complex_loops_and_control] %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
139+
; MBEC-NEXT: [F: complex_loops_and_control] call void @B()
140+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp = add nsw i32 %.0, 1
141+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp3 = icmp eq i32 %tmp, %arg1
142+
; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp3, label %bb4, label %bb5
143+
; MBEC-NOT: call
144+
; MBEC: -- Explore context of: br
145+
br label %bb2
146+
147+
bb2: ; preds = %.backedge, %bb
148+
%.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
149+
call void @B()
150+
; ME: call void @B() ; (mustexec in: bb2)
151+
; MBEC: -- Explore context of: call void @B()
152+
; MBEC-NEXT: [F: complex_loops_and_control] call void @B()
153+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp = add nsw i32 %.0, 1
154+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp3 = icmp eq i32 %tmp, %arg1
155+
; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp3, label %bb4, label %bb5
156+
; MBEC-NOT: call
157+
; MBEC: -- Explore context of: %tmp
158+
%tmp = add nsw i32 %.0, 1
159+
%tmp3 = icmp eq i32 %tmp, %arg1
160+
br i1 %tmp3, label %bb4, label %bb5
161+
162+
bb4: ; preds = %bb2
163+
call void @C()
164+
; ME: call void @C()
165+
; ME-NOT: mustexec
166+
; ME-NEXT: br
167+
; FIXME: Missing A and B (backward)
168+
; MBEC: -- Explore context of: call void @C()
169+
; MBEC-NEXT: [F: complex_loops_and_control] call void @C()
170+
; MBEC-NEXT: [F: complex_loops_and_control] br label %bb5
171+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp6 = add nsw i32 %.0, 2
172+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp7 = icmp eq i32 %tmp6, %arg1
173+
; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp7, label %bb8, label %bb9
174+
; MBEC-NOT: call
175+
; MBEC: -- Explore context of: br
176+
br label %bb5
177+
178+
bb5: ; preds = %bb4, %bb2
179+
%tmp6 = add nsw i32 %.0, 2
180+
%tmp7 = icmp eq i32 %tmp6, %arg1
181+
br i1 %tmp7, label %bb8, label %bb9
182+
183+
bb8: ; preds = %bb5
184+
br label %.backedge
185+
186+
.backedge: ; preds = %bb8, %bb22
187+
%.0.be = phi i32 [ %tmp6, %bb8 ], [ %.lcssa, %bb22 ]
188+
br label %bb2
189+
190+
bb9: ; preds = %bb5
191+
call void @D()
192+
; ME: call void @D()
193+
; ME-NOT: mustexec
194+
; ME-NEXT: %tmp10
195+
; FIXME: Missing A and B (backward)
196+
; MBEC: -- Explore context of: call void @D()
197+
; MBEC-NEXT: [F: complex_loops_and_control] call void @D()
198+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp10 = add nsw i32 %.0, 3
199+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp11 = icmp eq i32 %tmp10, %arg1
200+
; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp11, label %bb12, label %bb13
201+
; MBEC-NOT: call
202+
; MBEC: -- Explore context of: %tmp10
203+
%tmp10 = add nsw i32 %.0, 3
204+
%tmp11 = icmp eq i32 %tmp10, %arg1
205+
br i1 %tmp11, label %bb12, label %bb13
206+
207+
bb12: ; preds = %bb9
208+
br label %bb23
209+
210+
bb13: ; preds = %bb9
211+
br label %bb14
212+
213+
bb14: ; preds = %bb19, %bb13
214+
%.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ]
215+
%tmp15 = add nsw i32 %.1, 1
216+
%tmp16 = icmp eq i32 %tmp15, %arg1
217+
br i1 %tmp16, label %bb17, label %bb18
218+
219+
bb17: ; preds = %bb14
220+
br label %bb19
221+
222+
bb18: ; preds = %bb14
223+
call void @E()
224+
; ME: call void @E()
225+
; ME-NOT: mustexec
226+
; ME-NEXT: br
227+
; FIXME: Missing A, B, and D (backward), as well as F
228+
; MBEC: -- Explore context of: call void @E()
229+
; MBEC-NEXT: [F: complex_loops_and_control] call void @E()
230+
; MBEC-NEXT: [F: complex_loops_and_control] br label %bb19
231+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp20 = add nsw i32 %.1, 2
232+
; MBEC-NEXT: [F: complex_loops_and_control] %tmp21 = icmp eq i32 %tmp20, %arg1
233+
; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp21, label %bb14, label %bb22
234+
; MBEC-NOT: call
235+
; MBEC: -- Explore context of: br
236+
br label %bb19
237+
238+
bb19: ; preds = %bb18, %bb17
239+
%tmp20 = add nsw i32 %.1, 2
240+
%tmp21 = icmp eq i32 %tmp20, %arg1
241+
br i1 %tmp21, label %bb14, label %bb22
242+
243+
bb22: ; preds = %bb19
244+
%.lcssa = phi i32 [ %tmp20, %bb19 ]
245+
call void @F()
246+
; ME: call void @F()
247+
; ME-NOT: mustexec
248+
; ME-NEXT: br
249+
; FIXME: Missing A, B, and D (backward)
250+
; MBEC: -- Explore context of: call void @F()
251+
; MBEC-NEXT: [F: complex_loops_and_control] call void @F()
252+
; MBEC-NOT: call
253+
; MBEC: -- Explore context of: br
254+
br label %.backedge
255+
256+
bb23: ; preds = %bb12
257+
call void @G()
258+
; ME: call void @G()
259+
; ME-NOT: mustexec
260+
; ME-NEXT: ret
261+
; FIXME: Missing A, B, and D (backward)
262+
; MBEC: -- Explore context of: call void @G()
263+
; MBEC-NEXT: [F: complex_loops_and_control] call void @G()
264+
; MBEC-NEXT: [F: complex_loops_and_control] ret void
265+
; MBEC-NOT: call
266+
; MBEC: -- Explore context of: ret
267+
ret void
268+
}
269+
270+
declare void @A() nounwind willreturn
271+
272+
declare void @B() nounwind willreturn
273+
274+
declare void @C() nounwind willreturn
275+
276+
declare void @D() nounwind willreturn
277+
278+
declare void @E() nounwind willreturn
279+
280+
declare void @F() nounwind
281+
282+
declare void @G() nounwind willreturn

0 commit comments

Comments
 (0)
Please sign in to comment.