fix semantics of constexprs as phi inputs
Test cases by Roman Lebedev, thank you!
MODIFY
ir/function.cpp
ir/function.cpp
@@ -161,6 +161,15 @@ const BasicBlock& Function::bbOf(const Instr &i) const {
UNREACHABLE();
}
+BasicBlock& Function::insertBBBefore(string_view name, const BasicBlock &bb) {
+ auto p = BBs.try_emplace(string(name), name);
+ assert(p.second);
+ auto I = find(BB_order.begin(), BB_order.end(), &bb);
+ assert(I != BB_order.end());
+ BB_order.insert(I, &p.first->second);
+ return p.first->second;
+}
+
void Function::removeBB(BasicBlock &BB) {
assert(BB.getName() != "#sink");
BBs.erase(BB.getName());

MODIFY
ir/function.h
ir/function.h
@@ -108,6 +108,8 @@ public:
const BasicBlock& getBB(std::string_view name) const;
const BasicBlock& bbOf(const Instr &i) const;
+ BasicBlock& insertBBBefore(std::string_view name, const BasicBlock &bb);
+
void removeBB(BasicBlock &BB);
void addConstant(std::unique_ptr<Value> &&c);

MODIFY
llvm_util/llvm2alive.cpp
llvm_util/llvm2alive.cpp
@@ -101,7 +101,7 @@ class llvm2alive_ : public llvm::InstVisitor<llvm2alive_, unique_ptr<Instr>> {
const llvm::TargetLibraryInfo &TLI;
vector<llvm::Instruction*> i_constexprs;
const vector<string_view> &gvnamesInSrc;
- vector<tuple<Phi*, llvm::PHINode*, unsigned>> todo_phis;
+ vector<pair<Phi*, llvm::PHINode*>> todo_phis;
ostream *out;
// (LLVM alloca, (Alive2 alloc, has lifetime.start?))
map<const llvm::AllocaInst *, std::pair<Alloc *, bool>> allocs;
@@ -605,14 +605,7 @@ public:
return error(i);
auto phi = make_unique<Phi>(*ty, value_name(i));
- for (unsigned idx = 0, e = i.getNumIncomingValues(); idx != e; ++idx) {
- if (auto op = get_operand(i.getIncomingValue(idx))) {
- phi->addValue(*op, value_name(*i.getIncomingBlock(idx)));
- } else {
- todo_phis.emplace_back(phi.get(), &i, idx);
- }
- }
-
+ todo_phis.emplace_back(phi.get(), &i);
RETURN_IDENTIFIER(move(phi));
}
@@ -1486,13 +1479,31 @@ public:
}
// patch phi nodes for recursive defs
- for (auto &[phi, llvm_i, idx] : todo_phis) {
- auto op = get_operand(llvm_i->getIncomingValue(idx));
- if (!op) {
- error(*llvm_i);
+ for (auto &[phi, i] : todo_phis) {
+ for (unsigned idx = 0, e = i->getNumIncomingValues(); idx != e; ++idx) {
+ // evaluation of constexprs in phi nodes is done "in the edge", thus we
+ // introduce a new BB even if not always needed.
+ auto val = i->getIncomingValue(idx);
+ if (isa<llvm::ConstantExpr>(val) || isa<llvm::ConstantAggregate>(val)) {
+ auto &phi_bb = getBB(i->getParent());
+ string bridge
+ = value_name(*i->getIncomingBlock(idx)) + "_" + phi_bb.getName();
+ BB = &Fn.insertBBBefore(bridge, phi_bb);
+ getBB(i->getIncomingBlock(idx)).replaceTargetWith(&phi_bb, BB);
+ auto op = get_operand(val);
+ assert(op);
+ phi->addValue(*op, move(bridge));
+ BB->addInstr(make_unique<Branch>(phi_bb));
+ continue;
+ }
+
+ if (auto op = get_operand(val)) {
+ phi->addValue(*op, value_name(*i->getIncomingBlock(idx)));
+ } else {
+ error(*i);
return {};
}
- phi->addValue(*op, value_name(*llvm_i->getIncomingBlock(idx)));
+ }
}
auto getGlobalVariable =

MODIFY
llvm_util/utils.h
llvm_util/utils.h
// Distributed under the MIT license that can be found in the LICENSE file.
#include "ir/instr.h"
+#include <functional>
#include <ostream>
#include <string>
-#include <functional>
namespace llvm {
class BasicBlock;

ADD
tests/alive-tv/constexpr/phi1.srctgt.ll
+@a = external global [2 x i8]
+@b = external global i8
+
+define i8 @src(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ br label %exit
+
+exit:
+ %p = phi i8 [ 0, %entry ], [ srem (i8 1, i8 zext (i1 icmp eq (i8* getelementptr inbounds ([2 x i8], [2 x i8]* @a, i64 0, i64 1), i8* @b) to i8)), %then ]
+ ret i8 %p
+}
+
+define i8 @tgt(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ %rem = srem i8 1, 0
+ br label %exit
+
+exit:
+ %p = phi i8 [ 0, %entry ], [ %rem, %then ]
+ ret i8 %p
+}

ADD
tests/alive-tv/constexpr/phi2.srctgt.ll
+@a = external global [2 x i8]
+@b = external global i8
+
+define i8 @src(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ br label %exit
+
+exit:
+ %p = phi i8 [ 0, %entry ], [ srem (i8 1, i8 zext (i1 icmp ne (i8* getelementptr inbounds ([2 x i8], [2 x i8]* @a, i64 0, i64 1), i8* @b) to i8)), %then ]
+ ret i8 %p
+}
+
+define i8 @tgt(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ %rem = srem i8 1, 0
+ br label %exit
+
+exit:
+ %p = phi i8 [ 0, %entry ], [ %rem, %then ]
+ ret i8 %p
+}
+
+; ERROR: Source is more defined than target

ADD
tests/alive-tv/constexpr/phi3.srctgt.ll
+@e = external global [2 x i32]
+@a = external global i32
+
+define <2 x i8> @src(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ %srem = srem i8 1, zext (i1 icmp eq (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @e, i64 0, i64 1), i32* @a) to i8)
+ %ins = insertelement <2 x i8> zeroinitializer, i8 %srem, i64 0
+ br label %exit
+
+exit:
+ %p = phi <2 x i8> [ zeroinitializer, %entry ], [ %ins, %then ]
+ ret <2 x i8> %p
+}
+
+define <2 x i8> @tgt(i1 %c) {
+entry:
+ br i1 %c, label %then, label %exit
+
+then:
+ br label %exit
+
+exit:
+ %p = phi <2 x i8> [ zeroinitializer, %entry ], [ <i8 srem (i8 1, i8 zext (i1 icmp eq (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @e, i64 0, i64 1), i32* @a) to i8)), i8 0>, %then ]
+ ret <2 x i8> %p
+}

fix #781: semantics of constexprs as phi inputs
Test cases by Roman Lebedev, thank you!