Sachverhalt:
A.
A._ wurde mit Entscheid der 1. Strafkammer des Obergerichts des Kantons Bern vom 15. Oktober 2014 unter anderem der mehrfachen schweren Körperverletzung schuldig gesprochen und zu einer Freiheitsstrafe von drei Jahren verurteilt. Zudem wurden eine stationäre therapeutische Massnahme nach <ref-law> und eine stationäre Suchtbehandlung nach <ref-law> angeordnet. Eine von A._ dagegen erhobene Beschwerde wies das Bundesgericht mit Urteil 6B_43/2015 vom 18. Mai 2015 ab.
Mit Verfügung vom 12. Oktober 2015 wies die Abteilung Straf- und Massnahmenvollzug (ASMV) der Polizei- und Militärdirektion des Kantons Bern A._ zum Vollzug der stationären therapeutischen Massnahme in die Justizvollzugsanstalt Solothurn ein. Wenige Tage später, am 23. Oktober 2015, wurde A._ in Anwendung von Art. 10 lit. g und Art. 30 Abs. 2 des Gesetzes des Kantons Bern vom 25. Juni 2003 über den Straf- und Massnahmenvollzug (SMVG; BSG 341.1) in das Regionalgefängnis Bern zurückverlegt, da er sich im Massnahmenvollzug in der Justizvollzugsanstalt Solothurn äusserst renitent verhalten hatte. A._ ersuchte um Erlass eines formellen Entscheids betreffend seine Verlegung. Die ASMV erliess am 30. November 2015 eine entsprechende Verfügung.
Mit Beschwerde vom 11. November 2015 an die Polizei- und Militärdirektion des Kantons Bern beantragte A._ die Aufhebung der Verfügung vom 12. Oktober 2015. Er machte geltend, es sei rechtsstaatlich unhaltbar, ihn nach fast vierjähriger Haft zusätzlich für die Maximaldauer von weiteren 5 Jahren in eine Massnahmenanstalt einzuweisen. Zudem wäre das vorgesehene Massnahmenzentrum ungeeignet gewesen. Mit einer weiteren Beschwerde, datierend vom 1. Dezember 2015 beantragte A._ zudem, die Verfügung vom 30. Oktober 2015 sei aufzuheben und es sei seine Rückversetzung in Sicherheitshaft anzuordnen. Mit Entscheid vom 14. April 2016 wies die Polizei- und Militärdirektion die Beschwerde vom 11. November 2015 ab, soweit sie darauf eintrat, und trat auf die Beschwerde vom 1. Dezember 2015 nicht ein.
Mit Beschwerde vom 12. Mai 2016 ans Obergericht des Kantons Bern beantragte A._, der Entscheid der Polizei- und Militärdirektion sei aufzuheben und es sei festzustellen, dass die Einweisungsverfügung vom 12. Oktober 2015 gegenstandslos sei und er sich formell nicht mehr im Massnahmenvollzug befinde. Zudem sei festzustellen, dass sein Aufenthalt im Regionalgefängnis Bern sich nicht auf Art. 30 Abs. 2 bzw. Art. 10 lit. g SMVG abstütze. Mit einer weiteren Eingabe desselben Datums beantragte A._, er sei umgehend aus der Haft zu entlassen und es sei ihm eine angemessene Entschädigung für die zu Unrecht ausgestandene Haft auszurichten.
Mit Verfügung vom 13. Mai 2016 beschränkte das Obergericht das Verfahren vorläufig auf die Frage, ob auf das Haftentlassungsgesuch einzutreten sei. Mit Beschluss vom 26. Mai 2016 trat es darauf nicht ein.
B.
Mit Beschwerde in Strafsachen vom 14. Juni 2016 ans Bundesgericht beantragt A._, der Beschluss des Obergerichts sei aufzuheben und dieses sei anzuweisen, das Haftentlassungsgesuch an die Hand zu nehmen.
Das Obergericht hat auf eine Vernehmlassung verzichtet. Die Generalstaatsanwaltschaft des Kantons Bern hat sich nicht vernehmen lassen

