[Opt] [ir] [refactor] Remove exceptions from IR passes

[xumingkuan]

Currently, we have many IR passes using the pattern of exception, and we want to get rid of it.

How do we use exceptions now
We throw IRModified(); when the IR is modified, and catch it using some code like the follows:

ConstantFold folder;
while (true) {
  bool modified = false;
  try {
    node->accept(&folder);
  } catch (IRModified) {
    modified = true;
  }
  if (!modified)
    break;
}

Why do we need to use exceptions
I think the main reason comes from here:

void BasicStmtVisitor::visit(Block *stmt_list) {
  for (auto &stmt : stmt_list->statements) {
    stmt->accept(this);
  }
}

Whenever we erase a statement from or insert one to a block, all std::vector::iterators of that block's statements may be invalidated. So we need to break all for loops like the above, and the most convenient way is to use exceptions.

Why we want & how to get rid of exceptions
Using exceptions is probably not a good coding style, and it may cause some incompatibility issues, as discussed in #655.

If we mark all modifications in IR optimization passes and do them together iteratively instead of modifying the IR and throw an exception as soon as we find an optimization opportunity, this will greatly reduce compilation time and solve #926.

TODO list

• alg_simp ([Opt] [refactor] Avoid throwing exceptions in alg_simp and let it support more types #1060, [opt] Add a DelayedIRModifier class #1103)
• check_out_of_bound ([Opt] [ir] [refactor] Remove exceptions from IR check_out_of_bound and constant_fold #1251)
• constant_fold ([Opt] [ir] [refactor] Remove exceptions from IR check_out_of_bound and constant_fold #1251)
• demote_atomics ([Opt] [ir] [refactor] Remove exceptions from demote_atomics pass #1272)
• die ([Opt] [ir] [refactor] Remove exceptions from DIE pass #1262)
• extract_constant ([Opt] [ir] [refactor] Remove exceptions from IR pass extract_constant #2966)
• lower_access ([Opt] [ir] [refactor] Remove exceptions from lower_access pass #1292)
• lower_ast ([opt] [ir] [refactor] Remove exceptions from lower_ast pass #3916)
• offload ([opt] [ir] [refactor] Remove exceptions from offload pass #3925)
• simplify (high priority) ([Opt] [ir] [refactor] Remove exception from simpify pass #3317)
• variable_optimization ([opt] [refactor] Remove the variable_optimization pass #3927)
• whole_kernel_cse ([opt] [refactor] [bug] Avoid throwing exceptions in whole_kernel_cse and fix a bug #1131)

Additional comments
Shall we add the noexcept specifier to some functions known to not throw IRModified? Will it cause some issues with other exceptions?

[TH3CHARLie]

@xumingkuan I'd like to help with this. What would you suggest the proper size of a related PR? Should we use a single PR to refactor all TODO passes or maybe 3-4 passes in one PR?

[xumingkuan]

@xumingkuan I'd like to help with this. What would you suggest the proper size of a related PR? Should we use a single PR to refactor all TODO passes or maybe 3-4 passes in one PR?

I think it's fine with only 1 pass in one PR. Different passes usually won't cause conflicts even if you open several PRs at the same time, and it might be error-prone if many passes are refactored in one PR.

[TH3CHARLie]

As I look through the lower_ast pass, I notice that:

taichi/taichi/transforms/lower_ast.cpp

Lines 143 to 145 in 4213973

	void visit(FrontendContinueStmt *stmt) override {
	stmt->parent->replace_with(stmt, Stmt::make<ContinueStmt>());
	}

Note: Block::replace_with(Stmt *old_statement, std::unique_ptr &&new_statement, bool replace_usages) is safe even if we modify it directly and don't throw exceptions. So is Block::replace_with(Stmt *old_statement, VecStatement &&new_statements, bool replace_usages) only when new_statements->size() == 1.

I believe the code corresponds to your comment in #1272. But if we'll change the pass's signature to bool(so that the higher level logic would have no whether this pass modified IR), maybe we'd introduce some flag to denote that a change is made.

[xumingkuan]

Oh, for the specific pass lower_ast, it must modify the IR because it converts the frontend IR to the middle-end IR. So feel free to not change that pass's signature.

[xumingkuan]

@TH3CHARLie
As #926 (comment) addressed, irpass::simplify will take half of the compilation time after I remove the variable_optimization pass next week. So among the remaining passes, let's remove exceptions from the simplify pass first.

[yuanming-hu]

@xumingkuan IIRC the simplify pass is mostly CSE. Given that we have a whole program CSE pass that does a better job, should we first try to remove the CSE part of simplify?

[xumingkuan]

I think yes, and shall we replace simplify with full_simplify in Simplified I?

[yuanming-hu]

That sounds good. Thanks.

[TH3CHARLie]

@TH3CHARLie
As #926 (comment) addressed, irpass::simplify will take half of the compilation time after I remove the variable_optimization pass next week. So among the remaining passes, let's remove exceptions from the simplify pass first.

If I understand the conversations correctly, simplify will be refactored soon, so maybe I shouldn't do it?

[xumingkuan]

I think yes -- I'll try to remove the CSE part of simplify first.

[mzmzm]

It looks like that variable_optimization pass never be called anywhere. Maybe it can be removed from this project?

[strongoier]

It looks like that variable_optimization pass never be called anywhere. Maybe it can be removed from this project?

I agree. It seems that its dependency, StateMachine, is also not used elsewhere now. @xumingkuan wdyt?

[xumingkuan]

It looks like that variable_optimization pass never be called anywhere. Maybe it can be removed from this project?

I agree. It seems that its dependency, StateMachine, is also not used elsewhere now. @xumingkuan wdyt?

Agreed. The variable_optimization pass is an obsolete approach to cfg_optimization and we can remove it.