[mojo-compiler] CompTime interpreter should be able to fold `pop.call_llvm_intrinsic` #933

soraros · 2023-09-27T01:47:21Z

Bug description

math.bit functions doesn't run at compile time.

Steps to reproduce

Consider the following code:

import math.bit as bit

fn main():
  alias n = bit.ctlz(10)

It produces the following error message:

/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:70:1: error: no viable expansions found
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:70:1: note:   call expansion failed - no concrete specializations
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:51:1: note:     no viable expansions found
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:65:57: note:       call expansion failed - no concrete specializations
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:29:1: note:         no viable expansions found
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:42:18: note:           call expansion failed - no concrete specializations
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:62:5: note:             no viable expansions found
/__w/modular/modular/Kernels/mojo/builtin/_startup.mojo:63:22: note:               call expansion failed - no concrete specializations
/workspaces/ubuntu/hello.mojo:3:1: note:                 no viable expansions found
def main():
^
/workspaces/ubuntu/hello.mojo:4:3: note:                   failed to evaluate 'apply'
  alias n = bit.ctlz(10)
  ^
/__w/modular/modular/Kernels/mojo/math/bit.mojo:81:1: note:                     failed to interpret function @$math::$bit::ctlz($builtin::$int::Int)_concrete
/__w/modular/modular/Kernels/mojo/math/bit.mojo:90:44: note:                       failed to fold operation pop.call_llvm_intrinsic(10 : index, #pop<simd false> : !pop.scalar<bool>)
mojo: error: failed to run the pass manager

System information

- OS: Docker on Intel macOS
- mojo -v: mojo 0.3.0 (f64f9601)
- modular -v: modular 0.1.4 (6b54d308)

The text was updated successfully, but these errors were encountered:

Mogball · 2023-09-27T20:28:00Z

Thanks for filing! We haven't implemented compile-time interpretation of LLVM intrinsics, and it's not clear that's a worthwhile endeavor. That said, there are other ways we can make this work.

soraros · 2023-09-27T23:02:52Z

@Mogball Regardless of how the internal works, I'd still expect this code to run. Because from a users perspective, math.bit just look like any other module. If they definitely can't run at compile time, we should somehow use the type system or some decorators to communicate that fact. It would still be great if you could try "the other way" to make this work though.

I was trying to implement power_of_2 with the math.bit functions in constrained[power_of_2(n)]() for SIMD width checking, which I think is pretty valid use case.

Mogball · 2023-09-28T15:37:43Z

A decorator would be useful from a library design perspective to clearly communicate to users what functions are not intended to run at compile time. However, the language can't rely on library authors always being meticulous with using the decorator, which is why it provides a detailed, if cryptic, error message.

I do agree that the category of functions in math.bit should run at compile time though.

abduld · 2023-10-02T00:14:36Z

FYI: There is an is_power_of_2 function in the math module which should be compile-time evaluated . You can implement it yourself using

fn is_power_of_2(val: Int) -> Bool:
    return (val & (val - 1) == 0) and (val != 0)

soraros · 2023-10-02T00:36:53Z

@abduld Thanks for the pointer. I'm familiar with this implementation yet didn't know the existence of this function in the stdlib.

JoeLoser · 2024-04-11T23:42:52Z

I've renamed this issue to track the general problem from my observations this past week. From our internal Mojo discussion on this yesterday, we do want to implement support for this (folding llvm_intrinsincs so they work in compile time).

Some notes I'll share from our internal discussion:

We don’t want a split source of truth that causes divergence between comptime and runtime. ⇒ We don’t want a “if running in the comptime interpreter” parameter check.
Not all llvm intrinsics have folders and some have side effects, so not everything can be run at comptime. This is also true of “printf” or c function at comptime today.
That said, some simple things like this do, and can be folded, so we just need to wire that up.
MLIR LLVM dialect may/probably doesn’t have the ability to do this, so we might have to implement these folders upstream.

The big issue is probably plumbing (4) correctly from the list above.

Mogball · 2024-04-18T01:22:27Z

We can inject fold/interpret hooks into the LLVMDialect. We're not bound by upstream in this regard. I suspect there will be resistance to adding intrinsics folders upstream anyways.

Signed-off-by: martinvuyk <[email protected]>

msaelices · 2024-08-18T21:43:28Z

@JoeLoser, somehow, above's code seems to be working now. I've tested it, and it worked:

from bit import count_leading_zeros

fn main():
  alias n = count_leading_zeros(10)

Note: this is the code adapted from the description based on some bit package changes, as now it's not part of the math package and the ctlz is now called count_leading_zeros

However, I'm not sure if the bug is fixed.

soraros · 2024-08-19T19:17:42Z

@msaelices I think it's because it's being eliminated as dead code. This still fails:

fn main():
  alias n = count_leading_zeros(10)
  print(n)

gabrieldemarmiesse · 2024-09-09T17:43:20Z

@lattner ping on this issue since you asked :)

