source/opt/loop_descriptor.cpp

   1 // Copyright (c) 2017 Google Inc.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #include "opt/loop_descriptor.h"
  16 #include <iostream>
  17 #include <type_traits>
  18 #include <utility>
  19 #include <vector>
  20
  21 #include "opt/cfg.h"
  22 #include "opt/dominator_tree.h"
  23 #include "opt/ir_builder.h"
  24 #include "opt/ir_context.h"
  25 #include "opt/iterator.h"
  26 #include "opt/make_unique.h"
  27 #include "opt/tree_iterator.h"
  28
  29 namespace spvtools {
  30 namespace ir {
  31
  32 Loop::Loop(IRContext* context, opt::DominatorAnalysis* dom_analysis,
  33            BasicBlock* header, BasicBlock* continue_target,
  34            BasicBlock* merge_target)
  35     : context_(context),
  36       loop_header_(header),
  37       loop_continue_(continue_target),
  38       loop_merge_(merge_target),
  39       loop_preheader_(nullptr),
  40       parent_(nullptr) {
  41   assert(context);
  42   assert(dom_analysis);
  43   loop_preheader_ = FindLoopPreheader(dom_analysis);
  44   AddBasicBlockToLoop(header);
  45   AddBasicBlockToLoop(continue_target);
  46 }
  47
  48 BasicBlock* Loop::FindLoopPreheader(opt::DominatorAnalysis* dom_analysis) {
  49   CFG* cfg = context_->cfg();
  50   opt::DominatorTree& dom_tree = dom_analysis->GetDomTree();
  51   opt::DominatorTreeNode* header_node = dom_tree.GetTreeNode(loop_header_);
  52
  53   // The loop predecessor.
  54   BasicBlock* loop_pred = nullptr;
  55
  56   auto header_pred = cfg->preds(loop_header_->id());
  57   for (uint32_t p_id : header_pred) {
  58     opt::DominatorTreeNode* node = dom_tree.GetTreeNode(p_id);
  59     if (node && !dom_tree.Dominates(header_node, node)) {
  60       // The predecessor is not part of the loop, so potential loop preheader.
  61       if (loop_pred && node->bb_ != loop_pred) {
  62         // If we saw 2 distinct predecessors that are outside the loop, we don't
  63         // have a loop preheader.
  64         return nullptr;
  65       }
  66       loop_pred = node->bb_;
  67     }
  68   }
  69   // Safe guard against invalid code, SPIR-V spec forbids loop with the entry
  70   // node as header.
  71   assert(loop_pred && "The header node is the entry block ?");
  72
  73   // So we have a unique basic block that can enter this loop.
  74   // If this loop is the unique successor of this block, then it is a loop
  75   // preheader.
  76   bool is_preheader = true;
  77   uint32_t loop_header_id = loop_header_->id();
  78   const auto* const_loop_pred = loop_pred;
  79   const_loop_pred->ForEachSuccessorLabel(
  80       [&is_preheader, loop_header_id](const uint32_t id) {
  81         if (id != loop_header_id) is_preheader = false;
  82       });
  83   if (is_preheader) return loop_pred;
  84   return nullptr;
  85 }
  86
  87 bool Loop::IsInsideLoop(Instruction* inst) const {
  88   const BasicBlock* parent_block = context_->get_instr_block(inst);
  89   if (!parent_block) return false;
  90   return IsInsideLoop(parent_block);
  91 }
  92
  93 bool Loop::IsBasicBlockInLoopSlow(const BasicBlock* bb) {
  94   assert(bb->GetParent() && "The basic block does not belong to a function");
  95
  96   opt::DominatorAnalysis* dom_analysis =
  97       context_->GetDominatorAnalysis(bb->GetParent(), *context_->cfg());
  98   if (!dom_analysis->Dominates(GetHeaderBlock(), bb)) return false;
  99
 100   opt::PostDominatorAnalysis* postdom_analysis =
 101       context_->GetPostDominatorAnalysis(bb->GetParent(), *context_->cfg());
 102   if (!postdom_analysis->Dominates(GetMergeBlock(), bb)) return false;
 103   return true;
 104 }
 105
 106 BasicBlock* Loop::GetOrCreatePreHeaderBlock() {
 107   if (loop_preheader_) return loop_preheader_;
 108
 109   Function* fn = loop_header_->GetParent();
 110   // Find the insertion point for the preheader.
 111   Function::iterator header_it =
 112       std::find_if(fn->begin(), fn->end(),
 113                    [this](BasicBlock& bb) { return &bb == loop_header_; });
 114   assert(header_it != fn->end());
 115
 116   // Create the preheader basic block.
 117   loop_preheader_ = &*header_it.InsertBefore(std::unique_ptr<ir::BasicBlock>(
 118       new ir::BasicBlock(std::unique_ptr<ir::Instruction>(new ir::Instruction(
 119           context_, SpvOpLabel, 0, context_->TakeNextId(), {})))));
 120   loop_preheader_->SetParent(fn);
 121   uint32_t loop_preheader_id = loop_preheader_->id();
 122
 123   // Redirect the branches and patch the phi:
 124   //  - For each phi instruction in the header:
 125   //    - If the header has only 1 out-of-loop incoming branch:
 126   //      - Change the incomning branch to be the preheader.
 127   //    - If the header has more than 1 out-of-loop incoming branch:
 128   //      - Create a new phi in the preheader, gathering all out-of-loops
 129   //      incoming values;
 130   //      - Patch the header phi instruction to use the preheader phi
 131   //      instruction;
 132   //  - Redirect all edges coming from outside the loop to the preheader.
 133   opt::InstructionBuilder builder(
 134       context_, loop_preheader_,
 135       ir::IRContext::kAnalysisDefUse |
 136           ir::IRContext::kAnalysisInstrToBlockMapping);
 137   // Patch all the phi instructions.
 138   loop_header_->ForEachPhiInst([&builder, this](Instruction* phi) {
 139     std::vector<uint32_t> preheader_phi_ops;
 140     std::vector<uint32_t> header_phi_ops;
 141     for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) {
 142       uint32_t def_id = phi->GetSingleWordInOperand(i);
 143       uint32_t branch_id = phi->GetSingleWordInOperand(i + 1);
 144       if (IsInsideLoop(branch_id)) {
 145         header_phi_ops.push_back(def_id);
 146         header_phi_ops.push_back(branch_id);
 147       } else {
 148         preheader_phi_ops.push_back(def_id);
 149         preheader_phi_ops.push_back(branch_id);
 150       }
 151     }
 152
 153     Instruction* preheader_insn_def = nullptr;
 154     // Create a phi instruction if and only if the preheader_phi_ops has more
 155     // than one pair.
 156     if (preheader_phi_ops.size() > 2)
 157       preheader_insn_def = builder.AddPhi(phi->type_id(), preheader_phi_ops);
 158     else
 159       preheader_insn_def =
 160           context_->get_def_use_mgr()->GetDef(preheader_phi_ops[0]);
 161     // Build the new incoming edge.
 162     header_phi_ops.push_back(preheader_insn_def->result_id());
 163     header_phi_ops.push_back(loop_preheader_->id());
 164     // Rewrite operands of the header's phi instruction.
 165     uint32_t idx = 0;
 166     for (; idx < header_phi_ops.size(); idx++)
 167       phi->SetInOperand(idx, {header_phi_ops[idx]});
 168     // Remove extra operands, from last to first (more efficient).
 169     for (uint32_t j = phi->NumInOperands() - 1; j >= idx; j--)
 170       phi->RemoveInOperand(j);
 171   });
 172   // Branch from the preheader to the header.
 173   builder.AddBranch(loop_header_->id());
 174
 175   // Redirect all out of loop branches to the header to the preheader.
 176   CFG* cfg = context_->cfg();
 177   cfg->RegisterBlock(loop_preheader_);
 178   for (uint32_t pred_id : cfg->preds(loop_header_->id())) {
 179     if (pred_id == loop_preheader_->id()) continue;
 180     if (IsInsideLoop(pred_id)) continue;
 181     BasicBlock* pred = cfg->block(pred_id);
 182     pred->ForEachSuccessorLabel([this, loop_preheader_id](uint32_t* id) {
 183       if (*id == loop_header_->id()) *id = loop_preheader_id;
 184     });
 185     cfg->AddEdge(pred_id, loop_preheader_id);
 186   }
 187   // Delete predecessors that are no longer predecessors of the loop header.
 188   cfg->RemoveNonExistingEdges(loop_header_->id());
 189   // Update the loop descriptors.
 190   if (HasParent()) {
 191     GetParent()->AddBasicBlock(loop_preheader_);
 192     context_->GetLoopDescriptor(fn)->SetBasicBlockToLoop(loop_preheader_->id(),
 193                                                          GetParent());
 194   }
 195
 196   context_->InvalidateAnalysesExceptFor(
 197       builder.GetPreservedAnalysis() |
 198       ir::IRContext::Analysis::kAnalysisLoopAnalysis |
 199       ir::IRContext::kAnalysisCFG);
 200
 201   return loop_preheader_;
 202 }
 203
 204 void Loop::SetLatchBlock(BasicBlock* latch) {
 205 #ifndef NDEBUG
 206   assert(latch->GetParent() && "The basic block does not belong to a function");
 207
 208   const auto* const_latch = latch;
 209   const_latch->ForEachSuccessorLabel([this](uint32_t id) {
 210     assert((!IsInsideLoop(id) || id == GetHeaderBlock()->id()) &&
 211            "A predecessor of the continue block does not belong to the loop");
 212   });
 213 #endif  // NDEBUG
 214   assert(IsInsideLoop(latch) && "The continue block is not in the loop");
 215
 216   SetLatchBlockImpl(latch);
 217 }
 218
 219 void Loop::SetMergeBlock(BasicBlock* merge) {
 220 #ifndef NDEBUG
 221   assert(merge->GetParent() && "The basic block does not belong to a function");
 222   CFG& cfg = *merge->GetParent()->GetParent()->context()->cfg();
 223
 224   for (uint32_t pred : cfg.preds(merge->id())) {
 225     assert(IsInsideLoop(pred) &&
 226            "A predecessor of the merge block does not belong to the loop");
 227   }
 228   assert(!IsInsideLoop(merge) && "The merge block is in the loop");
 229 #endif  // NDEBUG
 230
 231   SetMergeBlockImpl(merge);
 232   if (GetHeaderBlock()->GetLoopMergeInst()) {
 233     UpdateLoopMergeInst();
 234   }
 235 }
 236
 237 void Loop::GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const {
 238   ir::CFG* cfg = context_->cfg();
 239   exit_blocks->clear();
 240
 241   for (uint32_t bb_id : GetBlocks()) {
 242     const spvtools::ir::BasicBlock* bb = cfg->block(bb_id);
 243     bb->ForEachSuccessorLabel([exit_blocks, this](uint32_t succ) {
 244       if (!IsInsideLoop(succ)) {
 245         exit_blocks->insert(succ);
 246       }
 247     });
 248   }
 249 }
 250
 251 void Loop::GetMergingBlocks(
 252     std::unordered_set<uint32_t>* merging_blocks) const {
 253   assert(GetMergeBlock() && "This loop is not structured");
 254   ir::CFG* cfg = context_->cfg();
 255   merging_blocks->clear();
 256
 257   std::stack<const ir::BasicBlock*> to_visit;
 258   to_visit.push(GetMergeBlock());
 259   while (!to_visit.empty()) {
 260     const ir::BasicBlock* bb = to_visit.top();
 261     to_visit.pop();
 262     merging_blocks->insert(bb->id());
 263     for (uint32_t pred_id : cfg->preds(bb->id())) {
 264       if (!IsInsideLoop(pred_id) && !merging_blocks->count(pred_id)) {
 265         to_visit.push(cfg->block(pred_id));
 266       }
 267     }
 268   }
 269 }
 270
 271 bool Loop::IsLCSSA() const {
 272   ir::CFG* cfg = context_->cfg();
 273   opt::analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();
 274
 275   std::unordered_set<uint32_t> exit_blocks;
 276   GetExitBlocks(&exit_blocks);
 277
 278   // Declare ir_context so we can capture context_ in the below lambda
 279   ir::IRContext* ir_context = context_;
 280
 281   for (uint32_t bb_id : GetBlocks()) {
 282     for (Instruction& insn : *cfg->block(bb_id)) {
 283       // All uses must be either:
 284       //  - In the loop;
 285       //  - In an exit block and in a phi instruction.
 286       if (!def_use_mgr->WhileEachUser(
 287               &insn,
 288               [&exit_blocks, ir_context, this](ir::Instruction* use) -> bool {
 289                 BasicBlock* parent = ir_context->get_instr_block(use);
 290                 assert(parent && "Invalid analysis");
 291                 if (IsInsideLoop(parent)) return true;
 292                 if (use->opcode() != SpvOpPhi) return false;
 293                 return exit_blocks.count(parent->id());
 294               }))
 295         return false;
 296     }
 297   }
 298   return true;
 299 }
 300
 301 bool Loop::ShouldHoistInstruction(IRContext* context, Instruction* inst) {
 302   return AreAllOperandsOutsideLoop(context, inst) &&
 303          inst->IsOpcodeCodeMotionSafe();
 304 }
 305
 306 bool Loop::AreAllOperandsOutsideLoop(IRContext* context, Instruction* inst) {
 307   opt::analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
 308   bool all_outside_loop = true;
 309
 310   const std::function<void(uint32_t*)> operand_outside_loop =
 311       [this, &def_use_mgr, &all_outside_loop](uint32_t* id) {
 312         if (this->IsInsideLoop(def_use_mgr->GetDef(*id))) {
 313           all_outside_loop = false;
 314           return;
 315         }
 316       };
 317
 318   inst->ForEachInId(operand_outside_loop);
 319   return all_outside_loop;
 320 }
 321
 322 LoopDescriptor::LoopDescriptor(const Function* f) : loops_() {
 323   PopulateList(f);
 324 }
 325
 326 LoopDescriptor::~LoopDescriptor() { ClearLoops(); }
 327
 328 void LoopDescriptor::PopulateList(const Function* f) {
 329   IRContext* context = f->GetParent()->context();
 330   opt::DominatorAnalysis* dom_analysis =
 331       context->GetDominatorAnalysis(f, *context->cfg());
 332
 333   ClearLoops();
 334
 335   // Post-order traversal of the dominator tree to find all the OpLoopMerge
 336   // instructions.
 337   opt::DominatorTree& dom_tree = dom_analysis->GetDomTree();
 338   for (opt::DominatorTreeNode& node :
 339        ir::make_range(dom_tree.post_begin(), dom_tree.post_end())) {
 340     Instruction* merge_inst = node.bb_->GetLoopMergeInst();
 341     if (merge_inst) {
 342       // The id of the merge basic block of this loop.
 343       uint32_t merge_bb_id = merge_inst->GetSingleWordOperand(0);
 344
 345       // The id of the continue basic block of this loop.
 346       uint32_t continue_bb_id = merge_inst->GetSingleWordOperand(1);
 347
 348       // The merge target of this loop.
 349       BasicBlock* merge_bb = context->cfg()->block(merge_bb_id);
 350
 351       // The continue target of this loop.
 352       BasicBlock* continue_bb = context->cfg()->block(continue_bb_id);
 353
 354       // The basic block containing the merge instruction.
 355       BasicBlock* header_bb = context->get_instr_block(merge_inst);
 356
 357       // Add the loop to the list of all the loops in the function.
 358       Loop* current_loop =
 359           new Loop(context, dom_analysis, header_bb, continue_bb, merge_bb);
 360       loops_.push_back(current_loop);
 361
 362       // We have a bottom-up construction, so if this loop has nested-loops,
 363       // they are by construction at the tail of the loop list.
 364       for (auto itr = loops_.rbegin() + 1; itr != loops_.rend(); ++itr) {
 365         Loop* previous_loop = *itr;
 366
 367         // If the loop already has a parent, then it has been processed.
 368         if (previous_loop->HasParent()) continue;
 369
 370         // If the current loop does not dominates the previous loop then it is
 371         // not nested loop.
 372         if (!dom_analysis->Dominates(header_bb,
 373                                      previous_loop->GetHeaderBlock()))
 374           continue;
 375         // If the current loop merge dominates the previous loop then it is
 376         // not nested loop.
 377         if (dom_analysis->Dominates(merge_bb, previous_loop->GetHeaderBlock()))
 378           continue;
 379
 380         current_loop->AddNestedLoop(previous_loop);
 381       }
 382       opt::DominatorTreeNode* dom_merge_node = dom_tree.GetTreeNode(merge_bb);
 383       for (opt::DominatorTreeNode& loop_node :
 384            make_range(node.df_begin(), node.df_end())) {
 385         // Check if we are in the loop.
 386         if (dom_tree.Dominates(dom_merge_node, &loop_node)) continue;
 387         current_loop->AddBasicBlockToLoop(loop_node.bb_);
 388         basic_block_to_loop_.insert(
 389             std::make_pair(loop_node.bb_->id(), current_loop));
 390       }
 391     }
 392   }
 393   for (Loop* loop : loops_) {
 394     if (!loop->HasParent()) dummy_top_loop_.nested_loops_.push_back(loop);
 395   }
 396 }
 397
 398 void LoopDescriptor::ClearLoops() {
 399   for (Loop* loop : loops_) {
 400     delete loop;
 401   }
 402   loops_.clear();
 403 }
 404
 405 }  // namespace ir
 406 }  // namespace spvtools