www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Eliding of slice range checking

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Does DMD/LDC avoid range-checking in slice-expressions such as 
the one in my array-overload of `startsWith` defined as

bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
{
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
slice range checking avoid here?
     }
     return false;
}

///
 safe pure nothrow  nogc unittest
{
     auto x = "beta version";
     assert(x.startsWith("beta"));
}

when building in release mode?

I remember a DMD pull from Ian Buclaw that enabled some eliding 
but I don't remember if it includes the case above.

How can I investigate the codegen myself here?
Oct 23 2019
next sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:

 How can I investigate the codegen myself here?


Simply check the IR or asm, e.g., on run.dlang.io. If there's a 
call to `_d_arraybounds` in the function of interest, bounds 
checks are enabled.

For your example, the template is inferred to be  safe, and 
`-release` only elides bounds checks in  system functions 
(corresponding to `-boundscheck=safeonly`). Use 
`-boundscheck=off` to elide it in all functions.
Oct 23 2019
next sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:

 For your example, the template is inferred to be  safe, and 
 `-release` only elides bounds checks in  system functions 
 (corresponding to `-boundscheck=safeonly`). Use 
 `-boundscheck=off` to elide it in all functions.


Thanks. But I'm talking about the compiler being able to figure 
out that the expression

     haystack[0 .. needle.length]

_never_ (regardless of compiler flags) needs any range checking 
because it is _only_ run when

     haystack.length >= needle.length

. Do you follow?
Oct 23 2019
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 23 October 2019 at 12:01:47 UTC, Per Nordlöw wrote:

 On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:

 For your example, the template is inferred to be  safe, and 
 `-release` only elides bounds checks in  system functions 
 (corresponding to `-boundscheck=safeonly`). Use 
 `-boundscheck=off` to elide it in all functions.


 Thanks. But I'm talking about the compiler being able to figure 
 out that the expression

     haystack[0 .. needle.length]

 _never_ (regardless of compiler flags) needs any range checking 
 because it is _only_ run when

     haystack.length >= needle.length

 . Do you follow?


Actually what you want is that the compiler uses a loop-invariant 
to only to bounds-checking once on the first loop entry?

That's quite tricky to do for all cases.
What you can do manually is to index the .ptr property which will 
decay the array to a pointer, and on a pointer you cannot and 
therefore will not do boundschecking

just replace x = a[i] with x = a.ptr[i];
Oct 25 2019
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/25/2019 05:37 AM, Stefan Koch wrote:


 just replace x = a[i] with x = a.ptr[i];


That's a neat trick!

Ali
Oct 25 2019
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 25 October 2019 at 15:22:12 UTC, Ali Çehreli wrote:

 On 10/25/2019 05:37 AM, Stefan Koch wrote:


 just replace x = a[i] with x = a.ptr[i];


 That's a neat trick!

 Ali


But it requires the function to be qualified as  trusted which 
might hide a  system == operator. How common is it for a == 
operator to be unsafe?
Oct 25 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 25 October 2019 at 21:33:26 UTC, Per Nordlöw wrote:

 But it requires the function to be qualified as  trusted which 
 might hide a  system == operator. How common is it for a == 
 operator to be unsafe?


Ping.
Oct 29 2019
prev sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:

 Simply check the IR or asm, e.g., on run.dlang.io. If there's a 
 call to `_d_arraybounds` in the function of interest, bounds 
 checks are enabled.


The ASM- and IR-output from the following code is pretty messy for

    ldc with flags `-release -O`

Is it possible to remove cluttering?

https://run.dlang.io/is/mAXOm6
Oct 23 2019
next sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 13:08:34 UTC, Per Nordlöw wrote:

 The ASM- and IR-output from the following code is pretty messy 
 for


You call this messy?!

cmpq	%rdi, %rdx
	jae	.LBB0_2
	xorl	%eax, %eax
	retq