lattner · 2024-09-16T00:31:00Z

Awesome, I put together a fix, I'll discuss with the team tomorrow and see if they like it.

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes #933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes modularml#933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17 Signed-off-by: Manuel Saelices <[email protected]>

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes modularml#933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes modularml#933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17 Signed-off-by: Derek Smith <[email protected]>

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes modularml#933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17

This teaches the mojo comptime interpreter about LLVM intrinsics, at least for simple cases involving integer operands and results (it would be straightforward to extend this to other types now). This fixes modularml#933 and Fixes MOCO-138 and Fixes MOCO-504 MODULAR_ORIG_COMMIT_REV_ID: 900128df66da907a0bf61a3b2affb730ef253e17 Signed-off-by: Derek Smith <[email protected]>

soraros added bug Something isn't working mojo Issues that are related to mojo labels Sep 27, 2023

ematejska added the mojo-lang Tag for all issues related to language. label Sep 27, 2023

soraros mentioned this issue Apr 7, 2024

[BUG] [mojo] POP folder fails to fold llvm.floor intrinsic when computing sqrt in parameter domain #2218

Closed

JoeLoser changed the title ~~[BUG]: math.bit functions doesn't run at compile time~~ [mojo-compiler] CompTime interpreter should be able to fold pop.call_llvm_intrinsic Apr 11, 2024

ematejska added the mojo-repo Tag all issues with this label label Apr 29, 2024

ematejska added the test-sync-delete after label May 1, 2024 — with Linear

linear bot removed the test-sync-delete after label May 2, 2024

soraros mentioned this issue May 27, 2024

[BUG]: Failed to evaluate math.abs and math.exp at compile-time #1244

Closed

martinvuyk added a commit to martinvuyk/mojo that referenced this issue Jul 2, 2024

add llvm intrinsics issue modularml#933

2cb0880

Signed-off-by: martinvuyk <[email protected]>

martinvuyk mentioned this issue Jul 2, 2024

[stdlib] Fix String.split() and start fixing String.__len__() #2960

Closed

martinvuyk mentioned this issue Jul 11, 2024

[stdlib] Fix SIMD uint cast #3172

Closed

msaelices mentioned this issue Aug 18, 2024

[stdlib] Fix String.lstrip() TODO item because of llvm intrinsics issue at compile time #3395

Open

martinvuyk mentioned this issue Sep 2, 2024

[stdlib] Use SIMD to make b64encode 4.7x faster #3443

Open

lattner self-assigned this Sep 16, 2024

lattner closed this as completed Sep 16, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[mojo-compiler] CompTime interpreter should be able to fold `pop.call_llvm_intrinsic` #933

[mojo-compiler] CompTime interpreter should be able to fold `pop.call_llvm_intrinsic` #933

soraros commented Sep 27, 2023 •

edited

Loading

Mogball commented Sep 27, 2023 •

edited

Loading

soraros commented Sep 27, 2023 •

edited

Loading

Mogball commented Sep 28, 2023

abduld commented Oct 2, 2023 •

edited

Loading

soraros commented Oct 2, 2023

JoeLoser commented Apr 11, 2024

Mogball commented Apr 18, 2024

msaelices commented Aug 18, 2024 •

edited

Loading

soraros commented Aug 19, 2024 •

edited

Loading

gabrieldemarmiesse commented Sep 9, 2024

lattner commented Sep 16, 2024

[mojo-compiler] CompTime interpreter should be able to fold pop.call_llvm_intrinsic #933

[mojo-compiler] CompTime interpreter should be able to fold pop.call_llvm_intrinsic #933

Comments

soraros commented Sep 27, 2023 • edited Loading

Bug description

Steps to reproduce

System information

Mogball commented Sep 27, 2023 • edited Loading

soraros commented Sep 27, 2023 • edited Loading

Mogball commented Sep 28, 2023

abduld commented Oct 2, 2023 • edited Loading

soraros commented Oct 2, 2023

JoeLoser commented Apr 11, 2024

Mogball commented Apr 18, 2024

msaelices commented Aug 18, 2024 • edited Loading

soraros commented Aug 19, 2024 • edited Loading

gabrieldemarmiesse commented Sep 9, 2024

lattner commented Sep 16, 2024

[mojo-compiler] CompTime interpreter should be able to fold `pop.call_llvm_intrinsic` #933

[mojo-compiler] CompTime interpreter should be able to fold `pop.call_llvm_intrinsic` #933

soraros commented Sep 27, 2023 •

edited

Loading

Mogball commented Sep 27, 2023 •

edited

Loading

soraros commented Sep 27, 2023 •

edited

Loading

abduld commented Oct 2, 2023 •

edited

Loading

msaelices commented Aug 18, 2024 •

edited

Loading

soraros commented Aug 19, 2024 •

edited

Loading