1 #include "Util.h"
2 #include "Debug.h"
3 #include "Error.h"
4 #include "Introspection.h"
5 #include <atomic>
6 #include <chrono>
7 #include <fstream>
8 #include <iomanip>
9 #include <map>
10 #include <mutex>
11 #include <sstream>
12 #include <string>
13
14 #ifdef _MSC_VER
15 #include <io.h>
16 #else
17 #include <stdlib.h>
18 #include <unistd.h>
19 #endif
20 #include <sys/stat.h>
21 #include <sys/types.h>
22
23 #ifdef __linux__
24 #define CAN_GET_RUNNING_PROGRAM_NAME
25 #include <linux/limits.h> // For PATH_MAX
26 #endif
27 #if defined(_MSC_VER) && !defined(NOMINMAX)
28 #define NOMINMAX
29 #endif
30 #ifdef _WIN32
31 #include <Objbase.h> // needed for CoCreateGuid
32 #include <Shlobj.h> // needed for SHGetFolderPath
33 #include <windows.h>
34 #else
35 #include <dlfcn.h>
36 #endif
37 #ifdef __APPLE__
38 #define CAN_GET_RUNNING_PROGRAM_NAME
39 #include <mach-o/dyld.h>
40 #endif
41
42 #ifdef _WIN32
43 namespace {
44
from_utf16(LPCWSTR pStr)45 std::string from_utf16(LPCWSTR pStr) {
46 int len = wcslen(pStr);
47
48 int mblen = WideCharToMultiByte(CP_UTF8, 0, pStr, len, nullptr, 0, nullptr, nullptr);
49 internal_assert(mblen) << "WideCharToMultiByte() failed; error " << GetLastError() << "\n";
50
51 std::string str(mblen, 0);
52
53 mblen = WideCharToMultiByte(CP_UTF8, 0, pStr, len, &str[0], (int)str.size(), nullptr, nullptr);
54 internal_assert(mblen) << "WideCharToMultiByte() failed; error " << GetLastError() << "\n";
55
56 return str;
57 }
58
from_utf8(const std::string & str)59 std::wstring from_utf8(const std::string &str) {
60 int wlen = MultiByteToWideChar(CP_UTF8, 0, str.c_str(), (int)str.size(), nullptr, 0);
61 internal_assert(wlen) << "MultiByteToWideChar() failed; error " << GetLastError() << "\n";
62
63 std::wstring wstr(wlen, 0);
64
65 wlen = MultiByteToWideChar(CP_UTF8, 0, str.c_str(), (int)str.size(), &wstr[0], (int)wstr.size());
66 internal_assert(wlen) << "MultiByteToWideChar() failed; error " << GetLastError() << "\n";
67
68 return wstr;
69 }
70
71 } // namespace
72 #endif
73
74 namespace Halide {
75 namespace Internal {
76
77 using std::ostringstream;
78 using std::string;
79 using std::vector;
80
get_env_variable(char const * env_var_name)81 std::string get_env_variable(char const *env_var_name) {
82 if (!env_var_name) {
83 return "";
84 }
85
86 #ifdef _MSC_VER
87 // call getenv_s without a buffer to determine the correct string length:
88 size_t length = 0;
89 if ((getenv_s(&length, NULL, 0, env_var_name) != 0) || (length == 0)) {
90 return "";
91 }
92 // call it again to retrieve the value of the environment variable;
93 // note that 'length' already accounts for the null-terminator
94 std::string lvl(length - 1, '@');
95 size_t read = 0;
96 if ((getenv_s(&read, &lvl[0], length, env_var_name) != 0) || (read != length)) {
97 return "";
98 }
99 return lvl;
100 #else
101 char *lvl = getenv(env_var_name);
102 if (lvl) return std::string(lvl);
103 #endif
104
105 return "";
106 }
107
running_program_name()108 string running_program_name() {
109 #ifndef CAN_GET_RUNNING_PROGRAM_NAME
110 return "";
111 #else
112 string program_name;
113 char path[PATH_MAX] = {0};
114 uint32_t size = sizeof(path);
115 #if defined(__linux__)
116 ssize_t len = ::readlink("/proc/self/exe", path, size - 1);
117 #elif defined(__APPLE__)
118 ssize_t len = ::_NSGetExecutablePath(path, &size);
119 #endif
120 if (len != -1) {
121 #if defined(__linux__)
122 path[len] = '\0';
123 #endif
124 string tmp = std::string(path);
125 program_name = tmp.substr(tmp.find_last_of("/") + 1);
126 } else {
127 return "";
128 }
129 return program_name;
130 #endif
131 }
132
133 namespace {
134 // We use 64K of memory to store unique counters for the purpose of
135 // making names unique. Using less memory increases the likelihood of
136 // hash collisions. This wouldn't break anything, but makes stmts
137 // slightly confusing to read because names that are actually unique
138 // will get suffixes that falsely hint that they are not.
139
140 const int num_unique_name_counters = (1 << 14);
141
142 // We want to init these to zero, but cannot use = {0} because that
143 // would invoke a (deleted) copy ctor. The default initialization for
144 // atomics doesn't guarantee any actual initialization. Fortunately
145 // this is a global, which is always zero-initialized.
146 std::atomic<int> unique_name_counters[num_unique_name_counters] = {};
147
unique_count(size_t h)148 int unique_count(size_t h) {
149 h = h & (num_unique_name_counters - 1);
150 return unique_name_counters[h]++;
151 }
152 } // namespace
153
154 // There are three possible families of names returned by the methods below:
155 // 1) char pattern: (char that isn't '$') + number (e.g. v234)
156 // 2) string pattern: (string without '$') + '$' + number (e.g. fr#nk82$42)
157 // 3) a string that does not match the patterns above
158 // There are no collisions within each family, due to the unique_count
159 // done above, and there can be no collisions across families by
160 // construction.
161
unique_name(char prefix)162 string unique_name(char prefix) {
163 if (prefix == '$') prefix = '_';
164 return prefix + std::to_string(unique_count((size_t)(prefix)));
165 }
166
unique_name(const std::string & prefix)167 string unique_name(const std::string &prefix) {
168 string sanitized = prefix;
169
170 // Does the input string look like something returned from unique_name(char)?
171 bool matches_char_pattern = true;
172
173 // Does the input string look like something returned from unique_name(string)?
174 bool matches_string_pattern = true;
175
176 // Rewrite '$' to '_'. This is a many-to-one mapping, but that's
177 // OK, we're about to hash anyway. It just means that some names
178 // will share the same counter.
179 int num_dollars = 0;
180 for (size_t i = 0; i < sanitized.size(); i++) {
181 if (sanitized[i] == '$') {
182 num_dollars++;
183 sanitized[i] = '_';
184 }
185 if (i > 0 && !isdigit(sanitized[i])) {
186 // Found a non-digit after the first char
187 matches_char_pattern = false;
188 if (num_dollars) {
189 // Found a non-digit after a '$'
190 matches_string_pattern = false;
191 }
192 }
193 }
194 matches_string_pattern &= num_dollars == 1;
195 matches_char_pattern &= prefix.size() > 1;
196
197 // Then add a suffix that's globally unique relative to the hash
198 // of the sanitized name.
199 int count = unique_count(std::hash<std::string>()(sanitized));
200 if (count == 0) {
201 // We can return the name as-is if there's no risk of it
202 // looking like something unique_name has ever returned in the
203 // past or will ever return in the future.
204 if (!matches_char_pattern && !matches_string_pattern) {
205 return prefix;
206 }
207 }
208
209 return sanitized + "$" + std::to_string(count);
210 }
211
starts_with(const string & str,const string & prefix)212 bool starts_with(const string &str, const string &prefix) {
213 if (str.size() < prefix.size()) return false;
214 for (size_t i = 0; i < prefix.size(); i++) {
215 if (str[i] != prefix[i]) return false;
216 }
217 return true;
218 }
219
ends_with(const string & str,const string & suffix)220 bool ends_with(const string &str, const string &suffix) {
221 if (str.size() < suffix.size()) return false;
222 size_t off = str.size() - suffix.size();
223 for (size_t i = 0; i < suffix.size(); i++) {
224 if (str[off + i] != suffix[i]) return false;
225 }
226 return true;
227 }
228
replace_all(const string & str,const string & find,const string & replace)229 string replace_all(const string &str, const string &find, const string &replace) {
230 size_t pos = 0;
231 string result = str;
232 while ((pos = result.find(find, pos)) != string::npos) {
233 result.replace(pos, find.length(), replace);
234 pos += replace.length();
235 }
236 return result;
237 }
238
make_entity_name(void * stack_ptr,const string & type,char prefix)239 string make_entity_name(void *stack_ptr, const string &type, char prefix) {
240 string name = Introspection::get_variable_name(stack_ptr, type);
241
242 if (name.empty()) {
243 return unique_name(prefix);
244 } else {
245 // Halide names may not contain '.'
246 for (size_t i = 0; i < name.size(); i++) {
247 if (name[i] == '.') {
248 name[i] = ':';
249 }
250 }
251 return unique_name(name);
252 }
253 }
254
split_string(const std::string & source,const std::string & delim)255 std::vector<std::string> split_string(const std::string &source, const std::string &delim) {
256 std::vector<std::string> elements;
257 size_t start = 0;
258 size_t found = 0;
259 while ((found = source.find(delim, start)) != std::string::npos) {
260 elements.push_back(source.substr(start, found - start));
261 start = found + delim.size();
262 }
263
264 // If start is exactly source.size(), the last thing in source is a
265 // delimiter, in which case we want to add an empty string to elements.
266 if (start <= source.size()) {
267 elements.push_back(source.substr(start, std::string::npos));
268 }
269 return elements;
270 }
271
extract_namespaces(const std::string & name,std::vector<std::string> & namespaces)272 std::string extract_namespaces(const std::string &name, std::vector<std::string> &namespaces) {
273 namespaces = split_string(name, "::");
274 std::string result = namespaces.back();
275 namespaces.pop_back();
276 return result;
277 }
278
file_exists(const std::string & name)279 bool file_exists(const std::string &name) {
280 #ifdef _MSC_VER
281 return _access(name.c_str(), 0) == 0;
282 #else
283 return ::access(name.c_str(), F_OK) == 0;
284 #endif
285 }
286
assert_file_exists(const std::string & name)287 void assert_file_exists(const std::string &name) {
288 internal_assert(file_exists(name)) << "File not found: " << name;
289 }
290
assert_no_file_exists(const std::string & name)291 void assert_no_file_exists(const std::string &name) {
292 internal_assert(!file_exists(name)) << "File (wrongly) found: " << name;
293 }
294
file_unlink(const std::string & name)295 void file_unlink(const std::string &name) {
296 #ifdef _MSC_VER
297 _unlink(name.c_str());
298 #else
299 ::unlink(name.c_str());
300 #endif
301 }
302
ensure_no_file_exists(const std::string & name)303 void ensure_no_file_exists(const std::string &name) {
304 if (file_exists(name)) {
305 file_unlink(name);
306 }
307 assert_no_file_exists(name);
308 }
309
dir_rmdir(const std::string & name)310 void dir_rmdir(const std::string &name) {
311 #ifdef _MSC_VER
312 std::wstring wname = from_utf8(name);
313 internal_assert(RemoveDirectoryW(wname.c_str()))
314 << "RemoveDirectoryW() failed to remove " << name << "; error " << GetLastError() << "\n";
315 #else
316 int r = ::rmdir(name.c_str());
317 internal_assert(r == 0) << "Unable to remove dir: " << name << "\n";
318 #endif
319 }
320
file_stat(const std::string & name)321 FileStat file_stat(const std::string &name) {
322 #ifdef _MSC_VER
323 struct _stat a;
324 if (_stat(name.c_str(), &a) != 0) {
325 user_error << "Could not stat " << name << "\n";
326 }
327 #else
328 struct stat a;
329 if (::stat(name.c_str(), &a) != 0) {
330 user_error << "Could not stat " << name << "\n";
331 }
332 #endif
333 return {static_cast<uint64_t>(a.st_size),
334 static_cast<uint32_t>(a.st_mtime),
335 static_cast<uint32_t>(a.st_uid),
336 static_cast<uint32_t>(a.st_gid),
337 static_cast<uint32_t>(a.st_mode)};
338 }
339
340 #ifdef _WIN32
341 namespace {
342
343 // GetTempPath() will fail rudely if env vars aren't set properly,
344 // which is the case when we run under a tool in Bazel. Instead,
345 // look for the current user's AppData/Local/Temp path, which
346 // should be valid and writable in all versions of Windows that
347 // we support for compilation purposes.
get_windows_tmp_dir()348 std::string get_windows_tmp_dir() {
349 // Allow overriding of the tmpdir on Windows via an env var;
350 // some Windows configs can (apparently) lock down AppData/Local/Temp
351 // via policy, making various things break. (Note that this is intended
352 // to be a short-lived workaround; we would prefer to be able to avoid
353 // requiring this sort of band-aid if possible.)
354 std::string tmp_dir = get_env_variable("HL_WINDOWS_TMP_DIR");
355 if (!tmp_dir.empty()) {
356 return tmp_dir;
357 }
358
359 PWSTR wlocal_path;
360 HRESULT ret = SHGetKnownFolderPath(FOLDERID_LocalAppData, 0, nullptr, &wlocal_path);
361 internal_assert(ret == S_OK) << "Unable to get Local AppData folder; error " << GetLastError() << "\n";
362
363 std::string tmp = from_utf16(wlocal_path);
364 CoTaskMemFree(wlocal_path);
365
366 tmp = replace_all(tmp, "\\", "/");
367 if (tmp.back() != '/') tmp += '/';
368 tmp += "Temp/";
369 return tmp;
370 }
371
372 } // namespace
373 #endif
374
file_make_temp(const std::string & prefix,const std::string & suffix)375 std::string file_make_temp(const std::string &prefix, const std::string &suffix) {
376 internal_assert(prefix.find("/") == string::npos &&
377 prefix.find("\\") == string::npos &&
378 suffix.find("/") == string::npos &&
379 suffix.find("\\") == string::npos);
380 #ifdef _WIN32
381 // Windows implementations of mkstemp() try to create the file in the root
382 // directory Unfortunately, that requires ADMIN privileges, which are not
383 // guaranteed here.
384 std::wstring tmp_dir = from_utf8(get_windows_tmp_dir());
385 std::wstring wprefix = from_utf8(prefix);
386
387 WCHAR tmp_file[MAX_PATH];
388 // Note that GetTempFileNameW() actually creates the file.
389 DWORD ret = GetTempFileNameW(tmp_dir.c_str(), wprefix.c_str(), 0, tmp_file);
390 internal_assert(ret != 0) << "GetTempFileNameW() failed; error " << GetLastError() << "\n";
391 return from_utf16(tmp_file);
392 #else
393 std::string templ = "/tmp/" + prefix + "XXXXXX" + suffix;
394 // Copy into a temporary buffer, since mkstemp modifies the buffer in place.
395 std::vector<char> buf(templ.size() + 1);
396 strcpy(&buf[0], templ.c_str());
397 int fd = mkstemps(&buf[0], suffix.size());
398 internal_assert(fd != -1) << "Unable to create temp file for (" << &buf[0] << ")\n";
399 close(fd);
400 return std::string(&buf[0]);
401 #endif
402 }
403
dir_make_temp()404 std::string dir_make_temp() {
405 #ifdef _WIN32
406 std::string tmp_dir = get_windows_tmp_dir();
407 // There's no direct API to do this in Windows;
408 // our clunky-but-adequate approach here is to use
409 // CoCreateGuid() to create a probably-unique name.
410 // Add a limit on the number of tries just in case.
411 for (int tries = 0; tries < 100; ++tries) {
412 GUID guid;
413 HRESULT hr = CoCreateGuid(&guid);
414 internal_assert(hr == S_OK);
415 std::ostringstream name;
416 name << std::hex
417 << std::setfill('0')
418 << std::setw(8)
419 << guid.Data1
420 << std::setw(4)
421 << guid.Data2
422 << guid.Data3
423 << std::setw(2);
424 for (int i = 0; i < 8; i++) {
425 name << (int)guid.Data4[i];
426 }
427 std::string dir = tmp_dir + name.str();
428 std::wstring wdir = from_utf8(dir);
429 BOOL success = CreateDirectoryW(wdir.c_str(), nullptr);
430 if (success) {
431 debug(1) << "temp dir is: " << dir << "\n";
432 return dir;
433 }
434 // If name already existed, just loop and try again.
435 // Any other error, break from loop and fail.
436 if (GetLastError() != ERROR_ALREADY_EXISTS) {
437 break;
438 }
439 }
440 internal_error << "Unable to create temp directory in " << tmp_dir << "\n";
441 return "";
442 #else
443 std::string templ = "/tmp/XXXXXX";
444 // Copy into a temporary buffer, since mkdtemp modifies the buffer in place.
445 std::vector<char> buf(templ.size() + 1);
446 strcpy(&buf[0], templ.c_str());
447 char *result = mkdtemp(&buf[0]);
448 internal_assert(result != nullptr) << "Unable to create temp directory.\n";
449 return std::string(result);
450 #endif
451 }
452
read_entire_file(const std::string & pathname)453 std::vector<char> read_entire_file(const std::string &pathname) {
454 std::ifstream f(pathname, std::ios::in | std::ios::binary);
455 std::vector<char> result;
456
457 f.seekg(0, std::ifstream::end);
458 size_t size = f.tellg();
459 result.resize(size);
460 f.seekg(0, std::ifstream::beg);
461 f.read(result.data(), result.size());
462 internal_assert(f.good()) << "Unable to read file: " << pathname;
463 f.close();
464 return result;
465 }
466
write_entire_file(const std::string & pathname,const void * source,size_t source_len)467 void write_entire_file(const std::string &pathname, const void *source, size_t source_len) {
468 std::ofstream f(pathname, std::ios::out | std::ios::binary);
469
470 f.write(reinterpret_cast<const char *>(source), source_len);
471 f.flush();
472 internal_assert(f.good()) << "Unable to write file: " << pathname;
473 f.close();
474 }
475
add_would_overflow(int bits,int64_t a,int64_t b)476 bool add_would_overflow(int bits, int64_t a, int64_t b) {
477 int64_t max_val = 0x7fffffffffffffffLL >> (64 - bits);
478 int64_t min_val = -max_val - 1;
479 return ((b > 0 && a > max_val - b) || // (a + b) > max_val, rewritten to avoid overflow
480 (b < 0 && a < min_val - b)); // (a + b) < min_val, rewritten to avoid overflow
481 }
482
sub_would_overflow(int bits,int64_t a,int64_t b)483 bool sub_would_overflow(int bits, int64_t a, int64_t b) {
484 int64_t max_val = 0x7fffffffffffffffLL >> (64 - bits);
485 int64_t min_val = -max_val - 1;
486 return ((b < 0 && a > max_val + b) || // (a - b) > max_val, rewritten to avoid overflow
487 (b > 0 && a < min_val + b)); // (a - b) < min_val, rewritten to avoid overflow
488 }
489
mul_would_overflow(int bits,int64_t a,int64_t b)490 bool mul_would_overflow(int bits, int64_t a, int64_t b) {
491 int64_t max_val = 0x7fffffffffffffffLL >> (64 - bits);
492 int64_t min_val = -max_val - 1;
493 if (a == 0) {
494 return false;
495 } else if (a == -1) {
496 return b == min_val;
497 } else {
498 // Do the multiplication as a uint64, for which overflow is
499 // well defined, then cast the bits back to int64 to get
500 // multiplication modulo 2^64.
501 int64_t ab = (int64_t)((uint64_t)a) * ((uint64_t)b);
502 // The first two clauses catch overflow mod 2^bits, assuming
503 // no 64-bit overflow occurs, and the third clause catches
504 // 64-bit overflow.
505 return ab < min_val || ab > max_val || (ab / a != b);
506 }
507 }
508
509 struct TickStackEntry {
510 std::chrono::time_point<std::chrono::high_resolution_clock> time;
511 string file;
512 int line;
513 };
514
515 vector<TickStackEntry> tick_stack;
516
halide_tic_impl(const char * file,int line)517 void halide_tic_impl(const char *file, int line) {
518 string f = file;
519 f = split_string(f, "/").back();
520 tick_stack.push_back({std::chrono::high_resolution_clock::now(), f, line});
521 }
522
halide_toc_impl(const char * file,int line)523 void halide_toc_impl(const char *file, int line) {
524 auto t1 = tick_stack.back();
525 auto t2 = std::chrono::high_resolution_clock::now();
526 std::chrono::duration<double> diff = t2 - t1.time;
527 tick_stack.pop_back();
528 for (size_t i = 0; i < tick_stack.size(); i++) {
529 debug(1) << " ";
530 }
531 string f = file;
532 f = split_string(f, "/").back();
533 debug(1) << t1.file << ":" << t1.line << " ... " << f << ":" << line << " : " << diff.count() * 1000 << " ms\n";
534 }
535
c_print_name(const std::string & name)536 std::string c_print_name(const std::string &name) {
537 ostringstream oss;
538
539 // Prefix an underscore to avoid reserved words (e.g. a variable named "while")
540 if (isalpha(name[0])) {
541 oss << "_";
542 }
543
544 for (size_t i = 0; i < name.size(); i++) {
545 if (name[i] == '.') {
546 oss << "_";
547 } else if (name[i] == '$') {
548 oss << "__";
549 } else if (name[i] != '_' && !isalnum(name[i])) {
550 oss << "___";
551 } else {
552 oss << name[i];
553 }
554 }
555 return oss.str();
556 }
557
get_llvm_version()558 int get_llvm_version() {
559 static_assert(LLVM_VERSION > 0, "LLVM_VERSION is not defined");
560 return LLVM_VERSION;
561 }
562
563 } // namespace Internal
564
load_plugin(const std::string & lib_name)565 void load_plugin(const std::string &lib_name) {
566 #ifdef _WIN32
567 std::string lib_path = lib_name;
568 if (lib_path.find('.') == std::string::npos) {
569 lib_path += ".dll";
570 }
571
572 std::wstring wide_lib = from_utf8(lib_path);
573 HMODULE library = LoadLibraryW(wide_lib.c_str());
574 if (!library) {
575 DWORD error = GetLastError();
576 LPWSTR message = nullptr;
577 FormatMessageW(FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
578 nullptr, error, 0, reinterpret_cast<LPWSTR>(&message), 0, nullptr);
579
580 user_assert(message)
581 << "Failed to load: " << lib_path << ".\n"
582 << "FormatMessage failed while processing error in LoadLibraryW (errno "
583 << error << ").\n";
584
585 std::string err_msg = from_utf16(message);
586 LocalFree(message);
587 user_error << "Failed to load: " << lib_path << ";\n"
588 << "LoadLibraryW failed with error " << error << ": "
589 << err_msg << "\n";
590 }
591 #else
592 std::string lib_path = lib_name;
593 if (lib_path.find('.') == std::string::npos) {
594 lib_path = "lib" + lib_path + ".so";
595 }
596 if (dlopen(lib_path.c_str(), RTLD_LAZY) == nullptr) {
597 user_error << "Failed to load: " << lib_path << ": " << dlerror() << "\n";
598 }
599 #endif
600 }
601
602 } // namespace Halide
603