Generate correctly structured do-while loops.
The loop test is always emitted before the loop body.
For do-while loops, use a phi node to track whether we're
on the first loop iteration, and only check the loop test
on the second and subsequent iterations.
For do-while loops, the loop test branch no longer occurs
at the top of the loop, so it must get its own selection
merge instruction.
A block can't be the target of more than one merge instruction.
So when the loop test executes after the body (as in do-while in GLSL)
we need to introduce a dummy block to be the target of the selection
merge just before the loop test conditional branch.
The other arm of the branch exits the loop and hence is the
"break block" exception in the structured control flow rules.
diff --git a/SPIRV/GlslangToSpv.cpp b/SPIRV/GlslangToSpv.cpp
index 7f9214c..dac5958 100644
--- a/SPIRV/GlslangToSpv.cpp
+++ b/SPIRV/GlslangToSpv.cpp
@@ -1147,28 +1147,18 @@
// body emission needs to know what the for-loop terminal is when it sees a "continue"
loopTerminal.push(node->getTerminal());
- builder.makeNewLoop();
-
- bool bodyOut = false;
- if (! node->testFirst()) {
- builder.endLoopHeaderWithoutTest();
- if (node->getBody()) {
- breakForLoop.push(true);
- node->getBody()->traverse(this);
- breakForLoop.pop();
- }
- bodyOut = true;
- builder.createBranchToLoopTest();
- }
+ builder.makeNewLoop(node->testFirst());
if (node->getTest()) {
node->getTest()->traverse(this);
// the AST only contained the test computation, not the branch, we have to add it
spv::Id condition = builder.accessChainLoad(TranslatePrecisionDecoration(node->getTest()->getType()));
builder.createLoopTestBranch(condition);
+ } else {
+ builder.createBranchToBody();
}
- if (! bodyOut && node->getBody()) {
+ if (node->getBody()) {
breakForLoop.push(true);
node->getBody()->traverse(this);
breakForLoop.pop();
diff --git a/SPIRV/SpvBuilder.cpp b/SPIRV/SpvBuilder.cpp
index 75e622c..c327d38 100644
--- a/SPIRV/SpvBuilder.cpp
+++ b/SPIRV/SpvBuilder.cpp
@@ -1736,16 +1736,29 @@
}
// Comments in header
-void Builder::makeNewLoop()
+void Builder::makeNewLoop(bool loopTestFirst)
{
- Loop loop = { };
+ loops.push({ });
+ Loop& loop = loops.top();
- loop.function = &getBuildPoint()->getParent();
- loop.header = new Block(getUniqueId(), *loop.function);
- loop.merge = new Block(getUniqueId(), *loop.function);
- loop.test = NULL;
+ loop.function = &getBuildPoint()->getParent();
+ loop.header = new Block(getUniqueId(), *loop.function);
+ loop.merge = new Block(getUniqueId(), *loop.function);
+ // Delaying creation of the loop body perturbs test results less,
+ // which makes for easier patch review.
+ // TODO(dneto): Create the loop body block here, instead of
+ // upon first use.
+ loop.body = 0;
+ loop.testFirst = loopTestFirst;
+ loop.isFirstIteration = 0;
- loops.push(loop);
+ // The loop test is always emitted before the loop body.
+ // But if the loop test executes at the bottom of the loop, then
+ // execute the test only on the second and subsequent iterations.
+
+ // Remember the block that branches to the loop header. This
+ // is required for the test-after-body case.
+ Block* preheader = getBuildPoint();
// Branch into the loop
createBranch(loop.header);
@@ -1753,56 +1766,95 @@
// Set ourselves inside the loop
loop.function->addBlock(loop.header);
setBuildPoint(loop.header);
+
+ if (!loopTestFirst) {
+ // Generate code to defer the loop test until the second and
+ // subsequent iterations.
+
+ // A phi node determines whether we're on the first iteration.
+ loop.isFirstIteration = new Instruction(getUniqueId(), makeBoolType(), OpPhi);
+ // It's always the first iteration when coming from the preheader.
+ // All other branches to this loop header will need to indicate "false",
+ // but we don't yet know where they will come from.
+ loop.isFirstIteration->addIdOperand(makeBoolConstant(true));
+ loop.isFirstIteration->addIdOperand(preheader->getId());
+ getBuildPoint()->addInstruction(loop.isFirstIteration);
+
+ // Mark the end of the structured loop. This must exist in the loop header block.
+ createMerge(OpLoopMerge, loop.merge, LoopControlMaskNone);
+
+ // Generate code to see if this is the first iteration of the loop.
+ // It needs to be in its own block, since the loop merge and
+ // the selection merge instructions can't both be in the same
+ // (header) block.
+ Block* firstIterationCheck = new Block(getUniqueId(), *loop.function);
+ createBranch(firstIterationCheck);
+ loop.function->addBlock(firstIterationCheck);
+ setBuildPoint(firstIterationCheck);
+
+ loop.body = new Block(getUniqueId(), *loop.function);
+ // Control flow after this "if" normally reconverges at the loop body.
+ // However, the loop test has a "break branch" out of this selection
+ // construct because it can transfer control to the loop merge block.
+ createMerge(OpSelectionMerge, loop.body, SelectionControlMaskNone);
+
+ Block* loopTest = new Block(getUniqueId(), *loop.function);
+ createConditionalBranch(loop.isFirstIteration->getResultId(), loop.body, loopTest);
+
+ loop.function->addBlock(loopTest);
+ setBuildPoint(loopTest);
+ }
}
void Builder::createLoopTestBranch(Id condition)
{
Loop& loop = loops.top();
- // If loop.test exists, then we've already generated the LoopMerge
- // for this loop.
- if (!loop.test)
- createMerge(OpLoopMerge, loop.merge, LoopControlMaskNone);
+ // Generate the merge instruction. If the loop test executes before
+ // the body, then this is a loop merge. Otherwise the loop merge
+ // has already been generated and this is a conditional merge.
+ if (loop.testFirst) {
+ createMerge(OpLoopMerge, loop.merge, LoopControlMaskNone);
+ loop.body = new Block(getUniqueId(), *loop.function);
+ // Branching to the "body" block will keep control inside
+ // the loop.
+ createConditionalBranch(condition, loop.body, loop.merge);
+ loop.function->addBlock(loop.body);
+ setBuildPoint(loop.body);
+ } else {
+ // The branch to the loop merge block is the allowed exception
+ // to the structured control flow. Otherwise, control flow will
+ // continue to loop.body block. Since that is already the target
+ // of a merge instruction, and a block can't be the target of more
+ // than one merge instruction, we need to make an intermediate block.
+ Block* stayInLoopBlock = new Block(getUniqueId(), *loop.function);
+ createMerge(OpSelectionMerge, stayInLoopBlock, SelectionControlMaskNone);
- // Branching to the "body" block will keep control inside
- // the loop.
- Block* body = new Block(getUniqueId(), *loop.function);
- createConditionalBranch(condition, body, loop.merge);
- loop.function->addBlock(body);
- setBuildPoint(body);
+ // This is the loop test.
+ createConditionalBranch(condition, stayInLoopBlock, loop.merge);
+
+ // The dummy block just branches to the real loop body.
+ loop.function->addBlock(stayInLoopBlock);
+ setBuildPoint(stayInLoopBlock);
+ createBranchToBody();
+ }
}
-void Builder::endLoopHeaderWithoutTest()
+void Builder::createBranchToBody()
{
Loop& loop = loops.top();
+ assert(loop.body);
- createMerge(OpLoopMerge, loop.merge, LoopControlMaskNone);
- Block* body = new Block(getUniqueId(), *loop.function);
- createBranch(body);
- loop.function->addBlock(body);
- setBuildPoint(body);
-
- assert(!loop.test);
- loop.test = new Block(getUniqueId(), *loop.function);
-}
-
-void Builder::createBranchToLoopTest()
-{
- Loop& loop = loops.top();
- Block* testBlock = loop.test;
- assert(testBlock);
- createBranch(testBlock);
- loop.function->addBlock(testBlock);
- setBuildPoint(testBlock);
+ // This is a reconvergence of control flow, so no merge instruction
+ // is required.
+ createBranch(loop.body);
+ loop.function->addBlock(loop.body);
+ setBuildPoint(loop.body);
}
void Builder::createLoopContinue()
{
- Loop& loop = loops.top();
- if (loop.test)
- createBranch(loop.test);
- else
- createBranch(loop.header);
+ createBranchToLoopHeaderFromInside(loops.top());
// Set up a block for dead code.
createAndSetNoPredecessorBlock("post-loop-continue");
}
@@ -1821,7 +1873,7 @@
Loop& loop = loops.top();
// Branch back to the top
- createBranch(loop.header);
+ createBranchToLoopHeaderFromInside(loop);
// Add the merge block and set the build point to it
loop.function->addBlock(loop.merge);
@@ -1830,6 +1882,18 @@
loops.pop();
}
+// Create a branch to the header of the given loop, from inside
+// the loop body.
+// Adjusts the phi node for the first-iteration value if needeed.
+void Builder::createBranchToLoopHeaderFromInside(const Loop& loop)
+{
+ createBranch(loop.header);
+ if (loop.isFirstIteration) {
+ loop.isFirstIteration->addIdOperand(makeBoolConstant(false));
+ loop.isFirstIteration->addIdOperand(getBuildPoint()->getId());
+ }
+}
+
void Builder::clearAccessChain()
{
accessChain.base = 0;
diff --git a/SPIRV/SpvBuilder.h b/SPIRV/SpvBuilder.h
index 4eef5a4..de7c336 100644
--- a/SPIRV/SpvBuilder.h
+++ b/SPIRV/SpvBuilder.h
@@ -357,35 +357,25 @@
// Finish off the innermost switch.
void endSwitch(std::vector<Block*>& segmentBB);
- // Start the beginning of a new loop.
- void makeNewLoop();
+ // Start the beginning of a new loop, and prepare the builder to
+ // generate code for the loop test.
+ // The loopTestFirst parameter is true when the loop test executes before
+ // the body. (It is false for do-while loops.)
+ void makeNewLoop(bool loopTestFirst);
// Add the branch for the loop test, based on the given condition.
- // The true branch goes to the block that remains inside the loop, and
- // the false branch goes to the loop's merge block. The builder insertion
- // point will be placed at the start of the inside-the-loop block.
+ // The true branch goes to the first block in the loop body, and
+ // the false branch goes to the loop's merge block. The builder insertion
+ // point will be placed at the start of the body.
void createLoopTestBranch(Id condition);
- // Finish generating the loop header block in the case where the loop test
- // is at the bottom of the loop. It will include the LoopMerge instruction
- // and a branch to the rest of the body. The loop header block must be
- // separate from the rest of the body to make room for the the two kinds
- // of *Merge instructions that might have to occur just before a branch:
- // the loop header must have a LoopMerge as its second-last instruction,
- // and the body might begin with a conditional branch, which must have its
- // own SelectionMerge instruction.
- // Also create the basic block that will contain the loop test, but don't
- // insert it into the function yet. Any "continue" constructs in this loop
- // will branch to the loop test block. The builder insertion point will be
- // placed at the start of the body block.
- void endLoopHeaderWithoutTest();
-
- // Generate a branch to the loop test block. This can only be called if
- // the loop test is at the bottom of the loop. The builder insertion point
- // is left at the start of the test block.
- void createBranchToLoopTest();
+ // Generate an unconditional branch to the loop body. The builder insertion
+ // point will be placed at the start of the body. Use this when there is
+ // no loop test.
+ void createBranchToBody();
// Add a branch to the test of the current (innermost) loop.
+ // The way we generate code, that's also the loop header.
void createLoopContinue();
// Add an exit (e.g. "break") for the innermost loop that you're in
@@ -499,6 +489,9 @@
void createConditionalBranch(Id condition, Block* thenBlock, Block* elseBlock);
void dumpInstructions(std::vector<unsigned int>&, const std::vector<Instruction*>&) const;
+ struct Loop; // Defined below.
+ void createBranchToLoopHeaderFromInside(const Loop& loop);
+
SourceLanguage source;
int sourceVersion;
std::vector<const char*> extensions;
@@ -543,11 +536,18 @@
// to the merge block when either the loop test fails, or when a
// nested "break" is encountered.
Block* merge;
- // If not NULL, the test block is the basic block containing the loop
- // test and the conditional branch back to the header or the merge
- // block. This is created for "do-while" loops, and is the target of
- // any "continue" constructs that might exist.
- Block* test;
+ // The body block is the first basic block in the body of the loop, i.e.
+ // the code that is to be repeatedly executed, aside from loop control.
+ // This member is null until we generate code that references the loop
+ // body block.
+ Block* body;
+ // True when the loop test executes before the body.
+ bool testFirst;
+ // When the test executes after the body, this is defined as the phi
+ // instruction that tells us whether we are on the first iteration of
+ // the loop. Otherwise this is null.
+ Instruction* isFirstIteration;
+ // The function containing the loop.
Function* function;
};