Merge pull request #43 from neonichu/update-project-to-latest-xcode
Update project settings to latest Xcode
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 2908e5b..8e8f5a7 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -14,7 +14,7 @@
# Configure the default set of bindings to build.
if(NOT DEFINED LLBUILD_SUPPORT_BINDINGS)
- set(LLBUILD_SUPPORT_BINDINGS "Swift")
+ set(LLBUILD_SUPPORT_BINDINGS "")
endif()
@@ -112,6 +112,13 @@
include_directories(BEFORE
${CMAKE_SOURCE_DIR}/include)
+# On FreeBSD, /usr/local/* is not used by default. In order to build LLVM
+# with sqlite3, etc., we must add /usr/local paths.
+if(${CMAKE_SYSTEM_NAME} MATCHES "(FreeBSD|DragonFly)")
+ include_directories("/usr/local/include")
+ link_directories("/usr/local/lib")
+endif(${CMAKE_SYSTEM_NAME} MATCHES "(FreeBSD|DragonFly)")
+
# Xcode: Use libc++ and c++14 using proper build settings.
if (XCODE)
# Force usage of Clang.
@@ -170,8 +177,8 @@
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wnon-virtual-dtor")
endif ()
-# On Linux, always build with PIC.
-if(${CMAKE_SYSTEM_NAME} MATCHES "Linux")
+# On BSD and Linux, always build with PIC.
+if(${CMAKE_SYSTEM_NAME} MATCHES ".*BSD" OR ${CMAKE_SYSTEM_NAME} MATCHES "Linux")
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -fPIC")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fPIC")
endif ()
diff --git a/docs/development.rst b/docs/development.rst
index 380da1c..3e1ea82 100644
--- a/docs/development.rst
+++ b/docs/development.rst
@@ -14,7 +14,9 @@
$ brew install cmake ninja
-* Install FileCheck
+* Install FileCheck::
+
+ $ brew install llvm
* Build::
@@ -30,6 +32,8 @@
$ env PATH=$HOME/Library/Python/2.7/bin/:"$PATH" cmake -G Ninja -DCMAKE_BUILD_TYPE:=Debug ..
+Note: this assumes you have installed `lit` as a user, by running `easy_install --user lit`.
+
**Building from source on Ubuntu**
* Install dependencies::
@@ -40,7 +44,9 @@
$ sudo pip install lit
-* Install FileCheck
+* Install FileCheck::
+
+ $ sudo apt-get install llvm-3.7-tools
* Build::
diff --git a/include/llbuild/Core/BuildEngine.h b/include/llbuild/Core/BuildEngine.h
index 85846ff..3b40281 100644
--- a/include/llbuild/Core/BuildEngine.h
+++ b/include/llbuild/Core/BuildEngine.h
@@ -195,7 +195,9 @@
/// Called when a cycle is detected by the build engine and it cannot make
/// forward progress.
///
- /// \param items The ordered list of items comprising the cycle.
+ /// \param items The ordered list of items comprising the cycle, starting from
+ /// the node which was requested to build and ending with the first node in
+ /// the cycle (i.e., the node participating in the cycle will appear twice).
virtual void cycleDetected(const std::vector<Rule*>& items) = 0;
};
diff --git a/lib/Basic/CMakeLists.txt b/lib/Basic/CMakeLists.txt
index 2a1041b..c886b88 100644
--- a/lib/Basic/CMakeLists.txt
+++ b/lib/Basic/CMakeLists.txt
@@ -7,6 +7,6 @@
ShellUtility.cpp
)
-if(${CMAKE_SYSTEM_NAME} MATCHES "Linux")
+if(${CMAKE_SYSTEM_NAME} MATCHES ".*BSD" OR ${CMAKE_SYSTEM_NAME} MATCHES "Linux")
target_link_libraries(llbuildBasic pthread)
endif()
diff --git a/lib/BuildSystem/LaneBasedExecutionQueue.cpp b/lib/BuildSystem/LaneBasedExecutionQueue.cpp
index 69bea51..2954e51 100644
--- a/lib/BuildSystem/LaneBasedExecutionQueue.cpp
+++ b/lib/BuildSystem/LaneBasedExecutionQueue.cpp
@@ -16,6 +16,7 @@
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/Twine.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/Program.h"
@@ -29,6 +30,7 @@
#include <string>
#include <fcntl.h>
+#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <spawn.h>
@@ -63,6 +65,18 @@
std::condition_variable readyJobsCondition;
void executeLane(unsigned laneNumber) {
+ // Set the thread name, if available.
+#if defined(__APPLE__)
+ pthread_setname_np(
+ (llvm::Twine("org.swift.llbuild Lane-") +
+ llvm::Twine(laneNumber)).str().c_str());
+#elif defined(__linux__)
+ pthread_setname_np(
+ pthread_self(),
+ (llvm::Twine("org.swift.llbuild Lane-") +
+ llvm::Twine(laneNumber)).str().c_str());
+#endif
+
// Execute items from the queue until shutdown.
while (true) {
// Take a job from the ready queue.
diff --git a/lib/Commands/BuildEngineCommand.cpp b/lib/Commands/BuildEngineCommand.cpp
index 8f9ad1a..602bf83 100644
--- a/lib/Commands/BuildEngineCommand.cpp
+++ b/lib/Commands/BuildEngineCommand.cpp
@@ -12,8 +12,11 @@
#include "llbuild/Commands/Commands.h"
+#include "llbuild/Basic/LLVM.h"
#include "llbuild/Core/BuildEngine.h"
+#include "llvm/Support/raw_ostream.h"
+
#include <cassert>
#include <cmath>
#include <cstring>
@@ -130,60 +133,60 @@
}
};
-static core::Task* buildAck(core::BuildEngine& engine, int m, int n) {
- struct AckermannTask : core::Task {
- int m, n;
- AckermannValue recursiveResultA = {};
- AckermannValue recursiveResultB = {};
+struct AckermannTask : core::Task {
+ int m, n;
+ AckermannValue recursiveResultA = {};
+ AckermannValue recursiveResultB = {};
- AckermannTask(int m, int n) : m(m), n(n) { }
+ AckermannTask(core::BuildEngine& engine, int m, int n) : m(m), n(n) {
+ engine.registerTask(this);
+ }
- virtual void provideValue(core::BuildEngine& engine, uintptr_t inputID,
- const core::ValueType& value) override {
- if (inputID == 0) {
- recursiveResultA = value;
+ /// Called when the task is started.
+ virtual void start(core::BuildEngine& engine) override {
+ // Request the first recursive result, if necessary.
+ if (m == 0) {
+ ;
+ } else if (n == 0) {
+ engine.taskNeedsInput(this, AckermannKey(m-1, 1), 0);
+ } else {
+ engine.taskNeedsInput(this, AckermannKey(m, n-1), 0);
+ }
+ }
- // Request the second recursive result, if needed.
- if (m != 0 && n != 0) {
- engine.taskNeedsInput(this, AckermannKey(m-1, recursiveResultA), 1);
- }
- } else {
- assert(inputID == 1 && "invalid input ID");
- recursiveResultB = value;
+ /// Called when a task’s requested input is available.
+ virtual void provideValue(core::BuildEngine& engine, uintptr_t inputID,
+ const core::ValueType& value) override {
+ if (inputID == 0) {
+ recursiveResultA = value;
+
+ // Request the second recursive result, if needed.
+ if (m != 0 && n != 0) {
+ engine.taskNeedsInput(this, AckermannKey(m-1, recursiveResultA), 1);
}
+ } else {
+ assert(inputID == 1 && "invalid input ID");
+ recursiveResultB = value;
+ }
+ }
+
+ /// Called when all inputs are available.
+ virtual void inputsAvailable(core::BuildEngine& engine) override {
+ if (m == 0) {
+ engine.taskIsComplete(this, AckermannValue(n + 1));
+ return;
}
- virtual void start(core::BuildEngine& engine) override {
- // Request the first recursive result, if necessary.
- if (m == 0) {
- ;
- } else if (n == 0) {
- engine.taskNeedsInput(this, AckermannKey(m-1, 1), 0);
- } else {
- engine.taskNeedsInput(this, AckermannKey(m, n-1), 0);
- }
+ assert(recursiveResultA != 0);
+ if (n == 0) {
+ engine.taskIsComplete(this, recursiveResultA);
+ return;
}
- virtual void inputsAvailable(core::BuildEngine& engine) override {
- if (m == 0) {
- engine.taskIsComplete(this, AckermannValue(n + 1));
- return;
- }
-
- assert(recursiveResultA != 0);
- if (n == 0) {
- engine.taskIsComplete(this, AckermannValue(recursiveResultA));
- return;
- }
-
- assert(recursiveResultB != 0);
- engine.taskIsComplete(this, AckermannValue(recursiveResultB));
- }
- };
-
- // Create the task.
- return engine.registerTask(new AckermannTask(m, n));
-}
+ assert(recursiveResultB != 0);
+ engine.taskIsComplete(this, recursiveResultB);
+ }
+};
static int runAckermannBuild(int m, int n, int recomputeCount,
const std::string& traceFilename,
@@ -198,13 +201,16 @@
public:
int numRules = 0;
+ /// Get the rule to use for the given Key.
virtual core::Rule lookupRule(const core::KeyType& keyData) override {
++numRules;
auto key = AckermannKey(keyData);
return core::Rule{key, [key] (core::BuildEngine& engine) {
- return buildAck(engine, key.m, key.n); } };
+ return new AckermannTask(engine, key.m, key.n); } };
}
+ /// Called when a cycle is detected by the build engine and it cannot make
+ /// forward progress.
virtual void cycleDetected(const std::vector<core::Rule*>& items) override {
assert(0 && "unexpected cycle!");
}
@@ -224,14 +230,14 @@
auto key = AckermannKey(m, n);
auto result = AckermannValue(engine.build(key));
- std::cout << "ack(" << m << ", " << n << ") = " << result << "\n";
+ llvm::outs() << "ack(" << m << ", " << n << ") = " << result << "\n";
if (n < 10) {
#ifndef NDEBUG
int expected = ack(m, n);
assert(result == expected);
#endif
}
- std::cout << "... computed using " << delegate.numRules << " rules\n";
+ llvm::outs() << "... computed using " << delegate.numRules << " rules\n";
if (!dumpGraphPath.empty()) {
engine.dumpGraphToFile(dumpGraphPath);
diff --git a/lib/Core/BuildEngine.cpp b/lib/Core/BuildEngine.cpp
index bedb2a5..74b23e3 100644
--- a/lib/Core/BuildEngine.cpp
+++ b/lib/Core/BuildEngine.cpp
@@ -596,11 +596,15 @@
/// Execute all of the work pending in the engine queues until they are empty.
///
+ /// \param buildKey The key to build.
/// \returns True on success, false if the build could not be completed; the
/// latter only occurs when the build contains a cycle currently.
- bool executeTasks() {
+ bool executeTasks(const KeyType& buildKey) {
std::vector<TaskInputRequest> finishedInputRequests;
+ // Push a dummy input request for the rule to build.
+ inputRequests.push_back({ nullptr, &getRuleInfoForKey(buildKey) });
+
// Process requests as long as we have work to do.
while (true) {
bool didWork = false;
@@ -863,20 +867,25 @@
// If there was no work to do, but we still have running tasks, then
// we have found a cycle and are deadlocked.
if (!taskInfos.empty()) {
- reportCycle();
+ reportCycle(buildKey);
return false;
}
return true;
}
- void reportCycle() {
+ /// Report the cycle which has called the engine to be unable to make forward
+ /// progress.
+ ///
+ /// \param buildKey The key which was requested to build (the reported cycle
+ /// with start with this node).
+ void reportCycle(const KeyType& buildKey) {
// Take all available locks, to ensure we dump a consistent state.
std::lock_guard<std::mutex> guard1(taskInfosMutex);
std::lock_guard<std::mutex> guard2(finishedTaskInfosMutex);
// Gather all of the successor relationships.
- std::unordered_map<Rule*, std::vector<Rule*>> graph;
+ std::unordered_map<Rule*, std::vector<Rule*>> successorGraph;
std::vector<const RuleScanRecord *> activeRuleScanRecords;
for (const auto& it: taskInfos) {
const TaskInfo& taskInfo = it.second;
@@ -890,7 +899,7 @@
// Add the sucessor for the deferred relationship itself.
successors.push_back(&request.ruleInfo->rule);
}
- graph.insert({ &taskInfo.forRuleInfo->rule, successors });
+ successorGraph.insert({ &taskInfo.forRuleInfo->rule, successors });
}
// Add the pending scan records for every rule.
@@ -919,7 +928,7 @@
// For each paused request, add the dependency.
for (const auto& request: record->pausedInputRequests) {
if (request.taskInfo) {
- graph[&request.inputRuleInfo->rule].push_back(
+ successorGraph[&request.inputRuleInfo->rule].push_back(
&request.taskInfo->forRuleInfo->rule);
}
}
@@ -927,7 +936,8 @@
// Process the deferred scan requests.
for (const auto& request: record->deferredScanRequests) {
// Add the sucessor for the deferred relationship itself.
- graph[&request.inputRuleInfo->rule].push_back(&request.ruleInfo->rule);
+ successorGraph[&request.inputRuleInfo->rule].push_back(
+ &request.ruleInfo->rule);
// Add the active rule scan record which needs to be traversed.
assert(request.ruleInfo->isScanning());
@@ -935,50 +945,64 @@
request.ruleInfo->getPendingScanRecord());
}
}
-
- // Find the cycle, which should be reachable from any remaining node.
- //
- // FIXME: Need a setvector.
- std::vector<Rule*> cycleList;
- std::unordered_set<Rule*> cycleItems;
- std::function<bool(Rule*)> findCycle;
- findCycle = [&](Rule* node) {
- // Push the node on the stack.
- cycleList.push_back(node);
- auto it = cycleItems.insert(node);
- // If the node is already in the stack, we found the cycle.
- if (!it.second)
- return true;
-
- // Otherwise, iterate over each successor looking for a cycle.
- for (Rule* successor: graph[node]) {
- if (findCycle(successor))
- return true;
+ // Invert the graph, so we can search from the root.
+ std::unordered_map<Rule*, std::vector<Rule*>> predecessorGraph;
+ for (auto& entry: successorGraph) {
+ Rule* node = entry.first;
+ for (auto& succ: entry.second) {
+ predecessorGraph[succ].push_back(node);
}
+ }
- // If we didn't find the cycle, pop this item.
- cycleItems.erase(it.first);
- cycleList.pop_back();
- return false;
- };
-
- // Iterate through the graph keys in a deterministic order.
- std::vector<Rule*> orderedKeys;
- for (auto& entry: graph)
- orderedKeys.push_back(entry.first);
- std::sort(orderedKeys.begin(), orderedKeys.end(), [] (Rule* a, Rule* b) {
+ // Normalize predecessor order, to ensure a deterministic result (at least,
+ // if the graph reaches the same cycle).
+ for (auto& entry: predecessorGraph) {
+ std::sort(entry.second.begin(), entry.second.end(), [](Rule* a, Rule* b) {
return a->key < b->key;
});
- for (const auto& key: orderedKeys) {
- if (findCycle(key))
- break;
+ }
+
+ // Find the cycle by searching from the entry node.
+ struct WorkItem {
+ Rule* node;
+ unsigned predecessorIndex = 0;
+ };
+ std::vector<Rule*> cycleList;
+ std::unordered_set<Rule*> cycleItems;
+ std::vector<WorkItem> stack{
+ WorkItem{ &getRuleInfoForKey(buildKey).rule } };
+ while (!stack.empty()) {
+ // Take the top item.
+ auto& entry = stack.back();
+ const auto& predecessors = predecessorGraph[entry.node];
+
+ // If the index is 0, we just started visiting the node.
+ if (entry.predecessorIndex == 0) {
+ // Push the node on the stack.
+ cycleList.push_back(entry.node);
+ auto it = cycleItems.insert(entry.node);
+
+ // If the node is already in the stack, we found a cycle.
+ if (!it.second)
+ break;
+ }
+
+ // Visit the next predecessor, if possible.
+ if (entry.predecessorIndex != predecessors.size()) {
+ auto* child = predecessors[entry.predecessorIndex];
+ entry.predecessorIndex += 1;
+ stack.emplace_back(WorkItem{ child });
+ continue;
+ }
+
+ // Otherwise, we are done visiting this node.
+ cycleItems.erase(entry.node);
+ cycleList.pop_back();
+ stack.pop_back();
}
assert(!cycleList.empty());
- // Reverse the cycle list, since it was formed from the successor graph.
- std::reverse(cycleList.begin(), cycleList.end());
-
delegate.cycleDetected(cycleList);
// Complete all of the remaining tasks.
@@ -1076,18 +1100,12 @@
// and \see RuleInfo::isComplete().
++currentTimestamp;
- // Find the rule.
- auto& ruleInfo = getRuleInfoForKey(key);
-
if (trace)
trace->buildStarted();
- // Push a dummy input request for this rule.
- inputRequests.push_back({ nullptr, &ruleInfo });
-
// Run the build engine, to process any necessary tasks.
- bool success = executeTasks();
-
+ bool success = executeTasks(key);
+
// Update the build database, if attached.
//
// FIXME: Is it correct to do this here, or earlier?
@@ -1115,6 +1133,7 @@
}
// The task queue should be empty and the rule complete.
+ auto& ruleInfo = getRuleInfoForKey(key);
assert(taskInfos.empty() && ruleInfo.isComplete(this));
return ruleInfo.result.value;
}
diff --git a/lib/Ninja/CMakeLists.txt b/lib/Ninja/CMakeLists.txt
index cf3b172..0c17f4b 100644
--- a/lib/Ninja/CMakeLists.txt
+++ b/lib/Ninja/CMakeLists.txt
@@ -4,3 +4,5 @@
ManifestLoader.cpp
Parser.cpp
)
+
+target_link_libraries(llbuildNinja llvmSupport)
diff --git a/lib/llvm/Support/CMakeLists.txt b/lib/llvm/Support/CMakeLists.txt
index 087ac8e..8e79e18 100644
--- a/lib/llvm/Support/CMakeLists.txt
+++ b/lib/llvm/Support/CMakeLists.txt
@@ -38,6 +38,10 @@
raw_ostream.cpp
)
+if(${CMAKE_SYSTEM_NAME} MATCHES "FreeBSD")
+ target_link_libraries(llvmSupport execinfo pthread)
+endif()
+
if(${CMAKE_SYSTEM_NAME} MATCHES "Linux")
target_link_libraries(llvmSupport pthread dl)
endif()
diff --git a/lib/llvm/Support/Unix/Process.inc b/lib/llvm/Support/Unix/Process.inc
index df13bd2..b9173d4 100644
--- a/lib/llvm/Support/Unix/Process.inc
+++ b/lib/llvm/Support/Unix/Process.inc
@@ -33,10 +33,10 @@
#if HAVE_SIGNAL_H
#include <signal.h>
#endif
-// DragonFlyBSD, OpenBSD, and Bitrig have deprecated <malloc.h> for
+// DragonFlyBSD, FreeBSD, OpenBSD, and Bitrig have deprecated <malloc.h> for
// <stdlib.h> instead. Unix.h includes this for us already.
#if defined(HAVE_MALLOC_H) && !defined(__DragonFly__) && \
- !defined(__OpenBSD__) && !defined(__Bitrig__)
+ !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__Bitrig__)
#include <malloc.h>
#endif
#if defined(HAVE_MALLCTL)
diff --git a/tests/BuildSystem/Build/introduced-cycle.llbuild b/tests/BuildSystem/Build/introduced-cycle.llbuild
index 9bfae2f..22bf415 100644
--- a/tests/BuildSystem/Build/introduced-cycle.llbuild
+++ b/tests/BuildSystem/Build/introduced-cycle.llbuild
@@ -43,7 +43,7 @@
# CHECK-VERSION-2-NOT: output
# CHECK-VERSION-2: END-OF-FILE
-# CHECK-VERSION-2-ERR: error: cycle detected while building: command 'output' -> node '<output-1>' -> command 'output-1' -> node '<output>' -> command 'output'
+# CHECK-VERSION-2-ERR: error: cycle detected while building: target '' -> node '<output>' -> command 'output' -> node '<output-1>' -> command 'output-1' -> node '<output>'
client:
name: basic
diff --git a/tests/Ninja/Build/cycle-detection.ninja b/tests/Ninja/Build/cycle-detection.ninja
index d62373f..b4e9c6f 100644
--- a/tests/Ninja/Build/cycle-detection.ninja
+++ b/tests/Ninja/Build/cycle-detection.ninja
@@ -6,7 +6,7 @@
# RUN: /bin/sh -c "%{llbuild} ninja build --jobs 1 --no-db --chdir %t.build; echo \"exit code: $?\"" &> %t.out
# RUN: %{FileCheck} < %t.out %s
-# CHECK: cycle detected among targets: "intermediate" -> "output-2" -> "output-1" -> "intermediate"
+# CHECK: cycle detected among targets: "output" -> "output-1" -> "intermediate" -> "output-2" -> "output-1"
# CHECK-NOT: command failure
# CHECK: exit code: 1
diff --git a/unittests/Core/BuildEngineTest.cpp b/unittests/Core/BuildEngineTest.cpp
index e8092d3..ff506ad 100644
--- a/unittests/Core/BuildEngineTest.cpp
+++ b/unittests/Core/BuildEngineTest.cpp
@@ -784,7 +784,7 @@
iteration = 1;
auto result = engine.build("A");
EXPECT_EQ(ValueType{}, result);
- EXPECT_EQ(std::vector<std::string>({ "B", "C", "B" }), delegate.cycle);
+ EXPECT_EQ(std::vector<std::string>({ "A", "C", "B", "C" }), delegate.cycle);
}
}
diff --git a/unittests/Ninja/CMakeLists.txt b/unittests/Ninja/CMakeLists.txt
index 606e491..d2f761e 100644
--- a/unittests/Ninja/CMakeLists.txt
+++ b/unittests/Ninja/CMakeLists.txt
@@ -2,4 +2,4 @@
LexerTest.cpp
)
-target_link_libraries(NinjaTests llbuildNinja)
+target_link_libraries(NinjaTests llbuildNinja curses)
diff --git a/utils/Xcode/create-lit-site-cfg.sh b/utils/Xcode/create-lit-site-cfg.sh
index f9ef52f..b285af3 100755
--- a/utils/Xcode/create-lit-site-cfg.sh
+++ b/utils/Xcode/create-lit-site-cfg.sh
@@ -2,6 +2,14 @@
set -e
+# Amend PATH with known location of LLVM tools
+BREW="$(which brew || true)"
+if [ -n "${BREW}" ]; then
+ PATH="$PATH:`${BREW} --prefix`/opt/llvm/bin"
+fi
+# Default location on Ubuntu
+PATH="$PATH:/usr/lib/llvm-3.7/bin"
+
# If we have an included copy of FileCheck, use that.
FILECHECK="${SRCROOT}/llbuild-test-tools/utils/Xcode/FileCheck"
if [ ! -f "${FILECHECK}" ]; then