.LBB0_2:
	movq	%rdi, %rax
	testq	%rdi, %rdi
	je	.LBB0_3
	pushq	%rax
	.cfi_def_cfa_offset 16
	movq	%rcx, %rdi
	movq	%rax, %rdx
	callq	memcmp PLT
	testl	%eax, %eax
	sete	%al
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	retq
.LBB0_3:
	movb	$1, %al
	retq

Anyway, clearly no bounds checks, LLVM's optimizer works as it 
should.
Oct 23 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 13:51:19 UTC, kinke wrote:

 You call this messy?!

 cmpq	%rdi, %rdx
 	jae	.LBB0_2
 	xorl	%eax, %eax
 	retq
 .LBB0_2:
 	movq	%rdi, %rax
 	testq	%rdi, %rdi
 	je	.LBB0_3
 	pushq	%rax
 	.cfi_def_cfa_offset 16
 	movq	%rcx, %rdi
 	movq	%rax, %rdx
 	callq	memcmp PLT
 	testl	%eax, %eax
 	sete	%al
 	addq	$8, %rsp
 	.cfi_def_cfa_offset 8
 	retq
 .LBB0_3:
 	movb	$1, %al
 	retq


No, this is fine. Thanks.
Oct 29 2019
prev sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 13:08:34 UTC, Per Nordlöw wrote:

 Is it possible to remove cluttering?


godbolt.org supports D as well and is way more powerful than 
run.dlang.io, besides offering way more LDC versions to choose 
from. It can also be used to remove the 'cluttering': 
https://d.godbolt.org/z/ejEmrK
Oct 23 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 14:52:42 UTC, kinke wrote:

 godbolt.org supports D as well and is way more powerful than 
 run.dlang.io, besides offering way more LDC versions to choose 
 from. It can also be used to remove the 'cluttering': 
 https://d.godbolt.org/z/ejEmrK


Very useful. Especially the mouse-over features for if and return 
statements. Are there any more D-code constructs that gets in 
assembly?
Oct 24 2019
prev sibling next sibling parent reply welkam <wwwelkam gmail.com> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:

 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }

 ///
  safe pure nothrow  nogc unittest
 {
     auto x = "beta version";
     assert(x.startsWith("beta"));
 }

 when building in release mode?

 I remember a DMD pull from Ian Buclaw that enabled some eliding 
 but I don't remember if it includes the case above.

 How can I investigate the codegen myself here?


I remember in some video Chandler Carruth said that value range 
propagation across function boundary was implemented in llvm but 
later removed because it produced no performance improvement for 
C and C++ code. I wonder how it fare when used on D code.
Oct 24 2019
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 24 October 2019 at 18:37:05 UTC, welkam wrote:

 I remember in some video Chandler Carruth said that value range 
 propagation across function boundary was implemented in llvm 
 but later removed because it produced no performance 
 improvement for C and C++ code. I wonder how it fare when used 
 on D code.


Interesting. What uses of VRP do you see in D?
Oct 24 2019
parent welkam <wwwelkam gmail.com> writes:
On Thursday, 24 October 2019 at 21:02:03 UTC, Per Nordlöw wrote:

 On Thursday, 24 October 2019 at 18:37:05 UTC, welkam wrote:

 I remember in some video Chandler Carruth said that value 
 range propagation across function boundary was implemented in 
 llvm but later removed because it produced no performance 
 improvement for C and C++ code. I wonder how it fare when used 
 on D code.


 Interesting. What uses of VRP do you see in D?


Now that you asked I realized that it wont be that much useful 
because in D all arrays go together with their size so cross 
function VRP would do little.
Oct 25 2019
prev sibling next sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:

 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }


LDC is good at optimizing simple patterns, the only pitfall I 
know is 
https://forum.dlang.org/post/eoftnwkannqmubhjotat forum.dlang.org
Oct 29 2019
prev sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:

 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }


LDC is good at optimizing simple patterns, the only pitfall I 
know is 
https://forum.dlang.org/post/eoftnwkannqmubhjotat forum.dlang.org
Oct 31 2019