source: doc/theses/mike_brooks_MMath/programs/array-boundcheck-removal-stdvec.cpp @ 8d76f2b

ADTast-experimentalenumpthread-emulationqualifiedEnum
Last change on this file since 8d76f2b was 8d76f2b, checked in by Michael Brooks <mlbrooks@…>, 2 years ago

Adding runtime bound checking for array subscripts and showing the optimizer removing them.

Adding draft thesis content on dependent types and bound checks.

  • Property mode set to 100644
File size: 2.8 KB
Line 
1/*
2// traditional "naiive" loops
3forall( [M], [N], [P] )
4void matmul( array(float, M, P) & src1,
5             array(float, P, N) & src2,
6             array(float, M, N) & tgt ) {
7    for (i; M) for (j; N) {
8        tgt[i][j] = 0;
9        for (k; P)
10            tgt[i][j] += src1[i][k] * src2[k][j];
11    }
12}
13*/
14
15#if defined BADBOUNDS
16#define BOUND(X) 17
17#else
18#define BOUND(X) X
19#endif
20
21#include <vector>
22using namespace std;
23
24
25#ifndef TESTCASE
26#define TESTCASE 1
27#endif
28
29#if TESTCASE==1
30
31float f( vector<float> & a ) {
32    float result = 0;
33    for( int i = 0; i < BOUND(a.size()); i++ ) {
34        result += a.at(i);
35        // hillarious that, while writing THIS VERY DEMO, on first go, I actaully wrote it a[i]
36    }
37    return result;
38}
39
40#ifdef WITHHARNESS
41#include <iostream>
42int main( int argc, char ** argv ) {
43    vector<float> v(5);
44    v.at(0) = 3.14;
45    v.at(1) = 3.14;
46    v.at(2) = 3.14;
47    v.at(3) = 3.14;
48    v.at(4) = 3.14;
49
50    float answer = f(v);
51
52    cout << "answer: " << answer << endl;
53
54}
55#endif
56
57// g++ array-boundcheck-removal-stdvec.cpp -DWITHHARNESS -DBADBOUNDS
58// ./a.out
59// Aborted: terminate called after throwing an instance of 'std::out_of_range'
60
61
62// g++ array-boundcheck-removal-stdvec.cpp -DWITHHARNESS
63// ./a.out
64// answer: 15.7
65
66// g++ array-boundcheck-removal-stdvec.cpp -S -O2 -DBADBOUNDS
67// loop has cmp-jmp
68// jmp target has call _ZSt24__throw_out_of_range_fmtPKcz@PLT
69
70// g++ array-boundcheck-removal-stdvec.cpp -S -O2
71// loop is clean
72
73
74#elif TESTCASE==2
75
76//#include <cassert>
77#define assert(prop) if (!prop) return
78
79typedef vector<vector<float> > mat;
80
81void matmul( mat & a, mat & b, mat & rslt ) {
82    size_t m = rslt.size();
83    assert( m == a.size() );
84    size_t p = b.size();
85    for ( int i = 0; i < BOUND(m); i++ ) {
86        assert( p == a.at(i).size() );
87        size_t n = rslt.at(i).size();
88        for ( int j = 0; j < BOUND(n); j++ ) {
89            rslt.at(i).at(j) = 0.0;
90            for ( int k = 0; k < BOUND(p); k++ ) {
91                assert(b.at(k).size() == n); // asking to check it too often
92                rslt.at(i).at(j) += a.at(i).at(k) * b.at(k).at(j);
93            }
94        }
95    }
96}
97
98#ifdef WITHHARNESS
99#include <iostream>
100int main( int argc, char ** argv ) {
101    mat a(5, vector<float>(6));
102    mat b(6, vector<float>(7));
103    mat r(5, vector<float>(7));
104    matmul(a, b, r);
105}
106#endif
107
108// (modify the declarations in main to be off by one, each of the 6 values at a time)
109// g++ array-boundcheck-removal-stdvec.cpp -DWITHHARNESS -DTESTCASE=2
110// ./a.out
111// (see an assertion failure)
112
113// g++ array-boundcheck-removal-stdvec.cpp -DWITHHARNESS -DTESTCASE=2
114// ./a.out
115// (runs fine)
116
117// g++ array-boundcheck-removal-stdvec.cpp -S -O2 -DTESTCASE=2
118// hypothesis: loop bound checks are clean because the assertions took care of it
119// actual so far:  both assertions and bound checks survived
120
121#endif
Note: See TracBrowser for help on using the repository browser.