WebAssembly
--spill-pointers fails on program
Below is a simple(ish) sudoku solver.
emcc a.cpp -o a.html produces a working program. If I then add wasm-opt a.wasm --spill-pointers -o a.wasm I get Uncaught RuntimeError: indirect call to null.
I started trying to reduce the program, but found many changes would fix the program, as (I think) the compiler is clever enough to optimise away the need for spilling pointers.
I could try to reduce the example further if that would be useful -- hopefully someone who knows more about wasm-opt might be able to figure out what's going on? --spill-pointers was re-added recently in #4570
I'm finding --spill-pointers fails on most large programs, this was one I found that was (I hope) small enough to be easily looked at, but big enough to fail.
// In this code we represent sudokus as a vector<vector<int> >,
// where the value 0 means 'not yet known'.
#include <vector>
#include <iostream>
#include <ostream>
using namespace std;
vector<int> check_sudoku_vector(vector<int> v);
vector<vector<int> > check_sudoku(vector<vector<int> > sudoku);
vector<vector<int> > read_sudoku();
void print_sudoku(vector<vector<int> > sudoku);
void solve_sudoku(vector<vector<int> > sudoku);
int main(void)
{
vector<vector<int> > v = read_sudoku();
solve_sudoku(v);
}
// Checks a vector does not contain any value twice
// Attempts to fill in values where possible.
// As a hack, we return the empty vector if there are
// any repeated values.
// This tries to fill in the blank value if it can.
vector<int> check_sudoku_vector(vector<int> v)
{
// We need 10 because we want 1..9, and 0 for empty.
vector<int> count(10);
// Count up the occurrences of each value
for(int i = 0; i < 9; ++i)
count[v[i]]++;
// Check if any value occurs twice
for(int i = 1; i <= 9; ++i)
{
if(count[i] > 1)
{
// Some value occurs twice!
vector<int> empty;
return empty;
}
}
if(count[0] == 1)
{
// There is exactly one value to fill in!
int empty_place = -1;
for(int i = 0; i < 9; ++i)
{
if(v[i] == 0)
empty_place = i;
}
for(int i = 1; i <= 9; ++i)
{
if(count[i] == 0)
{
v[empty_place] = i;
return v;
}
}
}
return v;
}
// Tries to fill in the sudoku.
// returns the empty vector if a flaw is found.
// Takes the return value of check_sudoku_vector and puts it back
// in the sudoku. This might be a waste of time, or might fill in a value.
// There are obviously other ways check_sudoku_vector could respond back,
// this is just one example.
vector<vector<int> > check_sudoku(vector<vector<int> > sudoku)
{
vector<vector<int> > empty_vector;
// First check rows
for(int i = 0; i < 9; ++i)
{
vector<int> v = check_sudoku_vector(sudoku[i]);
if(v.empty())
{
return empty_vector;
}
sudoku[i] = v;
}
// then columns
for(int i = 0; i < 9; ++i)
{
vector<int> column;
for(int j = 0; j < 9; ++j)
column.push_back(sudoku[j][i]);
vector<int> v = check_sudoku_vector(column);
if(v.empty())
return empty_vector;
for(int j = 0; j < 9; ++j)
sudoku[j][i] = v[j];
}
// then boxes. Notice we do some interesting
// loop indexing!
for(int i = 0; i < 9; i+=3)
{
for(int j = 0; j < 9; j+=3)
{
vector<int> box;
for(int a = i; a < i + 3; ++a)
for(int b = j; b < j + 3; ++b)
box.push_back(sudoku[a][b]);
vector<int> v = check_sudoku_vector(box);
if(v.empty())
return empty_vector;
// Put the values back in!
int counter = 0;
for(int a = i; a < i + 3; ++a)
for(int b = j; b < j + 3; ++b)
{
sudoku[a][b] = v[counter];
counter++;
}
}
}
// The sudoku is fine!
return sudoku;
}
vector<vector<int> > read_sudoku()
{
vector<vector<int> > v;
for(int i = 0; i < 9; ++i)
{
vector<int> row;
for(int j = 0; j < 9; ++j)
{
int val = 0;
row.push_back(val);
}
v.push_back(row);
}
return v;
}
void print_sudoku(vector<vector<int> > sudoku)
{
for(int i = 0; i < 9; ++i)
{
for(int j = 0; j < 9; ++j)
{
cout << sudoku[i][j] << " ";
}
cout << endl;
}
cout << endl;
exit(0);
}
int counter = 0;
void solve_sudoku(vector<vector<int> > sudoku)
{
counter++;
vector<vector<int> > sudoku_copy = check_sudoku(sudoku);
// This means the sudoku is unsolvable
if(sudoku_copy.empty())
return;
// let's keep looping around until check_sudoku stops filling
// in values!
while(sudoku_copy != sudoku)
{
sudoku = sudoku_copy;
sudoku_copy = check_sudoku(sudoku);
if(sudoku_copy.empty())
return;
}
for(int i = 0; i < 9; ++i)
{
for(int j = 0; j < 9; ++j)
{
if(sudoku[i][j] == 0)
{
// We have found a value to branch on!
for(int k = 1; k <= 9; ++k)
{
sudoku[i][j] = k;
solve_sudoku(sudoku);
}
// No solution found here!
return;
}
}
}
// if we get here, then the solution is complete!
print_sudoku(sudoku);
std::cout << "Search: " << counter << std::endl;
}
Perhaps the stack size is not big enough?
If that doesn't fix it, can try to run with sanitizers who might find something. And reducing it to something minimal would be useful.
Thanks, I'll have a go. Is there a guide to running sanitisers with wasm? Is this the clang ones, do iiust pass them on the command line when compiling?
I reduced to two different small programs but (unfortunately) while they are small C++ programs, they are still calling into significant parts of the standard library:
#include <vector>
int main(void)
{
std::vector<std::vector<int> > v;
std::vector<int> row;
v.push_back(row);
}
And
#include <iostream>
int main(void)
{
std::cout << 2;
}
With emscripten you can use sanitizers normally, just pass the flags at compile and link time, https://emscripten.org/docs/debugging/Sanitizers.html
This isn't a fix, but I have just discovered that ASYNCIFY in emscripten does a similar job to spill pointers (for my purposes anyway), by writing out the stack to a place where I can read it. There may be reasons that spill pointers would be better for some people's purposes, but for mine ASYNCIFY in emscripten is doing the job.
