From 7819bee82c5caafba1f2fdae2b8f1a9a9419bd67 Mon Sep 17 00:00:00 2001 From: Dejan Mircevski Date: Mon, 11 Jan 2016 09:35:22 -0500 Subject: [PATCH] Switch loops stack to use LoopBlocks. Also remove dead code. Change-Id: I2c0177d8cab48b7d6f9442715aecb7951597f3c8 --- SPIRV/SpvBuilder.cpp | 154 ++------------------------------------------------- SPIRV/SpvBuilder.h | 75 ++++--------------------- 2 files changed, 16 insertions(+), 213 deletions(-) diff --git a/SPIRV/SpvBuilder.cpp b/SPIRV/SpvBuilder.cpp index 8e023ea..eb8c4d3 100755 --- a/SPIRV/SpvBuilder.cpp +++ b/SPIRV/SpvBuilder.cpp @@ -1761,155 +1761,31 @@ Block& Builder::makeNewBlock() return *block; } -Builder::LoopBlocks Builder::makeNewLoop() +Builder::LoopBlocks& Builder::makeNewLoop() { - return {makeNewBlock(), makeNewBlock(), makeNewBlock()}; -} - -// Comments in header -void Builder::makeNewLoop(bool loopTestFirst) -{ - loops.push(Loop(*this, loopTestFirst)); - const Loop& loop = loops.top(); - - // 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); - - // 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. - - // 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. - createLoopMerge(loop.merge, loop.header, 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); - - // 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. - createSelectionMerge(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) -{ - const Loop& loop = loops.top(); - - // 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) { - createLoopMerge(loop.merge, loop.header, LoopControlMaskNone); - // 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); - createSelectionMerge(stayInLoopBlock, SelectionControlMaskNone); - - // 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::createBranchToBody() -{ - const Loop& loop = loops.top(); - assert(loop.body); - - // This is a reconvergence of control flow, so no merge instruction - // is required. - createBranch(loop.body); - loop.function->addBlock(loop.body); - setBuildPoint(loop.body); + loops.push({makeNewBlock(), makeNewBlock(), makeNewBlock()}); + return loops.top(); } void Builder::createLoopContinue() { - createBranchToLoopHeaderFromInside(loops.top()); + createBranch(&loops.top().continue_target); // Set up a block for dead code. createAndSetNoPredecessorBlock("post-loop-continue"); } -// Add an exit (e.g. "break") for the innermost loop that you're in void Builder::createLoopExit() { - createBranch(loops.top().merge); + createBranch(&loops.top().merge); // Set up a block for dead code. createAndSetNoPredecessorBlock("post-loop-break"); } -// Close the innermost loop void Builder::closeLoop() { - const Loop& loop = loops.top(); - - // Branch back to the top - createBranchToLoopHeaderFromInside(loop); - - // Add the merge block and set the build point to it - loop.function->addBlock(loop.merge); - setBuildPoint(loop.merge); - 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 = NoResult; @@ -2273,24 +2149,4 @@ void MissingFunctionality(const char* fun) exit(1); } -Builder::Loop::Loop(Builder& builder, bool testFirstArg) - : function(&builder.getBuildPoint()->getParent()), - header(new Block(builder.getUniqueId(), *function)), - merge(new Block(builder.getUniqueId(), *function)), - body(new Block(builder.getUniqueId(), *function)), - testFirst(testFirstArg), - isFirstIteration(nullptr) -{ - if (!testFirst) - { -// You may be tempted to rewrite this as -// new Instruction(builder.getUniqueId(), builder.makeBoolType(), OpPhi); -// This will cause subtle test failures because builder.getUniqueId(), -// and builder.makeBoolType() can then get run in a compiler-specific -// order making tests fail for certain configurations. - Id instructionId = builder.getUniqueId(); - isFirstIteration = new Instruction(instructionId, builder.makeBoolType(), OpPhi); - } -} - }; // end spv namespace diff --git a/SPIRV/SpvBuilder.h b/SPIRV/SpvBuilder.h index d3e7ad9..a1ed84c 100755 --- a/SPIRV/SpvBuilder.h +++ b/SPIRV/SpvBuilder.h @@ -373,35 +373,24 @@ public: // Finish off the innermost switch. void endSwitch(std::vector& segmentBB); - // 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); struct LoopBlocks { Block &body, &merge, &continue_target; }; - LoopBlocks makeNewLoop(); - // Create a new block in the function containing the build point. - Block& makeNewBlock(); - - // Add the branch for the loop test, based on the given condition. - // 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); + // Start a new loop and prepare the builder to generate code for it. Until + // closeLoop() is called for this loop, createLoopContinue() and + // createLoopExit() will target its corresponding blocks. + LoopBlocks& makeNewLoop(); - // 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(); + // Create a new block in the function containing the build point. Memory is + // owned by the function object. + Block& makeNewBlock(); - // Add a branch to the test of the current (innermost) loop. - // The way we generate code, that's also the loop header. + // Add a branch to the continue_target of the current (innermost) loop. void createLoopContinue(); - // Add an exit (e.g. "break") for the innermost loop that you're in + // Add an exit (e.g. "break") from the innermost loop that we're currently + // in. void createLoopExit(); // Close the innermost loop that you're in @@ -517,9 +506,6 @@ public: void createSelectionMerge(Block* mergeBlock, unsigned int control); void dumpInstructions(std::vector&, const std::vector&) const; - struct Loop; // Defined below. - void createBranchToLoopHeaderFromInside(const Loop& loop); - SourceLanguage source; int sourceVersion; std::vector extensions; @@ -550,47 +536,8 @@ public: // stack of switches std::stack switchMerges; - // Data that needs to be kept in order to properly handle loops. - struct Loop { - // Constructs a default Loop structure containing new header, merge, and - // body blocks for the current function. - // The testFirst argument indicates whether the loop test executes at - // the top of the loop rather than at the bottom. In the latter case, - // also create a phi instruction whose value indicates whether we're on - // the first iteration of the loop. The phi instruction is initialized - // with no values or predecessor operands. - Loop(Builder& builder, bool testFirst); - - // The function containing the loop. - Function* const function; - // The header is the first block generated for the loop. - // It dominates all the blocks in the loop, i.e. it is always - // executed before any others. - // If the loop test is executed before the body (as in "while" and - // "for" loops), then the header begins with the test code. - // Otherwise, the loop is a "do-while" loop and the header contains the - // start of the body of the loop (if the body exists). - Block* const header; - // The merge block marks the end of the loop. Control is transferred - // to the merge block when either the loop test fails, or when a - // nested "break" is encountered. - Block* const merge; - // 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* const body; - // True when the loop test executes before the body. - const 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. This is non-const because - // it has to be initialized outside of the initializer-list. - Instruction* isFirstIteration; - }; - // Our loop stack. - std::stack loops; + std::stack loops; }; // end Builder class // Use for non-fatal notes about what's not complete -- 2.7.4