| 1 |
// Copyright (c) 2018 Google LLC. |
| 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 <algorithm> |
| 16 |
#include <memory> |
| 17 |
#include <unordered_map> |
| 18 |
#include <unordered_set> |
| 19 |
#include <utility> |
| 20 |
#include <vector> |
| 21 |
|
| 22 |
#include "source/cfa.h" |
| 23 |
#include "source/opt/cfg.h" |
| 24 |
#include "source/opt/ir_builder.h" |
| 25 |
#include "source/opt/ir_context.h" |
| 26 |
#include "source/opt/loop_descriptor.h" |
| 27 |
#include "source/opt/loop_utils.h" |
| 28 |
|
| 29 |
namespace spvtools { |
| 30 |
namespace opt { |
| 31 |
|
| 32 |
namespace { |
| 33 |
// Return true if |bb| is dominated by at least one block in |exits| |
| 34 |
static inline bool DominatesAnExit(BasicBlock* bb, |
| 35 |
const std::unordered_set<BasicBlock*>& exits, |
| 36 |
const DominatorTree& dom_tree) { |
| 37 |
for (BasicBlock* e_bb : exits) |
| 38 |
if (dom_tree.Dominates(bb, e_bb)) return true; |
| 39 |
return false; |
| 40 |
} |
| 41 |
|
| 42 |
// Utility class to rewrite out-of-loop uses of an in-loop definition in terms |
| 43 |
// of phi instructions to achieve a LCSSA form. |
| 44 |
// For a given definition, the class user registers phi instructions using that |
| 45 |
// definition in all loop exit blocks by which the definition escapes. |
| 46 |
// Then, when rewriting a use of the definition, the rewriter walks the |
| 47 |
// paths from the use the loop exits. At each step, it will insert a phi |
| 48 |
// instruction to merge the incoming value according to exit blocks definition. |
| 49 |
class LCSSARewriter { |
| 50 |
public: |
| 51 |
LCSSARewriter(IRContext* context, const DominatorTree& dom_tree, |
| 52 |
const std::unordered_set<BasicBlock*>& exit_bb, |
| 53 |
BasicBlock* merge_block) |
| 54 |
: context_(context), |
| 55 |
cfg_(context_->cfg()), |
| 56 |
dom_tree_(dom_tree), |
| 57 |
exit_bb_(exit_bb), |
| 58 |
merge_block_id_(merge_block ? merge_block->id() : 0) {} |
| 59 |
|
| 60 |
struct UseRewriter { |
| 61 |
explicit UseRewriter(LCSSARewriter* base, const Instruction& def_insn) |
| 62 |
: base_(base), def_insn_(def_insn) {} |
| 63 |
// Rewrites the use of |def_insn_| by the instruction |user| at the index |
| 64 |
// |operand_index| in terms of phi instruction. This recursively builds new |
| 65 |
// phi instructions from |user| to the loop exit blocks' phis. The use of |
| 66 |
// |def_insn_| in |user| is replaced by the relevant phi instruction at the |
| 67 |
// end of the operation. |
| 68 |
// It is assumed that |user| does not dominates any of the loop exit basic |
| 69 |
// block. This operation does not update the def/use manager, instead it |
| 70 |
// records what needs to be updated. The actual update is performed by |
| 71 |
// UpdateManagers. |
| 72 |
void RewriteUse(BasicBlock* bb, Instruction* user, uint32_t operand_index) { |
| 73 |
assert( |
| 74 |
(user->opcode() != SpvOpPhi || bb != GetParent(user)) && |
| 75 |
"The root basic block must be the incoming edge if |user| is a phi " |
| 76 |
"instruction"); |
| 77 |
assert((user->opcode() == SpvOpPhi || bb == GetParent(user)) && |
| 78 |
"The root basic block must be the instruction parent if |user| is " |
| 79 |
"not " |
| 80 |
"phi instruction"); |
| 81 |
|
| 82 |
Instruction* new_def = GetOrBuildIncoming(bb->id()); |
| 83 |
|
| 84 |
user->SetOperand(operand_index, {new_def->result_id()}); |
| 85 |
rewritten_.insert(user); |
| 86 |
} |
| 87 |
|
| 88 |
// In-place update of some managers (avoid full invalidation). |
| 89 |
inline void UpdateManagers() { |
| 90 |
analysis::DefUseManager* def_use_mgr = base_->context_->get_def_use_mgr(); |
| 91 |
// Register all new definitions. |
| 92 |
for (Instruction* insn : rewritten_) { |
| 93 |
def_use_mgr->AnalyzeInstDef(insn); |
| 94 |
} |
| 95 |
// Register all new uses. |
| 96 |
for (Instruction* insn : rewritten_) { |
| 97 |
def_use_mgr->AnalyzeInstUse(insn); |
| 98 |
} |
| 99 |
} |
| 100 |
|
| 101 |
private: |
| 102 |
// Return the basic block that |instr| belongs to. |
| 103 |
BasicBlock* GetParent(Instruction* instr) { |
| 104 |
return base_->context_->get_instr_block(instr); |
| 105 |
} |
| 106 |
|
| 107 |
// Builds a phi instruction for the basic block |bb|. The function assumes |
| 108 |
// that |defining_blocks| contains the list of basic block that define the |
| 109 |
// usable value for each predecessor of |bb|. |
| 110 |
inline Instruction* CreatePhiInstruction( |
| 111 |
BasicBlock* bb, const std::vector<uint32_t>& defining_blocks) { |
| 112 |
std::vector<uint32_t> incomings; |
| 113 |
const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); |
| 114 |
assert(bb_preds.size() == defining_blocks.size()); |
| 115 |
for (size_t i = 0; i < bb_preds.size(); i++) { |
| 116 |
incomings.push_back( |
| 117 |
GetOrBuildIncoming(defining_blocks[i])->result_id()); |
| 118 |
incomings.push_back(bb_preds[i]); |
| 119 |
} |
| 120 |
InstructionBuilder builder(base_->context_, &*bb->begin(), |
| 121 |
IRContext::kAnalysisInstrToBlockMapping); |
| 122 |
Instruction* incoming_phi = |
| 123 |
builder.AddPhi(def_insn_.type_id(), incomings); |
| 124 |
|
| 125 |
rewritten_.insert(incoming_phi); |
| 126 |
return incoming_phi; |
| 127 |
} |
| 128 |
|
| 129 |
// Builds a phi instruction for the basic block |bb|, all incoming values |
| 130 |
// will be |value|. |
| 131 |
inline Instruction* CreatePhiInstruction(BasicBlock* bb, |
| 132 |
const Instruction& value) { |
| 133 |
std::vector<uint32_t> incomings; |
| 134 |
const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); |
| 135 |
for (size_t i = 0; i < bb_preds.size(); i++) { |
| 136 |
incomings.push_back(value.result_id()); |
| 137 |
incomings.push_back(bb_preds[i]); |
| 138 |
} |
| 139 |
InstructionBuilder builder(base_->context_, &*bb->begin(), |
| 140 |
IRContext::kAnalysisInstrToBlockMapping); |
| 141 |
Instruction* incoming_phi = |
| 142 |
builder.AddPhi(def_insn_.type_id(), incomings); |
| 143 |
|
| 144 |
rewritten_.insert(incoming_phi); |
| 145 |
return incoming_phi; |
| 146 |
} |
| 147 |
|
| 148 |
// Return the new def to use for the basic block |bb_id|. |
| 149 |
// If |bb_id| does not have a suitable def to use then we: |
| 150 |
// - return the common def used by all predecessors; |
| 151 |
// - if there is no common def, then we build a new phi instr at the |
| 152 |
// beginning of |bb_id| and return this new instruction. |
| 153 |
Instruction* GetOrBuildIncoming(uint32_t bb_id) { |
| 154 |
assert(base_->cfg_->block(bb_id) != nullptr && "Unknown basic block"); |
| 155 |
|
| 156 |
Instruction*& incoming_phi = bb_to_phi_[bb_id]; |
| 157 |
if (incoming_phi) { |
| 158 |
return incoming_phi; |
| 159 |
} |
| 160 |
|
| 161 |
BasicBlock* bb = &*base_->cfg_->block(bb_id); |
| 162 |
// If this is an exit basic block, look if there already is an eligible |
| 163 |
// phi instruction. An eligible phi has |def_insn_| as all incoming |
| 164 |
// values. |
| 165 |
if (base_->exit_bb_.count(bb)) { |
| 166 |
// Look if there is an eligible phi in this block. |
| 167 |
if (!bb->WhileEachPhiInst([&incoming_phi, this](Instruction* phi) { |
| 168 |
for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { |
| 169 |
if (phi->GetSingleWordInOperand(i) != def_insn_.result_id()) |
| 170 |
return true; |
| 171 |
} |
| 172 |
incoming_phi = phi; |
| 173 |
rewritten_.insert(incoming_phi); |
| 174 |
return false; |
| 175 |
})) { |
| 176 |
return incoming_phi; |
| 177 |
} |
| 178 |
incoming_phi = CreatePhiInstruction(bb, def_insn_); |
| 179 |
return incoming_phi; |
| 180 |
} |
| 181 |
|
| 182 |
// Get the block that defines the value to use for each predecessor. |
| 183 |
// If the vector has 1 value, then it means that this block does not need |
| 184 |
// to build a phi instruction unless |bb_id| is the loop merge block. |
| 185 |
const std::vector<uint32_t>& defining_blocks = |
| 186 |
base_->GetDefiningBlocks(bb_id); |
| 187 |
|
| 188 |
// Special case for structured loops: merge block might be different from |
| 189 |
// the exit block set. To maintain structured properties it will ease |
| 190 |
// transformations if the merge block also holds a phi instruction like |
| 191 |
// the exit ones. |
| 192 |
if (defining_blocks.size() > 1 || bb_id == base_->merge_block_id_) { |
| 193 |
if (defining_blocks.size() > 1) { |
| 194 |
incoming_phi = CreatePhiInstruction(bb, defining_blocks); |
| 195 |
} else { |
| 196 |
assert(bb_id == base_->merge_block_id_); |
| 197 |
incoming_phi = |
| 198 |
CreatePhiInstruction(bb, *GetOrBuildIncoming(defining_blocks[0])); |
| 199 |
} |
| 200 |
} else { |
| 201 |
incoming_phi = GetOrBuildIncoming(defining_blocks[0]); |
| 202 |
} |
| 203 |
|
| 204 |
return incoming_phi; |
| 205 |
} |
| 206 |
|
| 207 |
LCSSARewriter* base_; |
| 208 |
const Instruction& def_insn_; |
| 209 |
std::unordered_map<uint32_t, Instruction*> bb_to_phi_; |
| 210 |
std::unordered_set<Instruction*> rewritten_; |
| 211 |
}; |
| 212 |
|
| 213 |
private: |
| 214 |
// Return the new def to use for the basic block |bb_id|. |
| 215 |
// If |bb_id| does not have a suitable def to use then we: |
| 216 |
// - return the common def used by all predecessors; |
| 217 |
// - if there is no common def, then we build a new phi instr at the |
| 218 |
// beginning of |bb_id| and return this new instruction. |
| 219 |
const std::vector<uint32_t>& GetDefiningBlocks(uint32_t bb_id) { |
| 220 |
assert(cfg_->block(bb_id) != nullptr && "Unknown basic block"); |
| 221 |
std::vector<uint32_t>& defining_blocks = bb_to_defining_blocks_[bb_id]; |
| 222 |
|
| 223 |
if (defining_blocks.size()) return defining_blocks; |
| 224 |
|
| 225 |
// Check if one of the loop exit basic block dominates |bb_id|. |
| 226 |
for (const BasicBlock* e_bb : exit_bb_) { |
| 227 |
if (dom_tree_.Dominates(e_bb->id(), bb_id)) { |
| 228 |
defining_blocks.push_back(e_bb->id()); |
| 229 |
return defining_blocks; |
| 230 |
} |
| 231 |
} |
| 232 |
|
| 233 |
// Process parents, they will returns their suitable blocks. |
| 234 |
// If they are all the same, this means this basic block is dominated by a |
| 235 |
// common block, so we won't need to build a phi instruction. |
| 236 |
for (uint32_t pred_id : cfg_->preds(bb_id)) { |
| 237 |
const std::vector<uint32_t>& pred_blocks = GetDefiningBlocks(pred_id); |
| 238 |
if (pred_blocks.size() == 1) |
| 239 |
defining_blocks.push_back(pred_blocks[0]); |
| 240 |
else |
| 241 |
defining_blocks.push_back(pred_id); |
| 242 |
} |
| 243 |
assert(defining_blocks.size()); |
| 244 |
if (std::all_of(defining_blocks.begin(), defining_blocks.end(), |
| 245 |
[&defining_blocks](uint32_t id) { |
| 246 |
return id == defining_blocks[0]; |
| 247 |
})) { |
| 248 |
// No need for a phi. |
| 249 |
defining_blocks.resize(1); |
| 250 |
} |
| 251 |
|
| 252 |
return defining_blocks; |
| 253 |
} |
| 254 |
|
| 255 |
IRContext* context_; |
| 256 |
CFG* cfg_; |
| 257 |
const DominatorTree& dom_tree_; |
| 258 |
const std::unordered_set<BasicBlock*>& exit_bb_; |
| 259 |
uint32_t merge_block_id_; |
| 260 |
// This map represent the set of known paths. For each key, the vector |
| 261 |
// represent the set of blocks holding the definition to be used to build the |
| 262 |
// phi instruction. |
| 263 |
// If the vector has 0 value, then the path is unknown yet, and must be built. |
| 264 |
// If the vector has 1 value, then the value defined by that basic block |
| 265 |
// should be used. |
| 266 |
// If the vector has more than 1 value, then a phi node must be created, the |
| 267 |
// basic block ordering is the same as the predecessor ordering. |
| 268 |
std::unordered_map<uint32_t, std::vector<uint32_t>> bb_to_defining_blocks_; |
| 269 |
}; |
| 270 |
|
| 271 |
// Make the set |blocks| closed SSA. The set is closed SSA if all the uses |
| 272 |
// outside the set are phi instructions in exiting basic block set (hold by |
| 273 |
// |lcssa_rewriter|). |
| 274 |
inline void MakeSetClosedSSA(IRContext* context, Function* function, |
| 275 |
const std::unordered_set<uint32_t>& blocks, |
| 276 |
const std::unordered_set<BasicBlock*>& exit_bb, |
| 277 |
LCSSARewriter* lcssa_rewriter) { |
| 278 |
CFG& cfg = *context->cfg(); |
| 279 |
DominatorTree& dom_tree = |
| 280 |
context->GetDominatorAnalysis(function)->GetDomTree(); |
| 281 |
analysis::DefUseManager* def_use_manager = context->get_def_use_mgr(); |
| 282 |
|
| 283 |
for (uint32_t bb_id : blocks) { |
| 284 |
BasicBlock* bb = cfg.block(bb_id); |
| 285 |
// If bb does not dominate an exit block, then it cannot have escaping defs. |
| 286 |
if (!DominatesAnExit(bb, exit_bb, dom_tree)) continue; |
| 287 |
for (Instruction& inst : *bb) { |
| 288 |
LCSSARewriter::UseRewriter rewriter(lcssa_rewriter, inst); |
| 289 |
def_use_manager->ForEachUse( |
| 290 |
&inst, [&blocks, &rewriter, &exit_bb, context]( |
| 291 |
Instruction* use, uint32_t operand_index) { |
| 292 |
BasicBlock* use_parent = context->get_instr_block(use); |
| 293 |
assert(use_parent); |
| 294 |
if (blocks.count(use_parent->id())) return; |
| 295 |
|
| 296 |
if (use->opcode() == SpvOpPhi) { |
| 297 |
// If the use is a Phi instruction and the incoming block is |
| 298 |
// coming from the loop, then that's consistent with LCSSA form. |
| 299 |
if (exit_bb.count(use_parent)) { |
| 300 |
return; |
| 301 |
} else { |
| 302 |
// That's not an exit block, but the user is a phi instruction. |
| 303 |
// Consider the incoming branch only. |
| 304 |
use_parent = context->get_instr_block( |
| 305 |
use->GetSingleWordOperand(operand_index + 1)); |
| 306 |
} |
| 307 |
} |
| 308 |
// Rewrite the use. Note that this call does not invalidate the |
| 309 |
// def/use manager. So this operation is safe. |
| 310 |
rewriter.RewriteUse(use_parent, use, operand_index); |
| 311 |
}); |
| 312 |
rewriter.UpdateManagers(); |
| 313 |
} |
| 314 |
} |
| 315 |
} |
| 316 |
|
| 317 |
} // namespace |
| 318 |
|
| 319 |
void LoopUtils::CreateLoopDedicatedExits() { |
| 320 |
Function* function = loop_->GetHeaderBlock()->GetParent(); |
| 321 |
LoopDescriptor& loop_desc = *context_->GetLoopDescriptor(function); |
| 322 |
CFG& cfg = *context_->cfg(); |
| 323 |
analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); |
| 324 |
|
| 325 |
const IRContext::Analysis PreservedAnalyses = |
| 326 |
IRContext::kAnalysisDefUse | IRContext::kAnalysisInstrToBlockMapping; |
| 327 |
|
| 328 |
// Gathers the set of basic block that are not in this loop and have at least |
| 329 |
// one predecessor in the loop and one not in the loop. |
| 330 |
std::unordered_set<uint32_t> exit_bb_set; |
| 331 |
loop_->GetExitBlocks(&exit_bb_set); |
| 332 |
|
| 333 |
std::unordered_set<BasicBlock*> new_loop_exits; |
| 334 |
bool made_change = false; |
| 335 |
// For each block, we create a new one that gathers all branches from |
| 336 |
// the loop and fall into the block. |
| 337 |
for (uint32_t non_dedicate_id : exit_bb_set) { |
| 338 |
BasicBlock* non_dedicate = cfg.block(non_dedicate_id); |
| 339 |
const std::vector<uint32_t>& bb_pred = cfg.preds(non_dedicate_id); |
| 340 |
// Ignore the block if all the predecessors are in the loop. |
| 341 |
if (std::all_of(bb_pred.begin(), bb_pred.end(), |
| 342 |
[this](uint32_t id) { return loop_->IsInsideLoop(id); })) { |
| 343 |
new_loop_exits.insert(non_dedicate); |
| 344 |
continue; |
| 345 |
} |
| 346 |
|
| 347 |
made_change = true; |
| 348 |
Function::iterator insert_pt = function->begin(); |
| 349 |
for (; insert_pt != function->end() && &*insert_pt != non_dedicate; |
| 350 |
++insert_pt) { |
| 351 |
} |
| 352 |
assert(insert_pt != function->end() && "Basic Block not found"); |
| 353 |
|
| 354 |
// Create the dedicate exit basic block. |
| 355 |
// TODO(1841): Handle id overflow. |
| 356 |
BasicBlock& exit = *insert_pt.InsertBefore(std::unique_ptr<BasicBlock>( |
| 357 |
new BasicBlock(std::unique_ptr<Instruction>(new Instruction( |
| 358 |
context_, SpvOpLabel, 0, context_->TakeNextId(), {}))))); |
| 359 |
exit.SetParent(function); |
| 360 |
|
| 361 |
// Redirect in loop predecessors to |exit| block. |
| 362 |
for (uint32_t exit_pred_id : bb_pred) { |
| 363 |
if (loop_->IsInsideLoop(exit_pred_id)) { |
| 364 |
BasicBlock* pred_block = cfg.block(exit_pred_id); |
| 365 |
pred_block->ForEachSuccessorLabel([non_dedicate, &exit](uint32_t* id) { |
| 366 |
if (*id == non_dedicate->id()) *id = exit.id(); |
| 367 |
}); |
| 368 |
// Update the CFG. |
| 369 |
// |non_dedicate|'s predecessor list will be updated at the end of the |
| 370 |
// loop. |
| 371 |
cfg.RegisterBlock(pred_block); |
| 372 |
} |
| 373 |
} |
| 374 |
|
| 375 |
// Register the label to the def/use manager, requires for the phi patching. |
| 376 |
def_use_mgr->AnalyzeInstDefUse(exit.GetLabelInst()); |
| 377 |
context_->set_instr_block(exit.GetLabelInst(), &exit); |
| 378 |
|
| 379 |
InstructionBuilder builder(context_, &exit, PreservedAnalyses); |
| 380 |
// Now jump from our dedicate basic block to the old exit. |
| 381 |
// We also reset the insert point so all instructions are inserted before |
| 382 |
// the branch. |
| 383 |
builder.SetInsertPoint(builder.AddBranch(non_dedicate->id())); |
| 384 |
non_dedicate->ForEachPhiInst( |
| 385 |
[&builder, &exit, def_use_mgr, this](Instruction* phi) { |
| 386 |
// New phi operands for this instruction. |
| 387 |
std::vector<uint32_t> new_phi_op; |
| 388 |
// Phi operands for the dedicated exit block. |
| 389 |
std::vector<uint32_t> exit_phi_op; |
| 390 |
for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { |
| 391 |
uint32_t def_id = phi->GetSingleWordInOperand(i); |
| 392 |
uint32_t incoming_id = phi->GetSingleWordInOperand(i + 1); |
| 393 |
if (loop_->IsInsideLoop(incoming_id)) { |
| 394 |
exit_phi_op.push_back(def_id); |
| 395 |
exit_phi_op.push_back(incoming_id); |
| 396 |
} else { |
| 397 |
new_phi_op.push_back(def_id); |
| 398 |
new_phi_op.push_back(incoming_id); |
| 399 |
} |
| 400 |
} |
| 401 |
|
| 402 |
// Build the new phi instruction dedicated exit block. |
| 403 |
Instruction* exit_phi = builder.AddPhi(phi->type_id(), exit_phi_op); |
| 404 |
// Build the new incoming branch. |
| 405 |
new_phi_op.push_back(exit_phi->result_id()); |
| 406 |
new_phi_op.push_back(exit.id()); |
| 407 |
// Rewrite operands. |
| 408 |
uint32_t idx = 0; |
| 409 |
for (; idx < new_phi_op.size(); idx++) |
| 410 |
phi->SetInOperand(idx, {new_phi_op[idx]}); |
| 411 |
// Remove extra operands, from last to first (more efficient). |
| 412 |
for (uint32_t j = phi->NumInOperands() - 1; j >= idx; j--) |
| 413 |
phi->RemoveInOperand(j); |
| 414 |
// Update the def/use manager for this |phi|. |
| 415 |
def_use_mgr->AnalyzeInstUse(phi); |
| 416 |
}); |
| 417 |
// Update the CFG. |
| 418 |
cfg.RegisterBlock(&exit); |
| 419 |
cfg.RemoveNonExistingEdges(non_dedicate->id()); |
| 420 |
new_loop_exits.insert(&exit); |
| 421 |
// If non_dedicate is in a loop, add the new dedicated exit in that loop. |
| 422 |
if (Loop* parent_loop = loop_desc[non_dedicate]) |
| 423 |
parent_loop->AddBasicBlock(&exit); |
| 424 |
} |
| 425 |
|
| 426 |
if (new_loop_exits.size() == 1) { |
| 427 |
loop_->SetMergeBlock(*new_loop_exits.begin()); |
| 428 |
} |
| 429 |
|
| 430 |
if (made_change) { |
| 431 |
context_->InvalidateAnalysesExceptFor( |
| 432 |
PreservedAnalyses | IRContext::kAnalysisCFG | |
| 433 |
IRContext::Analysis::kAnalysisLoopAnalysis); |
| 434 |
} |
| 435 |
} |
| 436 |
|
| 437 |
void LoopUtils::MakeLoopClosedSSA() { |
| 438 |
CreateLoopDedicatedExits(); |
| 439 |
|
| 440 |
Function* function = loop_->GetHeaderBlock()->GetParent(); |
| 441 |
CFG& cfg = *context_->cfg(); |
| 442 |
DominatorTree& dom_tree = |
| 443 |
context_->GetDominatorAnalysis(function)->GetDomTree(); |
| 444 |
|
| 445 |
std::unordered_set<BasicBlock*> exit_bb; |
| 446 |
{ |
| 447 |
std::unordered_set<uint32_t> exit_bb_id; |
| 448 |
loop_->GetExitBlocks(&exit_bb_id); |
| 449 |
for (uint32_t bb_id : exit_bb_id) { |
| 450 |
exit_bb.insert(cfg.block(bb_id)); |
| 451 |
} |
| 452 |
} |
| 453 |
|
| 454 |
LCSSARewriter lcssa_rewriter(context_, dom_tree, exit_bb, |
| 455 |
loop_->GetMergeBlock()); |
| 456 |
MakeSetClosedSSA(context_, function, loop_->GetBlocks(), exit_bb, |
| 457 |
&lcssa_rewriter); |
| 458 |
|
| 459 |
// Make sure all defs post-dominated by the merge block have their last use no |
| 460 |
// further than the merge block. |
| 461 |
if (loop_->GetMergeBlock()) { |
| 462 |
std::unordered_set<uint32_t> merging_bb_id; |
| 463 |
loop_->GetMergingBlocks(&merging_bb_id); |
| 464 |
merging_bb_id.erase(loop_->GetMergeBlock()->id()); |
| 465 |
// Reset the exit set, now only the merge block is the exit. |
| 466 |
exit_bb.clear(); |
| 467 |
exit_bb.insert(loop_->GetMergeBlock()); |
| 468 |
// LCSSARewriter is reusable here only because it forces the creation of a |
| 469 |
// phi instruction in the merge block. |
| 470 |
MakeSetClosedSSA(context_, function, merging_bb_id, exit_bb, |
| 471 |
&lcssa_rewriter); |
| 472 |
} |
| 473 |
|
| 474 |
context_->InvalidateAnalysesExceptFor( |
| 475 |
IRContext::Analysis::kAnalysisCFG | |
| 476 |
IRContext::Analysis::kAnalysisDominatorAnalysis | |
| 477 |
IRContext::Analysis::kAnalysisLoopAnalysis); |
| 478 |
} |
| 479 |
|
| 480 |
Loop* LoopUtils::CloneLoop(LoopCloningResult* cloning_result) const { |
| 481 |
// Compute the structured order of the loop basic blocks and store it in the |
| 482 |
// vector ordered_loop_blocks. |
| 483 |
std::vector<BasicBlock*> ordered_loop_blocks; |
| 484 |
loop_->ComputeLoopStructuredOrder(&ordered_loop_blocks); |
| 485 |
|
| 486 |
// Clone the loop. |
| 487 |
return CloneLoop(cloning_result, ordered_loop_blocks); |
| 488 |
} |
| 489 |
|
| 490 |
Loop* LoopUtils::CloneAndAttachLoopToHeader(LoopCloningResult* cloning_result) { |
| 491 |
// Clone the loop. |
| 492 |
Loop* new_loop = CloneLoop(cloning_result); |
| 493 |
|
| 494 |
// Create a new exit block/label for the new loop. |
| 495 |
// TODO(1841): Handle id overflow. |
| 496 |
std::unique_ptr<Instruction> new_label{new Instruction( |
| 497 |
context_, SpvOp::SpvOpLabel, 0, context_->TakeNextId(), {})}; |
| 498 |
std::unique_ptr<BasicBlock> new_exit_bb{new BasicBlock(std::move(new_label))}; |
| 499 |
new_exit_bb->SetParent(loop_->GetMergeBlock()->GetParent()); |
| 500 |
|
| 501 |
// Create an unconditional branch to the header block. |
| 502 |
InstructionBuilder builder{context_, new_exit_bb.get()}; |
| 503 |
builder.AddBranch(loop_->GetHeaderBlock()->id()); |
| 504 |
|
| 505 |
// Save the ids of the new and old merge block. |
| 506 |
const uint32_t old_merge_block = loop_->GetMergeBlock()->id(); |
| 507 |
const uint32_t new_merge_block = new_exit_bb->id(); |
| 508 |
|
| 509 |
// Replace the uses of the old merge block in the new loop with the new merge |
| 510 |
// block. |
| 511 |
for (std::unique_ptr<BasicBlock>& basic_block : cloning_result->cloned_bb_) { |
| 512 |
for (Instruction& inst : *basic_block) { |
| 513 |
// For each operand in each instruction check if it is using the old merge |
| 514 |
// block and change it to be the new merge block. |
| 515 |
auto replace_merge_use = [old_merge_block, |
| 516 |
new_merge_block](uint32_t* id) { |
| 517 |
if (*id == old_merge_block) *id = new_merge_block; |
| 518 |
}; |
| 519 |
inst.ForEachInOperand(replace_merge_use); |
| 520 |
} |
| 521 |
} |
| 522 |
|
| 523 |
const uint32_t old_header = loop_->GetHeaderBlock()->id(); |
| 524 |
const uint32_t new_header = new_loop->GetHeaderBlock()->id(); |
| 525 |
analysis::DefUseManager* def_use = context_->get_def_use_mgr(); |
| 526 |
|
| 527 |
def_use->ForEachUse(old_header, |
| 528 |
[new_header, this](Instruction* inst, uint32_t operand) { |
| 529 |
if (!this->loop_->IsInsideLoop(inst)) |
| 530 |
inst->SetOperand(operand, {new_header}); |
| 531 |
}); |
| 532 |
|
| 533 |
// TODO(1841): Handle failure to create pre-header. |
| 534 |
def_use->ForEachUse( |
| 535 |
loop_->GetOrCreatePreHeaderBlock()->id(), |
| 536 |
[new_merge_block, this](Instruction* inst, uint32_t operand) { |
| 537 |
if (this->loop_->IsInsideLoop(inst)) |
| 538 |
inst->SetOperand(operand, {new_merge_block}); |
| 539 |
|
| 540 |
}); |
| 541 |
new_loop->SetMergeBlock(new_exit_bb.get()); |
| 542 |
|
| 543 |
new_loop->SetPreHeaderBlock(loop_->GetPreHeaderBlock()); |
| 544 |
|
| 545 |
// Add the new block into the cloned instructions. |
| 546 |
cloning_result->cloned_bb_.push_back(std::move(new_exit_bb)); |
| 547 |
|
| 548 |
return new_loop; |
| 549 |
} |
| 550 |
|
| 551 |
Loop* LoopUtils::CloneLoop( |
| 552 |
LoopCloningResult* cloning_result, |
| 553 |
const std::vector<BasicBlock*>& ordered_loop_blocks) const { |
| 554 |
analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); |
| 555 |
|
| 556 |
std::unique_ptr<Loop> new_loop = MakeUnique<Loop>(context_); |
| 557 |
|
| 558 |
CFG& cfg = *context_->cfg(); |
| 559 |
|
| 560 |
// Clone and place blocks in a SPIR-V compliant order (dominators first). |
| 561 |
for (BasicBlock* old_bb : ordered_loop_blocks) { |
| 562 |
// For each basic block in the loop, we clone it and register the mapping |
| 563 |
// between old and new ids. |
| 564 |
BasicBlock* new_bb = old_bb->Clone(context_); |
| 565 |
new_bb->SetParent(&function_); |
| 566 |
// TODO(1841): Handle id overflow. |
| 567 |
new_bb->GetLabelInst()->SetResultId(context_->TakeNextId()); |
| 568 |
def_use_mgr->AnalyzeInstDef(new_bb->GetLabelInst()); |
| 569 |
context_->set_instr_block(new_bb->GetLabelInst(), new_bb); |
| 570 |
cloning_result->cloned_bb_.emplace_back(new_bb); |
| 571 |
|
| 572 |
cloning_result->old_to_new_bb_[old_bb->id()] = new_bb; |
| 573 |
cloning_result->new_to_old_bb_[new_bb->id()] = old_bb; |
| 574 |
cloning_result->value_map_[old_bb->id()] = new_bb->id(); |
| 575 |
|
| 576 |
if (loop_->IsInsideLoop(old_bb)) new_loop->AddBasicBlock(new_bb); |
| 577 |
|
| 578 |
for (auto new_inst = new_bb->begin(), old_inst = old_bb->begin(); |
| 579 |
new_inst != new_bb->end(); ++new_inst, ++old_inst) { |
| 580 |
cloning_result->ptr_map_[&*new_inst] = &*old_inst; |
| 581 |
if (new_inst->HasResultId()) { |
| 582 |
// TODO(1841): Handle id overflow. |
| 583 |
new_inst->SetResultId(context_->TakeNextId()); |
| 584 |
cloning_result->value_map_[old_inst->result_id()] = |
| 585 |
new_inst->result_id(); |
| 586 |
|
| 587 |
// Only look at the defs for now, uses are not updated yet. |
| 588 |
def_use_mgr->AnalyzeInstDef(&*new_inst); |
| 589 |
} |
| 590 |
} |
| 591 |
} |
| 592 |
|
| 593 |
// All instructions (including all labels) have been cloned, |
| 594 |
// remap instruction operands id with the new ones. |
| 595 |
for (std::unique_ptr<BasicBlock>& bb_ref : cloning_result->cloned_bb_) { |
| 596 |
BasicBlock* bb = bb_ref.get(); |
| 597 |
|
| 598 |
for (Instruction& insn : *bb) { |
| 599 |
insn.ForEachInId([cloning_result](uint32_t* old_id) { |
| 600 |
// If the operand is defined in the loop, remap the id. |
| 601 |
auto id_it = cloning_result->value_map_.find(*old_id); |
| 602 |
if (id_it != cloning_result->value_map_.end()) { |
| 603 |
*old_id = id_it->second; |
| 604 |
} |
| 605 |
}); |
| 606 |
// Only look at what the instruction uses. All defs are register, so all |
| 607 |
// should be fine now. |
| 608 |
def_use_mgr->AnalyzeInstUse(&insn); |
| 609 |
context_->set_instr_block(&insn, bb); |
| 610 |
} |
| 611 |
cfg.RegisterBlock(bb); |
| 612 |
} |
| 613 |
|
| 614 |
PopulateLoopNest(new_loop.get(), *cloning_result); |
| 615 |
|
| 616 |
return new_loop.release(); |
| 617 |
} |
| 618 |
|
| 619 |
void LoopUtils::PopulateLoopNest( |
| 620 |
Loop* new_loop, const LoopCloningResult& cloning_result) const { |
| 621 |
std::unordered_map<Loop*, Loop*> loop_mapping; |
| 622 |
loop_mapping[loop_] = new_loop; |
| 623 |
|
| 624 |
if (loop_->HasParent()) loop_->GetParent()->AddNestedLoop(new_loop); |
| 625 |
PopulateLoopDesc(new_loop, loop_, cloning_result); |
| 626 |
|
| 627 |
for (Loop& sub_loop : |
| 628 |
make_range(++TreeDFIterator<Loop>(loop_), TreeDFIterator<Loop>())) { |
| 629 |
Loop* cloned = new Loop(context_); |
| 630 |
if (Loop* parent = loop_mapping[sub_loop.GetParent()]) |
| 631 |
parent->AddNestedLoop(cloned); |
| 632 |
loop_mapping[&sub_loop] = cloned; |
| 633 |
PopulateLoopDesc(cloned, &sub_loop, cloning_result); |
| 634 |
} |
| 635 |
|
| 636 |
loop_desc_->AddLoopNest(std::unique_ptr<Loop>(new_loop)); |
| 637 |
} |
| 638 |
|
| 639 |
// Populates |new_loop| descriptor according to |old_loop|'s one. |
| 640 |
void LoopUtils::PopulateLoopDesc( |
| 641 |
Loop* new_loop, Loop* old_loop, |
| 642 |
const LoopCloningResult& cloning_result) const { |
| 643 |
for (uint32_t bb_id : old_loop->GetBlocks()) { |
| 644 |
BasicBlock* bb = cloning_result.old_to_new_bb_.at(bb_id); |
| 645 |
new_loop->AddBasicBlock(bb); |
| 646 |
} |
| 647 |
new_loop->SetHeaderBlock( |
| 648 |
cloning_result.old_to_new_bb_.at(old_loop->GetHeaderBlock()->id())); |
| 649 |
if (old_loop->GetLatchBlock()) |
| 650 |
new_loop->SetLatchBlock( |
| 651 |
cloning_result.old_to_new_bb_.at(old_loop->GetLatchBlock()->id())); |
| 652 |
if (old_loop->GetContinueBlock()) |
| 653 |
new_loop->SetContinueBlock( |
| 654 |
cloning_result.old_to_new_bb_.at(old_loop->GetContinueBlock()->id())); |
| 655 |
if (old_loop->GetMergeBlock()) { |
| 656 |
auto it = |
| 657 |
cloning_result.old_to_new_bb_.find(old_loop->GetMergeBlock()->id()); |
| 658 |
BasicBlock* bb = it != cloning_result.old_to_new_bb_.end() |
| 659 |
? it->second |
| 660 |
: old_loop->GetMergeBlock(); |
| 661 |
new_loop->SetMergeBlock(bb); |
| 662 |
} |
| 663 |
if (old_loop->GetPreHeaderBlock()) { |
| 664 |
auto it = |
| 665 |
cloning_result.old_to_new_bb_.find(old_loop->GetPreHeaderBlock()->id()); |
| 666 |
if (it != cloning_result.old_to_new_bb_.end()) { |
| 667 |
new_loop->SetPreHeaderBlock(it->second); |
| 668 |
} |
| 669 |
} |
| 670 |
} |
| 671 |
|
| 672 |
// Class to gather some metrics about a region of interest. |
| 673 |
void CodeMetrics::Analyze(const Loop& loop) { |
| 674 |
CFG& cfg = *loop.GetContext()->cfg(); |
| 675 |
|
| 676 |
roi_size_ = 0; |
| 677 |
block_sizes_.clear(); |
| 678 |
|
| 679 |
for (uint32_t id : loop.GetBlocks()) { |
| 680 |
const BasicBlock* bb = cfg.block(id); |
| 681 |
size_t bb_size = 0; |
| 682 |
bb->ForEachInst([&bb_size](const Instruction* insn) { |
| 683 |
if (insn->opcode() == SpvOpLabel) return; |
| 684 |
if (insn->IsNop()) return; |
| 685 |
if (insn->opcode() == SpvOpPhi) return; |
| 686 |
bb_size++; |
| 687 |
}); |
| 688 |
block_sizes_[bb->id()] = bb_size; |
| 689 |
roi_size_ += bb_size; |
| 690 |
} |
| 691 |
} |
| 692 |
|
| 693 |
} // namespace opt |
| 694 |
} // namespace spvtools |