Handling loads and stores of non-pointer types in pointer analysis

haved commented 2 months ago

This issue replaces #252, since that issue mixed together a lot of more or less relevant points. This issue will present a more concise problem, and avoid extreme cases of pointer casting and (mis)use of unions.

Take the following code, which is valid C and C++:


#include <stdlib.h>

typedef struct node node;

// Copy one array of node* values into another
void copyPointerArray(node ** dest, node ** src, size_t n)
{
    char* destC = (char*) dest;
    char* srcC = (char*) src;
    for (size_t i = 0; i < n * sizeof(node*); i++)
        destC[i] = srcC[i];
}

Normally, casting a pointer to a different pointer type and dereferencing it is undefined behavior, but char * is different, since char may alias any other type. This is a valid way of copying data, corresponding to a memcpy. We do have special handling of memcpy to avoid this issue in most cases, but doing memcpy manually should also be allowed.

Inside the loop, we are only reading and writing chars, so the current alias analysis implementations ignore those loads and stores. This means the pointees of *src are not propagated to *dest. From the perspective of a the alias analysis, nothing is happening in this function.

I have never seen an alias analysis paper where they attempt to track pointees of values smaller than sizeof(void*), so I'm not suggesting we do that either. My suggested way of handling this is as follows:

When loading a char, the memory objects being (possibly) loaded are all marked as "pointees escaping". When storing a char, all memory objects being (possibly) written are marked as pointing to external. I'm hoping that due to strict aliasing, we can get away with only doing this for char, and not all scalars. LLVM has a much more "untyped" memory model, but we can start with C/C++ with strict aliasing only.

This alone might cause the PointsToGraph to get a lot of extra edges, which is why I propose a second change: Alloca, Delta and Import memory objects corresponding to non-pointer types, should have no pointees in the PointsToGraph, like we are currently doing with functions.

In total, I don't think this change would affect most programs. However, since our analysis is currently field-insensitive, a struct containing both char and pointers will mix them up, and mark the pointer as pointing to external, when the char is written to. I'm unsure how much this will affect the final precision of the analysis. It is an unfortunate side-effect of trying to catch all cases of pointers being read and written as something other than pointers.

I would like to test how much of a difference it makes in Andersen, where it would be very easy to implement (create a dummy node marked with PointsToExternal and PointeesEscaping, and pretend to load and store all chars from it). This testing can be done outside of the master branch until I know more about its effects.

What I would like to confirm is the idea of not adding any outgoing edges in the PointsToGraph from Alloca, Delta and Import nodes that represent variables that the type system says do not contain pointers.

phate commented 2 months ago

Adding the LLVM IR:

; ModuleID = 'test.c'                                                                                  
source_filename = "test.c"                                                                             
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"           
target triple = "x86_64-pc-linux-gnu"                                                                  

; Function Attrs: nofree norecurse nosync nounwind memory(argmem: readwrite) uwtable                   
define dso_local void @copyPointerArray(ptr nocapture noundef writeonly %0, ptr nocapture noundef readonly %1, i64 noundef %2) local_unnamed_addr #0 {
  %4 = shl i64 %2, 3                                                                                   
  %5 = icmp eq i64 %4, 0                                                                               
  br i1 %5, label %6, label %7                                                                         

6:                                                ; preds = %7, %3                                     
  ret void                                                                                             

7:                                                ; preds = %3, %7                                     
  %8 = phi i64 [ %12, %7 ], [ 0, %3 ]                                                                  
  %9 = getelementptr inbounds i8, ptr %1, i64 %8                                                       
  %10 = load i8, ptr %9, align 1, !tbaa !5                                                             
  %11 = getelementptr inbounds i8, ptr %0, i64 %8                                                      
  store i8 %10, ptr %11, align 1, !tbaa !5                                                             
  %12 = add nuw i64 %8, 1                                                                              
  %13 = icmp eq i64 %12, %4                                                                            
  br i1 %13, label %6, label %7, !llvm.loop !8                                                         
}                                                                                                      

attributes #0 = { nofree norecurse nosync nounwind memory(argmem: readwrite) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}                                                                 
!llvm.ident = !{!4}                                                                                    

!0 = !{i32 1, !"wchar_size", i32 4}                                                                    
!1 = !{i32 8, !"PIC Level", i32 2}                                                                     
!2 = !{i32 7, !"PIE Level", i32 2}                                                                     
!3 = !{i32 7, !"uwtable", i32 2}                                                                       
!4 = !{!"Ubuntu clang version 16.0.6 (15)"}                                                            
!5 = !{!6, !6, i64 0}                                                                                  
!6 = !{!"omnipotent char", !7, i64 0}                                                                  
!7 = !{!"Simple C/C++ TBAA"}                                                                           
!8 = distinct !{!8, !9, !10}                                                                           
!9 = !{!"llvm.loop.mustprogress"}                                                                      
!10 = !{!"llvm.loop.unroll.disable"}

It was created using clang -S -emit-llvm -Wall -O1 test.c, where test.c contains the C program from above.

@caleridas I would be interested to here your opinion here.

phate commented 2 months ago

Just leaving this here as I found them useful:

Moreover, there are multiple proposals in the LLVM community to also address this problem:

So the entire matter is rather not even settled in the LLVM community. I need to ponder more about this, but I am wondering how much energy we should actually put into this, i.e., effort vs. return.

haved commented 2 months ago

Thanks for the sources, I know Ralf Jung has put a lot of thought into these types of things. I will take a look, as I definitely haven't read everything he has written about it. I think he is the one who introduced me to pointer provenance originally.

I will not put that much thought into this for now, and continue to ignore loads and stores of scalars in the analysis. I can still write about the issue in the thesis.

phate / jlm

Handling loads and stores of non-pointer types in pointer analysis #444