Handle id overflow in inlining. (#2196)
Have inlining return Failure if the ids overflow.
Part of #1841.
diff --git a/source/opt/function.cpp b/source/opt/function.cpp
index d4457ad..9bd46e2 100644
--- a/source/opt/function.cpp
+++ b/source/opt/function.cpp
@@ -46,29 +46,77 @@
void Function::ForEachInst(const std::function<void(Instruction*)>& f,
bool run_on_debug_line_insts) {
- if (def_inst_) def_inst_->ForEachInst(f, run_on_debug_line_insts);
- for (auto& param : params_) param->ForEachInst(f, run_on_debug_line_insts);
- for (auto& bb : blocks_) bb->ForEachInst(f, run_on_debug_line_insts);
- if (end_inst_) end_inst_->ForEachInst(f, run_on_debug_line_insts);
+ WhileEachInst(
+ [&f](Instruction* inst) {
+ f(inst);
+ return true;
+ },
+ run_on_debug_line_insts);
}
void Function::ForEachInst(const std::function<void(const Instruction*)>& f,
bool run_on_debug_line_insts) const {
- if (def_inst_)
- static_cast<const Instruction*>(def_inst_.get())
- ->ForEachInst(f, run_on_debug_line_insts);
+ WhileEachInst(
+ [&f](const Instruction* inst) {
+ f(inst);
+ return true;
+ },
+ run_on_debug_line_insts);
+}
- for (const auto& param : params_)
- static_cast<const Instruction*>(param.get())
- ->ForEachInst(f, run_on_debug_line_insts);
+bool Function::WhileEachInst(const std::function<bool(Instruction*)>& f,
+ bool run_on_debug_line_insts) {
+ if (def_inst_) {
+ if (!def_inst_->WhileEachInst(f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
- for (const auto& bb : blocks_)
- static_cast<const BasicBlock*>(bb.get())->ForEachInst(
- f, run_on_debug_line_insts);
+ for (auto& param : params_) {
+ if (!param->WhileEachInst(f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
+
+ for (auto& bb : blocks_) {
+ if (!bb->WhileEachInst(f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
+
+ if (end_inst_) return end_inst_->WhileEachInst(f, run_on_debug_line_insts);
+
+ return true;
+}
+
+bool Function::WhileEachInst(const std::function<bool(const Instruction*)>& f,
+ bool run_on_debug_line_insts) const {
+ if (def_inst_) {
+ if (!static_cast<const Instruction*>(def_inst_.get())
+ ->WhileEachInst(f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
+
+ for (const auto& param : params_) {
+ if (!static_cast<const Instruction*>(param.get())
+ ->WhileEachInst(f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
+
+ for (const auto& bb : blocks_) {
+ if (!static_cast<const BasicBlock*>(bb.get())->WhileEachInst(
+ f, run_on_debug_line_insts)) {
+ return false;
+ }
+ }
if (end_inst_)
- static_cast<const Instruction*>(end_inst_.get())
- ->ForEachInst(f, run_on_debug_line_insts);
+ return static_cast<const Instruction*>(end_inst_.get())
+ ->WhileEachInst(f, run_on_debug_line_insts);
+
+ return true;
}
void Function::ForEachParam(const std::function<void(Instruction*)>& f,
diff --git a/source/opt/function.h b/source/opt/function.h
index 7c0166f..c80b078 100644
--- a/source/opt/function.h
+++ b/source/opt/function.h
@@ -110,6 +110,10 @@
bool run_on_debug_line_insts = false);
void ForEachInst(const std::function<void(const Instruction*)>& f,
bool run_on_debug_line_insts = false) const;
+ bool WhileEachInst(const std::function<bool(Instruction*)>& f,
+ bool run_on_debug_line_insts = false);
+ bool WhileEachInst(const std::function<bool(const Instruction*)>& f,
+ bool run_on_debug_line_insts = false) const;
// Runs the given function |f| on each parameter instruction in this function,
// and optionally on debug line instructions that might precede them.
diff --git a/source/opt/inline_exhaustive_pass.cpp b/source/opt/inline_exhaustive_pass.cpp
index 10b5e98..24f4e73 100644
--- a/source/opt/inline_exhaustive_pass.cpp
+++ b/source/opt/inline_exhaustive_pass.cpp
@@ -21,7 +21,7 @@
namespace spvtools {
namespace opt {
-bool InlineExhaustivePass::InlineExhaustive(Function* func) {
+Pass::Status InlineExhaustivePass::InlineExhaustive(Function* func) {
bool modified = false;
// Using block iterators here because of block erasures and insertions.
for (auto bi = func->begin(); bi != func->end(); ++bi) {
@@ -30,7 +30,9 @@
// Inline call.
std::vector<std::unique_ptr<BasicBlock>> newBlocks;
std::vector<std::unique_ptr<Instruction>> newVars;
- GenInlineCode(&newBlocks, &newVars, ii, bi);
+ if (!GenInlineCode(&newBlocks, &newVars, ii, bi)) {
+ return Status::Failure;
+ }
// If call block is replaced with more than one block, point
// succeeding phis at new last block.
if (newBlocks.size() > 1) UpdateSucceedingPhis(newBlocks);
@@ -58,14 +60,18 @@
}
}
}
- return modified;
+ return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
}
Pass::Status InlineExhaustivePass::ProcessImpl() {
+ Status status = Status::SuccessWithoutChange;
// Attempt exhaustive inlining on each entry point function in module
- ProcessFunction pfn = [this](Function* fp) { return InlineExhaustive(fp); };
- bool modified = context()->ProcessEntryPointCallTree(pfn);
- return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
+ ProcessFunction pfn = [&status, this](Function* fp) {
+ status = CombineStatus(status, InlineExhaustive(fp));
+ return false;
+ };
+ context()->ProcessEntryPointCallTree(pfn);
+ return status;
}
InlineExhaustivePass::InlineExhaustivePass() = default;
diff --git a/source/opt/inline_exhaustive_pass.h b/source/opt/inline_exhaustive_pass.h
index 103e091..c2e8547 100644
--- a/source/opt/inline_exhaustive_pass.h
+++ b/source/opt/inline_exhaustive_pass.h
@@ -40,8 +40,8 @@
private:
// Exhaustively inline all function calls in func as well as in
- // all code that is inlined into func. Return true if func is modified.
- bool InlineExhaustive(Function* func);
+ // all code that is inlined into func. Returns the status.
+ Status InlineExhaustive(Function* func);
void Initialize();
Pass::Status ProcessImpl();
diff --git a/source/opt/inline_opaque_pass.cpp b/source/opt/inline_opaque_pass.cpp
index e94f26d..6ccaf90 100644
--- a/source/opt/inline_opaque_pass.cpp
+++ b/source/opt/inline_opaque_pass.cpp
@@ -63,7 +63,7 @@
});
}
-bool InlineOpaquePass::InlineOpaque(Function* func) {
+Pass::Status InlineOpaquePass::InlineOpaque(Function* func) {
bool modified = false;
// Using block iterators here because of block erasures and insertions.
for (auto bi = func->begin(); bi != func->end(); ++bi) {
@@ -72,7 +72,10 @@
// Inline call.
std::vector<std::unique_ptr<BasicBlock>> newBlocks;
std::vector<std::unique_ptr<Instruction>> newVars;
- GenInlineCode(&newBlocks, &newVars, ii, bi);
+ if (!GenInlineCode(&newBlocks, &newVars, ii, bi)) {
+ return Status::Failure;
+ }
+
// If call block is replaced with more than one block, point
// succeeding phis at new last block.
if (newBlocks.size() > 1) UpdateSucceedingPhis(newBlocks);
@@ -90,16 +93,20 @@
}
}
}
- return modified;
+ return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
}
void InlineOpaquePass::Initialize() { InitializeInline(); }
Pass::Status InlineOpaquePass::ProcessImpl() {
+ Status status = Status::SuccessWithoutChange;
// Do opaque inlining on each function in entry point call tree
- ProcessFunction pfn = [this](Function* fp) { return InlineOpaque(fp); };
- bool modified = context()->ProcessEntryPointCallTree(pfn);
- return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
+ ProcessFunction pfn = [&status, this](Function* fp) {
+ status = CombineStatus(status, InlineOpaque(fp));
+ return false;
+ };
+ context()->ProcessEntryPointCallTree(pfn);
+ return status;
}
InlineOpaquePass::InlineOpaquePass() = default;
diff --git a/source/opt/inline_opaque_pass.h b/source/opt/inline_opaque_pass.h
index aad43fd..1e3081d 100644
--- a/source/opt/inline_opaque_pass.h
+++ b/source/opt/inline_opaque_pass.h
@@ -48,7 +48,7 @@
// Inline all function calls in |func| that have opaque params or return
// type. Inline similarly all code that is inlined into func. Return true
// if func is modified.
- bool InlineOpaque(Function* func);
+ Status InlineOpaque(Function* func);
void Initialize();
Pass::Status ProcessImpl();
diff --git a/source/opt/inline_pass.cpp b/source/opt/inline_pass.cpp
index cdd5659..f348bbe 100644
--- a/source/opt/inline_pass.cpp
+++ b/source/opt/inline_pass.cpp
@@ -34,7 +34,11 @@
uint32_t InlinePass::AddPointerToType(uint32_t type_id,
SpvStorageClass storage_class) {
- uint32_t resultId = TakeNextId();
+ uint32_t resultId = context()->TakeNextId();
+ if (resultId == 0) {
+ return resultId;
+ }
+
std::unique_ptr<Instruction> type_inst(
new Instruction(context(), SpvOpTypePointer, 0, resultId,
{{spv_operand_type_t::SPV_OPERAND_TYPE_STORAGE_CLASS,
@@ -108,10 +112,16 @@
if (false_id_ != 0) return false_id_;
uint32_t boolId = get_module()->GetGlobalValue(SpvOpTypeBool);
if (boolId == 0) {
- boolId = TakeNextId();
+ boolId = context()->TakeNextId();
+ if (boolId == 0) {
+ return 0;
+ }
get_module()->AddGlobalValue(SpvOpTypeBool, boolId, 0);
}
- false_id_ = TakeNextId();
+ false_id_ = context()->TakeNextId();
+ if (false_id_ == 0) {
+ return 0;
+ }
get_module()->AddGlobalValue(SpvOpConstantFalse, false_id_, boolId);
return false_id_;
}
@@ -120,50 +130,64 @@
Function* calleeFn, BasicBlock::iterator call_inst_itr,
std::unordered_map<uint32_t, uint32_t>* callee2caller) {
int param_idx = 0;
- calleeFn->ForEachParam([&call_inst_itr, ¶m_idx,
- &callee2caller](const Instruction* cpi) {
- const uint32_t pid = cpi->result_id();
- (*callee2caller)[pid] = call_inst_itr->GetSingleWordOperand(
- kSpvFunctionCallArgumentId + param_idx);
- ++param_idx;
- });
+ calleeFn->ForEachParam(
+ [&call_inst_itr, ¶m_idx, &callee2caller](const Instruction* cpi) {
+ const uint32_t pid = cpi->result_id();
+ (*callee2caller)[pid] = call_inst_itr->GetSingleWordOperand(
+ kSpvFunctionCallArgumentId + param_idx);
+ ++param_idx;
+ });
}
-void InlinePass::CloneAndMapLocals(
+bool InlinePass::CloneAndMapLocals(
Function* calleeFn, std::vector<std::unique_ptr<Instruction>>* new_vars,
std::unordered_map<uint32_t, uint32_t>* callee2caller) {
auto callee_block_itr = calleeFn->begin();
auto callee_var_itr = callee_block_itr->begin();
while (callee_var_itr->opcode() == SpvOp::SpvOpVariable) {
std::unique_ptr<Instruction> var_inst(callee_var_itr->Clone(context()));
- uint32_t newId = TakeNextId();
+ uint32_t newId = context()->TakeNextId();
+ if (newId == 0) {
+ return false;
+ }
get_decoration_mgr()->CloneDecorations(callee_var_itr->result_id(), newId);
var_inst->SetResultId(newId);
(*callee2caller)[callee_var_itr->result_id()] = newId;
new_vars->push_back(std::move(var_inst));
++callee_var_itr;
}
+ return true;
}
uint32_t InlinePass::CreateReturnVar(
Function* calleeFn, std::vector<std::unique_ptr<Instruction>>* new_vars) {
uint32_t returnVarId = 0;
const uint32_t calleeTypeId = calleeFn->type_id();
- analysis::Type* calleeType = context()->get_type_mgr()->GetType(calleeTypeId);
- if (calleeType->AsVoid() == nullptr) {
- // Find or create ptr to callee return type.
- uint32_t returnVarTypeId = context()->get_type_mgr()->FindPointerToType(
- calleeTypeId, SpvStorageClassFunction);
- if (returnVarTypeId == 0)
- returnVarTypeId = AddPointerToType(calleeTypeId, SpvStorageClassFunction);
- // Add return var to new function scope variables.
- returnVarId = TakeNextId();
- std::unique_ptr<Instruction> var_inst(
- new Instruction(context(), SpvOpVariable, returnVarTypeId, returnVarId,
- {{spv_operand_type_t::SPV_OPERAND_TYPE_STORAGE_CLASS,
- {SpvStorageClassFunction}}}));
- new_vars->push_back(std::move(var_inst));
+ analysis::TypeManager* type_mgr = context()->get_type_mgr();
+ assert(type_mgr->GetType(calleeTypeId)->AsVoid() == nullptr &&
+ "Cannot create a return variable of type void.");
+ // Find or create ptr to callee return type.
+ uint32_t returnVarTypeId =
+ type_mgr->FindPointerToType(calleeTypeId, SpvStorageClassFunction);
+
+ if (returnVarTypeId == 0) {
+ returnVarTypeId = AddPointerToType(calleeTypeId, SpvStorageClassFunction);
+ if (returnVarTypeId == 0) {
+ return 0;
+ }
}
+
+ // Add return var to new function scope variables.
+ returnVarId = context()->TakeNextId();
+ if (returnVarId == 0) {
+ return 0;
+ }
+
+ std::unique_ptr<Instruction> var_inst(
+ new Instruction(context(), SpvOpVariable, returnVarTypeId, returnVarId,
+ {{spv_operand_type_t::SPV_OPERAND_TYPE_STORAGE_CLASS,
+ {SpvStorageClassFunction}}}));
+ new_vars->push_back(std::move(var_inst));
get_decoration_mgr()->CloneDecorations(calleeFn->result_id(), returnVarId);
return returnVarId;
}
@@ -172,37 +196,44 @@
return inst->opcode() == SpvOpSampledImage || inst->opcode() == SpvOpImage;
}
-void InlinePass::CloneSameBlockOps(
+bool InlinePass::CloneSameBlockOps(
std::unique_ptr<Instruction>* inst,
std::unordered_map<uint32_t, uint32_t>* postCallSB,
std::unordered_map<uint32_t, Instruction*>* preCallSB,
std::unique_ptr<BasicBlock>* block_ptr) {
- (*inst)->ForEachInId(
- [&postCallSB, &preCallSB, &block_ptr, this](uint32_t* iid) {
- const auto mapItr = (*postCallSB).find(*iid);
- if (mapItr == (*postCallSB).end()) {
- const auto mapItr2 = (*preCallSB).find(*iid);
- if (mapItr2 != (*preCallSB).end()) {
- // Clone pre-call same-block ops, map result id.
- const Instruction* inInst = mapItr2->second;
- std::unique_ptr<Instruction> sb_inst(inInst->Clone(context()));
- CloneSameBlockOps(&sb_inst, postCallSB, preCallSB, block_ptr);
- const uint32_t rid = sb_inst->result_id();
- const uint32_t nid = this->TakeNextId();
- get_decoration_mgr()->CloneDecorations(rid, nid);
- sb_inst->SetResultId(nid);
- (*postCallSB)[rid] = nid;
- *iid = nid;
- (*block_ptr)->AddInstruction(std::move(sb_inst));
- }
- } else {
- // Reset same-block op operand.
- *iid = mapItr->second;
+ return (*inst)->WhileEachInId([&postCallSB, &preCallSB, &block_ptr,
+ this](uint32_t* iid) {
+ const auto mapItr = (*postCallSB).find(*iid);
+ if (mapItr == (*postCallSB).end()) {
+ const auto mapItr2 = (*preCallSB).find(*iid);
+ if (mapItr2 != (*preCallSB).end()) {
+ // Clone pre-call same-block ops, map result id.
+ const Instruction* inInst = mapItr2->second;
+ std::unique_ptr<Instruction> sb_inst(inInst->Clone(context()));
+ if (!CloneSameBlockOps(&sb_inst, postCallSB, preCallSB, block_ptr)) {
+ return false;
}
- });
+
+ const uint32_t rid = sb_inst->result_id();
+ const uint32_t nid = context()->TakeNextId();
+ if (nid == 0) {
+ return false;
+ }
+ get_decoration_mgr()->CloneDecorations(rid, nid);
+ sb_inst->SetResultId(nid);
+ (*postCallSB)[rid] = nid;
+ *iid = nid;
+ (*block_ptr)->AddInstruction(std::move(sb_inst));
+ }
+ } else {
+ // Reset same-block op operand.
+ *iid = mapItr->second;
+ }
+ return true;
+ });
}
-void InlinePass::GenInlineCode(
+bool InlinePass::GenInlineCode(
std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
std::vector<std::unique_ptr<Instruction>>* new_vars,
BasicBlock::iterator call_inst_itr,
@@ -232,10 +263,20 @@
// Define caller local variables for all callee variables and create map to
// them.
- CloneAndMapLocals(calleeFn, new_vars, &callee2caller);
+ if (!CloneAndMapLocals(calleeFn, new_vars, &callee2caller)) {
+ return false;
+ }
// Create return var if needed.
- uint32_t returnVarId = CreateReturnVar(calleeFn, new_vars);
+ const uint32_t calleeTypeId = calleeFn->type_id();
+ uint32_t returnVarId = 0;
+ analysis::Type* calleeType = context()->get_type_mgr()->GetType(calleeTypeId);
+ if (calleeType->AsVoid() == nullptr) {
+ returnVarId = CreateReturnVar(calleeFn, new_vars);
+ if (returnVarId == 0) {
+ return false;
+ }
+ }
// Create set of callee result ids. Used to detect forward references
std::unordered_set<uint32_t> callee_result_ids;
@@ -269,241 +310,294 @@
uint32_t singleTripLoopContinueId = 0;
uint32_t returnLabelId = 0;
bool multiBlocks = false;
- const uint32_t calleeTypeId = calleeFn->type_id();
// new_blk_ptr is a new basic block in the caller. New instructions are
// written to it. It is created when we encounter the OpLabel
// of the first callee block. It is appended to new_blocks only when
// it is complete.
std::unique_ptr<BasicBlock> new_blk_ptr;
- calleeFn->ForEachInst([&new_blocks, &callee2caller, &call_block_itr,
- &call_inst_itr, &new_blk_ptr, &prevInstWasReturn,
- &returnLabelId, &returnVarId, caller_is_loop_header,
- callee_begins_with_structured_header, &calleeTypeId,
- &multiBlocks, &postCallSB, &preCallSB, earlyReturn,
- &singleTripLoopHeaderId, &singleTripLoopContinueId,
- &callee_result_ids, this](const Instruction* cpi) {
- switch (cpi->opcode()) {
- case SpvOpFunction:
- case SpvOpFunctionParameter:
- // Already processed
- break;
- case SpvOpVariable:
- if (cpi->NumInOperands() == 2) {
- assert(callee2caller.count(cpi->result_id()) &&
- "Expected the variable to have already been mapped.");
- uint32_t new_var_id = callee2caller.at(cpi->result_id());
+ bool successful = calleeFn->WhileEachInst(
+ [&new_blocks, &callee2caller, &call_block_itr, &call_inst_itr,
+ &new_blk_ptr, &prevInstWasReturn, &returnLabelId, &returnVarId,
+ caller_is_loop_header, callee_begins_with_structured_header,
+ &calleeTypeId, &multiBlocks, &postCallSB, &preCallSB, earlyReturn,
+ &singleTripLoopHeaderId, &singleTripLoopContinueId, &callee_result_ids,
+ this](const Instruction* cpi) {
+ switch (cpi->opcode()) {
+ case SpvOpFunction:
+ case SpvOpFunctionParameter:
+ // Already processed
+ break;
+ case SpvOpVariable:
+ if (cpi->NumInOperands() == 2) {
+ assert(callee2caller.count(cpi->result_id()) &&
+ "Expected the variable to have already been mapped.");
+ uint32_t new_var_id = callee2caller.at(cpi->result_id());
- // The initializer must be a constant or global value. No mapped
- // should be used.
- uint32_t val_id = cpi->GetSingleWordInOperand(1);
- AddStore(new_var_id, val_id, &new_blk_ptr);
- }
- break;
- case SpvOpUnreachable:
- case SpvOpKill: {
- // Generate a return label so that we split the block with the function
- // call. Copy the terminator into the new block.
- if (returnLabelId == 0) returnLabelId = this->TakeNextId();
- std::unique_ptr<Instruction> terminator(
- new Instruction(context(), cpi->opcode(), 0, 0, {}));
- new_blk_ptr->AddInstruction(std::move(terminator));
- break;
- }
- case SpvOpLabel: {
- // If previous instruction was early return, insert branch
- // instruction to return block.
- if (prevInstWasReturn) {
- if (returnLabelId == 0) returnLabelId = this->TakeNextId();
- AddBranch(returnLabelId, &new_blk_ptr);
- prevInstWasReturn = false;
- }
- // Finish current block (if it exists) and get label for next block.
- uint32_t labelId;
- bool firstBlock = false;
- if (new_blk_ptr != nullptr) {
- new_blocks->push_back(std::move(new_blk_ptr));
- // If result id is already mapped, use it, otherwise get a new
- // one.
- const uint32_t rid = cpi->result_id();
- const auto mapItr = callee2caller.find(rid);
- labelId = (mapItr != callee2caller.end()) ? mapItr->second
- : this->TakeNextId();
- } else {
- // First block needs to use label of original block
- // but map callee label in case of phi reference.
- labelId = call_block_itr->id();
- callee2caller[cpi->result_id()] = labelId;
- firstBlock = true;
- }
- // Create first/next block.
- new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(labelId));
- if (firstBlock) {
- // Copy contents of original caller block up to call instruction.
- for (auto cii = call_block_itr->begin(); cii != call_inst_itr;
- cii = call_block_itr->begin()) {
- Instruction* inst = &*cii;
- inst->RemoveFromList();
- std::unique_ptr<Instruction> cp_inst(inst);
- // Remember same-block ops for possible regeneration.
- if (IsSameBlockOp(&*cp_inst)) {
- auto* sb_inst_ptr = cp_inst.get();
- preCallSB[cp_inst->result_id()] = sb_inst_ptr;
+ // The initializer must be a constant or global value. No mapped
+ // should be used.
+ uint32_t val_id = cpi->GetSingleWordInOperand(1);
+ AddStore(new_var_id, val_id, &new_blk_ptr);
+ }
+ break;
+ case SpvOpUnreachable:
+ case SpvOpKill: {
+ // Generate a return label so that we split the block with the
+ // function call. Copy the terminator into the new block.
+ if (returnLabelId == 0) {
+ returnLabelId = context()->TakeNextId();
+ if (returnLabelId == 0) {
+ return false;
+ }
+ }
+ std::unique_ptr<Instruction> terminator(
+ new Instruction(context(), cpi->opcode(), 0, 0, {}));
+ new_blk_ptr->AddInstruction(std::move(terminator));
+ break;
+ }
+ case SpvOpLabel: {
+ // If previous instruction was early return, insert branch
+ // instruction to return block.
+ if (prevInstWasReturn) {
+ if (returnLabelId == 0) {
+ returnLabelId = context()->TakeNextId();
+ if (returnLabelId == 0) {
+ return false;
+ }
+ }
+ AddBranch(returnLabelId, &new_blk_ptr);
+ prevInstWasReturn = false;
+ }
+ // Finish current block (if it exists) and get label for next block.
+ uint32_t labelId;
+ bool firstBlock = false;
+ if (new_blk_ptr != nullptr) {
+ new_blocks->push_back(std::move(new_blk_ptr));
+ // If result id is already mapped, use it, otherwise get a new
+ // one.
+ const uint32_t rid = cpi->result_id();
+ const auto mapItr = callee2caller.find(rid);
+ labelId = (mapItr != callee2caller.end())
+ ? mapItr->second
+ : context()->TakeNextId();
+ if (labelId == 0) {
+ return false;
+ }
+ } else {
+ // First block needs to use label of original block
+ // but map callee label in case of phi reference.
+ labelId = call_block_itr->id();
+ callee2caller[cpi->result_id()] = labelId;
+ firstBlock = true;
+ }
+ // Create first/next block.
+ new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(labelId));
+ if (firstBlock) {
+ // Copy contents of original caller block up to call instruction.
+ for (auto cii = call_block_itr->begin(); cii != call_inst_itr;
+ cii = call_block_itr->begin()) {
+ Instruction* inst = &*cii;
+ inst->RemoveFromList();
+ std::unique_ptr<Instruction> cp_inst(inst);
+ // Remember same-block ops for possible regeneration.
+ if (IsSameBlockOp(&*cp_inst)) {
+ auto* sb_inst_ptr = cp_inst.get();
+ preCallSB[cp_inst->result_id()] = sb_inst_ptr;
+ }
+ new_blk_ptr->AddInstruction(std::move(cp_inst));
+ }
+ if (caller_is_loop_header &&
+ callee_begins_with_structured_header) {
+ // We can't place both the caller's merge instruction and
+ // another merge instruction in the same block. So split the
+ // calling block. Insert an unconditional branch to a new guard
+ // block. Later, once we know the ID of the last block, we
+ // will move the caller's OpLoopMerge from the last generated
+ // block into the first block. We also wait to avoid
+ // invalidating various iterators.
+ const auto guard_block_id = context()->TakeNextId();
+ if (guard_block_id == 0) {
+ return false;
+ }
+ AddBranch(guard_block_id, &new_blk_ptr);
+ new_blocks->push_back(std::move(new_blk_ptr));
+ // Start the next block.
+ new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(guard_block_id));
+ // Reset the mapping of the callee's entry block to point to
+ // the guard block. Do this so we can fix up phis later on to
+ // satisfy dominance.
+ callee2caller[cpi->result_id()] = guard_block_id;
+ }
+ // If callee has early return, insert a header block for
+ // single-trip loop that will encompass callee code. Start
+ // postheader block.
+ //
+ // Note: Consider the following combination:
+ // - the caller is a single block loop
+ // - the callee does not begin with a structure header
+ // - the callee has multiple returns.
+ // We still need to split the caller block and insert a guard
+ // block. But we only need to do it once. We haven't done it yet,
+ // but the single-trip loop header will serve the same purpose.
+ if (earlyReturn) {
+ singleTripLoopHeaderId = context()->TakeNextId();
+ if (singleTripLoopHeaderId == 0) {
+ return false;
+ }
+ AddBranch(singleTripLoopHeaderId, &new_blk_ptr);
+ new_blocks->push_back(std::move(new_blk_ptr));
+ new_blk_ptr =
+ MakeUnique<BasicBlock>(NewLabel(singleTripLoopHeaderId));
+ returnLabelId = context()->TakeNextId();
+ singleTripLoopContinueId = context()->TakeNextId();
+ if (returnLabelId == 0 || singleTripLoopContinueId == 0) {
+ return false;
+ }
+ AddLoopMerge(returnLabelId, singleTripLoopContinueId,
+ &new_blk_ptr);
+ uint32_t postHeaderId = context()->TakeNextId();
+ if (postHeaderId == 0) {
+ return false;
+ }
+ AddBranch(postHeaderId, &new_blk_ptr);
+ new_blocks->push_back(std::move(new_blk_ptr));
+ new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(postHeaderId));
+ multiBlocks = true;
+ // Reset the mapping of the callee's entry block to point to
+ // the post-header block. Do this so we can fix up phis later
+ // on to satisfy dominance.
+ callee2caller[cpi->result_id()] = postHeaderId;
+ }
+ } else {
+ multiBlocks = true;
+ }
+ } break;
+ case SpvOpReturnValue: {
+ // Store return value to return variable.
+ assert(returnVarId != 0);
+ uint32_t valId = cpi->GetInOperand(kSpvReturnValueId).words[0];
+ const auto mapItr = callee2caller.find(valId);
+ if (mapItr != callee2caller.end()) {
+ valId = mapItr->second;
+ }
+ AddStore(returnVarId, valId, &new_blk_ptr);
+
+ // Remember we saw a return; if followed by a label, will need to
+ // insert branch.
+ prevInstWasReturn = true;
+ } break;
+ case SpvOpReturn: {
+ // Remember we saw a return; if followed by a label, will need to
+ // insert branch.
+ prevInstWasReturn = true;
+ } break;
+ case SpvOpFunctionEnd: {
+ // If there was an early return, we generated a return label id
+ // for it. Now we have to generate the return block with that Id.
+ if (returnLabelId != 0) {
+ // If previous instruction was return, insert branch instruction
+ // to return block.
+ if (prevInstWasReturn) AddBranch(returnLabelId, &new_blk_ptr);
+ if (earlyReturn) {
+ // If we generated a loop header for the single-trip loop
+ // to accommodate early returns, insert the continue
+ // target block now, with a false branch back to the loop
+ // header.
+ new_blocks->push_back(std::move(new_blk_ptr));
+ new_blk_ptr =
+ MakeUnique<BasicBlock>(NewLabel(singleTripLoopContinueId));
+ uint32_t false_id = GetFalseId();
+ if (false_id == 0) {
+ return false;
+ }
+ AddBranchCond(false_id, singleTripLoopHeaderId, returnLabelId,
+ &new_blk_ptr);
+ }
+ // Generate the return block.
+ new_blocks->push_back(std::move(new_blk_ptr));
+ new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(returnLabelId));
+ multiBlocks = true;
+ }
+ // Load return value into result id of call, if it exists.
+ if (returnVarId != 0) {
+ const uint32_t resId = call_inst_itr->result_id();
+ assert(resId != 0);
+ AddLoad(calleeTypeId, resId, returnVarId, &new_blk_ptr);
+ }
+ // Copy remaining instructions from caller block.
+ for (Instruction* inst = call_inst_itr->NextNode(); inst;
+ inst = call_inst_itr->NextNode()) {
+ inst->RemoveFromList();
+ std::unique_ptr<Instruction> cp_inst(inst);
+ // If multiple blocks generated, regenerate any same-block
+ // instruction that has not been seen in this last block.
+ if (multiBlocks) {
+ if (!CloneSameBlockOps(&cp_inst, &postCallSB, &preCallSB,
+ &new_blk_ptr)) {
+ return false;
+ }
+
+ // Remember same-block ops in this block.
+ if (IsSameBlockOp(&*cp_inst)) {
+ const uint32_t rid = cp_inst->result_id();
+ postCallSB[rid] = rid;
+ }
+ }
+ new_blk_ptr->AddInstruction(std::move(cp_inst));
+ }
+ // Finalize inline code.
+ new_blocks->push_back(std::move(new_blk_ptr));
+ } break;
+ default: {
+ // Copy callee instruction and remap all input Ids.
+ std::unique_ptr<Instruction> cp_inst(cpi->Clone(context()));
+ bool succeeded = cp_inst->WhileEachInId(
+ [&callee2caller, &callee_result_ids, this](uint32_t* iid) {
+ const auto mapItr = callee2caller.find(*iid);
+ if (mapItr != callee2caller.end()) {
+ *iid = mapItr->second;
+ } else if (callee_result_ids.find(*iid) !=
+ callee_result_ids.end()) {
+ // Forward reference. Allocate a new id, map it,
+ // use it and check for it when remapping result ids
+ const uint32_t nid = context()->TakeNextId();
+ if (nid == 0) {
+ return false;
+ }
+ callee2caller[*iid] = nid;
+ *iid = nid;
+ }
+ return true;
+ });
+ if (!succeeded) {
+ return false;
+ }
+ // If result id is non-zero, remap it. If already mapped, use mapped
+ // value, else use next id.
+ const uint32_t rid = cp_inst->result_id();
+ if (rid != 0) {
+ const auto mapItr = callee2caller.find(rid);
+ uint32_t nid;
+ if (mapItr != callee2caller.end()) {
+ nid = mapItr->second;
+ } else {
+ nid = context()->TakeNextId();
+ if (nid == 0) {
+ return false;
+ }
+ callee2caller[rid] = nid;
+ }
+ cp_inst->SetResultId(nid);
+ get_decoration_mgr()->CloneDecorations(rid, nid);
}
new_blk_ptr->AddInstruction(std::move(cp_inst));
- }
- if (caller_is_loop_header && callee_begins_with_structured_header) {
- // We can't place both the caller's merge instruction and another
- // merge instruction in the same block. So split the calling block.
- // Insert an unconditional branch to a new guard block. Later,
- // once we know the ID of the last block, we will move the caller's
- // OpLoopMerge from the last generated block into the first block.
- // We also wait to avoid invalidating various iterators.
- const auto guard_block_id = this->TakeNextId();
- AddBranch(guard_block_id, &new_blk_ptr);
- new_blocks->push_back(std::move(new_blk_ptr));
- // Start the next block.
- new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(guard_block_id));
- // Reset the mapping of the callee's entry block to point to
- // the guard block. Do this so we can fix up phis later on to
- // satisfy dominance.
- callee2caller[cpi->result_id()] = guard_block_id;
- }
- // If callee has early return, insert a header block for
- // single-trip loop that will encompass callee code. Start postheader
- // block.
- //
- // Note: Consider the following combination:
- // - the caller is a single block loop
- // - the callee does not begin with a structure header
- // - the callee has multiple returns.
- // We still need to split the caller block and insert a guard block.
- // But we only need to do it once. We haven't done it yet, but the
- // single-trip loop header will serve the same purpose.
- if (earlyReturn) {
- singleTripLoopHeaderId = this->TakeNextId();
- AddBranch(singleTripLoopHeaderId, &new_blk_ptr);
- new_blocks->push_back(std::move(new_blk_ptr));
- new_blk_ptr =
- MakeUnique<BasicBlock>(NewLabel(singleTripLoopHeaderId));
- returnLabelId = this->TakeNextId();
- singleTripLoopContinueId = this->TakeNextId();
- AddLoopMerge(returnLabelId, singleTripLoopContinueId, &new_blk_ptr);
- uint32_t postHeaderId = this->TakeNextId();
- AddBranch(postHeaderId, &new_blk_ptr);
- new_blocks->push_back(std::move(new_blk_ptr));
- new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(postHeaderId));
- multiBlocks = true;
- // Reset the mapping of the callee's entry block to point to
- // the post-header block. Do this so we can fix up phis later
- // on to satisfy dominance.
- callee2caller[cpi->result_id()] = postHeaderId;
- }
- } else {
- multiBlocks = true;
+ } break;
}
- } break;
- case SpvOpReturnValue: {
- // Store return value to return variable.
- assert(returnVarId != 0);
- uint32_t valId = cpi->GetInOperand(kSpvReturnValueId).words[0];
- const auto mapItr = callee2caller.find(valId);
- if (mapItr != callee2caller.end()) {
- valId = mapItr->second;
- }
- AddStore(returnVarId, valId, &new_blk_ptr);
+ return true;
+ });
- // Remember we saw a return; if followed by a label, will need to
- // insert branch.
- prevInstWasReturn = true;
- } break;
- case SpvOpReturn: {
- // Remember we saw a return; if followed by a label, will need to
- // insert branch.
- prevInstWasReturn = true;
- } break;
- case SpvOpFunctionEnd: {
- // If there was an early return, we generated a return label id
- // for it. Now we have to generate the return block with that Id.
- if (returnLabelId != 0) {
- // If previous instruction was return, insert branch instruction
- // to return block.
- if (prevInstWasReturn) AddBranch(returnLabelId, &new_blk_ptr);
- if (earlyReturn) {
- // If we generated a loop header for the single-trip loop
- // to accommodate early returns, insert the continue
- // target block now, with a false branch back to the loop header.
- new_blocks->push_back(std::move(new_blk_ptr));
- new_blk_ptr =
- MakeUnique<BasicBlock>(NewLabel(singleTripLoopContinueId));
- AddBranchCond(GetFalseId(), singleTripLoopHeaderId, returnLabelId,
- &new_blk_ptr);
- }
- // Generate the return block.
- new_blocks->push_back(std::move(new_blk_ptr));
- new_blk_ptr = MakeUnique<BasicBlock>(NewLabel(returnLabelId));
- multiBlocks = true;
- }
- // Load return value into result id of call, if it exists.
- if (returnVarId != 0) {
- const uint32_t resId = call_inst_itr->result_id();
- assert(resId != 0);
- AddLoad(calleeTypeId, resId, returnVarId, &new_blk_ptr);
- }
- // Copy remaining instructions from caller block.
- for (Instruction* inst = call_inst_itr->NextNode(); inst;
- inst = call_inst_itr->NextNode()) {
- inst->RemoveFromList();
- std::unique_ptr<Instruction> cp_inst(inst);
- // If multiple blocks generated, regenerate any same-block
- // instruction that has not been seen in this last block.
- if (multiBlocks) {
- CloneSameBlockOps(&cp_inst, &postCallSB, &preCallSB, &new_blk_ptr);
- // Remember same-block ops in this block.
- if (IsSameBlockOp(&*cp_inst)) {
- const uint32_t rid = cp_inst->result_id();
- postCallSB[rid] = rid;
- }
- }
- new_blk_ptr->AddInstruction(std::move(cp_inst));
- }
- // Finalize inline code.
- new_blocks->push_back(std::move(new_blk_ptr));
- } break;
- default: {
- // Copy callee instruction and remap all input Ids.
- std::unique_ptr<Instruction> cp_inst(cpi->Clone(context()));
- cp_inst->ForEachInId([&callee2caller, &callee_result_ids,
- this](uint32_t* iid) {
- const auto mapItr = callee2caller.find(*iid);
- if (mapItr != callee2caller.end()) {
- *iid = mapItr->second;
- } else if (callee_result_ids.find(*iid) != callee_result_ids.end()) {
- // Forward reference. Allocate a new id, map it,
- // use it and check for it when remapping result ids
- const uint32_t nid = this->TakeNextId();
- callee2caller[*iid] = nid;
- *iid = nid;
- }
- });
- // If result id is non-zero, remap it. If already mapped, use mapped
- // value, else use next id.
- const uint32_t rid = cp_inst->result_id();
- if (rid != 0) {
- const auto mapItr = callee2caller.find(rid);
- uint32_t nid;
- if (mapItr != callee2caller.end()) {
- nid = mapItr->second;
- } else {
- nid = this->TakeNextId();
- callee2caller[rid] = nid;
- }
- cp_inst->SetResultId(nid);
- get_decoration_mgr()->CloneDecorations(rid, nid);
- }
- new_blk_ptr->AddInstruction(std::move(cp_inst));
- } break;
- }
- });
+ if (!successful) {
+ return false;
+ }
if (caller_is_loop_header && (new_blocks->size() > 1)) {
// Move the OpLoopMerge from the last block back to the first, where
@@ -532,6 +626,7 @@
for (auto& blk : *new_blocks) {
id2block_[blk->id()] = &*blk;
}
+ return true;
}
bool InlinePass::IsInlinableFunctionCall(const Instruction* inst) {
diff --git a/source/opt/inline_pass.h b/source/opt/inline_pass.h
index e23e7f0..ecfe964 100644
--- a/source/opt/inline_pass.h
+++ b/source/opt/inline_pass.h
@@ -41,7 +41,8 @@
protected:
InlinePass();
- // Add pointer to type to module and return resultId.
+ // Add pointer to type to module and return resultId. Returns 0 if the type
+ // could not be created.
uint32_t AddPointerToType(uint32_t type_id, SpvStorageClass storage_class);
// Add unconditional branch to labelId to end of block block_ptr.
@@ -67,20 +68,22 @@
std::unique_ptr<Instruction> NewLabel(uint32_t label_id);
// Returns the id for the boolean false value. Looks in the module first
- // and creates it if not found. Remembers it for future calls.
+ // and creates it if not found. Remembers it for future calls. Returns 0 if
+ // the value could not be created.
uint32_t GetFalseId();
// Map callee params to caller args
void MapParams(Function* calleeFn, BasicBlock::iterator call_inst_itr,
std::unordered_map<uint32_t, uint32_t>* callee2caller);
- // Clone and map callee locals
- void CloneAndMapLocals(Function* calleeFn,
+ // Clone and map callee locals. Return true if successful.
+ bool CloneAndMapLocals(Function* calleeFn,
std::vector<std::unique_ptr<Instruction>>* new_vars,
std::unordered_map<uint32_t, uint32_t>* callee2caller);
- // Create return variable for callee clone code if needed. Return id
- // if created, otherwise 0.
+ // Create return variable for callee clone code. The return type of
+ // |calleeFn| must not be void. Returns the id of the return variable if
+ // created. Returns 0 if the return variable could not be created.
uint32_t CreateReturnVar(Function* calleeFn,
std::vector<std::unique_ptr<Instruction>>* new_vars);
@@ -92,7 +95,7 @@
// Look in preCallSB for instructions that need cloning. Look in
// postCallSB for instructions already cloned. Add cloned instruction
// to postCallSB.
- void CloneSameBlockOps(std::unique_ptr<Instruction>* inst,
+ bool CloneSameBlockOps(std::unique_ptr<Instruction>* inst,
std::unordered_map<uint32_t, uint32_t>* postCallSB,
std::unordered_map<uint32_t, Instruction*>* preCallSB,
std::unique_ptr<BasicBlock>* block_ptr);
@@ -111,7 +114,9 @@
// Also return in new_vars additional OpVariable instructions required by
// and to be inserted into the caller function after the block at
// call_block_itr is replaced with new_blocks.
- void GenInlineCode(std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
+ //
+ // Returns true if successful.
+ bool GenInlineCode(std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
std::vector<std::unique_ptr<Instruction>>* new_vars,
BasicBlock::iterator call_inst_itr,
UptrVectorIterator<BasicBlock> call_block_itr);