Erwägungen:
1.
Die Beschwerde richtet sich gegen einen verfahrensabschliessenden, kantonal letztinstanzlichen Nichteintretensentscheid in Strafsachen (Art. 78, Art. 80 Abs. 1 und Art. 90 BGG). Der Beschwerdeführer ist zur Beschwerde berechtigt (<ref-law>). Die weiteren Sachurteilsvoraussetzungen sind erfüllt. Auf die Beschwerde in Strafsachen ist einzutreten.
Streitgegenstand ist einzig, ob das Obergericht zu Recht auf das bei ihm erhobene Haftentlassungsgesuch nicht eingetreten ist.
2.
2.1. Der Beschwerdeführer bringt vor, das Obergericht habe seinen grundrechtlichen Anspruch auf ein jederzeitiges Haftüberprüfungsverfahren verletzt, indem es auf sein Haftentlassungsgesuch nicht eingetreten sei. Es sei inzwischen völlig klar, dass keine Massnahme mehr vollzogen und sein Aufenthalt im Regionalgefängnis Bern bereits aus diesem Grund nicht mehr bloss vorübergehend sein könne. Selbst wenn die Vollzugsbehörde nun ein Verfahren betreffend Überprüfung der Aufhebung der Massnahme in Aussicht stelle, so könne bis zu einem rechtskräftigen Entscheid viel Zeit vergehen. Dasselbe gelte für ein Verfahren infolge Aussichtslosigkeit der Massnahme, das er allenfalls selber einleite. Das Obergericht habe <ref-law>, <ref-law> und Art. 5 Ziff. 4 EMRK verletzt.
2.2. Das Obergericht führt aus, die Frage, ob die Verlegung ins Regionalgefängnis nach wie vor vorübergehend im Sinne von Art. 30 Abs. 2 SMVG bzw. rechtmässig sei, führe nicht zu einer Änderung der Rechtsnatur des Freiheitsentzugs. Der Beschwerdeführer befinde sich weiterhin im Massnahmenvollzug. Dass die ASMV mit Schreiben vom 6. Mai 2016 in Aussicht gestellt habe, infolge Fehlens einer geeigneten Einrichtung ein Verfahren betreffend Prüfung der Aufhebung der stationären therapeutischen Massnahme durchzuführen, vermöge daran nichts zu ändern. Da sich der Beschwerdeführer nicht in Sicherheitshaft befinde, sei ein Haftentlassungsgesuch nicht das richtige Mittel, um den fortdauernden Freiheitsentzug überprüfen zu lassen. Auf das Haftentlassungsgesuch sei deshalb nicht einzutreten. Der Vollständigkeit halber sei jedoch darauf hinzuweisen, dass dem Anspruch des Gesuchstellers auf gerichtliche Überprüfung seiner Massnahmenvollzugssituation im Rahmen des Beschwerdeverfahrens gegen den Entscheid der Polizei- und Militärdirektion vom 14. April 2016 Rechnung zu tragen sein werde.
2.3. Diese Ausführungen sind nicht zu beanstanden. Wie das Bundesgericht in einem den Beschwerdeführer betreffenden Urteil in anderem Zusammenhang bereits festhielt, befindet er sich auch nach der Verlegung im Massnahmenvollzug. Ein Haftentlassungsgesuch ist deshalb nicht das richtige Mittel, um sich gegen den fortdauernden Freiheitsentzug zu wehren (ausführlich: Urteil 6B_1331/2015 vom 13. Januar 2016 E. 2.1 f.). Aus dem vom Beschwerdeführer angerufenen <ref-law> ergibt sich ebendies: Als Sicherheitshaft gilt die Haft während der Zeit zwischen dem Eingang der Anklageschrift beim erstinstanzlichen Gericht und der Rechtskraft des Urteils, dem Antritt einer freiheitsentziehenden Sanktion oder der Entlassung (vgl. zur Haftprüfung im Verfahren betreffend die nachträgliche Anordnung der Verwahrung <ref-ruling>).
Die Vorinstanz wies, wie erwähnt, auch darauf hin, dass dem Anspruch des Beschwerdeführers auf gerichtliche Überprüfung seiner Massnahmenvollzugssituation im Rahmen des Beschwerdeverfahrens gegen den Entscheid der Polizei- und Militärdirektion vom 14. April 2016 Rechnung getragen werde. Diese Frage ist hier jedoch nicht Prozessgegenstand. Dem Beschwerdeführer scheint es vorliegend denn auch primär darum zu gehen, möglichst rasch in Freiheit entlassen zu werden. Dabei übersieht er, dass auch im Verfahren der Prüfung der bedingten Entlassung aus der Massnahme bzw. deren Aufhebung gemäss <ref-law> die Garantien von <ref-law> und Art. 5 Ziff. 4 EMRK zu beachten sind (vgl. Urteil 6B_471/2012 vom 21. Januar 2013 E. 5 mit Hinweisen). Seine Argumentation stösst insofern ins Leere.
3.
Die Beschwerde ist aus diesen Gründen abzuweisen.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege. Sein Gesuch kann unter den gegebenen Umständen nicht als von vornherein aussichtslos bezeichnet werden und ist gutzuheissen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Vertreterin des Beschwerdeführers, Rechtsanwältin Simone Gasser, Bern, wird eine Entschädigung von Fr. 1'500.-- aus der Bundesgerichtskasse ausgerichtet.
5.
Dieses Urteil wird dem Beschwerdeführer, der Generalstaatsanwaltschaft und dem Obergericht des Kantons Bern, 1. Strafkammer, schriftlich mitgeteilt.
Lausanne, 1. Juli 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold