taichi: Support break in non-parallel for statements

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).

About this issue

Original URL
State: closed
Created 4 years ago
Comments: 34 (16 by maintainers)

Commits related to this issue

Support break in non-parallel for statements by translate range-for into while #578 (#583) * [skip ci] tmp save * [skip ci] why die loop * [skip ci] try fix2 btysegf * [skip ci] reformat; ad... — committed to taichi-dev/taichi by archibate 4 years ago

Most upvoted comments

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.

yuanming-hu on Mar 11, 2020

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

yuanming-hu on Mar 12, 2020

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

yuanming-hu on Mar 11, 2020

[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…

archibate on Mar 11, 2020

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.

yuanming-hu on Mar 11, 2020

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.

yuanming-hu on Mar 11, 2020

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?

archibate on Mar 11, 2020

I believe for git clone --recursive this is automatic

yuanming-hu on Mar 11, 2020

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

yuanming-hu on Mar 11, 2020

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…

archibate on Mar 11, 2020

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…

archibate on Mar 11, 2020

Working after init then update!

archibate on Mar 11, 2020

Try git submodule init?

yuanming-hu on Mar 11, 2020

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.

yuanming-hu on Mar 11, 2020

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.

archibate on Mar 11, 2020

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

exactly!

yuanming-hu on Mar 11, 2020

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

archibate on Mar 11, 2020