1 // Copyright (c) 2017 The Khronos Group Inc.
2 // Copyright (c) 2017 Valve Corporation
3 // Copyright (c) 2017 LunarG Inc.
4 // Copyright (c) 2018 Google Inc.
5 //
6 // Licensed under the Apache License, Version 2.0 (the "License");
7 // you may not use this file except in compliance with the License.
8 // You may obtain a copy of the License at
9 //
10 //     http://www.apache.org/licenses/LICENSE-2.0
11 //
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 
18 #include "source/opt/dead_branch_elim_pass.h"
19 
20 #include <list>
21 #include <memory>
22 #include <vector>
23 
24 #include "source/cfa.h"
25 #include "source/opt/ir_context.h"
26 #include "source/opt/iterator.h"
27 #include "source/opt/struct_cfg_analysis.h"
28 #include "source/util/make_unique.h"
29 
30 namespace spvtools {
31 namespace opt {
32 
33 namespace {
34 
35 const uint32_t kBranchCondTrueLabIdInIdx = 1;
36 const uint32_t kBranchCondFalseLabIdInIdx = 2;
37 
38 }  // anonymous namespace
39 
GetConstCondition(uint32_t condId,bool * condVal)40 bool DeadBranchElimPass::GetConstCondition(uint32_t condId, bool* condVal) {
41   bool condIsConst;
42   Instruction* cInst = get_def_use_mgr()->GetDef(condId);
43   switch (cInst->opcode()) {
44     case SpvOpConstantNull:
45     case SpvOpConstantFalse: {
46       *condVal = false;
47       condIsConst = true;
48     } break;
49     case SpvOpConstantTrue: {
50       *condVal = true;
51       condIsConst = true;
52     } break;
53     case SpvOpLogicalNot: {
54       bool negVal;
55       condIsConst =
56           GetConstCondition(cInst->GetSingleWordInOperand(0), &negVal);
57       if (condIsConst) *condVal = !negVal;
58     } break;
59     default: { condIsConst = false; } break;
60   }
61   return condIsConst;
62 }
63 
GetConstInteger(uint32_t selId,uint32_t * selVal)64 bool DeadBranchElimPass::GetConstInteger(uint32_t selId, uint32_t* selVal) {
65   Instruction* sInst = get_def_use_mgr()->GetDef(selId);
66   uint32_t typeId = sInst->type_id();
67   Instruction* typeInst = get_def_use_mgr()->GetDef(typeId);
68   if (!typeInst || (typeInst->opcode() != SpvOpTypeInt)) return false;
69   // TODO(greg-lunarg): Support non-32 bit ints
70   if (typeInst->GetSingleWordInOperand(0) != 32) return false;
71   if (sInst->opcode() == SpvOpConstant) {
72     *selVal = sInst->GetSingleWordInOperand(0);
73     return true;
74   } else if (sInst->opcode() == SpvOpConstantNull) {
75     *selVal = 0;
76     return true;
77   }
78   return false;
79 }
80 
AddBranch(uint32_t labelId,BasicBlock * bp)81 void DeadBranchElimPass::AddBranch(uint32_t labelId, BasicBlock* bp) {
82   assert(get_def_use_mgr()->GetDef(labelId) != nullptr);
83   std::unique_ptr<Instruction> newBranch(
84       new Instruction(context(), SpvOpBranch, 0, 0,
85                       {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {labelId}}}));
86   context()->AnalyzeDefUse(&*newBranch);
87   context()->set_instr_block(&*newBranch, bp);
88   bp->AddInstruction(std::move(newBranch));
89 }
90 
GetParentBlock(uint32_t id)91 BasicBlock* DeadBranchElimPass::GetParentBlock(uint32_t id) {
92   return context()->get_instr_block(get_def_use_mgr()->GetDef(id));
93 }
94 
MarkLiveBlocks(Function * func,std::unordered_set<BasicBlock * > * live_blocks)95 bool DeadBranchElimPass::MarkLiveBlocks(
96     Function* func, std::unordered_set<BasicBlock*>* live_blocks) {
97   std::vector<std::pair<BasicBlock*, uint32_t>> conditions_to_simplify;
98   std::unordered_set<BasicBlock*> blocks_with_backedge;
99   std::vector<BasicBlock*> stack;
100   stack.push_back(&*func->begin());
101   bool modified = false;
102   while (!stack.empty()) {
103     BasicBlock* block = stack.back();
104     stack.pop_back();
105 
106     // Live blocks doubles as visited set.
107     if (!live_blocks->insert(block).second) continue;
108 
109     uint32_t cont_id = block->ContinueBlockIdIfAny();
110     if (cont_id != 0) {
111       AddBlocksWithBackEdge(cont_id, block->id(), block->MergeBlockIdIfAny(),
112                             &blocks_with_backedge);
113     }
114 
115     Instruction* terminator = block->terminator();
116     uint32_t live_lab_id = 0;
117     // Check if the terminator has a single valid successor.
118     if (terminator->opcode() == SpvOpBranchConditional) {
119       bool condVal;
120       if (GetConstCondition(terminator->GetSingleWordInOperand(0u), &condVal)) {
121         live_lab_id = terminator->GetSingleWordInOperand(
122             condVal ? kBranchCondTrueLabIdInIdx : kBranchCondFalseLabIdInIdx);
123       }
124     } else if (terminator->opcode() == SpvOpSwitch) {
125       uint32_t sel_val;
126       if (GetConstInteger(terminator->GetSingleWordInOperand(0u), &sel_val)) {
127         // Search switch operands for selector value, set live_lab_id to
128         // corresponding label, use default if not found.
129         uint32_t icnt = 0;
130         uint32_t case_val;
131         terminator->WhileEachInOperand(
132             [&icnt, &case_val, &sel_val, &live_lab_id](const uint32_t* idp) {
133               if (icnt == 1) {
134                 // Start with default label.
135                 live_lab_id = *idp;
136               } else if (icnt > 1) {
137                 if (icnt % 2 == 0) {
138                   case_val = *idp;
139                 } else {
140                   if (case_val == sel_val) {
141                     live_lab_id = *idp;
142                     return false;
143                   }
144                 }
145               }
146               ++icnt;
147               return true;
148             });
149       }
150     }
151 
152     // Don't simplify back edges unless it becomes a branch to the header. Every
153     // loop must have exactly one back edge to the loop header, so we cannot
154     // remove it.
155     bool simplify = false;
156     if (live_lab_id != 0) {
157       if (!blocks_with_backedge.count(block)) {
158         // This is not a back edge.
159         simplify = true;
160       } else {
161         const auto& struct_cfg_analysis = context()->GetStructuredCFGAnalysis();
162         uint32_t header_id = struct_cfg_analysis->ContainingLoop(block->id());
163         if (live_lab_id == header_id) {
164           // The new branch will be a branch to the header.
165           simplify = true;
166         }
167       }
168     }
169 
170     if (simplify) {
171       conditions_to_simplify.push_back({block, live_lab_id});
172       stack.push_back(GetParentBlock(live_lab_id));
173     } else {
174       // All successors are live.
175       const auto* const_block = block;
176       const_block->ForEachSuccessorLabel([&stack, this](const uint32_t label) {
177         stack.push_back(GetParentBlock(label));
178       });
179     }
180   }
181 
182   // Traverse |conditions_to_simplify| in reverse order.  This is done so that
183   // we simplify nested constructs before simplifying the constructs that
184   // contain them.
185   for (auto b = conditions_to_simplify.rbegin();
186        b != conditions_to_simplify.rend(); ++b) {
187     modified |= SimplifyBranch(b->first, b->second);
188   }
189 
190   return modified;
191 }
192 
SimplifyBranch(BasicBlock * block,uint32_t live_lab_id)193 bool DeadBranchElimPass::SimplifyBranch(BasicBlock* block,
194                                         uint32_t live_lab_id) {
195   Instruction* merge_inst = block->GetMergeInst();
196   Instruction* terminator = block->terminator();
197   if (merge_inst && merge_inst->opcode() == SpvOpSelectionMerge) {
198     if (merge_inst->NextNode()->opcode() == SpvOpSwitch &&
199         SwitchHasNestedBreak(block->id())) {
200       if (terminator->NumInOperands() == 2) {
201         // We cannot remove the branch, and it already has a single case, so no
202         // work to do.
203         return false;
204       }
205       // We have to keep the switch because it has a nest break, so we
206       // remove all cases except for the live one.
207       Instruction::OperandList new_operands;
208       new_operands.push_back(terminator->GetInOperand(0));
209       new_operands.push_back({SPV_OPERAND_TYPE_ID, {live_lab_id}});
210       terminator->SetInOperands(move(new_operands));
211       context()->UpdateDefUse(terminator);
212     } else {
213       // Check if the merge instruction is still needed because of a
214       // non-nested break from the construct.  Move the merge instruction if
215       // it is still needed.
216       StructuredCFGAnalysis* cfg_analysis =
217           context()->GetStructuredCFGAnalysis();
218       Instruction* first_break = FindFirstExitFromSelectionMerge(
219           live_lab_id, merge_inst->GetSingleWordInOperand(0),
220           cfg_analysis->LoopMergeBlock(live_lab_id),
221           cfg_analysis->LoopContinueBlock(live_lab_id),
222           cfg_analysis->SwitchMergeBlock(live_lab_id));
223 
224       AddBranch(live_lab_id, block);
225       context()->KillInst(terminator);
226       if (first_break == nullptr) {
227         context()->KillInst(merge_inst);
228       } else {
229         merge_inst->RemoveFromList();
230         first_break->InsertBefore(std::unique_ptr<Instruction>(merge_inst));
231         context()->set_instr_block(merge_inst,
232                                    context()->get_instr_block(first_break));
233       }
234     }
235   } else {
236     AddBranch(live_lab_id, block);
237     context()->KillInst(terminator);
238   }
239   return true;
240 }
241 
MarkUnreachableStructuredTargets(const std::unordered_set<BasicBlock * > & live_blocks,std::unordered_set<BasicBlock * > * unreachable_merges,std::unordered_map<BasicBlock *,BasicBlock * > * unreachable_continues)242 void DeadBranchElimPass::MarkUnreachableStructuredTargets(
243     const std::unordered_set<BasicBlock*>& live_blocks,
244     std::unordered_set<BasicBlock*>* unreachable_merges,
245     std::unordered_map<BasicBlock*, BasicBlock*>* unreachable_continues) {
246   for (auto block : live_blocks) {
247     if (auto merge_id = block->MergeBlockIdIfAny()) {
248       BasicBlock* merge_block = GetParentBlock(merge_id);
249       if (!live_blocks.count(merge_block)) {
250         unreachable_merges->insert(merge_block);
251       }
252       if (auto cont_id = block->ContinueBlockIdIfAny()) {
253         BasicBlock* cont_block = GetParentBlock(cont_id);
254         if (!live_blocks.count(cont_block)) {
255           (*unreachable_continues)[cont_block] = block;
256         }
257       }
258     }
259   }
260 }
261 
FixPhiNodesInLiveBlocks(Function * func,const std::unordered_set<BasicBlock * > & live_blocks,const std::unordered_map<BasicBlock *,BasicBlock * > & unreachable_continues)262 bool DeadBranchElimPass::FixPhiNodesInLiveBlocks(
263     Function* func, const std::unordered_set<BasicBlock*>& live_blocks,
264     const std::unordered_map<BasicBlock*, BasicBlock*>& unreachable_continues) {
265   bool modified = false;
266   for (auto& block : *func) {
267     if (live_blocks.count(&block)) {
268       for (auto iter = block.begin(); iter != block.end();) {
269         if (iter->opcode() != SpvOpPhi) {
270           break;
271         }
272 
273         bool changed = false;
274         bool backedge_added = false;
275         Instruction* inst = &*iter;
276         std::vector<Operand> operands;
277         // Build a complete set of operands (not just input operands). Start
278         // with type and result id operands.
279         operands.push_back(inst->GetOperand(0u));
280         operands.push_back(inst->GetOperand(1u));
281         // Iterate through the incoming labels and determine which to keep
282         // and/or modify.  If there in an unreachable continue block, there will
283         // be an edge from that block to the header.  We need to keep it to
284         // maintain the structured control flow.  If the header has more that 2
285         // incoming edges, then the OpPhi must have an entry for that edge.
286         // However, if there is only one other incoming edge, the OpPhi can be
287         // eliminated.
288         for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) {
289           BasicBlock* inc = GetParentBlock(inst->GetSingleWordInOperand(i));
290           auto cont_iter = unreachable_continues.find(inc);
291           if (cont_iter != unreachable_continues.end() &&
292               cont_iter->second == &block && inst->NumInOperands() > 4) {
293             if (get_def_use_mgr()
294                     ->GetDef(inst->GetSingleWordInOperand(i - 1))
295                     ->opcode() == SpvOpUndef) {
296               // Already undef incoming value, no change necessary.
297               operands.push_back(inst->GetInOperand(i - 1));
298               operands.push_back(inst->GetInOperand(i));
299               backedge_added = true;
300             } else {
301               // Replace incoming value with undef if this phi exists in the
302               // loop header. Otherwise, this edge is not live since the
303               // unreachable continue block will be replaced with an
304               // unconditional branch to the header only.
305               operands.emplace_back(
306                   SPV_OPERAND_TYPE_ID,
307                   std::initializer_list<uint32_t>{Type2Undef(inst->type_id())});
308               operands.push_back(inst->GetInOperand(i));
309               changed = true;
310               backedge_added = true;
311             }
312           } else if (live_blocks.count(inc) && inc->IsSuccessor(&block)) {
313             // Keep live incoming edge.
314             operands.push_back(inst->GetInOperand(i - 1));
315             operands.push_back(inst->GetInOperand(i));
316           } else {
317             // Remove incoming edge.
318             changed = true;
319           }
320         }
321 
322         if (changed) {
323           modified = true;
324           uint32_t continue_id = block.ContinueBlockIdIfAny();
325           if (!backedge_added && continue_id != 0 &&
326               unreachable_continues.count(GetParentBlock(continue_id)) &&
327               operands.size() > 4) {
328             // Changed the backedge to branch from the continue block instead
329             // of a successor of the continue block. Add an entry to the phi to
330             // provide an undef for the continue block. Since the successor of
331             // the continue must also be unreachable (dominated by the continue
332             // block), any entry for the original backedge has been removed
333             // from the phi operands.
334             operands.emplace_back(
335                 SPV_OPERAND_TYPE_ID,
336                 std::initializer_list<uint32_t>{Type2Undef(inst->type_id())});
337             operands.emplace_back(SPV_OPERAND_TYPE_ID,
338                                   std::initializer_list<uint32_t>{continue_id});
339           }
340 
341           // Either replace the phi with a single value or rebuild the phi out
342           // of |operands|.
343           //
344           // We always have type and result id operands. So this phi has a
345           // single source if there are two more operands beyond those.
346           if (operands.size() == 4) {
347             // First input data operands is at index 2.
348             uint32_t replId = operands[2u].words[0];
349             context()->ReplaceAllUsesWith(inst->result_id(), replId);
350             iter = context()->KillInst(&*inst);
351           } else {
352             // We've rewritten the operands, so first instruct the def/use
353             // manager to forget uses in the phi before we replace them. After
354             // replacing operands update the def/use manager by re-analyzing
355             // the used ids in this phi.
356             get_def_use_mgr()->EraseUseRecordsOfOperandIds(inst);
357             inst->ReplaceOperands(operands);
358             get_def_use_mgr()->AnalyzeInstUse(inst);
359             ++iter;
360           }
361         } else {
362           ++iter;
363         }
364       }
365     }
366   }
367 
368   return modified;
369 }
370 
EraseDeadBlocks(Function * func,const std::unordered_set<BasicBlock * > & live_blocks,const std::unordered_set<BasicBlock * > & unreachable_merges,const std::unordered_map<BasicBlock *,BasicBlock * > & unreachable_continues)371 bool DeadBranchElimPass::EraseDeadBlocks(
372     Function* func, const std::unordered_set<BasicBlock*>& live_blocks,
373     const std::unordered_set<BasicBlock*>& unreachable_merges,
374     const std::unordered_map<BasicBlock*, BasicBlock*>& unreachable_continues) {
375   bool modified = false;
376   for (auto ebi = func->begin(); ebi != func->end();) {
377     if (unreachable_continues.count(&*ebi)) {
378       uint32_t cont_id = unreachable_continues.find(&*ebi)->second->id();
379       if (ebi->begin() != ebi->tail() ||
380           ebi->terminator()->opcode() != SpvOpBranch ||
381           ebi->terminator()->GetSingleWordInOperand(0u) != cont_id) {
382         // Make unreachable, but leave the label.
383         KillAllInsts(&*ebi, false);
384         // Add unconditional branch to header.
385         assert(unreachable_continues.count(&*ebi));
386         ebi->AddInstruction(MakeUnique<Instruction>(
387             context(), SpvOpBranch, 0, 0,
388             std::initializer_list<Operand>{{SPV_OPERAND_TYPE_ID, {cont_id}}}));
389         get_def_use_mgr()->AnalyzeInstUse(&*ebi->tail());
390         context()->set_instr_block(&*ebi->tail(), &*ebi);
391         modified = true;
392       }
393       ++ebi;
394     } else if (unreachable_merges.count(&*ebi)) {
395       if (ebi->begin() != ebi->tail() ||
396           ebi->terminator()->opcode() != SpvOpUnreachable) {
397         // Make unreachable, but leave the label.
398         KillAllInsts(&*ebi, false);
399         // Add unreachable terminator.
400         ebi->AddInstruction(
401             MakeUnique<Instruction>(context(), SpvOpUnreachable, 0, 0,
402                                     std::initializer_list<Operand>{}));
403         context()->AnalyzeUses(ebi->terminator());
404         context()->set_instr_block(ebi->terminator(), &*ebi);
405         modified = true;
406       }
407       ++ebi;
408     } else if (!live_blocks.count(&*ebi)) {
409       // Kill this block.
410       KillAllInsts(&*ebi);
411       ebi = ebi.Erase();
412       modified = true;
413     } else {
414       ++ebi;
415     }
416   }
417 
418   return modified;
419 }
420 
EliminateDeadBranches(Function * func)421 bool DeadBranchElimPass::EliminateDeadBranches(Function* func) {
422   bool modified = false;
423   std::unordered_set<BasicBlock*> live_blocks;
424   modified |= MarkLiveBlocks(func, &live_blocks);
425 
426   std::unordered_set<BasicBlock*> unreachable_merges;
427   std::unordered_map<BasicBlock*, BasicBlock*> unreachable_continues;
428   MarkUnreachableStructuredTargets(live_blocks, &unreachable_merges,
429                                    &unreachable_continues);
430   modified |= FixPhiNodesInLiveBlocks(func, live_blocks, unreachable_continues);
431   modified |= EraseDeadBlocks(func, live_blocks, unreachable_merges,
432                               unreachable_continues);
433 
434   return modified;
435 }
436 
FixBlockOrder()437 void DeadBranchElimPass::FixBlockOrder() {
438   context()->BuildInvalidAnalyses(IRContext::kAnalysisCFG |
439                                   IRContext::kAnalysisDominatorAnalysis);
440   // Reorders blocks according to DFS of dominator tree.
441   ProcessFunction reorder_dominators = [this](Function* function) {
442     DominatorAnalysis* dominators = context()->GetDominatorAnalysis(function);
443     std::vector<BasicBlock*> blocks;
444     for (auto iter = dominators->GetDomTree().begin();
445          iter != dominators->GetDomTree().end(); ++iter) {
446       if (iter->id() != 0) {
447         blocks.push_back(iter->bb_);
448       }
449     }
450     for (uint32_t i = 1; i < blocks.size(); ++i) {
451       function->MoveBasicBlockToAfter(blocks[i]->id(), blocks[i - 1]);
452     }
453     return true;
454   };
455 
456   // Reorders blocks according to structured order.
457   ProcessFunction reorder_structured = [this](Function* function) {
458     std::list<BasicBlock*> order;
459     context()->cfg()->ComputeStructuredOrder(function, &*function->begin(),
460                                              &order);
461     std::vector<BasicBlock*> blocks;
462     for (auto block : order) {
463       blocks.push_back(block);
464     }
465     for (uint32_t i = 1; i < blocks.size(); ++i) {
466       function->MoveBasicBlockToAfter(blocks[i]->id(), blocks[i - 1]);
467     }
468     return true;
469   };
470 
471   // Structured order is more intuitive so use it where possible.
472   if (context()->get_feature_mgr()->HasCapability(SpvCapabilityShader)) {
473     context()->ProcessReachableCallTree(reorder_structured);
474   } else {
475     context()->ProcessReachableCallTree(reorder_dominators);
476   }
477 }
478 
Process()479 Pass::Status DeadBranchElimPass::Process() {
480   // Do not process if module contains OpGroupDecorate. Additional
481   // support required in KillNamesAndDecorates().
482   // TODO(greg-lunarg): Add support for OpGroupDecorate
483   for (auto& ai : get_module()->annotations())
484     if (ai.opcode() == SpvOpGroupDecorate) return Status::SuccessWithoutChange;
485   // Process all entry point functions
486   ProcessFunction pfn = [this](Function* fp) {
487     return EliminateDeadBranches(fp);
488   };
489   bool modified = context()->ProcessReachableCallTree(pfn);
490   if (modified) FixBlockOrder();
491   return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
492 }
493 
FindFirstExitFromSelectionMerge(uint32_t start_block_id,uint32_t merge_block_id,uint32_t loop_merge_id,uint32_t loop_continue_id,uint32_t switch_merge_id)494 Instruction* DeadBranchElimPass::FindFirstExitFromSelectionMerge(
495     uint32_t start_block_id, uint32_t merge_block_id, uint32_t loop_merge_id,
496     uint32_t loop_continue_id, uint32_t switch_merge_id) {
497   // To find the "first" exit, we follow branches looking for a conditional
498   // branch that is not in a nested construct and is not the header of a new
499   // construct.  We follow the control flow from |start_block_id| to find the
500   // first one.
501 
502   while (start_block_id != merge_block_id && start_block_id != loop_merge_id &&
503          start_block_id != loop_continue_id) {
504     BasicBlock* start_block = context()->get_instr_block(start_block_id);
505     Instruction* branch = start_block->terminator();
506     uint32_t next_block_id = 0;
507     switch (branch->opcode()) {
508       case SpvOpBranchConditional:
509         next_block_id = start_block->MergeBlockIdIfAny();
510         if (next_block_id == 0) {
511           // If a possible target is the |loop_merge_id| or |loop_continue_id|,
512           // which are not the current merge node, then we continue the search
513           // with the other target.
514           for (uint32_t i = 1; i < 3; i++) {
515             if (branch->GetSingleWordInOperand(i) == loop_merge_id &&
516                 loop_merge_id != merge_block_id) {
517               next_block_id = branch->GetSingleWordInOperand(3 - i);
518               break;
519             }
520             if (branch->GetSingleWordInOperand(i) == loop_continue_id &&
521                 loop_continue_id != merge_block_id) {
522               next_block_id = branch->GetSingleWordInOperand(3 - i);
523               break;
524             }
525             if (branch->GetSingleWordInOperand(i) == switch_merge_id &&
526                 switch_merge_id != merge_block_id) {
527               next_block_id = branch->GetSingleWordInOperand(3 - i);
528               break;
529             }
530           }
531 
532           if (next_block_id == 0) {
533             return branch;
534           }
535         }
536         break;
537       case SpvOpSwitch:
538         next_block_id = start_block->MergeBlockIdIfAny();
539         if (next_block_id == 0) {
540           // A switch with no merge instructions can have at most 5 targets:
541           //   a. |merge_block_id|
542           //   b. |loop_merge_id|
543           //   c. |loop_continue_id|
544           //   d. |switch_merge_id|
545           //   e. 1 block inside the current region.
546           //
547           // Note that because this is a switch, |merge_block_id| must equal
548           // |switch_merge_id|.
549           //
550           // This leads to a number of cases of what to do.
551           //
552           // 1. Does not jump to a block inside of the current construct.  In
553           // this case, there is not conditional break, so we should return
554           // |nullptr|.
555           //
556           // 2. Jumps to |merge_block_id| and a block inside the current
557           // construct.  In this case, this branch conditionally break to the
558           // end of the current construct, so return the current branch.
559           //
560           // 3.  Otherwise, this branch may break, but not to the current merge
561           // block.  So we continue with the block that is inside the loop.
562           bool found_break = false;
563           for (uint32_t i = 1; i < branch->NumInOperands(); i += 2) {
564             uint32_t target = branch->GetSingleWordInOperand(i);
565             if (target == merge_block_id) {
566               found_break = true;
567             } else if (target != loop_merge_id && target != loop_continue_id) {
568               next_block_id = branch->GetSingleWordInOperand(i);
569             }
570           }
571 
572           if (next_block_id == 0) {
573             // Case 1.
574             return nullptr;
575           }
576 
577           if (found_break) {
578             // Case 2.
579             return branch;
580           }
581 
582           // The fall through is case 3.
583         }
584         break;
585       case SpvOpBranch:
586         // Need to check if this is the header of a loop nested in the
587         // selection construct.
588         next_block_id = start_block->MergeBlockIdIfAny();
589         if (next_block_id == 0) {
590           next_block_id = branch->GetSingleWordInOperand(0);
591         }
592         break;
593       default:
594         return nullptr;
595     }
596     start_block_id = next_block_id;
597   }
598   return nullptr;
599 }
600 
AddBlocksWithBackEdge(uint32_t cont_id,uint32_t header_id,uint32_t merge_id,std::unordered_set<BasicBlock * > * blocks_with_back_edges)601 void DeadBranchElimPass::AddBlocksWithBackEdge(
602     uint32_t cont_id, uint32_t header_id, uint32_t merge_id,
603     std::unordered_set<BasicBlock*>* blocks_with_back_edges) {
604   std::unordered_set<uint32_t> visited;
605   visited.insert(cont_id);
606   visited.insert(header_id);
607   visited.insert(merge_id);
608 
609   std::vector<uint32_t> work_list;
610   work_list.push_back(cont_id);
611 
612   while (!work_list.empty()) {
613     uint32_t bb_id = work_list.back();
614     work_list.pop_back();
615 
616     BasicBlock* bb = context()->get_instr_block(bb_id);
617 
618     bool has_back_edge = false;
619     bb->ForEachSuccessorLabel([header_id, &visited, &work_list,
620                                &has_back_edge](uint32_t* succ_label_id) {
621       if (visited.insert(*succ_label_id).second) {
622         work_list.push_back(*succ_label_id);
623       }
624       if (*succ_label_id == header_id) {
625         has_back_edge = true;
626       }
627     });
628 
629     if (has_back_edge) {
630       blocks_with_back_edges->insert(bb);
631     }
632   }
633 }
634 
SwitchHasNestedBreak(uint32_t switch_header_id)635 bool DeadBranchElimPass::SwitchHasNestedBreak(uint32_t switch_header_id) {
636   std::vector<BasicBlock*> block_in_construct;
637   BasicBlock* start_block = context()->get_instr_block(switch_header_id);
638   uint32_t merge_block_id = start_block->MergeBlockIdIfAny();
639 
640   StructuredCFGAnalysis* cfg_analysis = context()->GetStructuredCFGAnalysis();
641   return !get_def_use_mgr()->WhileEachUser(
642       merge_block_id,
643       [this, cfg_analysis, switch_header_id](Instruction* inst) {
644         if (!inst->IsBranch()) {
645           return true;
646         }
647 
648         BasicBlock* bb = context()->get_instr_block(inst);
649         if (bb->id() == switch_header_id) {
650           return true;
651         }
652         return (cfg_analysis->ContainingConstruct(inst) == switch_header_id &&
653                 bb->GetMergeInst() == nullptr);
654       });
655 }
656 
657 }  // namespace opt
658 }  // namespace spvtools
659