Taichi: Support break in non-parallel for statements

[yuanming-hu]

Concisely describe the proposed feature

@ti.kernel
def sums():
  for i in range(n):
    is_prime[i] = 1
    for j in range(i):
       if i % j == 0:
         is_prime[i] = 0
       if j * j > i:
         break # This is not supported now...

Describe the solution you'd like (if any)
Add an IR pass that lower non-parallel fors with break statements into while statements.
While statements already support breaks (WhileControlStmt).

[archibate]

Can we lower RangeForStmt into WhileStmt? So no reludent work is necessary on each backend.
Also StructForStmt? I'm not super clear about the diff between them. May work some degree?

[yuanming-hu]

Can we lower RangeForStmt into WhileStmt? So no reludent work is necessary on each backend.
Also StructForStmt? I'm not super clear about the diff between them. May work some degree?

We can only lower non-parallel for loops into while. Struct-for loops are always parallel.

[archibate]

Btw, break in parallel ones aren't allowed, right? (break have a clear assumption of serial execution...)

[yuanming-hu]

Btw, break in parallel ones aren't allowed, right? (break have a clear assumption of serial execution...)

exactly!

[archibate]

Can we lower RangeForStmt into WhileStmt? So no reludent work is necessary on each backend.
Also StructForStmt? I'm not super clear about the diff between them. May work some degree?

We can only lower non-parallel for loops into while. Struct-for loops are always parallel.

Great! I decided to work on this today.

[yuanming-hu]

Nice! Before you start, keep in mind that we only want to lower non-parallel range-for statements that contain at least one FrontendBreakStmt. For loops that live at the outer-most scope are automatically parallel. We should implement this within the lower pass when FrontendBreakStmt has not been lowered into WhileControlStmt.

[archibate]

Before I could compile, I need to ask how to deal with the spdlog submodule? Keeps fatal error: 'spdlog/fmt/bundled/color.h' file not found though I've cloned spdlog there into external/spdlog...

[yuanming-hu]

git submodule update?

[archibate]

Didn't have any response... Tried removing the whole dir and run that, dir not created.

[yuanming-hu]

Try git submodule init?

[archibate]

I would suggest not to introduce a submodule... since their API could change by time. And contributors will stuck with dealing color.h file not found for a long time...

[archibate]

Working after init then update!

[yuanming-hu]

I would suggest not to introduce a submodule... since their API could change by time. And contributors will stuck with dealing color.h file not found for a long time...

Yeah I know submodules can be confusing, but using them makes it easy to upgrade our dependencies frequently. Also, it leads to a clearer git history compared to copy-pasting files with huge changesets.

[archibate]

I hate submodules :(

尚未暂存以备提交的变更：
  （使用 "git add <文件>..." 更新要提交的内容）
  （使用 "git restore <文件>..." 丢弃工作区的改动）
  （提交或丢弃子模组中未跟踪或修改的内容）
        修改：     external/spdlog (新提交, 修改的内容)

修改尚未加入提交（使用 "git add" 和/或 "git commit -a"）

Make me can't happily git add . anymore.
Tried .gitignore, didn't work...

[yuanming-hu]

I hate them too but they are used by a lot of mature open-source projects.

Make me can't happily git add . anymore.
Tried .gitignore, didn't work...

The submodules will not be changed frequently. Maybe we can add a submodule tutorial to Contributor Guideline.

[archibate]

Super slow receving spdlog in GFW :(

接收对象中:  69% (12579/18034), 14.22 MiB | 28.00 KiB/s

Can I specify --depth=1 to that? Didn't move for a few miniutes...

[yuanming-hu]

Does this work for you? https://stackoverflow.com/questions/2144406/how-to-make-shallow-git-submodules

[archibate]

It works!

[archibate]

I hate them too but they are used by a lot of mature open-source projects.

Make me can't happily git add . anymore.
Tried .gitignore, didn't work...

The submodules will not be changed frequently. Maybe we can add a submodule tutorial to Contributor Guideline.

To tell them run git submodule init&update after git clone?
Or this is automatically done for new-cloners?

[yuanming-hu]

I believe for git clone --recursive this is automatic

[archibate]

I also found taichi_assets may be not appreciated by some users, containing some meshes used by mpm examples which may not be so useful for some people.. Is this cloned by git clone --recursive?

[yuanming-hu]

No, it's no longer an existing submodule. It's just part of the module list. Not sure if we will need it sometime later so I kept the git URL.

[archibate]

Good. Can't found a good place in taichi/transforms/xx.cpp's, shall I create a taichi/transforms/for_by_while.cpp?

[yuanming-hu]

I would suggest implementing this in lower_ast.cpp: https://github.com/taichi-dev/taichi/issues/578#issuecomment-597395981

You might also want to create a pass in analysis named find_serial_range_fors_with_break that returns an std::set<Stmt *> of fors to lower into while.

[archibate]

I would suggest implementing this in lower_ast.cpp: #578 (comment)

But FrontendBreakStmt is also in lower_ast.cpp.

You might also want to create a pass in analysis named find_serial_range_fors_with_break that returns an std::set<Stmt *> of fors to lower into while.

So only those fors_with_break are lowered into while?

[yuanming-hu]

But FrontendBreakStmt is also in lower_ast.cpp.

Yes, that's why we should first do an analysis pass before FrontendBreakStmts are lower into WhileControlStmt.

So only those fors_with_break are lowered into while?

Exactly!

[archibate]

So only those fors_with_break are lowered into while?

Exactly!

What I was thinking about was, translate FrontendForStmt into GlobalTempStmt + WhileStmt:

for i in range(233):

i = 0
tmp_range_max = 233
while i < tmp_range_max:

So break could be done simpler and else could be added just once.

[yuanming-hu]

I guess using a local AllocaStmt is easier? You might have multiple instances of serial fors running in parallel so allocating GlobalTemp would be tricky.

[archibate]

[E 03/11/20 13:54:26.793] [ir.h:BinaryOpStmt@972] !lhs->is<AllocaStmt>()

Why not allow me to binary cmp_lt with alloca-ed loop_var..

[yuanming-hu]

You probably need a LocalLoadStmt to convert that local pointer to a local value?

[archibate]

May works but:
no known conversion from 'taichi::lang::AllocaStmt *' to 'LaneAttribute<taichi::lang::LocalAddress>'
How can I make LocalLoad load an alloca variable?

[yuanming-hu]

Stmt::make<LocaLoadStmt>(LaneAttribute<LocalAddress>(alloca, 0))?

[archibate]

Ok now, using LaneAttribute<LocalAddress>(LocalAddress(alloca, 0)). Would you like to add a (T args...) initializer to LaneAttribute?
Now keep [E 03/12/20 22:15:10.195] [ir.h:replace_with@1345] location != -1.
Seems we can't find FrontendForStmt in its parent but FrontendWhileStmt (which I copied codes from) can.

[yuanming-hu]

Well done by @archibate.